Fişierul intrare/ieşire:biomech.in, biomech.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Biomech

In anul 2006, oamenii au construit primul robot biomecanic cu inteligenta artificiala. In orice caz, inca nu se stie prea bine cat de avansata este inteligenta sa. Tocmai de aceea, robotul va fi supus unui test. El va fi plasat intr-o zona rectangulara, impartita in patrate amplasate pe 5 linii si un numar infinit de coloane. Coloanele sunt numerotate de la -infinit la +infinit si robotul este plasat initial in coloana cu numarul 0. Liniile zonei rectangulare sunt numerotate de la 1 la 5 si robotul va fi plasat la inceput in linia 3 (cea din mijloc). Robotul va fi orientat in una din cele 8 directii posibile: Nord, Nord-Est, Est, Sud-Est, Est, Sud, Sud-Vest, Vest, Nord-Vest.

Mutarile pe care robotul le poate face sunt:

  • Rotatie cu un unghi multiplu de 45 de grade
    Din directia spre care este indreptat, robotul se poate intoarce astfel spre oricare alta directie. O rotatie de la o directie initiala la o directie finala consuma o anumita cantitate de timp. Din cauza structurii interne a robotului, se poate ca o rotatie cu un unghi mai mare sa dureze mai putin decat o rotatie cu un unghi mic. De asemenea, o rotatie din directia X in directia Y s-ar putea sa nu dureze la fel de mult ca o rotatie din directia Y in directia X.
  • Miscare in directia spre care este orientat, din patratul curent in urmatorul patrat (avand o muchie comuna sau un varf comun cu acesta)
    De exemplu, daca robotelul este la linia 3, coloana X, orientat spre Nord-Est, s-ar putea deplasa in patratelul de pe linia 2, coloana X+1. Dupa mutare, robotul nu-si schimba directia in care este orientat. De asemenea, nu ii este permis sa mute in afara zonei rectangulare (asadar, anumite miscari sunt interzise din anumite patrate).

Cantitatea de timp necesara pentru o mutare depinde atat de directia in care se muta (din cauza campului magnetic al Pamantului) cat si de linia pe care robotul se afla in momentul curent (deoarece fiecare dintre cele 5 randuri are o structura electromagnetica diferita). Totusi, costurile mutarilor nu depind de coloana in care se afla robotul.

Robotul va fi supus unui test, dupa cum urmeaza: i se vor acorda TMAX unitati de timp. Folosindu-le, va trebui sa mute cat mai departe posibil de pozitia curenta. Distanta nu este masurata in termeni de patrate, ci in termeni de coloane. Daca dupa TMAX unitati temporale robotul se afla pe coloana X, distanta este considerata |X| (valoarea absoluta a lui X). Nu este importanta linia pe care ajunge.

Robotul va alege directia in care va fi orientat initial si cantitatea de timp va incepe sa scada dupa ce face aceasta decizie. Aflati care este distanta maxima pe care robotul o poate parcurge in TMAX unitati de timp.

Date de Intrare

Prima linie a fisierului de intrare biomech.in contine cantitatea de timp TMAX. Urmatoarele 8 linii contin cate 8 numere intregi fiecare. Al j-lea numar de pe a i-a dintre aceste linii reprezinta timpul necesar pentru a schimba directia i in directia j. Urmatoarele 5 linii contin cate 8 numere intregi fiecare. Al j-lea numar de pe a i-a dintre aceste linii reprezinta timpul necesar pentru a muta in directia j dintr-un patrat de pe linia i. Sunt date valori si pentru mutarile interzise. Acestea trebuie ignorate.

Ordinea directiilor (de la 1 la 8) este urmatoarea: N, NE, E, SE, S, SV, V, NV.

Date de Iesire

Afisati pe singura linie a fisierului biomech.out distanta maxima pe care robotul o poate parcurge fara sa depaseasca durata de timp TMAX.

Restrictii si precizari

  • 1 ≤ TMAX ≤ 1015, TMAX este intreg
  • 1 ≤ timpul necesar pentru orice rotatie sau miscare ≤ 1.000

Exemple

biomech.inbiomech.out
4
0 10 10 10 10 10 10 10
10 0 10 10 10 10 10 1
10 10 0 10 10 10 10 10
10 10 10 0 10 10 10 10
10 10 10 10 0 10 10 10
10 10 10 10 10 0 10 10
10 10 10 10 10 10 0 10
10 10 10 1 10 10 10 0
1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1 1000 1000 1000 1000
1000 1 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000
2
100000
0 1000 1000 1000 1000 1000 1000 1000
1000 0 1000 1000 1000 1000 1000 1000
1000 1000 0 1000 1000 1000 1000 1000
1000 1000 1000 0 1000 1000 1000 1000
1000 1000 1000 1000 0 1000 1000 1000
1000 1000 1000 1000 1000 0 1000 1000
1000 1000 1000 1000 1000 1000 0 1000
1000 1000 1000 1000 1000 1000 1000 0
1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 7 1000
1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000
14285
50
12 8 43 20 45 13 28 18
34 28 17 18 19 49 43 46
22 32 11 48 29 46 15 22
42 20 5 5 25 13 4 39
31 31 1 34 26 31 40 40
29 5 19 25 47 37 3 45
32 43 25 18 42 33 47 34
35 35 6 49 32 15 23 40
22 4 1 12 24 16 46 40
23 27 39 21 19 16 20 39
42 26 42 45 50 46 39 6
23 8 45 16 36 26 31 18
40 47 48 26 10 7 3 13
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content