#1643
Tromino
Bulbuka a primit de curând cadou un infinit de tromino-uri în formă de L
. După ce s-a jucat un timp cu ele, a ajuns la următoarea concluzie: poate să acopere cu tromino-uri o tablă de dimensiuni 2
K
x2
K
aproape complet (mai puţin un pătrăţel de dimensiune 1x1
). Deşteapta de Bulbuka are un algoritm pentru asta: porneşte de la o configuraţie 2
K-1
x2
K-1
, o copiază de încă 3
ori, apoi roteşte 2
dintre copii şi la sfârşit, adaugă un tromino la mijloc (v-a făcut un desen mai jos, ca să înţelegeţi mai bine, pentru K = 1
, 2
şi 3
). Pornind de la o configuraţie de acest tip, ea a observat că poate roti la 90
o
câte un tromino, în sensul acelor de ceasornic sau invers, doar dacă după rotire încape înapoi pe tablă. Folosind astfel de rotaţii, pătrăţelul lipsă poate ajunge pe orice poziţie de pe tablă.
Bulbuka vă pune acum Q
întrebări de tipul: care este numărul minim de rotaţii necesare pentru ca pătrăţelul lipsă să ajungă de la coordonatele (S
R
,S
C
)
la coordonatele (F
R
,F
C
)
?
Urmasii lui Moisil, 2016
#1642
Culegere
Pădurea magică din Povestea lui Negrimon este situată pe un teren dreptunghiular care poate fi privit ca o matrice cu N
linii, numerotate de la 1
la N
şi M
coloane, numerotate de la 1
la M
. Putem spune că terenul este împărţit în N * M
parcele pătrate de latură 1
. În pădure trăieşte şarpele Snake care, iniţial, este lung cât K
parcele şi lat cât una singură. La începutul poveştii şarpele se află pe prima linie, pe parcelele de la 1
la K
, capul fiind pe poziţia K
şi orientat spre est.
Snake se deplasează cu o parcelă pe secundă. Astfel, după prima secundă, şarpele se va afla tot pe linia 1
, deplasat cu o poziţie spre dreapta, mai exact capul va fi în parcela K + 1
. Deplasarea se face simultan cu întreg corpul.
În pădure au loc E
evenimente ce pot fi de tipurile următoare:
st
pe linia x
şi coloana y
, care va dispărea la secunda en
, dacă nu este mâncat până atunci de şarpe. Snake înghite mărul când capul său ajunge în parcela care îl conţine. Mărul dispare, desigur, iar corpul şarpelui creşte instantaneu cu o unitate care îi va fi adăugată la coadă şi va ocupa aceeaşi parcelă pe care s-a aflat coada (ultima porţiune din corp) la secunda anterioară înghiţirii mărului.st
pe linia x
şi coloana y
, care va dispărea la secunda en
şi care are valoarea v
. Când capul şarpelui ajunge în parcela schimbătorului, direcţia ulterioară de deplasare va fi dată de valoarea v ∈ {1, 2, 3, 4}
cu semnificaţia: 1
Nord (sus); 2
Est (dreapta); 3
Sud (jos); 4
Vest (stânga).Schimbătorul funcţionează astfel: de exemplu, dacă Snake se deplasează spre Est şi la o anumită secundă capul acestuia ajunge într-o parcelă unde se află un schimbător cu valoarea 1
, la următoarea secundă capul se va afla în parcela situată deasupra schimbătorului şi în parcela schimbătorului se află prima porţiune din corpul şarpelui.
Schimbătorul dispare exact în secunda en
iar până atunci rămâne în matrice indiferent de câte ori Snake trece prin parcela acestuia. Schimbătorul va acţiona doar când capul lui Snake ajunge în parcela lui şi nu va exista nicio situaţie în care să se schimbe direcţia în sens opus celei din care vine. De exemplu, dacă direcţia lui Snake este spre Est, nu va întâlni un schimbător cu valoarea 4
, care l-ar întoarce spre Vest.
În fiecare secundă s
, evenimentele se petrec în acestă ordine: dispar obiectele programate să dispară în secunda s
, apar obiectele ce trebuie să apară în secunda s
, Snake se deplasează cu o parcelă. Dacă printr-o combinaţie nefericită de mişcări, Snake se loveşte de propriul corp, el se blochează şi aşteptă serviciul de asistenţă a pădurii.
Deoarece Snake se află într-o pădure magică, deplasarea lui respectă reguli speciale: când capul este pe ultima coloană din matrice şi se mişcă spre Est, el reapare pe aceeaşi linie, dar pe prima coloană, trăgând corpul simultan. Analog şi pentru prima coloană, când se deplasează spre Vest, capul reapare pe aceeaşi linie dar pe ultima coloană. Dacă şarpele se află pe prima linie şi se deplasează spre Nord, mişcarea va continua pe ultima linie şi aceeaşi coloană din matrice. Analog pentru ultima linie, când Snake se deplasează spre Sud, capul reapare pe prima linie şi aceeaşi
coloană. Aceste mişcări au loc doar dacă Snake nu se blochează în propriul corp.
Povestea se termină în secunda în care apare oricare dintre situaţiile: Snake se loveşte de propriul corp, caz în care el rămâne BLOCAT; toate cele E
evenimente s-au produs şi nu mai există niciun obiect în matrice pentru că toate au
dispărut, caz în care rămâne un şarpe LIBER.
Cerința: În funcţie de finalul poveştii, afişaţi starea lui Snake şi harta pădurii în secunda respectivă. Pe hartă trebuie să fie marcate parcelele ocupate de corpul lui Snake, inclusiv capul.
Urmasii lui Moisil, 2016
#1645
Fibocel
Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1
din reprezentarea binară a numărului este un număr Fibonacci.
Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.
Să se raspundă la Q
întrebări de forma: Câte numere fibocel există în intervalul închis [A, B]
?
Urmasii lui Moisil, 2016
#1648
Diez
Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N
, alcătuit din litere mici ale alfabetului englez, se efectuează M
operaţii de următoarele tipuri:
x
, pe poziţia p
, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p
. Dacă valoarea p
este egală cu lungimea şirului, x
este alipit la finalul şirului.1
dacă secvenţa de litere care începe la poziţia q1
şi are lungimea lg
coincide literă cu literă, cu secvenţa care începe la poziţia q2
şi are aceeaşi lungime lg
şi se răspunde cu 0
în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.Fiind dat un şir de N
litere mici şi o listă de M
operaţii, să se afişeze răspunsurile la operaţiile de tip 2
, respectând ordinea din succesiunea de operaţii date.
Urmasii lui Moisil, 2016
#1644
Bilute1
X şi Y se joacă cu N
biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N
biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.
Dându-se cele N
valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013
.
Urmasii lui Moisil, 2016
#1646
Crescator
Aurel a învăţat la matematică despre şiruri de numere. Fiind curios din fire, el ar vrea acum să ştie câte şiruri crescătoare de numere naturale nenule cu suma elementelor mai mică sau egală cu S
există.
Ajutaţi-l pe Aurel să afle câte astfel de şiruri există.
Urmasii lui Moisil, 2016