| #816. [2016-11-20 - 18:23:58] Colorarea hartii folosind metoda Greedy. Fiind data o harta cu n tari, se cere o solutie de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari ce au frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata. Exemplu: colorare.in 6 alb verde galben rosu 1 2 1 3 1 4 1 5 1 6 2 3 2 5 2 6 3 4 3 5 4 5 5 6 colorare.out 1 alb 2 verde 3 galben 4 verde 5 rosu 6 galben | Rezolvare |
| #592. [2014-05-15 - 09:33:48] Se citesc 3 numere naturale S, n si e cu urmatoarele semnificatii: S este o suma de bani care trebuie platita folosind bancnote care au valori puterile lui e de la 1 la e la n. Se se afiseze modalitatea de plata folosind un numar minim de bancnote de tipurile precizate. Sa se afiseze la final numarul de bancnote folosite. Datele se vor citi din fisierul eur.in, iar rezultatele se vor afisa in fisierul eur.out. Exemplu: eur.in 444 5 2 eur.out 13 bancnote de valoarea 32 1 bancnote de valoarea 16 1 bancnote de valoarea 8 1 bancnote de valoarea 4 16 Explicatie: n=5, e=2 rezulta ca bancotele au valorile 1, 2, 4, 8, 16 si 32. | Rezolvare |
| #395. [2012-11-22 - 09:34:32] Problema comis-voiajorului (varianta 1) | Rezolvare |
| #394. [2012-11-22 - 08:28:07] Fiind data o tabla de sah de dimensiunea nxn si un cal în coltul stânga sus al acesteia, se cere sa se deplaseze calul pe tabla astfel încât sa treaca o singura data prin fiecare patrat al tablei. Solutia va fi afisata ca o matrice nxn în care sunt numerotate sariturile calului. Exemplu, pentru n=11 1 26 85 30 23 28 99 120 21 104 101 84 31 24 27 86 119 22 103 100 121 20 25 2 83 80 29 98 107 118 115 102 105 32 81 34 87 108 79 116 97 106 19 114 3 36 69 82 75 88 109 112 117 96 93 64 33 76 35 70 111 78 95 92 113 18 37 4 63 68 77 74 89 110 57 94 91 40 65 38 71 62 67 56 73 90 17 54 5 44 41 66 49 72 61 58 55 14 11 42 39 46 7 60 51 48 9 12 53 16 45 6 43 50 47 8 59 52 15 10 13 | Rezolvare |
| #393. [2012-11-21 - 10:07:15] Problema rucsacului (cazul continuu) O persoana are un rucsac cu care poate transporta o greutate maxima g. Persoana are la dispozitie n obiecte pentru care stie greutatea si castigul obtinut daca transporta obiectul. Fiecare obiect poate fi transportat integral sau taiat. Sa se precizeze ce obiecte alege persoana si in ce proportie le ia astfel incat castigul total sa fie maxim si sa nu se depaseasca greutatea maxima a rucsacului. Exemplu: g=3 n=3 obiectele(greutate,castig): 2 2 1 4 3 6 Solutie(greutate, castig, raport taiere): 1,4,1 3,6,0.6667 (al doilea obiect se ia in raport de 2/3) castig maxim=8 | Rezolvare |
| #392. [2012-11-21 - 08:38:04] Problema programarii spectacolelor Intr-o sala de spectacol trebuie planificate n spectacole intr-o zi. Pentru fiecare spectacol se cunosc ora de inceput si ora de terminare (numere intregi). Sa se planifice un numar maxim de spectacole astfel inct sa nu fie doua spectacole care sa se suprapuna. Exemplu: date.in 7 2 4 8 11 5 6 5 8 3 7 7 8 9 12 date.out: 2,4 5,6 7,8 9,12 | Rezolvare |