.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » strict

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
strict


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Un arbore binar se numeste strict daca toate nodurile sale interne au exact doi fii.
Se da un set de n arbori binari stricti fiecare avand m noduri numerotate de la 1 la m.
Definim recurent egalitatea dintre doi arbori avand radacinile fixate in nodurile x, respectiv y.
A(x) = A(y) daca:

  • x,y nu au fii

  • sau
  • x,y au fii, A(fiu_drept(x)) = A(fiu_drept(y)) si A(fiu_stang(x)) = A(fiu_stang(y))

  • (unde am notat cu A(x) arborele cu radacina in x)

    La fel putem defini relatia de ordine "<" intre doi arbori A(x) si A(y).

    A(x) < A(y) daca:
  • x nu are fii si y are fii

  • sau
  • nodurile x si y au fii iar A(fiu_stang(x)) < A(fiu_stang(y))

  • sau
  • nodurile x si y au fii, A(fiu_stang(x)) = A(fiu_stang(y)) si A(fiu_drept(x)) < A(fiu_drept(y))
  • Cerinta

    Sa se determine lungimea celui mai lung subsir (nu neaparat strict) "crescator" de arbori din setul dat conform cu relatia de ordine definita mai sus.

    Date de intrare

    Fisierul de intrare strict.in are urmatoarea structura:   
    - pe prima linie sunt scrise doua numere naturale separate prin spatiu n m, reprezentând numarul de arbori si respectiv dimensiunea arborilor
    - pe fiecare dintre urmatoarele n linii se gasesc cate m - 1 + (m + 1) / 2 numere; pe linia i + 1 se gasesc informatiile necesare pentru arborele i astfel: pentru fiecare nod de la 1 la m este scris 0 daca nodul nu are fii sau sunt scrise doua numere reprezentand fiul stang si respectiv, fiul drept; mai intai este descris nodul 1, apoi nodul 2 etc. Linia: 0 0 5 1 0 0 7 3 2 4 inseamna ca nodurile 1 si 2 nu au fii, nodul 3 il are ca fiu stang pe nodul 5 si ca fiu drept pe nodul 1, nodul 4 nu are fii s.a.m.d.

    Date de iesire

    Fisierul de iesire strict.out va contine un singur numar reprezentand lungimea celui mai lung subsir crescator.

    Restrictii

    0 < n <= 10000
    0 < m <= 51
    Campionii isi pot da seama de ce intr-un arbore binar strict exista un singur nod care poate indeplini rolul de radacina a arborelui. Din aceasta cauza relatia de ordine e bine definita.
    40% din teste vor avea
    n <= 5000 si m <= 31.
    Participantii sunt incurajati sa foloseasca pentru citirea datelor functii ca fgets() sau fread()!
    Fie
    x=(x1, x2, ..., xn) un sir de n elemente. Un subsir al lui x este format din elemente din x, in ordinea in care acestea apar in x (xi1, xi2, ..., xik cu i1<i2<...<ik).

    Exemplu

    strict.in strict.out Explicatie

    5 7
    0 0 5 1 0 0 7 3 2 4
    3 7 6 4 0 1 5 0 0 0
    7 5 0 0 0 6 3 0 2 4
    4 3 0 0 5 6 0 0 2 1
    2 5 3 4 0 7 6 0 0 0

    3

    O solutie poate fi reprezentata de arborii 2, 3 si 5

    Iolanda Popa
    studenta - Facultatea de Informatica, Iasi
    Contact: iolivp@gmail.com

    propunător: Prof. Emanuela Cerchez
    emanuela.cerchez@gmail.com
    Articole recomandate
    Probleme recomandate
    De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
    De acelaşi autor: iepuri, rlcs, herbert, masina
    Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
    Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
    surse trimise | ajutor