infoarena informatica de performanta

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

Este clar ca exponentul unui număr de forma a^b, unde a este prim şi b este mai mare ca 2, nu poate depăşi 60, deoarece 2⁶⁰ > 10¹⁸, iar baza nu depăşeşte 10⁹. 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.

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.