Soluții trimise

Rezumat problemă

Dragoni

#1136

Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele A j și B j și are lungime D j.

Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmax i. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.

Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:

  1. Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă Dj ≤ Dmaxt.
  2. Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat pe insula respectivă.

Cerințe:

a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.

ID   Utilizator Problema Data încărcării Stare
Alex Cristi (AlexAC) Dragoni 14 Martie 2025, 15:22 Evaluare finalizată 20
Alex Cristi (AlexAC) Dragoni 14 Martie 2025, 15:19 Evaluare finalizată 0
stroe razvan (stroe16) Dragoni 14 Martie 2025, 13:20 Evaluare finalizată 20
stroe razvan (stroe16) Dragoni 14 Martie 2025, 13:20 Evaluare finalizată 0
stroe razvan (stroe16) Dragoni 14 Martie 2025, 13:19 Evaluare finalizată 0
stroe razvan (stroe16) Dragoni 14 Martie 2025, 12:48 Evaluare finalizată 20
stroe razvan (stroe16) Dragoni 14 Martie 2025, 12:48 Evaluare finalizată 0
stroe razvan (stroe16) Dragoni 14 Martie 2025, 11:32 Evaluare finalizată 20
stroe razvan (stroe16) Dragoni 14 Martie 2025, 11:31 Evaluare finalizată 0
Leucea Mihnea (Mihnea_Leucea) Dragoni 14 Martie 2025, 11:14 Evaluare finalizată 100
Leucea Mihnea (Mihnea_Leucea) Dragoni 14 Martie 2025, 11:13 Evaluare finalizată 20
Leucea Mihnea (Mihnea_Leucea) Dragoni 14 Martie 2025, 10:57 Evaluare finalizată 20
lapusan vlad (Vlad_lapusan) Dragoni 14 Martie 2025, 09:34 Evaluare finalizată 100
Bolea Cristina (boleacristina) Dragoni 14 Martie 2025, 07:26 Evaluare finalizată 100
Bolea Cristina (boleacristina) Dragoni 14 Martie 2025, 07:26 Evaluare finalizată E.C
Stefan Susanu (stefan_313) Dragoni 13 Martie 2025, 21:16 Evaluare finalizată 100
Stefan Susanu (stefan_313) Dragoni 13 Martie 2025, 21:15 Evaluare finalizată E.C
Stefan Susanu (stefan_313) Dragoni 13 Martie 2025, 21:15 Evaluare finalizată 30
stroe razvan (stroe16) Dragoni 13 Martie 2025, 18:44 Evaluare finalizată 20
stroe razvan (stroe16) Dragoni 13 Martie 2025, 14:46 Evaluare finalizată 20
Leucea Mihnea (Mihnea_Leucea) Dragoni 13 Martie 2025, 11:40 Evaluare finalizată 20
Paun Arthur-Octavian (Arthur_Paun) Dragoni 13 Martie 2025, 01:29 Evaluare finalizată 100
Dascal Raul (Raul69) Dragoni 12 Martie 2025, 20:24 Evaluare finalizată 20
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 12:14 Evaluare finalizată 100
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 11:30 Evaluare finalizată 52
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 11:26 Evaluare finalizată 52
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 11:24 Evaluare finalizată 52
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 11:06 Evaluare finalizată 36
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 10:54 Evaluare finalizată 20
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 10:52 Evaluare finalizată 20
Badu Ioana (bufulicii) Dragoni 12 Martie 2025, 10:07 Evaluare finalizată 20
Iulia Lincan (iulia_lincan) Dragoni 11 Martie 2025, 19:53 Evaluare finalizată 100
Badu Ioana (bufulicii) Dragoni 11 Martie 2025, 18:08 Evaluare finalizată 0
Stana Vlad (StanaVlad) Dragoni 11 Martie 2025, 09:50 Evaluare finalizată 100
Stana Vlad (StanaVlad) Dragoni 11 Martie 2025, 09:47 Evaluare finalizată 100
Stana Vlad (StanaVlad) Dragoni 11 Martie 2025, 09:45 Evaluare finalizată E.C
Radulescu Alex (Alex110506) Dragoni 10 Martie 2025, 17:31 Evaluare finalizată 100
Butoi Alexandru (alyymov) Dragoni 10 Martie 2025, 13:51 Evaluare finalizată 100
Ghenea Radu (McMeat) Dragoni 10 Martie 2025, 13:22 Evaluare finalizată 100
Ghenea Radu (McMeat) Dragoni 10 Martie 2025, 13:21 Evaluare finalizată 0
Ghenea Radu (McMeat) Dragoni 10 Martie 2025, 13:16 Evaluare finalizată 80
Ghenea Radu (McMeat) Dragoni 10 Martie 2025, 13:15 Evaluare finalizată 48
Ghenea Radu (McMeat) Dragoni 10 Martie 2025, 13:15 Evaluare finalizată E.C
Nicula Rebeca (RebecaN) Dragoni 10 Martie 2025, 11:54 Evaluare finalizată 100
Mario Bascan (PregatireAdmitere) Dragoni 09 Martie 2025, 22:45 Evaluare finalizată 20
Mario Bascan (PregatireAdmitere) Dragoni 09 Martie 2025, 22:44 Evaluare finalizată 14
Mario Bascan (PregatireAdmitere) Dragoni 09 Martie 2025, 22:41 Evaluare finalizată 14
Nistor Dora Valentina (nistor_dora_valentina) Dragoni 09 Martie 2025, 16:37 Evaluare finalizată 100
Moga Riana (Riana_m) Dragoni 09 Martie 2025, 14:55 Evaluare finalizată 100
Dumitru Mihai Cosmin (dumitru_cosmin) Dragoni 08 Martie 2025, 20:59 Evaluare finalizată 20
Du-te sus!