Pai na, sa spunem ca la testul 10 ai K = 100 000!... Mai verifica ciurul! Verifica daca toate numerele prime iti dau bine! Eu am facut asa: am generat toate numerele prime ( cu ciurul ) mai mici de X ( unde X e suficient de mare, de ex. 10 000 000 ), si am aflat al (K+1)-lea nr. prim! Ai grija k rezultatul sa fie pe 64 de biti. Si de exemplu dak ai ceva de genu' "long P;" unde P e numarul prim determinat, ca sa il ridici la patrat il convertesti la long long: fprintf(fout, "%lld\n", (long long)P * P);

Si eu tot binar am cautat si tot 70 am luat, pe ultimele 3 teste TLE... Cel de-al treilea punct il gaseam insa altfel: din mijlocul segmentului celor doua puncte curente duceam o perpendiculara de lungime l * sqrt(3) / 2 in ambele directii posibile si aflam astfel coordonatele celui de-al treilea punct. Un algoritm O(N^2 log N) zic ca ar trebui sa se incadreze fara probleme in 1 secunda... dar la mine nu se incadreaza pentru ca am prea multe calcule consumatoare de timp...
   Sincer sa fiu, eu nu as incerca cu hash aici, mi se pare prea mica probabilitatea sa nu greseasca ( indiferent de cheia pe care o alegi )...

                                   bubbleSORT

Eu sunt gata sa cooperez... In special pentru partea cu propunere de probleme...

                                                     bubbleSORT

Bineinteles ca mai exista un caz particular daca faci asa: trebuie sa consideri si cand dreapta ta este paralela cu Oy, adica Xa = Xb...

La problema asta, imi da TLE pe 5 teste... Exista un algoritm mai destept sau pur si simplu merge in timp si recurenta normala [ in O(N^3 * MAX), unde MAX este numarul de cifre ale rezultatului ] implementata ordonat? Sau poate trebuie sa implementam operatiile pe numere mari intr-o baza mai mare de 10? 

   P.S: In sursa mea, tabelul cu combinarile e preprocesat inainte de a inepe recurentele...

Stie cineva care e site-ul oficial al BOI 2005 ( olimpiada balcanica )? Nu am gasit nimic nici cu google, nici cu altavista... Sau nu are site oficial?
 
                                                        bubbleSORT

Poate ciclu hamiltonian...

La problema asta iau 70 pct, pt. k pe 3 teste primesc WA. Cum am facut eu: dupa ce am construit infasuratoarea convexa, am luat fiecare segment de pe infasuratoare ca dreapta suport d pt. una din laturile dreptunghiului. Aflam din punctele ramase ale poligonului care este cel mai departat de dreapta d ( prin acest punct duceam || la d, care era directia celui de-al doilea segment al dreptunghiului ). Apoi aflam si punctele M si N din cele ramase din care, daca ducem perpendiculara pe directia aleasa, intersecteaza dreapta suport cel mai sus ( respectiv cel mai jos ), si aflam si ultimele doua directii. Cel mai de sus punct de pe dreapta suport initiala era considerat a fi cel care are ordonata (y) cea mai mare, si pentru y egali, x-ul cel mai mare.
  As vrea sa stiu daca rationamentul este corect.  
  Daca este corect, pot aparea erori de la precizie? Am lucrat pe double.

                             Filip b.

Problemele din arhiva sunt interesante. Dar rasfoind azi niste probleme de info mi-am dat seama ca ele nu acopera toate genurile de probleme de la concursurile internationale ( adica tipuri de probleme, nu privind modul de rezolvare... ). De exemplu, la IOI, CEOI sau BOI se dau si probleme de tipul: "Se dau cele 10 fisiere de intrare. Sa se submit-eze cele 10 fisiere corecte de iesire corespunzatoare.", dar in special "Programul vostru nu va citi si nu va scrie in nici un fisier. El va interactiona cu un program al comisiei... Se pun intrebari de genul ASK()...", etc. Probleme ca aceasta din urma ( cu biblioteci ) se dau in numar destul de mare pe la baraje sau chiar la olimpiade internationale. Se pot pune si probleme de acest gen in arhiva? ( ar trebui modificat evaluatorul in acest scop?...) Ar fi foarte utile...
  Sper sa nu supar pe nimeni, mi-am exprimat doar o parere ( despre faptul ca acest tip de probleme ar trebui sa existe in arhiva ).  

                                                                  Mersi mult,
                                                                     Filip b.

Pai si tu de unde stii ca pentru Testul X trebuie sa afisezi A si nu B? Doar nu cunosti si raspunsurile la teste.. Acea constanta nu e cunoscuta...

Construieste un ex de arbore cu vreo 20 noduri si verifica stiva DFS la fiecare pas sa vezi daca DFS-ul manual merge bine. Altceva nu are ce sa fie...Fara cod in fata nu pot sa imi dau seama..
  HINT: Vezi sa initializezi cu 0 toate nodurile in care se pot rezolva cererile ( sa nu le consideri la distanta 1 fata de ele insele ). Mai rescrie o data sursa daca tot nu-ti iese... Mai mult de atat n-am ce sa fac sa te ajut...

