apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

shunas Skaitļu šūnas 1 sek.


 Uzdevums

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.

 
 Ievaddati

Skaitļu šūnu fragmenta malas garums ir teksta faila shunas.in 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.

 
 Izvaddati

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

 
 Piemērs

shunas.inshunas.out
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
22

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).

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

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS