Lista de probleme 208

Filtrare

#3249 subimp3

Se citește un număr natural n. Calculați și afișați câte din submulțimile mulțimii {1, 2, ..., n} sunt formate dintr-un număr impar de elemente.

#3363 fmat

Fie o matrice (care are M linii si N coloane) colorată folosind C culori. Aceasta este K-frumoasă doar dacă are exact K coloane omogene. O coloană omogenă este o coloană care are toate elementele colorate la fel.

#3853 Clasa0

Astăzi în clasa 0 profesoara a numit Q copii și le-a dat 3 numere, a, b și c, copiii trebuiau să spună care este rezultatul calculului \({a}^{{C}_{b}^{c}}\), adică \({a}^{ \frac{b! }{{c! *(b-c)! }}}\), modulo \(10^9+7\). Copiii nu au știut să răspundă la întrebări așa că voi trebuie acuma să le spuneți rezultatul.

#1676 Elmer

În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze rațe în orașul său preferat, Craiova. Se știe că există N rațe reprezentate prin puncte în planul de coordonate xOy, având coordonatele (x,y) și M ziduri sub forma unor segmente verticale având un capăt pe axa Ox și o anumită înălţime fiecare.

Vânătorul Elmer dorește să împuște cât mai multe rațe. El poate fi poziționat în orice punct de abscisă număr natural nenul, pe axa Ox. O rață poate fi ochită de vânător dacă zidul nu blochează glonțul vânătorului, adică segmentul imaginar delimitat de rață și de vânător nu se intersectează cu nici un zid.

Să se afle numărul maxim de rațe care pot fi ochite de vânătorul Elmer.

ONI 2016, clasa a X-a

#1675 Calc

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cunoscând N, să se determine:

  1. Numărul de zile modulo 1000000007 în care se desfășoară concursul.
  2. Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.

ONI 2016, clasa a X-a

#1677 Tort

Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la 1 la N pentru linii și de la 1 la M pentru coloane. Tortul este format din bucăți de dimensiune 1x1, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel mai mare pătrat care conține bucăți acoperite cu același tip de glazură. În cazul în care există mai multe astfel de felii, NN o alege pe cea care are colțul din dreapta jos situat pe linia cu indicele cel mai mic. Dacă și în acest caz există mai multe posibilități, el o va alege pe cea cu colțul din dreapta jos situat în coloana cu indicele cel mai mic.

Precizați latura și coordonatele colțului din dreapta jos pentru fiecare felie de tort primită, în ordinea specificată mai sus.

ONI 2016, clasa a X-a

#1689 MoveDel

Se consideră două șiruri de caractere A și B, ambele șiruri având același număr de caractere.

Asupra șirurilor se aplică următorul algoritm:

  • șirul A se permută circular cu ki poziții spre stânga
  • din cele două șiruri se elimină caracterele care coincid din punct de vedere al poziției și valorilor

Algoritmul se oprește când fie ambele șiruri devin vide, fie șirurile nu mai au caractere comune. Valoarea ki pentru fiecare pas i reprezintă al i-lea număr prim din mulțimea numerelor prime.

Dându-se N și M, să se genereze șirurile A și B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două șiruri să fie M.

ONI 2016, clasa a X-a

#1703 Parchet

Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte 1 m2 şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând X m2 de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni N x M, fiecare element al tabloului reprezentând exact 1 m2. Pereţii sunt reprezentaţi prin caracterul ‘P’ iar suprafeţele camerelor prin caracterul ‘S’ (spaţiu). În planul din figura următoare este descrisă o locuinţă cu 5 camere acestea având respectiv, suprafeţele de 10, 2, 1, 3, 5 m2.

PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.

Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Fiind date N, M, X şi planul locuinţei să se determine:

  1. numărul C de camere pe care a reuşit să le acopere Gigel şi numărul R de m2 de parchet care îi rămân, procedând aşa cum a hotărât iniţial;
  2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet.

ONI 2016, clasa a VII-a

#1765 Cutie

După ce au vizitat toate obiectivele turistice din municipiul Iaşi, Ioana şi Maria au inventat un joc.

Ele au la dispoziţie un număr de n cutii aranjate în linie dreaptă, numerotate în ordine de la 1 la n, şi un număr de m bile ce pot fi aşezate în unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel că bilele dispar dacă sunt puse în acele cutii.

O mutare constă în alegerea unei bile şi poziţionarea ei în una din cutiile învecinate (precedenta sau următoarea ). Bilele pot fi mutate după următoarea regulă: când o bilă a fost mutată pentru prima dată într-o anumită direcţie, atunci bila îşi păstrează direcţia de deplasare la următoarele mutări (de exemplu, dacă o bilă a fost mutată pentru prima dată spre stânga atunci orice mutări ulterioare ale acestei bile se pot face doar spre stânga).

Jocul se termină atunci când nici un jucător nu mai poate face nici o mutare. Pierde primul jucător care nu mai poate face nici o mutare. Fetele joacă un număr de T astfel de jocuri. Ştiind că Ioana este prima care face o mutare, iar apoi fetele mută alternativ, se cere să se stabilească pentru fiecare din cele T jocuri dacă ea are sau nu o strategie sigură de câştig.

ONI 2012, Clasa a X-a

Un număr natural nenul n se numește cumpănit dacă în descompunerea sa în factori primi suma bazelor este egală cu suma exponenților. Să se scrie un program care citește două numere naturale nenule a și b și determină toate numerele cumpănite din intervalul închis [a, b].

ONI 2013, Clasa a X-a