Soluții trimise

Rezumat problemă

#1788 Rege1

Regele Leonidas trebuie să-și aleagă o armată de 300 de spartani. Surprins de mulțimea mare de voluntari care vor să-l urmeze în viitoarea luptă de la Termopile, regele are nevoie să facă o selecție a războinicilor. Astfel, el a decis să le dea următoarea problemă:

Se dă un arbore cu N noduri (etichetate cu numere consecutive începând de la 1) cu rădăcina în nodul 1, în care fiecare muchie are asociat un cost. Se definește un lanț în jos în arbore ca fiind orice lanț simplu ce unește un nod A cu alt nod B din subarborele lui A. Cu alte cuvinte, un lanț în jos este un lanț de la A la B în care A este strămoș al lui B. Definim costul unui lanț în jos ca fiind suma costurilor muchiilor din care este format lanțul.

Numim acoperire a unui arbore o partiționare a muchiilor în lanțuri disjuncte, a căror reuniune este arborele inițial. Regele Leonidas dorește să acopere întreg arborele cu lanțuri în jos, însa are un număr limitat de lanțuri, notat în continuare cu S.

Se cere să se determine cel mai mic număr K pentru care să existe o partiționare completă a arborelui cu maxim S lanțuri astfel încât costul fiecărui lanț să fie cel mult K. Dacă nu există un astfel de număr K, să se afișeze -1.

Pentru că și tu vrei să lupți alături de Leonidas pentru libertatea Spartei, trebuie să rezolvi această problemă ca să-ți asiguri un loc în primii 300 de spartani. Leonidas este un rege înțelept. Ca să se asigure că nu vor exista Spartani care vor încerca să ghicească rezultatul, el vă cere să răspundeți la T astfel de probleme.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

ID   Utilizator Problema Data încărcării Stare
Cmeciu Alexandru (alexcmeciucristian) Rege1 22 Martie 2024, 12:32 Evaluare finalizată 0
Chertes Rares (RaresChertes) Rege1 21 Martie 2024, 17:19 Evaluare finalizată 100
Chertes Rares (RaresChertes) Rege1 21 Martie 2024, 17:16 Evaluare finalizată 20
Lezau Andrei (Lezau_Andrei) Rege1 21 Martie 2024, 11:34 Evaluare finalizată 10
Lezau Andrei (Lezau_Andrei) Rege1 21 Martie 2024, 11:34 Evaluare finalizată 10
Lezau Andrei (Lezau_Andrei) Rege1 20 Martie 2024, 13:58 Evaluare finalizată E.C
POPESCU ANDREI (andreip99) Rege1 24 Ianuarie 2024, 17:58 Evaluare finalizată 100
Radu Alexandru (superffff) Rege1 20 Ianuarie 2024, 21:39 Evaluare finalizată 100
Nume Prenume (pbinfonume) Rege1 17 Ianuarie 2024, 12:23 Evaluare finalizată E.C
Taschina Luca (LucaTaschina) Rege1 04 Ianuarie 2024, 13:26 Evaluare finalizată 100
SS KMF (SSKMF) Rege1 23 Decembrie 2023, 20:07 Evaluare finalizată 100
SS KMF (SSKMF) Rege1 23 Decembrie 2023, 19:59 Evaluare finalizată 0
Cazacu Razvan (RazvanCazacu) Rege1 13 Decembrie 2023, 21:49 Evaluare finalizată 100
Pelea Radu (RaduPelea21) Rege1 13 Decembrie 2023, 21:37 Evaluare finalizată 100
Pelea Radu (RaduPelea21) Rege1 13 Decembrie 2023, 20:44 Evaluare finalizată 0
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 19:25 Evaluare finalizată 100
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 19:06 Evaluare finalizată 10
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 13:17 Evaluare finalizată 10
Cazacu Razvan (RazvanCazacu) Rege1 13 Decembrie 2023, 12:58 Evaluare finalizată 0
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 12:57 Evaluare finalizată 0
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 12:50 Evaluare finalizată 0
Mitri Robert (Robertutul) Rege1 13 Decembrie 2023, 12:07 Evaluare finalizată E.C
Ardelean Raul (Raul_A) Rege1 24 Noiembrie 2023, 16:28 Evaluare finalizată 100
Rosca Vasilica (vasilicarosca) Rege1 06 Noiembrie 2023, 13:31 Evaluare finalizată 100
prof CNTV (tudor) Rege1 09 August 2023, 11:41 Evaluare finalizată 100
Black Chris (Cristiansjsncndns) Rege1 21 Iulie 2023, 16:10 Evaluare finalizată 100
Adrian Statescu (thinkphp) Rege1 02 Iulie 2023, 22:56 Evaluare finalizată 100
Benchea Matei (matei__b) Rege1 17 Iunie 2023, 13:07 Evaluare finalizată 100
adcdefg adcddd (randomdud01) Rege1 04 Iunie 2023, 21:42 Evaluare finalizată E.C
Mark R (HELLOS) Rege1 15 Aprilie 2023, 21:35 Evaluare finalizată 100
Musceleanu Cristian (musceleanucristian) Rege1 13 Aprilie 2023, 18:29 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) Rege1 02 Aprilie 2023, 18:31 Evaluare finalizată 100
Moldovan Robert (use KN) (moldovan_robert_lol) Rege1 02 Aprilie 2023, 18:24 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) Rege1 02 Aprilie 2023, 18:21 Evaluare finalizată 0
Moldovan Robert (use KN) (moldovan_robert_lol) Rege1 02 Aprilie 2023, 18:20 Evaluare finalizată 0
Barbu David (Barbu_David) Rege1 30 Martie 2023, 18:22 Evaluare finalizată 0
Dumitrascu Theodor (TheodorCristian) Rege1 30 Martie 2023, 10:19 Evaluare finalizată 0
😎 ( ͡° ͜ʖ ͡°) (Tester) Rege1 22 Martie 2023, 10:13 Evaluare finalizată 30
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:45 Evaluare finalizată 100
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:44 Evaluare finalizată 0
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:43 Evaluare finalizată 0
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:42 Evaluare finalizată 100
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:41 Evaluare finalizată E.C
Fazacaș Mihai Tudor (FazacasMihai) Rege1 21 Martie 2023, 10:35 Evaluare finalizată 10
solinfo.ro | Soluții probleme (solinfo_ro) Rege1 21 Martie 2023, 10:21 Evaluare finalizată 100
Alexutan Cristian (cristi_a) Rege1 21 Martie 2023, 10:16 Evaluare finalizată 100
Alexutan Cristian (cristi_a) Rege1 20 Martie 2023, 18:34 Evaluare finalizată 0
Fazacaș Mihai Tudor (FazacasMihai) Rege1 20 Martie 2023, 18:30 Evaluare finalizată E.C
Pirvulescu Serban (Zexsoft) Rege1 20 Martie 2023, 08:46 Evaluare finalizată 0
Rusen Mihai (Rusen_Mihai) Rege1 12 Martie 2023, 23:23 Evaluare finalizată 100