Lista de probleme 444

Filtrare

Dificultate

Operații intrare/ieșire

#2544 materom

Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.

#2534 Bogdan

Bogdan și Ionuț au fost prieteni încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a
rezolva problema împreuna.

#2539 flori4

Compania lui Jimmy are n plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin n - 1 drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația x la plantația y , pentru fiecare 1 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri. Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

Olimpiada internațională pe Echipe, 2018

#2540 optiuni

Michael își petrece vacanța de vară la bunici, în Delta Dunării. În prima zi, se duce la pescuit cu tatăl său în locul în care acesta se ducea în copilărie. Michael își dă seama că traseul ales nu este singura opțiune de a parcurge distanța de la casa bunicilor până la locul unde pescuiesc, așa că, odată ce vizitează întreaga regiune împreună cu bunicul său, se întreabă în câte moduri distincte poate parcurge distanța de la casa bunicilor la locul unde pescuiesc. Regiunea pe care Michael o cunoaște are formă dreptunghiulară, cu rânduri numerotate de la 1 la L și coloane numerotate de la 1 la C. Valorile de 1 reprezintă zone de uscat și valorile de 0 reprezintă zone acoperite de apă. Michael poate merge doar pe uscat, cu următoarea restricție: din zona de coordonate (i, j) se poate duce doar în una din zonele (i – 1, j + 1), (i, j + 1), (i + 1, j + 1) – bineînțeles, doar dacă acestea reprezintă zone de uscat și Michael nu părăsește regiunea. Fiind un băiat inteligent, când Michael vizitează împrejurimile cu bunicul său, își dă seama de următorul lucru: coloanele din matricea care codifică regiunea se repetă identic din K în K. Coloanele 2, K + 2, 2 * K + 2, … sunt identice, coloanele K – 1, K + (K - 1), 2 * K + (K - 1), … sunt identice. Două coloane c1 și c2 sunt identice dacă elementul de pe poziția (i, c1) este egal cu elementul de pe poziția (i, c2), oricare ar fi i de la 1 la L. Știind coordonatele locului unde se află casa bunicilor și coordonatele locului de pescuit pe care tatăl lui Michael i l-a arătat acestuia, să se determine numărul de moduri de a parcurge distanța dintre ele. Două drumuri sunt considerate distincte dacă, scriind secvența rândurilor vizitate (în ordine crescătoare a coloanelor), ele diferă prin cel puțin o poziție.

Olimpiada internațională pe Echipe, 2018

#2536 kst

Un KST este un arbore de căutare care are K valori în fiecare nod și fiecare nod are K+1 fii. De exemplu, pentru k=1, un KST devine un arbore de căutare binar. Valorile din fiecare nod sunt în ordine crescătoare. Notăm cu v[i], a i-a valoare dintr-un nod. Arborele are următoarea proprietate: pentru fiecare nod, primul său fiu va avea valori mai mici decât v[1], al doilea va avea valori aparținând intervalului (v[1], v[2]), al treilea va avea valori din intervalul (v[2], v[3]), …, penultimul fiu din intervalul (v[k-1], v[k]), ultimul va avea valori mai mari decât v[k]. Un nod nu poate avea fii dacă nu conține K valori. Frunzele pot avea și mai puțin de K valori. Se dă N – numărul de elemente și K, trebuie să se afle câți arbori care respectă cerința există.

Olimpiada internațională pe Echipe, 2018

Se dă un număr N și un număr S. Să se determine câte numere de N cifre au suma cifrelor S.

Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se afișeze cel mai lung subșir comun al lor.

Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se determine lungimea celui mai lung subșir comun.

Ionuț tocmai a terminat liceul și susține examenul de admitere la facultate. Știind că s-a pregătit foarte bine pentru examen, el dorește să își anunțe reușita după examen printr-o postare pe Facebook.
Ionuț cunoaște n utilizatori reprezentați de numerele de la 1 la n, între care există m relații de prietenie de forma i j, unde i și j sunt utilizatori, iar n și m sunt numere naturale nenule. Un utilizator nu poate fi prieten cu el însuși, iar o relație de prietenie între doi utilizatori ne spune că fiecare dintre ei este prieten cu celălalt.

Întrucât dorește ca postarea lui să fie cât mai răspândită, Ionuț vrea să afle care sunt utilizatorii cei mai bine conectați din mulțimea sa de cunoscuți, pentru ca eventual să le ceară prietenia. Pentru aceasta, Ionuț trebuie să găsească cea mai mare submulțime de utilizatori cunoscuți, în care fiecare utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime, unde k este un număr natural nenul.

