Lista de probleme 501

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#2929 origami

Tocmai ai primit o foaie dreptunghiulară (foarte mare) de dimensiuni N⨯M, împărțită în pătrățele de 1⨯1. Fiecare pătrățel este colorat pe ambele părți cu una din cele 26 de culori existente în univers, identificată pentru simplitate printr-un caracter mic al alfabetului englez.

Neavând ceva mai bun de făcut în timpul probei de baraj, te-ai gândit să înveți origami. Totuși, cum nu oricine este maestru în origami și acest sport necesită experiență și viziune artistică (lucruri pe care, bineînțeles, le vei dobândi cu timpul), ai hotărât că, pentru început, este mai interesant să împăturești foaia într-un mod clar stabilit.

Mai exact, la fiecare pas vei alege o dreaptă (orizontală sau verticală) situată între două linii (respectiv coloane) consecutive și vei “îndoi” jumătatea mai mică peste cea mare doar dacă culorile se vor suprapune perfect. Un exemplu de o astfel de îndoire validă este prezentat mai jos:

După orice îndoire vei obține un nou model (bineînțeles, de dimensiuni mai mici). În cazul în care cele două jumătăți sunt egale, ambele variante de îndoire sunt valide. Maestru în algoritmi și structuri de date eficiente, observi imediat că, după orice îndoitură, modelul rezultat va constitui o submatrice din modelul inițial. Natural, îți vine următoarea
întrebare:

“Câte submatrice distincte pot obține, îndoind foaia de un număr arbitrar de ori (sau deloc), fără a roti foaia sau a o întoarce pe cealaltă parte?”

Formal, două submatrice se consideră distincte, dacă măcar unul din cele patru colțuri diferă de la o submatrice la alta (ca indici).

ONI 2017, Baraj

Se dă n și un sir cu n elemente, numere naturale. Folosind metoda HeapSort, să se sorteze crescător șirul și să se afișeze elementele sale, separate prin câte un spațiu.

Cătălin lucrează la o firmă de transport de marfă. El se ocupă de planificarea traseelor pe care circulă camioanele. Există N trasee pe care pot merge camioanele, pe fiecare traseu poate circula cel mult un camion, iar acest camion nu poate depăși o limită de greutate ai. Firma deţine M camioane, fiecare camion poate circula pe maxim un traseu şi are o greutate bi. Ajutați-l pe Cătălin să planifice camioanele pe trasee în așa fel încât să poată circula cât mai multe camioane. Determinați numărul maxim de camioane care pot circula în același timp pe trasee și afișați o modalitate de a distribui camioanele pe trasee pentru a obține acest maxim.

Olimpiada Municipală Iași, clasele XI-XII

Primăria din Iași a hotărât să modernizeze șoselele din localitate. O șosea este o porțiune de drum care unește două intersecții. Firma constructoare a făcut un studiu pentru a determina costurile pentru fiecare șosea. Fondurile sunt limitate, astfel că în prima fază vor fi modernizate doar drumurile din apropierea Palas-ului, care se află la intersecția cu numărul 1. Mai precis: orice șosea modernizată trebuie sa fie cel puțin la fel de aproape de Palas ca orice șosea ce nu va fi modernizată.

Lungimea drumului dintre două intersecții a și b este numărul cel mai mic de intersecții ce trebuie parcurse pentru a ajunge de la a la b. Șoseaua (a, b) este mai aproape de Palas față de șoseaua (c, d) dacă lungimea drumului de la Palas până la cea mai apropiată intersecție dintre a și b este mai mică decât până la cea mai apropiată intersecție dintre c și d. Dacă lungimile drumurilor până la cele mai apropiate intersecții sunt egale, se compară lungimile drumurilor până la celelalte două intersecții. De exemplu dacă pentru șoselele (4, 7) și (3, 5) avem distanțele de la Palas până la intersecțiile: 3, 4, 5, 7 egale cu: 10, 10, 10, 11 în această ordine, atunci (3, 5) e mai aproape de Palas față de (4, 7) deoarece distanțele minime sunt ambele egale cu 10 dar distanța până la intersecția 3 este tot 10, mai mică față de distanța până la intersecția 7 care este 11. Dacă nu există cale de acces de la Palas la o intersecție a atunci șoselele legate de a nu vor fi modernizate.

Cunoscând: N – numărul de intersecții din oraș codificate prin numere naturale din mulțimea 1..N, M – numărul de șosele și șoselele împreună cu costul de modernizare, și F – fondurile de care dispune primăria, să se afle K – numărul maxim de șosele care pot fi modernizate.

Olimpiada Municipală Iași, clasele XI-XII

#2882 No_pals

Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.

Se consideră un graf neorientat conex cu n noduri și n muchii. Să se determine numărul arborilor parțiali ai grafului.

#2884 Rucsac2

Într-un magazin intergalactic sunt n tipuri de obiecte, o infinitate din fiecare; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

#2785 galeti

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort. Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

#2862 stiva2

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

Se dă un șir de n cifre. Șirul se împarte în secvențe disjuncte de cifre, fiecare secvență având lungimea cel mult 6. Cu fiecare secvență extrasă se formează numărul corespunzător și apoi se adună doar numerele prime obținute. De exemplu, dacă șirul de cifre este 37237, se pot extrage secvențele disjuncte 3, 72, 37, iar suma numerelor prime este 3 + 37 = 40. O altă modalitate este 3, 7237 care are suma 7240 (deoarece numărul 7237 este prim). Să se determine suma maximă care se poate obține împărțind șirul în secvențe disjuncte de lungimi cel mult 6 și adunând apoi numai numerele prime.