Cu Ciurul lui Eratostenes. Si nu mai puneti intrebari de genul "CUM SE REZOLVA?", incercati singuri sa va dati seama... Daca am sti rezolvarile la toate problemele nu ar mai fi interesant...

  bubbleSORT

Pentru n = 2: (1,1), (1,2),(2,1),(2,2) -> 4 moduri
 Pentru n = 3: (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3), (2,1,3),(2,2,3),(2,3,3) -> 9 moduri

 ___________________________________________
 Si apropo de complexitate: e O(N) spatiu si O(N) memorie. Ar fi fost O(1) daca  ar fi fost pur si simplu o formula (de genul n^2+5-17*32)... sper ca nu am rascolit prea tare trecutul   Parerea mea...

Am o nelamurire la problema asta: noi trebuie sa afisam "numarul minim pentru... ultimele P perechi ". Primul numar afisat va fi cel pt. cea de a (M-P+1)-a pereche sau pentru cea de a M-a pereche?
  Adica rasp. pt. perechi se afiseaza in ordinea: (M-P+1), (M-P+2).. M, sau in ordinea M, M-1... (M-P+1) ( incepand cu ultima pereche)?

  bubbleSORT

Eu zic ca e doar formal... Adica intotdeauna exista solutie!

Poti sa pui "include <time.h>" si apoi retii 2 variabile t1 si t2 ca fiind timpii curenti ( masurati intr-o unitate oarecare, in Borland dif. dintre timpul curent si 1970 ). Variabilele le afli apeland functia time, t1 calculat la inceput si t2 calculat la sfarsit. Timpul de executie al programului tau este t2-t1, aflat bineinteles intr-o unitate de masura care poate fi convertita in sec, min, ore, etc.
  In aceasta privinta, helpul din C se dovedeste foarte util. Ai si un exemplu acolo care sa te lamureasca cat de cat...

  bubbleSORT

Se demonstra matematica ca q = [sqrt(N)] ( ) ). Eu am vazut asta prn multe incercari ( vreo 20 )... Dupa aia aflam in O(sqrt(N)) perechile (a,b) printr-o ecuatie de gradul doi...

 bubbleSORT

 P.S: azi am ajuns acasa

[svalentin]

Sal. Si eu va scriu tot din Yakutsk, da' nu din sala de net, ci de la contestatii... ) A fost un set de probleme destul de 'original', adica cum spunea si svalentin, prima problema suna cam asa:
  ' Fie q si r catul si restul a^2 + b^2 la (a+b). Sa se determine toate perechile (a,b) a.i. q^2 + r = N, unde N este dat! N <= 2 * 10^9"... cum vi se pare? ) Am reusit (nu stiu cum) sa iau 100 la asta (dupa 2 ore de incercari)
   In rest, vreo doua dinamici si una cu grafuri (care as caracteriza-o ca cute )...
  Eu am luat 470.
  In rest, o sa aducem subiectele in tara.. Mult succes la IOI, BOI si CEOI...

                 bubbleSORT

Si eu luam tot 40 la un moment dat cu WA pe ultimele 6 teste. Problema era ca foloseam tipuri doar pe 32 de biti, in loc de tipuri pe 64. Incearca sa schimbi cu int64 ( daca lucrezi in Pascal ) sau cu long long ( pentru C/Cpp)..

  bubbleSORT

Da. M-am grabit cand am scris... "5 5". Sorry.

Iti sugerez sa incepi cu probleme mai usoare de dinamica daca esti incepator, asta e "destul de incalcita"... Incearca alta probleme mai usurele din arhiva: "perm" (asta e o relatie de recurenta cunoscuta... nu iti spun mai mult), "joc", "siruri 2-3 monotone" (si asta e destul de grea daca nu o stii dinainte ), "Energii", etc.

  bubbleSORT

Pentru n=6 da ceva de genul:
  "4
   3 1
   4 3
   5 6
   6 2"

Probabil evaluatorul asteapta un posibil raspuns si tine programul tau "agatat". (desi e ilogic, dar de altceva de ce ti-ar da TLE?) Oricum, o simpla citire a doua numere (oricat de mari ar fi ele  :lol: ) este realizata instantaneu. Nu mai trimite surse din astea care fac doar citirea si incearca sa faci pur si simplu un algoritm. La fel si la problema "fractii" (eu faceam de ex. initializari in O(n) si nu mi-a dat TLE cum iti da tie pe for-ul cu instructiunea vida...)

 bubbleSORT

[Later edit: Incearca sa citesti datele de intrare cu READLN!]

La problema asta m-am prins partial ce avea (acum iau 40, nu 10.. se vede diferenta... ) )... Era de la faptul ca unele muchii se puteau repeta... Eu citeam doar primele n-1 muchii (credeam ca nu se repeta...), si nu pana la sfarsitul fisierului.... Daca mai vad inca o greseala, iau 100

Sigur e de la implementare... O sa o rescriu de la inceput, alta varianta nu am...