Nosaukums
Rinda (rinda)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Uz tāfeles ir uzzīmēta skaitļu piramīda, kas veidota no veseliem nenegatīviem skaitļiem tā, ka tās virsotnē ir viens skaitlis, nākošajā rindā divi skaitļi, ..., pēdējā rindā ir N skaitļi (1 <N≤10). Neviena skaitļa vērtība piramīdā nepārsniedz 109. Katrs skaitlis, kas neatrodas pēdējā rindā, ir vienāds ar divu tieši zem tā pa labi un pa kreisi esošo skaitļu summu. Skaitļu piramīda var izskatīties, piemēram, šādi:

                77
              34  43
            11  23  20
           4   7  16  4


Ariadne starpbrīdī katrā piramīdas rindā nodzēsa skaitļus tā, ka katrā rindā palika tikai viens skaitlis, un katras nākošās rindas nenodzēstais skaitlis atradās tieši zem šajā rindā nenodzēstā skaitļa pa labi vai pa kreisi. Iepriekš aplūkotajā piemērā nenodzēstie skaitļi varēja būt, piemēram, 77,43,23,7, bet nevarēja būt 77,34,20,16 (jo 20 neatrodas tieši zem 34). Uzrakstiet programmu, kas dotiem nenodzēstajiem piramīdas skaitļiem atrod visus piramīdas pēdējā rindā esošos N skaitļus!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dota naturāla skaitļa N vērtība (1<N≤10). Faila otrajā rindā doti N veseli nenegatīvi skaitļi - nenodzēstie piramīdas skaitļi. Katram i (1 ≤i≤N) i-tais skaitlis rindā ir piramīdas i-tajā rindā nenodzēstais skaitlis. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols. Zināms, ka katriem dotajiem ievaddatiem eksistē vismaz viens atrisinājums.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada N veseli nenegatīvi skaitļi - piramīdas pēdējā rindā esošie skaitļi pēc kārtas no kreisās uz labo pusi. Starp katriem diviem blakus skaitļiem izvaddatos jābūt vienam tukšumsimbolam. Ja iespējami vairāki atrisinājumi, jāizvada tas, kurš leksikogrāfiskā sakārtojumā ir pats pirmais, t.i., ja ir divi dažādi atrisinājumi A=(a 1 a2 ... an) un B=(b1 b2 ... bn), tad atrisinājums A leksikogrāfiskajā sakārtojumā atrodas pirms atrisinājuma B, ja iespējams atrast tādu i (1≤i≤n), ka ai<bi un aj=bj visiem j<i.


Piezīmes

Pirmajam piemēra testam visas rindas leksikogrāfiskā secībā ir:

1 13 7 16 4 7 16 4 4 16 7 4 7 16 4 10 10 4 16 7 16 7 13 1

Uzdevums izmantots Latvijas 16.informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
4
77 43 23 7
Stdout
1 13 7 16

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