Fişierul intrare/ieşire:bec.in, bec.outSursăOlimpiada pe scoala clasa a 10-a, 2018
AutorCarmen MincaAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inbec.outExplicaţ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
Trebuie sa te autentifici pentru a trimite solutii. Click aici