Lista de probleme 888

Două veverițe gemene au descoperit un depozit de alune care are o formă foarte ciudată. Mai precis, depozitul are forma unei matrice N x N cu N impar. Fiecare poziție din matrice este o cameră și în fiecare cameră se află câte o alună. Camerele sunt numerotate cu numărul de linie și numărul de coloană. Cunoscând N, să se răspundă la Q întrebări de forma: “Ce traseu a notat Chip pe poziția P?”

Prietenii lui RAU-Gigel vor să-i facă o surpriză de ziua lui! Pentru aceasta, ei trebuie să se întâlnească într-un singur loc pentru a se putea organiza mai eficient. Poți să-i ajuți cu cunoștințele tale informatice să rezolve această problemă?

RAU-Gigel se pregătește pentru admiterea la facultate. Curios din fire, el împrumută niște cursuri de la un prieten student, de unde află despre limbajele formale, gramatici, automate finite, expresii regulate și multe alte lucruri interesante. Găsește acolo și o problemă:

Se consideră un alfabet X format din N simboluri (diferite două câte două). Pe mulțimea X este definită o relație de ordine totală (să o numim lexicografică) astfel: orice două elemente a și b alegem din X (a diferit de b), avem fie a<b, fie b<a. Câte cuvinte se pot forma cu simboluri din alfabetul X astfel încât simbolurile prezente în cuvânt să fie în ordine strict crescătoare (de la stânga spre dreapta) și să nu existe în cuvânt două simboluri consecutive lexicografic?

Steve Stonecutter se află într-o lume formată din cuburi, iar fiecare cub aparține unui singur biom. Cuburile sunt dispuse într-o linie și sunt numerotate de la 1 la N. Se consideră că blocurile i și i + 1 sunt vecine între ele pentru toate valorile i de la 1 la N - 1. Putem reprezenta această lume ca și un șir de caractere S de lungime N format din litere mici ale alfabetului limbii engleze, numerotat de la 1 la N, unde al i-lea caracter reprezintă biomul din care face parte al i-lea cub. Aceste mișcări se pot realiza dacă și numai dacă poziția în care Steve vrea să se deplaseze există. Începând de la cubul 1, Steve dorește să ajungă la cubul N cu cost minim, așa că vă roagă pe voi să aflați care este acest cost.

ate, sora ei Mitzu s-a jucat cu şirul Piei şi acesta a fost pierdut, dar Pia în continuare are permutările obţinute la fiecare pas în urma apelării algoritmului. Ajutaţi-o pe Pia să descopere un posibil şir iniţial.

Se dă un arbore cu N noduri, numerotate de la 1 la N. Arborele este înrădăcinat în nodul 1. Vrem să facem o parcurgere a arborelui, pornind din rădăcină. Pentru fiecare nod, putem considera fiii acestuia în orice ordine dorim. Există două tipuri de cerințe, reprezentate printr-un număr c:

• Pentru C = 1, parcurgerea va fi de tip adâncime (DFS) pre-ordine.
• Pentru C = 2, parcurgerea arborelui va fi de tip lățime (BFS).

Care noduri din arbore pot să fie pe a K-a poziție în vreuna dintre posibilele parcurgeri?

Fie numerele întregi N, M și T. Calculați numărul de moduri de a construi o matrice cu N linii și M coloane folosind valori întregi aflate în intervalul închis [0, T], astfel încât fiecare linie și fiecare coloană a matricei să aibă elementele în progresie aritmetică cu rație strict pozitivă. Progresiile se consideră pentru secvența elementelor de pe linii ca fiind de la stânga la dreapta, iar pentru coloane ca fiind de sus în jos. De asemenea, fiecare linie și fiecare coloană poate avea o rație proprie, distinctă de celelalte, iar rațiile asociate liniilor și coloanelor trebuie să fie crescătoare de sus în jos, respectiv de la stânga la dreapta. Deoarece acest număr poate fi foarte mare, el se va afișa modulo 1.000.000.009.

În cel mai recent eveniment al companiei Tesla, Paul Musk a anunțat un nou produs inovativ: parcarea autonomă. Fiind cunoscut pentru lansările produselor incomplete, nici parcarea nu este completă, fiind nevoie de o automatizare pentru a atribui câte un loc mașinilor care vor să folosească parcarea. Parcarea este formată din N locuri, numerotate de la 1 la N, și este deschisă timp de T secunde, începând cu secunda 1. Pe parcursul zilei, sosesc M mașini care vor să folosească parcarea, pentru fiecare dintre acestea știindu-se timpul de sosire s[i] și timpul de plecare p[i]. Mașinile vin în ordinea timpului de sosire s[i] și ocupă locul de parcare în intervalul de timp [ s[i], p[i] ]. Pentru fiecare dintre acestea, trebuie să afișați un loc liber de parcare (dacă sunt mai multe, se poate afișa oricare) în care aceasta se poate așeza sau -1 dacă parcarea este plină în momentul venirii mașinii. Dacă o mașină nu are loc în parcare la timpul de sosire, aceasta nu va mai intra în parcare la niciun timp viitor. La final, Paul este interesat de mașinile care mai sunt rămase în parcare la închiderea parcării, de aceea vă cere să afișați configurația parcării la timpul T.

De ziua lui, Florin a primit un șir de caractere periodic și infinit. Perioada lui are lungime n și conține doar litere mici ale alfabetului englez. Deoarece este curios, el vrea să își personalizeze șirul primit în diverse moduri. Pentru a face asta, el vă dă q operații care se realizează pe șirul dat, operații de două tipuri, după cum urmează:

• 1 x y: Litera de pe poziția x devine egală cu y, unde y este o literă mică a alfabetului englez.
• 2 a b c: Florin vrea să afle câte litere egale cu c există între pozițiile [a, b] din șirul de caractere.

Fiindcă nu vrea să strice periodicitatea șirului foarte mult, Florin vă garantează că pentru toate operațiile de actualizare, valorile pozițiilor modificate au în reprezentarea binară cel mult k biți egali cu 1. Scrieţi un program care, dându-se șirul de caractere și actualizările, răspunde la interogări.

Se dă un graf conex neorientat G cu N noduri și M muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii. Se cere găsirea unui arbore parțial al grafului G, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.