Lista de probleme 878

Filtrare

#1354 varf

Se consideră un şir a cu n numere naturale distincte: a1, a2,..., an.

Să se genereze în ordine lexicografică toate subşirurile vârf ale şirului a, de lungime k≥3.

Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găsește pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în așa fel încât acesta să ajungă la o variantă din dicționar:
– poate șterge o literă;
– poate insera o literă;
– poate schimba o literă în altă literă.
Totuși, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K schimbări în cuvântul greșit pentru a-l aduce la o formă corectă (existentă în dicționar).
Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.

#2413 reteta1

Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:
1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește.
Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.
Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.

#2408 divtrei

Se consideră numerele naturale N şi K şi cifrele nenule distincte c[1], c[2], …, c[N]. Să se determine câte numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.

#2226 Chimic

Cercetătorii bistrițeni vor să creeze cea mai puternica soluţie stabilă, în limita elementelor disponibile. Ei deţin N elemente chimice reprezentate de numerele 1,2,3...N, cu puteri cunoscute. Puterea unei soluții este dată de suma puterilor elementelor. Nu pot să amestece orice elemente, pentru că soluţia ar deveni instabilă. Ei pot să combine elementele după anumite reguli:

1) Primul element al soluţiei poate fi oricare.
2) Dacă ultimul element al soluţiei curente este i, atunci următorul element trebuie să aparţină intervalului [si,di], pentru că altfel soluţia ar deveni instabilă.

Tu fiind noul angajat trebuie să găseşti puterea cea mai mare unei soluţii.

#2396 arbsum

Se consideră un arbore cu n noduri numerotate de la 1 la n. Se știe că rădăcina arborelui este nodul 1. Fiecare nod i are asociat un număr natural nenul v[i]. Să se determine suma maximă care se poate obține alegând în mod convenabil o submulțime de noduri, astfel încât dacă este ales un nod i, în submulțime nu poate fi nici nodul tată al lui i, nici eventualii fii ai lui i.

#2387 mosia1

Păcală a primit, aşa cum era învoiala, un petec de teren de pe moşia boierului. Terenul este împrejmuit complet cu segmente drepte de gard ce se sprijină la ambele capete de câte un par zdravăn. La o nouă prinsoare, Păcală iese iar in câştig şi primeşte dreptul să strămute nişte pari, unul câte unul, cum i-o fi voia, astfel încât să-şi extindă suprafaţa de teren. Dar învoiala prevede că fiecare par poate fi mutat în orice direcţie, dar nu pe o distanţă mai mare decât o valoare dată (scrisă pe fiecare par) şi fiecare segment de gard, fiind cam şubred, poate fi rotit şi prelungit de la un singur capăt, celălalt rămânând nemişcat.

Cunoscând poziţiile iniţiale ale parilor şi valoarea înscrisă pe fiecare par, se cere suprafaţa maximă cu care poate să-şi extindă Păcală proprietatea. Se ştie că parii sunt daţi într-o ordine oarecare, poziţiile lor iniţiale sunt date prin numere întregi de cel mult 3 cifre, distanțele pe care fiecare par poate fi deplasat sunt numere naturale strict pozitive şi figura formată de terenul iniţial este un poligon neconcav.

Se organizează o petrecere la care participă N băieți (numerotați de la 1 la N) și N fete (numerotate de la 1 la N). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele și băieții formează o configurație de dans, adică N perechi, după una din următoarele reguli:
1. băiatul i dansează cu fata i;
2. băiatul i dansează cu fata j și atunci obligatoriu băiatul j dansează cu fata i.
De exemplu, pentru N = 7, două configurații de dans posibile sunt:
(1, 1) (2, 2) (3, 7)(4, 5) (5, 4) (6, 6) (7, 3)
(1, 1) (2, 2) (3, 3)(4, 5) (5, 4) (6, 6) (7, 7)
Prin perechea (i, j) s-a notat faptul că băiatul i dansează cu fata j. Două configurații sunt distincte dacă ele diferă prin cel puțin o pereche. Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.

#2355 card

În orașul Imios se află n galerii ce au locații interesante de vizitat (muzee, expoziții, castele), notate de la 1 la n. O galerie conține m locații, notate de la 1 la m. Fiecare locație are atribuit un număr de puncte, unic ca valoare. Orașul are multe birouri de informare turistică, de unde turiștii pot cumpăra un card de o zi pentru vizitarea locațiilor. Pe fiecare card se înregistrează punctul de plecare, notat prin 2 numere: numărul galeriei și cel al locației, din care se pot vizita cel mult k locații din oraș, diferite de punctul de plecare. Cardul are înregistrat un număr de puncte, ce vor fi utilizate în locațiile vizitate. Alegând o locație ce are x puncte, turistul poate selecta 4 categorii de vizitare, ce modifică punctele de pe card astfel:

  • categoria rapidă: numărul de puncte de pe card se reduce cu dublul lui x
  • categoria extinsă: numărul de puncte de pe card se reduce cu x/2 puncte
  • categoria medie: la numărul de puncte de pe card se adaugă x puncte
  • categoria clasică: din numărul de puncte de pe card se scad x puncte.

Alexandru a cumpărat un card și dorește să viziteze cât mai puține locații și să utilizeze toate punctele de pe card. Împreună cu cardul, a primit o hartă electronică a locațiilor din oraș, codificată printr-o matrice h, având n linii și m coloane, pe care este înregistrat numărul de puncte al fiecărei locații. Pe hartă, punctul de plecare, înregistrat pe card, conține numărul de puncte disponibile pe card pentru vizitare. A fost informat că după vizitarea unei locații, se poate deplasa numai într-o locație vecină cu aceasta în cele 8 direcții (N, NE, E, SE, S, SV, V, NV). Fiecare locație poate fi vizitată o singură dată, pe baza cardului. Alexandru a decis că dacă are mai multe variante posibile de vizitare, din care să aleagă, va opta pentru acea variantă în care ultima locație are cel mai mic număr de puncte. Dacă există mai multe variante de vizitare care au același număr minim de puncte pentru ultima locație, va opta pentru varianta în care prima locație are cel mai mic număr de puncte. Două variante de vizitare diferă prin: locațiile lor, ordinea locațiilor vizitate și categorii de vizitare alese pentru locații.

Să se scrie un program care obține numărul de variante posibile de vizitare a unor locații din oraș, care conțin cât mai puține locații vizitate din punctul de plecare, ce asigură utilizarea tuturor punctelor de pe card și lista punctelor din locațiile vizitate, în ordinea vizitării lor, pentru varianta pe care Alexandru o alege.

Olimpiada Municipala de Informatica, Iasi, 2018

În Iași a fost constituit grupul de sprijin “Împreună pentru A8”. Printre manifestările acestui grup este și o grevă în care trebuie să fie blocată o singură șosea din județ. Autoritățile județene vor să autorizeze aceste manifestări însă doar pe anumite șosele, astfel încât traficul să rămână posibil între oricare două localități. Cunoscând N numărul de localități din județ, acestea fiind codificate prin numere naturale din mulțimea 1, 2, …, N și M numărul de șosele care leagă direct câte două localități ale județului, să se afle K numărul de șosele pe care nu trebuie aprobate manifestările și care sunt aceste șosele. Fiecare șosea este determinată în mod unic de două numere naturale X și Y reprezentând cele două localități legate direct de șosea.

Olimpiada Municipala de Informatica, Iasi, 2018