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

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


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
64MB / 8MB

Odată cu vacanţa de Paşte, Alex s-a hotărât să plece cu maşina la mare. Harta României este modelată ca un arbore (graf conex aciclic neorientat) ce are N noduri, reprezentând oraşele ţării. Este binecunoscut faptul că Alex este vitezoman, de aceea el vrea să se ferească de eventualele radare, care sunt plasate pe muchiile arborelui (pe o muchie se poate afla maxim un radar). Dacă pe o muchie există un radar, atunci Alex nu va risca şi nu va merge pe acea muchie.
Fiecare oraş are un timp de vizitare dat, iar cu toţii ştim că Alex este foarte ocupat, aşadar el nu vrea sa piardă prea mult timp vizitând. Alex pleacă din Gheorgheni (nodul 1, considerat rădăcină) şi doreşte să ştie în câte moduri ar putea fi plasate radarele pe hartă astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P, ştiind că Alex nu va merge pe nicio muchie ce conţine un radar.
Problema aceasta este destul de simplă pentru Alex, aşa că s-a gândit să v-o dea vouă.

Cerinţă

Scrieţi un program care să răspundă problemei lui Alex, adică să determine în câte moduri pot fi plasate radare pe muchii astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P.

Date de intrare

Fişierul radare.in conţine pe prima linie N şi P, cu semnificaţia din enunţ. Următoarele N-1 linii vor conţine fiecare câte două numere întregi x y, însemnând că există o muchie între oraşele x şi y.
Pe ultima linie se vor afla N numere naturale cuprinse între 1 şi P inclusiv, al i-lea dintre acestea reprezentând timpul de vizitare al oraşului i.

Date de ieşire

Fişierul radare.out va conţine un singur număr reprezentând răspunsul problemei lui Alex modulo 31333.

Restricţii

1 ≤ N ≤ 3 000
1 ≤ P ≤ 3 500
1 ≤ x, y ≤ N
1 ≤ timpul de vizitare al unui oraş ≤ P
• dacă un radar este plasat pe o muchie, Alex NU va merge pe acea muchie
• două configuraţii de radare diferă între ele dacă există cel puţin o muchie (a, b) care într-una dintre configuraţii să conţină un radar, iar în cealaltă nu.

Exemple

radare.inradare.outExplicaţii
6 3 1 2 1 3 2 4 4 5 4 6 1 1 1 1 1 1 5 Cele 5 moduri posibile sunt:
1. există radar pe muchia (2,4)
2. sunt radare pe muchiile (2,4), (4,5)
3. sunt radare pe muchiile (2,4), (4,6)
4. sunt radare pe muchiile (2, 4), (4,5), (4,6)
5. sunt radare pe muchiile (1,3), (4,5), (4,6)



autor: Andrei Parvu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: hacker, terenuri3d, enigma, jocs, 3max, confuzie
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, strict, 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, 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, strict, 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, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor