Fişierul intrare/ieşire:cub.in, cub.outSursăOlimpiada locala 2010, Clasele 11-12
AutorDan GrigoriuAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cub

Un cub are latura de n unităţi şi este împărţit în n3 cuburi elementare de latură 1. Fiecare cubuleţ elementar are asociat un număr de puncte. Numerotarea cubuleţelor elementare se face cu indicii:

  • i, arată etajul (nivelul): 1 pentru cel de sus şi n pentru cel de jos, cele n etaje fiind obţinute prin secţionarea cubului cu n-1 plane echidistante paralele cu feţele sus-jos ale cubului;
  • j, arată "felia" verticală astfel: 1 pentru cea din spate şi n pentru cea din faţă, cele n “felii” fiind obţinute prin secţionarea cubului cu n-1 plane echidistante paralele cu feţele faţă-spate ale cubului;
  • k, arată "felia" verticală astfel: 1 pentru cea din stânga şi n pentru cea din dreapta, cele n “felii” fiind obţinute prin secţionarea cubului cu n-1 plane echidistante paralele cu feţele stînga-dreapta ale cubului.

Fiecărui cub elementar i se asociază un punctaj exprimat printr-o valoare naturală cel mutl egală cu 10.

Un mobil se află pe poziţia (1, 1, 1), adică sus, în spate şi în stânga şi trebuie să ajungă în poziţia (n, n, n), adică jos, în faţă şi în dreapta. El se poate deplasa doar în direcţiile: sus, jos, stânga, dreapta, faţă şi spate.

Drumul trebuie sa fie de lungime minimă (număr minim de paşi) şi în aceste condiţii el trebuie să acumuleze un număr maxim de puncte, culegând tot punctajul cubuleţelor prin care trece, inclusiv poziţiile (1, 1, 1) şi (n, n, n).

Cerinţe:

  • Să se afle puntajul maxim ce se poate obţine în aceste condiţii.
  • Să se precizeze poziţiile elementare prin care trece drumul corect care a fost ales.

Date de intrare

Fişierul de intrare cub.in conţine:

  • Numerele n şi m separate cu un spaţiu pe prima linie: n este dimensiunea cubului şi m este numărul de poziţii elementare ce conţin un punctaj strict pozitiv, celelalte poziţii având punctajul 0.
  • Pe următoarele m linii: câte 4 numere naturale, primele 3 reprezentând câte o poziţie (i, j, k) şi al patrulea fiind punctajul asociat acelei poziţii; cele 4 numere se separă cu câte un spaţiu.

Date de ieşire

Fişierul de ieşire cub.out conţine:

  • Numărul maxim de puncte culese pe drumul ales, pe prima linie
  • Pe următoarele linii se trec poziţiile drumului ales (prin cele trei coordonate separate de câte un spaţiu), începând cu (1, 1, 1) şi până la (n, n, n).

Restricţii

  • 1 ≤ n ≤ 20
  • 0 ≤ m ≤ n3
  • Punctajul asociat unei poziţii elementare are valori naturale de la 0 la 10
  • Pot fi mai multe variante de drum ce respectă condiţiile; se cere doar o soluţie.
  • Se va acorda 60% din punctaj pentru determinarea corecta a punctajului maxim si 100% din punctaj pentru rezolvarea corecta a ambelor cerinte

Exemplu

cub.incub.outExplicatie
3 8
1 1 1 2
2 1 1 1
2 1 2 3
2 2 1 5
2 2 2 4
3 3 1 6
3 3 2 7
3 3 3 8
29
1 1 1
2 1 1
2 2 1
3 2 1
3 3 1
3 3 2
3 3 3
Cubul are latura 3 şi 8 poziţii cu valori nenule: (1, 1, 1) cu valoarea 2, (2, 1, 1) cu valoarea 1,
(2, 1, 2) cu valoarea 3, ..., (3, 3, 3) cu valoarea 8, celelalte având valori 0.
Drumul ales strabate 7 poziţii şi anume: (1, 1, 1), (2, 1, 1), (2, 2, 1), ..., (3, 3, 3),
culegând respectiv punctajele: 2+1+5+6+7+8=29, valoare ce se afişează pe prima linie din cub.out şi
care este urmată de poziţiile prin care trece drumul.
Pot fi şi alte drumuri cu acelaşi punctaj maxim, dar s-a ales unul dintre ele.
Trebuie sa te autentifici pentru a trimite solutii. Click aici