Nosaukums
Skaitļu šūnas (shunas)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Zīmējumā attēlots skaitļu šūnu fragments, kura šūnās (zīmējumā aplīšos) ir ierakstīti skaitļi (malas garums attēlotajam šūnu fragmentam ir 3).

Maršruts sākas no jebkuras šūnas augšējā līnijā un beidzas ar kādu šūnu apakšējā līnijā. No katras šūnas maršruts var turpināties tikai vai nu diagonāli uz leju pa labi vai arī diagonāli uz leju pa kreisi. Veidojot maršrutu caur skaitļu šūnām, jums ir atļauts ne vairāk kā vienu reizi izpildīt divu skaitļu maiņu ne vairāk kā vienā skaitļu šūnu horizontālajā rindā. (Maiņa būtībā nozīmē, ka vienā izvēlētā rindā jums ir atļauts pārvietot lielāko šis rindas skaitli uz jebkuru vietu tajā pašā rindā).

Jūsu uzdevums ir uzrakstīt programmu, kas skaitļu šūnu fragmentam atrod lielāko starp visu iespējamo maršrutu skaitļu summām, izmantojot iespēju vienu reizi izpildīt skaitļu maiņu, kā aprakstīts iepriekš.
Ierobežojumi:

  • Skaitļi šūnās ir veseli skaitļi no 0 līdz 99;
  • Šūnu fragmenta malas garums ir naturāls skaitlis robežās no 1 līdz 99.

Ievaddatu raksturojums

Skaitļu šūnu fragmenta malas garums ir izvaddatu pirmajā rindā. Ja fragmenta malas garums ir n, fragments sastāv no 2n-1 skaitļu šūnu rindas. Nākamajās 2n-1 ievaddatu faila rindās ir doti katrai šūnu rindai atbilstošie skaitļi, kas atdalīti ar tukšumsimboliem.


Izvaddatu raksturojums

Ievaddatu vienīgajā rindā jāizvada vesels skaitlis - vislielākā iespējamā maršruta summa.


Piezīmes

Zīmējumā maršruts ar lielāko summu (3+2+8+5+4=22) ir ieēnots. 

Atzīmēsim, ka skaitlis '5' ceturtajā rindā ir jāsamaina uz šīs rindas trešo šūnu (skaitot no kreisās puses).

Uzdevums izmantots 6.Baltijas informātikas olimpiādē Haningē(Zviedrija) 2000.gadā.


Paraugdati

Stdin
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
Stdout
22

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.