Lista de probleme 221

În regatul Ofni este Ajunul Crăciunului. Maleficul vrăjitor Irum din regatul vecin Akizif a aruncat un blestem asupra a k orașe din regatul Ofni, orașe care pot fi vizualizate ca matrici cu ni linii și mi coloane. Acest blestem constă în grinchificarea persoanelor din aceste orașe. Blestemul funcționează în felul următor. Irum alege din fiecare oraș mai multe case (pătrățele unitate ale matricei oraș) și le infectează. După ce termină de infectat casele de pornire, blestemul infectează oricare casă cu cel puțin doi vecini pe linie sau coloană. Cum blestemul se mișcă foarte rapid, transformările se petrec instantaneu. Pentru că era bătrân și obosit, Irum a făcut o greșeală, astfel că dacă blestemul nu va putea infecta întregul oraș, acesta se destramă și nu va avea efect. Dacă toate casele din oraș vor fi afectate, toți locuitorii orașului vor deveni grinchi.

Pentru a salva Crăciunul, bunul vrăjitor Picm trebuie să găsească o vrajă pentru a preschimba locuitorii grinchificați ai orașului înapoi cum erau. Cu ajutorul unui spion, Picm a aflat câte orașe sunt infectate, dimensiunile acestora, precum și câte și care au fost celule infectate inițial de Irum. Picm știe că vraja se află în cartea lui magică, Pbofni, la pagina numărul P unde P este suma oki*ini*mi%97 și oki este 1 dacă orașul a fost infectat și 0 în cazul contrar. Cum în Ofni nu s-au inventat încă calculatoarele și apusul e aproape, Picm, bun algoritmician de altfel, vă cere ajutorul pentru a afla numărul paginii și a salva Crăciunul de pandemia de grinchi.

Problema are două cerințe.
Pentru c = 1, se cere determinarea numărului de orașe grinchificate.
Pentru c = 2, se cere numărul paginii P la care se află vraja salvatoare.

Dându-se o mulțime de puncte și o mulțime de cercuri, pentru fiecare cerc să se stabilească câte puncte conține.

Se consideră un cerc. Pe cerc se desemnează N puncte oarecare. Dacă tragem linii între toate perechile de puncte, care este numărul maxim de bucăți în care poate fi descompus cercul? Să se răspundă la Q astfel de scenarii.

La ferma din Valea Vinului trăiesc n ciori care stau pe n sperietori (pe fiecare sperietoare poate sta o singură cioară). Fermierul Amadeus, supărat că acestea îi fură porumbul, decide să le alunge folosindu-și pușca, însă el ratează ciorile și nimerește un geam care se sparge. Astfel, ciorile se sperie, dar neștiind de unde vine glonțul, doar își schimbă sperietoarea pe care stă fiecare. În câte moduri distincte se pot așeza ciorile după tragerea glonțului, astfel încât niciuna să nu stea pe sperietoarea inițială?

Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. O celulă care conține caracterul 'A' reprezintă o alună, una care conține caracterul 'N' marchează o nucă, iar una care conține caracterul 'C' codifică o castană. Cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei inițiale poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

Se dau Q query-uri de forma n k. Pentru fiecare query să se afișeze numărul de partiții ale unei mulțimi cu n elemente în n/k submulțimi neordonate cu câte k elemente.

Se consideră o mulţime A cu n elemente (distincte).
Determinaţi numărul de posibilităţi de a scrie pe A ca reuniune de m mulţimi. Două moduri de scriere B1 U B2 U ... U Bm şi C1 U C2 U ... U Cm diferă dacă există cel puţin un indice i din mulțimea {1,2 … m} astfel încât mulţimile Bi şi Ci diferă prin cel puţin un element.

Se dă a, b și c, să se calculeze \({a}^{{b}^{c}}\) modulo \({10}^{9}+7\).

Considerăm o piramida xor unde fiecare valoare este egală cu xorul valorilor din stânga jos și dreapta jos. Dându-se cel mai de jos nivel, care este valoarea din vârf?

Săturat de ținut uși, Hodor s-a hotărât să devină ceasornicar. Maestrul ceasornicar îi spune lui Hodor că îl va învăța, doar dacă va trece un test. Maestrul îi da lui Hodor un sistem de coordonate xOy, și un ceas cu raza r, al cărui centru se află în centrul sistemului de coordonate O(0,0). Ceasul contine doar limba care indica orele, de lungime r. Inițial limba indică ora 12:00, cu vârful în punctul de coordonate A(0,r). Hodor trebuie să afle coordonatele vârfului limbii, după h ore și m minute.