Nivelul concursului: Local
Grupe
Clasa a V-a Clasa a VI-a Clasele VII-VIII Clasa a IX-a Clasa a X-a Clasele XI-XII#1913
mr
Rică se joacă în fiecare seară The MazeRunnerVladVersion, joc pe care îl vom numi pentru simplitatea problemei MR. Jocul constă în găsirea unei căi de scăpare dintr-un labirint care conține:
p1(x1, y1)
și p2(x2, y2)
se face într-un minut, dacă se doreşte acest lucru;Rică pleacă din colțul stânga-sus al labirintului și doreşte să ajungă în colțul dreapta-jos.
El știe că are o teză în ziua următoare, așa că vă cere ajutorul vouă, programatorilor, și vă roagă să aflați timpul minim în care poate să ajungă din colțul stânga-sus în colțul dreapta-jos al labirintului.
Moisil++, 2016
#1938
Catalin si armata
Cătălin este cel mai important general din armata țării sale, care are N
membri (soldați și ofițeri), numerotați de la 1
la N
(Cătălin are numărul 1
). Un ofițer este un soldat care are în subordinea sa alți soldaţi. Conform ierarhiei militare, Cătălin și toți ceilalți ofițeri primesc inițial 3
subalterni (soldații cu numerele 2
, 3
şi 4
). Fiecare dintre cei trei, primește la rândul lui alți 3
subalterni, după următoarea regulă: ofițerul cu numărul x
primește subalternii 3 * x – 1
, 3 * x
, 3 * x + 1
(dacă aceștia există în armată).
S-a descoperit că în această armată există trădători. Mai exact, toți cei numerotați cu numere prime sunt dovediți trădători, iar Cătălin știe bine asta, asa că ia măsuri radicale: decide să îi elimine pe rând pe toți acești misei, începând chiar cu subalternul său cu numărul 2
. Dacă ofițerul cu numărul X
este eliminat, toți subalternii săi devin subalternii comandantului său. Eliminându-l pe 2
, subalternii acestuia devin subalternii comandantului lui 2
, adică ai lui Cătălin. După trista eliminare a lui 2
, Cătălin trece mai departe și elimină pe rând pe cei cu numerele 3
, 5
, 7
, 11
, 13
… Subalternii lui 3
, 5
, 7
devin subalternii lui 1
, cei ai lui 11
devin ai lui 4
și tot așa.
După măcel, Cătălin trebuie să răspundă la Q
întrebări ale împăratului care dorește să afle câți subalterni are un membru x
al armatei sale. Dacă x
a fost eliminat, Cătălin va transmite pentru acesta răspunsul -1
.
Moisil++, 2016
#1914
Rica
Rică a învățat la școală despre șiruri recurente și a primit ca temă să lucreze cu un anumit șir. Rică știe că primele elemente din acest șir sunt următoarele: 1,1,2,4,7,13,24,44,81,149,274,504
. Tema lui Rică este să găsească termenul de pe locul X
. Rică nu știa să zică… regula şirului nostru, de aceea el vă cere ajutorul.
Deduceți regula de formare a șirului și scrieți un program care să afișeze pentru un X
dat, elementul din șir de pe poziția X
.
Moisil++, 2016
#1917
Catalin si prietenii
Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).
Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.
Definim două tipuri de operații:
1 x y
– ce reprezintă faptul că x
se împrietenește cu y
.2 p
– Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p
. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.Moisil++, 2016
#1916
Catalin si greselile
Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N
greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i
, poate alege să corecteze o singură greșeală j
, cu proprietatea 1<j<i
şi i%j=0
. El știe că, dacă face această alegere poate să continue din greșeala j
, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.
Cătălin alege T
greșeli G[1] G[2] … G[T]
și dorește să știe, pentru fiecare G[i]
, numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.
Moisil++, 2016