Fișierul intrare/ieșire bec.in, bec.out Sursă Olimpiada pe scoala clasa a 10-a, 2018
Autor Carmen Mincă Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii