Binārā koka platums

Uzdevums

Nepieciešams iezīmēt bināro koku rūtiņu lapā, kuras rindas un kolonnas ir numurētas.

Zīmējumam ir jāatbilst šādām prasībām:

• Katra virsotne jāiezīmē savā rūtiņā;
• Viena līmeņa virsotnēm jāatrodas vienā rindā;
• Katrā kolonnā var atrasties ne vairāk kā viena virsotne;
• Virsotnēm, kas atrodas kreisajā apakškokā, rūtiņu lapā jāatrodas no vecāku virsotnes pa kreisi;
• Virsotnēm, kas atrodas labajā apakškokā, rūtiņu lapā jāatrodas no vecāku virsotnes pa labi;
• Visām kolonnām pēc kārtas (sākot ar to, kas satur virsotni visvairāk pa kreisi un beidzot ar to, kas satur virsotni visvairāk pa labi) jābūt aizņemtām.

Katra līmeņa platumu aprēķina kā tās virsotnes, kas atrodas visvairāk pa labi, un tās, kas atrodas visvairāk pa kreisi, aizņemto kolonnu numuru starpību, kam pieskaitīts 1.

Saknes līmenis ir 1 un katru reizi pārejot no vecāka virsotnes uz bērna virsotni, līmenis palielinās par 1.

Zīmējumā attēlots viens koks, kas atbilst iepriekšminētajiem nosacījumiem. Pirmā līmeņa platums ir 1, otrā un piektā - 13, trešā un ceturtā - 18, sestā - 12.

Uzrakstiet programmu, kas dotam binārā koka aprakstam aprēķina lielāko līmeņa platumu un līmeņa numuru, kurā tas sasniegts! Ja ir vairāki līmeņi ar šo lielāko platumu, tad jāizvada mazākais no līmeņu numuriem.

Ievaddati

Teksta faila binkopl.dat pirmajā rindā dots naturāls skaitlis N(1≤N≤1000) - koka virsotņu skaits. Katrā no nākošajām N faila rindām doti trīs skaitļi, kur pirmais ir virsotnes- vecāka numurs, otrais ir kreisā bērna virsotnes numurs, bet trešais - labā bērna virsotnes numurs. Visas virsotnes ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Saknes virsotnes numurs ir 1. Ja virsotnei nav bērnu virsotņu, tad bērnu virsotnes numura vietā ir skaitlis -1. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols.

Izvaddati

Teksta faila binkopl.rez vienīgajā rindā jāizvada divi naturāli skaitļi - mazākā līmeņa, pie kura sasniegts vislielākais platums, numurs un šī līmeņa platums.

Piemērs

binkopl.dat	binkopl.rez
19 1 2 3 2 4 5 3 6 7 4 8 -1 5 9 10 6 11 12 7 13 -1 8 -1 -1 9 14 15 10 -1 -1 11 16 -1 12 -1 -1 13 17 -1 14 -1 -1 15 18 -1 16 -1 -1 17 -1 19 18 -1 -1 19 -1 -1	3 18

Atsauces