Ajutați-l pe Ionuț să se determine și să se afișeze, printr-o soluție de complexitate timp cât mai bună, în funcție de datele de intrare, membrii celei mai mari submulțimi de utilizatori, cu proprietatea că fiecare utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime.

Durotan, căpetenia clanului Frostwolf, face o ultima încercare în a cuceri clanurile rivale (Orcish Horde). Conform ierarhiei Orcish, căpeteniile de clan sunt denumite warchief, în timp ce liderii triburilor sunt denumiți șamani. Triburile din care fac parte căpeteniile sunt triburi dominante, iar triburile conduse de șamani sunt triburi vasale.
Pe planetă există N triburi, numerotate de la 1 la N. Șamanul unui trib are anumite abilități de luptă. Căpetenia unui clan este șamanul tribului său. Abilitățile de luptă cunoscute de șamani sunt numerotate de la 1 la M.
De-a lungul timpului între triburile aceluiași clan s-au stabilit relații de vasalitate. Dacă tribul 1 este trib dominant al tribului vasal 2, iar tribul 2 are ca vasal tribul 3, vom spune că tribul 3 se află în zona de influență a triburilor 1 și 2. Triburile 1,2,3 alcătuiesc un clan.
Puterea unei căpetenii depinde de numărul triburilor ce alcătuiesc clanul, precum și de abilitățile de luptă învățate. Căpetenia unui clan are anumite abilități de luptă, dar poate să-și însușească (învețe) și abilități de luptă unice de la șamanii triburilor clanului aflate în zona sa de influență. Prin abilități de luptă unice înțelegem abilități cunoscute doar de un singur șaman din totalitatea triburilor clanului.
Exemplu: Considerăm un clan ce are 4 triburi: 1(3,6), 2(1,2,4), 3(3,5,6), 4(1,3,4). Căpetenia clanului se află la tribul 1, el fiind considerat și șamanul tribului. Acesta are abilitățile 3,6. Șamanul tribului 2 are abilitățile 1,2,4, șamanul tribului 3 are abilitățile 3,5,6, șamanul tribului 4 are abilitățile 1,3,4. Presupunem că tribul 4 este vasal tribului 2, iar triburile 2 și 3 sunt vasale tribului 1. Căpetenia, la abilitățile 3,6 avute deja, poate să dobândească abilitățile unice 2, 5 de la șamanii triburilor clanului.
Durotan invocă vechiul cod al onoarei Mak’gora, ce implică provocarea la duel a căpeteniilor de clan. Câștigă duelul dacă are un număr strict mai mare de triburi în zona sa de influență, iar la număr egal de triburi, un număr strict mai mare de abilități diferite. Triburile clanului învins se vor alătura clanului său, Durotan însușindu-și (adăugându-și) abilitățile unice ale învinsului.

Cerința

Fiind cunoscute pentru cele N triburi abilitățile fiecărui șaman, relațiile de vasalitate între triburi, numărul de ordine al unui trib al clanului Frostwolf, să se determine:

  • numărul total de clanuri
  • numărul de triburi din clanul Frostwolf înainte de duel
  • numărul maxim de triburi pe care Duroton le poate avea după invocarea codului Mak’gora.

Date de intrare

Fișierul de intrare warcraft.in conține pe prima linie trei numere natural N M X ce reprezintă N – numărul de triburi, M – numărul de abilități, X – numărul de ordine al unui trib ce face parte din clanul lui Durotan.
Pe următoarele N linii descrierea fiecărui trib: x y k a1 a2 … ak, unde: tribul x este vasal tribului y. Șamanul tribului x are k abilități de luptă, a1, a2,…,ak, valori strict crescătoare.

Date de ieșire

Fișierul de ieșire warcraft.out va conține trei numere naturale n1, n2, n3, scrise fiecare pe câte o linie, unde:

  • n1 reprezintă total numărul de clanuri
  • n2 numărul de triburi ai clanului Frostwolf înainte de duel
  • n3 numărul maxim de triburi ai clanului Frostwolf după ce Durotan invocă codul Mak’gora.

Restricții și precizări

  • 2 ≤ N ≤ 1000
  • 1 ≤ X ≤ N
  • 1 ≤ M ≤ 500
  • 1 ≤ k ≤ M
  • Numărul de clanuri ≤ 500
  • Dacă un trib nu este vasal altui trib, atunci y=0
  • Durotan provoacă la duel doar căpeteniile de trib. În duel sunt folosite abilitățile cunoscute sau dobândite de căpetenie
  • Pentru determinarea corectă a lui n1 se acordă 20% din punctaj/test. Pentru determinarea corectă a lui n2 se acordă 20% din punctaj/test. Pentru determinarea corectă a lui n3 se acordă 60% din punctaj/test.