[C++] Problemă olimpiadă

[pr00f]

Azi a fost olimpiada local?, dou? probleme, pe prima am f?cut-o toat?. Doar c? în cazul celei de-a doua probleme, n-am în?eles mai nimic din ea, plus c? m? cam dep??e?te. Enun?ul sun? în felul urm?tor :

În fi?ierul „numere.in” se afl?, pe prima linie, trei numere naturale n, m ?i b, iar pe a doua linie un ?ir x de n numere naturare x1, x2, ... xn (x indice 1, 2, ... n). Fiecare dintre aceste numere din ?irul x se converte?te în baza 7, ob?inându-se un ?ir de numere notate y1, y2, ... yn (y indice 1, 2, ... n), unde ci (c indice i) este cifra cea mai semnificativ? (prima cifr?) din scrierea num?rului yi (y indice i).

Cerin?? :

S? se determine cel mai mare num?r scris în baza b cu exact m cifre care se poate forma cu unele dintre cifrele c1, c2 ... cn (c indice 1, 2, ... n). Dac? nu se poate forma un astfel de num?r se va afi?a valoarea -1. Afi?area se va face în fi?ierul „numere.out”.

Restric?ii ?i preciz?ri :

1 <= n, m <= 1000

x1, x2 ... xn <= 100.000.000

2 <= b <= 5

Exemple :

1) numere.in :

5 3 5
12 34 5 6 7

numere.out

411

Explica?ii : în urma conversiei celor 5 numere din fi?ier în baza 7 se ob?ine ?irul cifrelor cele mai semnificative 1, 4, 5, 6 ?i 1. Cel mai mare num?r în baza 5 format cu 3 cifre dintre cifrele cele mai semnificative este 411.

2) numere.in :

5 3 3
12 34 5 6 7

numere.out :

-1

Explica?ii : nu exist? un num?r scris în baza 3 format din 3 cifre care poate fi compus din cifrele care formeaz? ?irul 1, 4, 5, 6 ?i 1.

Nu înteleg cum se face conversia în baza 7, verificat, prostii. V? a?tept cu diferite rezolv?ri, postul fiind la „Competi?ie [challenges]”. Dac? nu, a? dori m?car s? în?eleg conversia în baza 7.

Mul?umesc.

Edited February 5, 2012 by pr00f

[Robert1995]

int dec2bin(int num)
{
int bin = 0, k = 1;
while (num)
{
    bin += (num % 2) * k;
    k *= 10;
    num /= 2;
}
return bin;
}

Asta ar trebui sa fie baza 2, foarte basic implementarea. Pentru baza 7 pur si simplu pui inloc de 2, 7 . Cel putin asa cred

[Patrunjel]

Oji e in martie....

Pentru conversia in b10 intr-o baza oarecara mai mica decat 10 iei fiecare cifra, o imparti la baza in care vrei sa treci, restul e adaugat la numarul in baza noua, catul merge mai departe.

Si totusi, oji e in martie

Edited February 5, 2012 by Patrunjel

[Andrei]

La ce clasa a fost OJI? Gimnaziu? Eu stiam ca e pe 3 OJI la liceu. Gresesc? Intr-o alta ordine de idei, arunca o privire peste articolul asta de pe Wikipedia : Baz? de numera?ie - Wikipedia

[pr00f]

Oji e in martie....

Local?, scuz?-m?, am editat.

[gotr00t]

Bai si eu ar trebui sa merg, dar oli pe liceu e mai tarziu, din cate zicea diriga. Zicea ceva de sfarsitul lui Martie.

Totusi, vineri am participat la un concurs local organizat de un colegiu din oras si problemele au fost de tip olimpiada. A doua problema presupunea aflarea cmmdc dintre fibonacci(n) si fibonacci(m). Problema erau restrictiile, respectiv:

0<n,m<30000

timp de executie<1 sec.

si asta presupunea putin out of the box.

[Andrei]

Bai si eu ar trebui sa merg, dar oli pe liceu e mai tarziu, din cate zicea diriga. Zicea ceva de sfarsitul lui Martie.

Totusi, vineri am participat la un concurs local organizat de un colegiu din oras si problemele au fost de tip olimpiada. A doua problema presupunea aflarea cmmdc dintre fibonacci(n) si fibonacci(m). Problema erau restrictiile, respectiv:

0<n,m<30000

timp de executie<1 sec.

si asta presupunea putin out of the box.

Ce ai facut? Is curios.

[gotr00t]

sincer, nu mai tin minte exact finalul, dar stiu ca am trecut prin mai multe etape. Prima oara, inainte sa vad ce restrictii mari erau am luat un vector de tip double double. Dupa ce am vazut restrictia am pus urmatoarele conditii:

if(i==101)

{/*am pus v[99] si v[100] in v[1] si v[2], am calculat v[3] si am dus i=3 si n=n-100;*/}

am mai modificat cate ceva la asta, dar cum olimpiada a fost dupa ore, vinerea nu mai pot sa-mi amintesc prea bine ce am facut.

Si prima problema era cu siruri, pot sa scriu aici din amintiri enuntul, daca vrea cineva.