Orice numar X are cel mult un divizor prim mai mare decat sqrt(X). Asadar, afli toti divizorii primi mai mici decat X, iar la sfarsit verifici daca X are un divizor prim mai mare decat sqrt(X).

In back trebuie sa generezi permutari de 5 elemente. Pentru fiecare astfel de permutare, verifici daca ai solutie mai buna decat pana in momentul curent. Pe larg: O solutie canditata este data de o permutare ( s-o notam cu [p1,p2,p3,p4,p5] ). Acum, presupui ca Fat-Frumos se deplaseaza intai la a p1-a fata. De aici, pleaca spre cea de-a p2-a, apoi la a p3-a, apoi la a p4-a, apoi la a p5-a, iar apoi spre iesire. Aduni aceste distante, si vezi daca cumva e mai bine decat ai pana in momentul curent. Apoi, continui back-ul cu urmatoarea permutare, si repeti procedeul.

Totusi, iti recomand sa abandonezi pt moment problema, si sa inveti cu ce se mananca back-ul. Rezolva, de exemplu, probleme din arhiva educationala, precum Generare permutari, Combinari sau Submultimi.

Florian

Fara demonstratie matematica, nu poti spune ca solutia e corecta. 

N-am încercat, dar cred că merge

Da, merge. Am facut-o eu mai demult si asa o rezolvasem.

@newsabbath: Ideea in sine e gresita. Poate de aceea nu da corect. Fa cum a zis Mişu.

Problemele sunt adaugate, insa nu sunt publicate. Probabil nu sunt inca gata. Nu inteleg de ce faceti atata caz. 

insa stiu toate structurile, fisiere, vectori-notiuni de baza , cred ca si matrici-adica am inteles modul lor de functionare.

Lucreaza tot ceea ce tine de matrice, vectori si fisiere. Nu are rost sa te apuci de algoritmi seriosi, daca nu stii notiunile de baza. Daca nu ai de unde sa iei probleme, cauta prin variantele de bac din anii trecuti ( de pe www.edu.ro ). Dupa ce stii 100% cele trei, poti reciti acest topic. 

O poti face oricand ( adica, direct din citire). Dar tu cam unde esti cu teoria? Stii vectori, matrice si fisiere?

http://infoarena.ro/problema/bmatrix

Si puteti sa imi spuneti cu ce sa incep( cu ce algoritmi)?

Apuca-te de problemele din anii anteriori. Bate-ti capul cu ele. O sa vezi ce algoritmi iti trebuie. La OJI clasa a-9a, nu iti trebuie nu stiu ce algoritmi sofisticati. Pur si simplu, rezolva probleme!

[s-a dat metoda backtracking.]

bine ar fi sa stii totul din cea de a 9-a pana pe 6 martie pentru ca mai mereu  s-a dat metoda backtracking.

Backtracking la a 9-a, mai mereu, zici ?   Arata-mi doua probleme.  

Pentru Sebastian: Ce faci la orele de info cu siguranta nu iti va fi suficient pt olimpiada. Nu e ca la celelalte materii. Vrei performanta la info? Ia-ti carti, invata algoritmii clasici ( te va ajuta si arhiva educationala ), invata smenuri, participa la concursuri online, rezolva probleme, munceste ! infoarena are o arhiva de probleme mare. Abia asteapta sa le lucrezi. Daca nu iti ajunge infoarena ( care are si un forum cu oameni capabili si dornici sa te ajute + nenumarate articole) , vezi si pe .campion.

Daca vrei un reper pentru a sti ce probleme sa rezolvi, iata o mini-lista:
# problemele date in anii precedenti la OJI, clasa a9 a
# problemele de la preONI + Algoritmiada ( clasele 5-8, in principiu, pt oji. Daca vrei ONI fa si de la clasele 9-10 ).
# problemele de la grupa "small" de pe .campion

Florian

http://campion.edu.ro/arhiva/index.php?page=home&action=view

