Ștefan și Tudor nu erau hoți obișnuiți. Ei erau genii în informatică și matematică, pasionați de provocări logice și labirinturi criptate. Într-o seară misterioasă, au primit un mesaj anonim:
Banca Centrală din Matrizopolis păstrează în seiful său cel mai valoros artefact digital: Cheia Primă, o secvență binară ce poate decripta orice algoritm. Seiful este protejat de un sistem de securitate sub formă de... matrice.
Matricea avea dimensiunea , iar fiecare celulă reprezenta un pas posibil prin bancă. Sistemul avea o particularitate:
- Dacă valoarea unei celule era un număr prim, însemna că zona respectivă era plină de lasere invizibile – deci necesita efort și timp (cost 1).
- Dacă nu era prim, zona era sigură – fără riscuri (cost 0).
Pentru a ajunge la artefact, cei doi trebuiau să răspundă mai multor interogări transmise de sistemul bancar:
Care este drumul de efort minim de la celula la celula ?
Orice pas într-o celulă primă le consuma timp prețios, deci trebuiau să evite cât mai multe astfel de celule. Mișcările erau permise în cele 4 direcții: sus, jos, stânga și dreapta.
Pe măsură ce răspundeau la fiecare întrebare, ușile băncii se deschideau una câte una. Dar sistemul nu ierta greșeli: o alegere neinspirată într-o celulă primă le putea declanșa alarma.
Sarcina ta este să fii creierul din spatele operațiunii și să-i ajuți pe Ștefan și Tudor să:
- Calculeze drumul optim dintre două puncte din matrice, evitând cât mai multe numere prime.
- Răspundă la toate interogările sistemului pentru a ajunge la Cheia Primă fără a fi prinși.
Cerință
Dându-se o matrice cu linii și coloane, determinați pentru fiecare interogare drumul de cost minim din celula la celula . Costul unei celule e:
- , dacă valorea celulei e număr prim;
- , altfel.
Date de intrare
Fișierul de intrare heist.in
conține:
- pe prima linie un singur număr natural, , cu semnificația din enunț;
- pe următoarele linii câte numere naturale, reprezentând numerele asociate zonelor în ordinea corespunzătoare elementelor din matrice, linie cu linie, de sus în jos, și de la stânga la dreapta pe fiecare linie;
- pe următoarea linie numărul , cu semnificația din enunț;
- pe următoarele linii câte patru numere naturale, , cu semnificația din enunț;
Numerele aflate pe aceeași linie a fişierului sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire heist.out
conține pe linii costul drumului de cost minim între celulele date, câte un singur număr pe linie, în ordinea citirii.
Restricții și precizări
- ;
- ;
- .
# | Punctaj | Restricții |
---|---|---|
1 | 20 | |
2 | 25 | |
3 | 20 | |
4 | 20 | |
5 | 5 | |
6 | 5 | |
7 | 5 | Fără restricții suplimentare |
Exemplu
heist.in
3
4 3 6
1 2 7
4 3 9
1
1 1 3 3
heist.out
1
Explicație
Vom merge jos, jos, dreapta, dreapta.