Balul Bobocilor

Observam ca pentru a afla distanta totala pe care o parcurge fata este indeajuns sa cunoastem timpul in care ea se deplaseaza. Acest timp este timpul pana cand cei doi baieti se vor intalni si este dat de relatia T=D/(V1+V2) . Solutia se va gasi inmultind timpul cu viteza fetei: sol=V*T;

Carti3

Problema se poate rezolva folosind o lista dublu inlantuita. Initial adaugam toate cele C carti in lista. La fiecare din cei N pasi trebuie sa stim daca teancul s-a rotit de un numar par sau impar de ori. Daca s-a rotit de un numar impar de ori adaugam noua carte la sfarsitul listei, in caz contrar adaugam la inceputul acesteia. Pentru afisarea solutiei trebuie doar sa afisam toate cele N+C carti din lista, avand grija sa le afisam de la sfarsit la inceput daca teancul a fost rotit de un numar impar de ori.

Captcha

Transformam imaginea intr-o matrice de 0 si 1 unde 0 corespunde unui pixel alb si 1 unui pixel colorat.

FILE *f = fopen("captcha.in", "rb");

fseek(f, 54, SEEK_SET); // sarim peste headere pt ca nu prezinta interes

for (int i=15; i>=0; --i) //imaginea este reprezentata invers pe verticala
  for (int j=0; j<64; ++j) {
    fscanf(f, "%c%c%c", &b, &g, &r);
    A[i][j] = '0' + (b != 0xff || g != 0xff || r != 0xff);
  }

fclose(f);

Apoi facem pattern matching pe cifre. Dimensiunile mici ne permit sa facem asta intr-o maniera brut-force.

for (int i=0; i<16-5; ++i)
  for (int j=0; j<64-5; ++j)
    for (int cif=0; cif<10; ++cif)
      // verifica daca cifra cif se potriveste pe submatricea 5x5 avand coltul stanga sus in i,j
      match(cif, i, j);

Pentru a evita cazuri cand 1 este confundat cu latura stanga de la 8 de exemplu, putem borda matricea in care tinem fiecare cifra cu 0 pe margini

Ubercool

Solutia 1

Este clar ca exponentul unui număr de forma ab, unde a este prim şi b este mai mare ca 2, nu poate depăşi 60, deoarece 260 > 1018, iar baza nu depăşeşte 109. Atunci putem fixa exponentul, iar pentru un exponent fixat, trebuie sa calculam radical de ordinul respectiv din numărul iniţial. Daca acesta este un întreg, şi este şi prim, răspunsul este afirmativ. Daca am parcurs toţi exponenţii şi nu am găsit un radical întreg şi prim, răspunsul este negativ.

Pentru a calcula radical de ordin N dintr-un număr X se putea alege căutarea binara pentru a evita erorile de precizie, sau se putea alege varianta cu pow (X,1.0/N), dar în acest caz trebuia atenţie la precizie.

Solutia 2

Este clar ca baza unui numar pentru un exponent mai mare sau egal ca 3 este mai mica decat 1.000.000. Astfel vom preprocesa toate numerele prime de la 2 la 1.000.000 cu ajutorul Ciurului lui Eratosthenes. Dupa ce avem fiecare numar prim vom calcula puterile lui (mai mici decat 10^18) si vom verifica in lista celor N numere daca se regaseste. Pentru o cautare optima se vor pastra cele N numere intr-un Hash.

In acest mod vom gasi toate solutiile pentru un exponent mai mare sau egal ca 3. Pentru fiecare numar care nu a fost gasit ca fiind ubercool se va cauta o solutie de forma a2, adica se va calcula radicalul, se va verifica daca este numar intreg si prim in acelasi timp. Pentru verificarea primalitatii se poate folosi algoritmul de pseudoprimalitate Miller-Rabin sau direct algoritm naiv in complexitate O(sqrt(N)).

Aceasta solutie este optima si pentru un N de pana la 1 milion (cu precizarea ca necesita algoritmul Miller-Rabin pentru determinarea primalitatii unui numar), deoarece preprocesarea numerelor ubercool pentru b >= 3 este rapida si independenta de numarul N.

Curatenie

Problema cere sa găsim un arbore binar având la dispoziţie parcurgerile lui inordine şi preordine. Parcurgerea inordine este: STÂNGA RĂDĂCINA DREAPTA iar cea în preordine este RĂDĂCINA STÂNGA DREAPTA.

Precalculând pentru fiecare nod care este poziţia sa din parcurgerea în inordine, putem rezolva problema în timp liniar, folosind o funcţie recursiva. Iniţial ştim ca rădăcina este primul nod din parcurgerea în preordine. O cautam în parcurgerea inordine. Acum fiul stâng al rădăcinii este subarborele cu parcurgerea în inordine intre indicii 1 şi X-1, iar fiul drept este subarborele cu parcurgerea în inordine intre indicii X+1 şi N. Apelam funcţia mai departe şi pentru cei doi fii, în aceasta ordine, pentru a ştii la al câtelea nod suntem din parcurgerea în preordine.

void construct (int left,int right,node* &root) {
    if (left>right)
        return ;

    int mij=pozino[pre[++M]];
    root=new node (ino[mij]);
    construct (left,mij-1,root->left);
    construct (mij+1,right,root->right);
}

Muzica

Pentru 100p problema se rezolva liniar. Se inserează melodiile lui Vasile într-un hash. Apoi se generează cele M melodii alei lui DJ Random, având grija ca înmulţirea trebuie făcută pe long long, iar operaţia modulo trebuie aplicata o singura data, pentru ca este foarte costisitoare din punct de vedere al timpului, iar pentru 10.000.000 de operaţii, o constanta de 3 creste timpul. Apoi, pentru o melodie de-a lui DJ Random, se cauta în hash, iar dacă aceasta exista, se incrementează soluţia, iar acea melodie se scoate din hash, pentru a nu fi adunata de mai multe ori la soluţie.

Problema se poate rezolva şi folosind o căutare binara, sau folosind set-uri. Aceste implementări ajungeau pana la 70p.

Meneaito

Se observa ca pentru ca un timp sa reprezinte o solutie, atunci pentru fiecare coloana i, 1 < i < N, dansatorul de pe coloana i trebuie sa nu fie pe pozitia i. Astfel, putem marca timpii in care pe o anumita coloana i, pozitia i este ocupata. Mentionam ca nu ne intereseaza cazul in care i < A[i] sau i > B[i]. Pentru celelalte cazuri(unde A[i] <= i <= B[i]), consideram 2 posibilitati:
1) Dansatorul se afla pe pozitia i si se indreapta in jos;
2) Dansatorul se afla pe pozitia i si se indreapta in sus;
Observam ca pentru fiecare dintre aceste cazuri avem un timp(notat X1 pentru primul caz si X2 pentru al doilea caz) cand evenimentul se produce prima data. Deasemenea observam ca evenimentul(aparitia unui timp care nu poate fi solutie) se produce la un interval dat de timp, notat in continuare Y.
Se vede usor faptul ca:
X1 = i - A[i];
X2 = 2 * (B[i] - i) - (A[i] - i);
Y = 2 * (B[i] - A[i]);
Vor aparea astfel ecuatii de forma: T = X1 + K * Y si T = X2 + K * Y, unde T reprezinta un timp ce nu poate constitui o solutie, iar K este un numar natural.
Vom marca aceste ecuatii cu ajutorul unui map care ne va ajuta sa nu avem ecuatii redundante. Astfel pentru fiecare Y, vom tine maxim Y ecuatii.
La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului.
Complexitate: O(N sqrt N)