Cauti problema, trimiti o sursa la ea [ orice ], si se va afisa pe pagina problemei un link spre solutie.

Este absolut fascinant cum in Romania nu se preda nici C, nici C++, ci Borland.

Oare tu mi-ai spus odata ca "A trecut demult vremea cand scoala era o buna sursa de informare" ? 

Am vazut, da le-as vrea pe hartie si nu stiu daca se pot cumpara de undeva.

Le poti printa.

A mai avut cineva probleme cu testele 4, 6 si 7?

Tu rezolvi problema pentru subsecventa. Trebuie sa o faci pentru subsir ( care nu are elementele pe pozitii consecutive in sirul initial ). Citeste cu atentie enuntul! 

a[ x ] = 1/0 (valoarea variabilei x ( x = 1, 26)) sau a[ x  ] = -1, daca variabila x nu apare in sir. Si da, cred ca am tastat gresit cand am scris forma poloneza.

Poti face si cu vector. Am gresit eu. Uite, aici:

   for(i=1;i<=m;i++)
   {
      f>>x;
       v

• =1;

   }

x poate fi mai mare de 500.000. Pune conditie!   Mai citeste o data formatul datelor de intrare.

Cam mult O(N/100).  Nu e mai optim sa scriem de mana MAX_B if-uri ? Iese O(1) !  

ab|c|d|e|f|g|x|y|z|
ab|c|d|e|f|g|x|y|yz^|

Asta e forma poloneza pt cele doua.

Cod:

for( ; a != b; ++a, --b )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;

Absolut genial!  Nu e acelasi numar de operatii ca la solutia liniara? Plus ca intra in ciclu infinit pt anumite teste. 

Parcugi fiecare element de la a la b, si le faci suma cifrelor, verificand apoi daca se divid prin ea. E brute force... E problema de "curtea scolii"...  

Daca a si b sunt relativ mici, poti precalcula un vector sum[ i ] = suma cifrelor lui i. Si o sa ai sum[ i ] = sum[i/10] + i%10 ( i = 1, b ) ( asta ca sa nu mai faci la fiecare pas suma cifrelor ) => complexitate O(b) . Ceva mai optim nu vad.

Ce inseamna optim? Da si tu niste restrictii de timp, memorie sau limitele numerelor din input.

Și la această problemă, și la cerc3 de la oji2009 îmi dă "Killed by signal 11(SIGSEGV)." pe toate testele, deși când le evaluez manual după testele de la oji, nu apare nicio problemă. Nu depășesc limitele niciunui vector

Ai grija la numele fisierelor .in si .out.  Am asa o vaga banuiala ca aici gresesti 

Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" )

pai nu e chiar poveste, chiar de la fotbal mi-am pus intrebarea asta adica  sa zicem ca vin in liga a 2-a din liga 1 : ceahlaul, poli iasi, otelul galati(care teoretic ar merge in seria de est a ligii a 2-a si pandurii targu jiu care e teoretic in divizia de vest si ar veni seria de est 19 echipe si cea de vest cu 17. atunci trebuie pusa fc arges de exemplu din seria a2-a in seria 1 si vom avea echilibru  
Dar da asa e  practic trebuie sa faci N grafuri complete a cate M noduri fiecare si pentru fiecare graf faci suma distantelor si aduni la suma totala care trebuie sa fie minima dar cum faci asta :
- programare dinamica sau
- backtacking in caz ca e Nedeterminist Polinomiala?
- greedy desi nu prea imi vine sa cred pentru ca nu mi se pare ca acopera toate solutiile

Cu alte cuvinte: "Da, asta cer." 

Tu nu citesti k-ul (  printf("%d",k); ). a[] e prea mic declarat. Fa si tu un debug ( cu watch, sau cu afisari ). Nu cred ca e indicat sa postezi pe forum chiar orice problema. In curand o sa discutam aici erori de compilare. Nu cred ca asta e scopul infoarena. Spor!