Fișierul intrare/ieșire oua.in, oua.out Sursă ONI 2007 clasa a 6-a
Autor Cristina Sichim Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Ouă (clasa a 6-a)

Pe o pajiște pătrată formată din LxL parcele pătrate cu latura de 1 metru au fost ascunse ouă. Unele ouă sunt mai valoroase decât altele. N iepurași se află în parcele situate pe marginea pajiștei și participă la concursul ,,Coșul meu este mai valoros”. Inițial nu există mai mulți iepurași în aceeași parcelă. Ei poartă tricouri cu numere distincte de la 1 la N. Pentru că au foarte mult antrenament iepurașii respectă cu strictețe următoarele reguli:

1. toți iepurașii încep căutarea ouălor simultan, pornind cu parcela în care se află;
2. direcțiile inițiale de deplasare a iepurașilor (reprezentate în figura 1) sunt următoarele: cei de pe latura nordică se deplasează către sud, cei de pe latura vestică se deplasează către est, cei de pe latura sudică către nord iar cei de pe latura estică către vest;

3. în fiecare parcelă un iepuraș stă un minut, timp în care caută și eventual culege un ou și sare în parcela indicată de direcția sa de deplasare;
4. culegerea unui ou determină schimbarea direcției de deplasare;
5. schimbarea direcției de deplasare se face astfel: dacă iepurașul vine de la Nord atunci el va pleca spre Vest , dacă vine de la Sud va pleca spre Est, dacă vine de la Est va pleca spre Nord iar dacă vine de la Vest va pleca spre Sud. Un exemplu de deplasare este reprezentat în figura 2 pentru un iepuraș care pleacă din parcela (1,4);

6. dacă doi sau mai mulți iepurași ajung simultan la același ou atunci acesta va fi cules de cel care are cel mai mic număr pe tricou.

Concursul se încheie atunci când nu mai există iepurași pe pajiște.

Cerință

Scrieți un program care să afișeze numărul total de ouă culese de cei N iepurași, cel mai valoros coș (valoarea acestuia) precum și durata (în minute) a concursului.

Date de intrare

Fișierul de intrare oua.in conține pe prima linie două numere naturale, L și P separate printr-un spațiu, L reprezentând numărul liniilor și al coloanelor tabloului utilizat în reprezentarea parcelei iar P numărul ouălor de pe pajiște.
Pe fiecare dintre următoarele P linii se află câte 3 numere naturale, separate prin câte un spațiu, reprezentând coordonatele parcelei (i,j) pe care se găsește un ou (1<=i<=L;1<=j<=L) și valoarea (v) acestuia.
Pe linia următoare se află numărul N al iepurașilor, iar pe fiecare dintre următoarele N linii se găsesc perechi de numere naturale reprezentând coordonatele parcelelor în care se găsesc inițial iepurașii, în ordinea numerelor de pe tricou.

Date de ieșire

Fișierul de ieșire oua.out va conține pe prima linie 3 numere naturale separate prin câte un spațiu, numere ce reprezintă numărul total de ouă culese de cei N iepurași, cel mai valoros coș (valoarea acestuia) precum și durata (în minute) a concursului.

Restricții

  • 2 ≤ L ≤ 50
  • 0 ≤ N ≤ 100
  • 0 ≤ P ≤ 2500
  • 1 ≤ v ≤ 30
  • Un iepuraș iese de pe pajiște dacă ajunge în afara matricei.
  • La un moment dat pot exista mai mulți iepurași în aceeași parcelă, cu excepția primului minut.

Exemplu

oua.in oua.out Explicații
5 6
1 4 10
2 2 1
2 3 5
3 3 6
5 1 4
5 2 2
2
2 1
3 5
5 11 10
Primul iepuraș stă 10 minute pe pajiște, culege 3 ouă, cu valoare totală 7
și parcurge traseul (2,1)-(2,2)-(3,2)-(4,2)-(5,2)-(5,1)-(4,1)-(3,1)-(2,1)-(1,1)->
 
Al doilea iepuraș stă 6 minute pe pajiște, culege 2 ouă, cu valoare totală 11
și parcurge traseul (3,5)-(3,4)-(3,3)-(2,3)-(2,4)-(2,5)->
 

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

Indicii de rezolvare

Arată 5 categorii