Fișierul intrare/ieșire | bec.in, bec.out | Sursă | Olimpiada pe scoala clasa a 10-a, 2018 |
---|---|---|---|
Autor | Carmen Mincă | Adăugată de | Victor Manz • vmanz |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Bec
Într-o pădure sunt plantați N*M copaci, pe N rânduri și M coloane, fiecare copac aflându-se la egală distanță de copacii vecini. Întrucât în pădure este cam intuneric, pădurarul (care supraveghează pădurea) montează K becuri (câte un bec într-un copac). Aceste becuri au consum diferit de energie electrică. Fiecare bec luminează doar o parte dintre copaci. Un copac este luminat de un bec dacă, trasând o linie dreaptă de la el la bec, niciun alt copac sau bec nu se află pe acea linie.
Energia electrică fiind scumpă, pădurarul va trebui să renunțe la K-1 becuri și să păstreze doar becul care luminează numărul maxim C de copaci. Dacă mai multe becuri dintre cele K luminează C copaci, pădurarul îl va păstra pe cel mai util adică care are cel mai mic consum de energie electrică.
Să se scrie un program care să determine:
1. numărul maxim X de copaci ce pot fi luminați de unul dintre cele K becuri
2. poziția (rândul R și coloana C) becului cel mai util păstrat de pădurar.
Date de intrare
Fișierul de intrare bec.in conține:
- pe prima linie, patru numere naturale P N M K, separate prin câte un spațiu, reprezentând: cerința P ce trebuie rezolvată (1 sau 2), numărul N de rânduri, numărul M de coloane, și numărul K de becuri
- pe fiecare din următoarele K linii, câte trei numere naturale A B C, separate prin câte un spațiu, reprezintând rândul A și coloana B în care se află fiecare bec și consumul C de energie electrică a acestuia.
Date de ieșire
Dacă P=1, atunci fișierul de ieșire bec.out va conține pe prima linie numărul X ( răspunsul la cerința 1).
Altfel, dacă P=2, atunci fișierul de ieșire bec.out va conține pe prima linie cele două numere naturale R C, ( răspunsul la cerința 2) separate prin câte un spațiu, cu semnificația din enunț.
Restricții
- 1 ≤ N ≤ 150
- 1 ≤ M ≤ 150
- 1 ≤ K ≤ N
- 1 ≤ K ≤ M
- 1 ≤ K ≤ 100
- 1 ≤ A ≤ N
- 1 ≤ B ≤ M
- 1 ≤ C ≤ 10000
- nu există două becuri asezate pe același rând și aceeași coloană
- nu există două becuri cu același consum de energie electrică
- se acordă 50% din punctaj pentru rezolvarea corectă a cerinței 1 și 50% din punctaj pentru rezolvarea corectă a cerinței 2.
Exemplu
bec.in | bec.out | Explicație |
---|---|---|
1 5 4 3 2 3 80 4 2 100 4 3 70 |
14 |
P=1. Se rezolvă cerința 1. Numerotăm copacii ca în tabloul alăturat. Primul bec, situat în rândul 2 și coloana 3 (consum energie 80) luminează 14 copaci (nu îi luminează pe cei numerotați cu 5, 12 și 16). Al doilea bec, situat în rândul 4 și coloana 2 (consum energie 100) luminează 13 copaci (nu îi luminează pe cei numerotați cu 2, 6, 7 și 13). Al treilea bec, situat în rândul 4 și coloana 3 (consum energie 70) luminează 14 copaci (nu le luminează pe cei numerotați cu 3, 5 și 12). |
2 5 4 3 2 3 80 4 2 100 4 3 70 |
4 3 |
P=2. Se rezolvă cerința 2. Becurile ce luminează numărul maxim de copaci (X=14) sunt: 1 (consum de energie 80) și 3 (consum de energie 70). Becul 3 are consumul de energie mai mic decât cel al primului bec (70<80) și se află în rândul R=4 și coloana C=3 |