Scribd
Încărcați
8 vizualizări1 pagină

2007 Zero

Documentul descrie o problemă de programare pentru Olimpiada de Informatică, în care un pion trebuie să navigheze pe o tablă de joc N*N, evitând pătratele cu valoarea 0. Scopul este de a determina numărul de zerouri la sfârșitul produsului numerelor de pe drumul optim de la colțul stânga-sus la colțul dreapta-jos. Cerințele includ citirea dimensiunii tablei și a valorilor din pătratele acesteia, precum și scrierea rezultatului într-un fișier de ieșire.

Încărcat de

artene mihaela
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd
8 vizualizări1 pagină

2007 Zero

Documentul descrie o problemă de programare pentru Olimpiada de Informatică, în care un pion trebuie să navigheze pe o tablă de joc N*N, evitând pătratele cu valoarea 0. Scopul este de a determina numărul de zerouri la sfârșitul produsului numerelor de pe drumul optim de la colțul stânga-sus la colțul dreapta-jos. Cerințele includ citirea dimensiunii tablei și a valorilor din pătratele acesteia, precum și scrierea rezultatului într-un fișier de ieșire.

Încărcat de

artene mihaela
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd

OLIMPIADA DE INFORMATICĂ Clasele XI-XII

Etapa municipală – IAŞI, 20 ianuarie 2007

Problema 1 – Zero 100 puncte


Să considerăm o tablă de joc constituită din N*N pătrate organizate sub forma unei matrice cu N linii şi N
coloane. În fiecare pătrat este scris un număr natural.
La începutul jocului, în colţul din stânga-sus al tablei se află un pion. Acest pion trebuie să ajungă în colţul din
dreapta-jos al tablei. La un pas pionul se poate mişca din poziţia sa curentă (x, y) fie în pătratul de dedesubt
(x+1, y) (pe linia următoare, aceeaşi coloană), fie în pătratul din dreapta poziţiei sale (x, y+1) (aceeaşi linie,
coloana următoare), dar nu poate fi plasat într-un pătrat care conţine valoarea 0.
Drumul unui pion este constituit din toate pătratele prin care trece pionul pentru a ajunge din colţul stânga-sus
până în colţul din dreapta-jos al tablei. Costul unui drum este definit ca produsul numerelor aflate în pătratele
situate pe drum. Costul unui drum este optimal dacă numărul de zerouri aflate la sfârşitul scrierii sale în baza 10
este minim.

Cerinţă
Scrieţi un program care să determine numărul de zerouri aflate la sfârşitul costului optimal.

Date de intrare
Fişierul de intrare [Link] conţine pe prima linie numărul natural N care reprezintă dimensiunea tablei de joc.
Fiecare dintre următoarele N linii conţine câte N numere naturale separate prin câte un spaţiu reprezentând tabla
de joc.

Date de ieşire
Fişierul de ieşire [Link] va conţine o singură linie pe care va fi scris numărul de zerouri aflate la sfârşitul
costului optimal.

Restricţii
1 ≤ N ≤ 500
Pe tabla de joc se află numere naturale ≤ 1 000 000.
Pentru datele de test există întotdeauna soluţie.

Exemplu
[Link] [Link] Explicaţie
4 2 Drumul optimal trece prin 1, 3, 8, 5, 15, 7, 4.
1 3 0 0 Produsul elementelor situate pe acest drum se termină cu două zerouri.
0 8 2 25
O altă soluţie de a ajunge în colţul dreapta-jos ar fi fost 1, 3, 8, 2, 25, 5, 4, dar
6 5 0 5
0 15 7 4 numărul de zerouri de la sfârşitul produsului elementelor de pe acest drum este 3.

Timp maxim de execuţie/test: 1 secundă.

S-ar putea să vă placă și