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

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


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

Într-o ţară care-şi caută drumul spre bunăstare şi civilizaţie, există N oraşe, numerotate de la 1 la N, legate între ele prin N–1 şosele bidirecţionale. Între oricare două oraşe există cel mult o singură şosea. Fiecare şosea uneşte două oraşe distincte. Se poate călători între oricare două oraşe, circulând numai pe şosele.
Din păcate, nu există autostrăzi. Nu există nici bani pentru construirea autostrăzilor. Din acest motiv, politica statului este de a concesiona şoselele celor K „regi ai asfaltului”. Aceştia vor construi autostrăzi pe cheltuiala lor, având apoi dreptul de a impune taxe de trecere pe autostradă, exprimate în euro. Fiecare autostradă astfel construită va înlocui una dintre şosele.

Cerinţă

Scrieţi un program care calculează numărul de posibilităţi modulo 30011 în care se pot concesiona şoselele, astfel încât pentru niciun vehicul care se deplasează între oricare două oraşe ale ţării mergând pe şosele şi autostrăzi să nu se depăşească un total al taxelor mai mare decât S euro.

Date de intrare

Pe prima linie a fişierului de intrare autostrazi.in se află trei numere întregi N, S şi K separate prin spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află K numere naturale, R1, R2, ... Rk, nu neapărat distincte, separate prin câte un singur spaţiu, reprezentând taxele percepute de regii asfaltului. Pe următoarele N–1 linii se găsesc câte două numere naturale distincte x şi y separate printr-un singur spaţiu reprezentând o şosea care leagă oraşul x de oraşul y.

Date de ieşire

În fişierul de ieşire autostrazi.out se află un singur număr natural M, reprezentând numărul de posibilităţi modulo 30011 în care poate fi construită reţeaua de autostrăzi, astfel încât suma taxelor plătite într-o călătorie între oricare două oraşe să nu depăşească S euro.

Restricţii

1 ≤ x, y ≤ N ≤ 100
1 ≤ K ≤ 20
1 ≤ S ≤ 100
1 ≤ R1, R2, ... Rk ≤ 100
• Regele i al asfaltului impune aceeaşi taxă Ri pentru fiecare autostradă construită de el şi poate construi zero, una sau maxim N – 1 autostrăzi.
• O şosea se concesionează în întregime unui singur constructor sau poate să nu fie concesionată deloc. În acest caz nu există taxă de trecere.
• Este admis cazul în care nu se concesionează nicio şosea.

Exemple

autostrazi.inautostrazi.outExplicaţii
4 2 2 2 1 1 2 2 3 4 2 11 Taxele: 2 si 1. Şoselele : 2 1, 2 3, 2 4
Variantele de taxare:
(0 0 0), (1 0 0), (0 1 0), (0 0 1), (1 1 0), (0 1 1), (1 0 1), (1 1 1), (2 0 0), (0 2 0), (0 0 2)

autor: Prof. Constantin Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2010: codif, game1, piatra, miere, left, acerc, bubblesort, carray, hawaii, radio1, randomizare, tetris1, trenuri1
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, teatru, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, randuri, panouri, powerpuff, cartele, joc15, stalpi1, telecab, pseudobil, harta2
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, 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, 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, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor