infoarena

Cine imi da si mie o idee cum sa descompun un numar n<=10^100 in suma de termeni fibbonaci(1,1,2,3,5,8....); timp de executie 0.1 sec

Mi se pare imposibil in timpul asta !

Asteapta sa se termine runda  :wink:

eu am facut problema dar nu iese in 0.1 secunde

Problema este acum la .campion si este normal sa se discute abia dupa terminarea rundei.

Vei vedea solutia imediat dupa ce se va termina runda :P.

Silviu Ganceanu

Gata !!! Am facut-o ! sper sa iau suta caci am nevoie ! :P

Si eu sper! Multa bafta!

Silviu

problema in sine nu se poate rezolva daca nu stii "smenul", rezolvarea (matematica) avand vreo 11 pagini. Oricum ma ingrijoreaza spatiul ca e cam la limita. Sa se incadreze oare la genul de probleme care se rezolva cu formule ? Oricum mishto corelarea celor 2 probleme.

vorbeam evident de Otilia

:) In fine.. eu NU am rezolvat-o matematic.. Solutia mea e informatica pura :D

Silviu

Ce inseamna informatica pura ? Eu am gasit niste chestii care par sa mearga. Nu am nici un contraexemplu pana acum. Timpul de executie  al programului meu este prea mic (0.0001 s) in comparatie cu 1 s si mai mult nu folosesc cei 19 MB.  Poate am gasit ceva mishto, dar poate nu valoreaza decat maxim 0 puncte.

Iti dai seama ca nu-ti raspund.



Intotdeauna se gasesc si alte solutii. Sa speram ca a ta este una buna.



Si asta e posibil..

Silviu

Oricum nu ma intereseaza o alta rezolvare pt ca m-am chinuit prea mult si m-am saturat de problema asta.

     Vreau altele ! Apropo daca mai ai probleme interesante pe care nu o sa le propui la concursuri poti sa-mi trimiti  si mie cateva. Asa ca nu prea am ce face. Am dat teza la romana, deci am scapat de scoala.

 [email protected]

P.S. Ce inveti la politehnica? C++, Java etc ?
       E mishto?

vorbeam de demonstratia matematica a rezolvarii (Otilia), care depaseste cu mult programa de liceu , cel putin.

Problema (Otilia) e interesanta. S-au facut studii pe teoria jocurilor si, o data ce le-ai gasit, citit si inteles problema devine destul de usoara. Oricum e bine venita pentru o runda de pregatire.

Silviu, salveaza-ma !!!!!!

Sursa mea fib merge perfect daca stergi caracterul "sfarsit de linie" din fisierul de intrare.
 
 In loc sa fiu in primii zece acum sunt la mama naibi pe locu 49.
 
   Se poate face ceva ?

 Pls!!!!!

Sper ca stii ca in enuntul problemei scrie ca orice linie (inclusiv cele din fisierul de intrare) se termina cu "sfarsit de linie". In conditiile acestea, voi analiza situatia, impreuna cu doamna Emanuela Cerchez, si vom stabili daca este cazul sa reevaluam.

Silviu

vladcyb1:
tu pe ce sistem de operare te-ai testat?
daca l-ai testat din windows, ai grija, ca linux si windows au caracterul "sfarsit de linie" diferit! #13 #10 (windows) si #10 (Linux)!

Eu am testa pe windows, dar nu asta e problema.

 Silviu,
 
  In exemplul dat la problema nu apare caracterul sfarsit de linie nici in enuntul in html, nici in cel doc. Daca nu l-am vazut am crezut ca doar fisierul meu de iesire trebuia sa se termine cu caracterul sf de linie.
 
   Esti de acord ca nu apare in exempul problemei ?

   Nu mi se pare corect sa pierd contactul cu primele 10 locuri din cauza unei ambiguitati. Te rog sa ma ti la curent cu decizia luata.
 
        Thanks a lot !

P.S. Daca acel caracter dispare din sursele de intrare atunci iau 100 pcte.

Omule, iti dai seama ca ce spui tu este deja la limita penibilului. Nu poti sa ceri ca enuntul sa fi continut "newline" in exemple. In general, exemplul e scris de mana si nu poti cere atentie chiar si la astfel de detalii. Oricum iti inteleg oftica pentru ca si eu am fost in situatii de astea, de foarte multe ori dar... suntem la informatica.

Silviu

Da mey, ai dreptate, am gresit.

 Asta e ! Sper sa mai pot recupera. Scuze !

  Oftica asta, bat-o vina !!!

 Daca shi tu ai facut astfel de greseli, atunci ma simt  mai bine. Se intampla si la case mai mari.
  Sorry daca am fost prea insistent.

         Thanks a lot !

      S-a mai propui si alte probleme.

P.S. De ficare data sa pui si urmatoarea linie in enunt.

  *** Pentru batuti in cap nu uitati de  sf de linie, mama lui de caracter, cine l-o fi inventat. :P

Am si eu o intrebare: la problema m01, pt n=999, ce fisier de iesire trebuie sa rezulte? mie imi da 111111111111111111111111111
Este bine ???

doh, daca imparti 111111111111111111111111111, la 999, iti da un nr fix!
deci raspunsul tau e bun!
(impartirea asta o poti face cu calc din windows!)
(exista oricum mai multe solutii!)

Mai valentine.

 Tu la ce grupa concurezi ca te-am vazut pe la toate grupele?
  In finala, unde candidezi?

sunt a X-a, deci concurez la grupa mijlocie in finala!

Vreau si o lamurire in urmatoarea privinta:
 O problema precizeaza ca dimensiunea toatala a memoriei ce poate fi alocata este de 2 MB din care 1 MB pentru stiva. Acest lucru ma impiedica sa declar o matrice ce ocupa 1,9 MB ? Ce inseamna pt ei stiva, deoarece pt mine nu e nimic mai mult decat mecanismul LIFO implementat static sau dinamic.


       Da-tim\-mi pls o explicatie ca de gradinita, poate intleg shi yo.

           Thanks.

spatiul alocat stivei (aici) inseamna spatiul total pe care-l poti folosi cand declari ceva static intr-o functie (orice functie). (vrei exemple ? )  :lol:

Raspuns: DA, indiferent daca e static sau pe stiva.
In consecinta, mare atentie!

Silviu

In legatura cu memoria , cum imi dau seama cat ocupa o matrice
a[501][501][501][501] ?

Le inmultesti :). Daca e o matrice de int pe un calculator 32b atunci sunt vreo 250 GB.

Silviu,

Dar daca fac o smekerie de genul

 type vector = array[1..1000]of byte;
 var a:array[1..1000]of ^vector;

Crezi ca merge?
P.S. La USACO zicea ca limta de memorie este 17 MB din care 1 MB pentru segmentul de stiva. Eu am declarat un array[1..4000,1..4000] of byte si am luat aproape tot punctajul. (mi-a iesit din timp, dar a mers)

Unde gasesc niste informatii despre kestiile astea?
Thanx

Nu ma cheama Silviu, dar am sa-ti raspund eu, ca mai oboseste saracul baiat.  :D

La USACO ti-a mers treaba pentru ca tu ai alocat static o matrice de 4000 * 4000 bytes adica mai putin de 16 MBytes (1 MB = 2 ^ 10 KB = 1024 KB). Te-ai incadrat in limita de memorie.

Cat despre "smecherie" ...
Acei 1000 de vectori pe care urmeaza sa-i aloci se vor duce toti in heap (adica nu in stack - stiva). Intrucat ai la dispozitie 2 MB din care 1 pentru stiva => 1 MB pentru heap.
Cei 1000 de vectori incap in heap si ii vei putea folosi.

Insa asta nu rezolva problema de la care am plecat (sa aloci o matrice de 1,9 MB).


Daca tii neaparat, poti face niste trucuri ieftine sa imparti matricea ta cea mare intre heap si stack dar mai bine zi-ne si noua problema sa gasim impreuna o solutie care merge lejer in limita de memorie.

Am reusit sa fac problema folosind o matrice a[501][501] . Multumesc oricum pentru sfaturi!!

Problema este la campion in desfasurare, deci nu avem voie sa o discutam.
 Mai, la USACO ai vazut ce zicea: Segment de stiva max. 1 MB si eu am declarat 16 MB

 Am vazut ca cineva a postat un reply in care zice ca stiva de 1 MB se aplica doar la subprograme.
 
 Eu pana acum credeam ca restrictia asta de stiva ma impiedica la recursivitate si atat.

 Thanks anyway.
  O sa incerc o fragmentare a matricei. Asa merge sigur.

Pe stiva, din cate stiu eu, se duc toate variabilele declarate local (adica intr-un subprogram) si apelurile din recursivitate. Restul, pe heap (adica si variabilele globale), deci probabil ca matricea ta de 16mb era o variabila globala.

Domino,
Concluzia din ce mi-ai spus tu este urmatoarea:
= daca problema spune ca spatiul total ce poate fi alocat este de 2 mb, din care 1 mb pt stiva atunci o declaratie de genul
 var a:array[1..1000,1..1000]of word ; va fi perfect valabila.

Daca din 2mb, 1 e de stiva, ramane 1 pentru heap, deci variabila ta nu va incapea fiindca are ~2mb.

Hai ca i-am dat de cap !
 Thanx!

Sarabogdan,
 Ce complexitate ai la problema ? N^2?

Se poate sa obti intr-un graf toate cuplajele maximale intr-un timp de 0.2 secunde ?
 
  Nu-mi dati idei. Vreau doar sa stiu daca se poate. 101 noduri in stanga si 101 in dreapta.

Cred ca vroiai sa zici graf bipartit.. si sa treci prin TOATE cuplajele maxime e cam mult.. numarul lor e exponential.

Am O(n*(n+1))^2 si nu intra in timp!!

vladcyb1, ai complexitate O(N^2) din cate am citit de pe forumul .campion. Se poate determina un poligon folosind doar 2 puncte?
(DA/NU). Eu am aproape O(N^3) (32mil. operatii pt n=500).

Nu se poate determina un poligon cu 2 puncte. Citeste enuntul. Te intreaba cate paralelograme se determina, nu care sunt.

Mai, ati facut problema bomboane. Pe mine ma cam depaseste teoria necesara. Invat de zor si sper ca pana miercuri sa scot un algoritm.

Spunet-mi si mie daca vre unul de clasa a X-a a facut-o pana acuma. Nu cred ca trebuia bagata la a X-a. Ce parere aveti?

Desi nu sunt la clasa a X-a si eu sunt de parere ca e cam dificila pentru clasa a X-a, dar totusi in 10 zile sau cate au fost la dispozitie se putea invata teoria necesara. :)

nu se da n=500 pentru un O(n^2), fratilor. tot O(n^3) shi un pic am shi io, dar merge kam greoi. daca era problema de n^2 dadeau n-ul mai mare.

Pana la urma cred ca am scos ceva destul de bun la "Paralel". Am O(n^2*(log n  +  1) ). In sfarsit putem discuta despre problema ca s-a terminat runda.

Ai luat 100? Vrei sa-ti dau sursa mea ? Da-mi mailul sau o postez pe forum.

Chiar ma intereseaza algoritmul tau(in N^2). Poti sa mi-o trimiti la [email protected]. Sper sa fie lizibila. Poti sa scrii si pe scurt metoda (geometrica).

Ti-am trimis mailul. Este in pascal pt ca altceva nu stiu. Sper sa intelegei. Am incercat sa o fac cat de cat lizibila. Oricum are cateva randuri.

Ar putea cineva sa-mi prezinte si mie rezolvarea detaliata (ca pt gradinita) a problemei JOC de la Runda 7? Va rog mult, deoarece sper ca la un moment dat sa reusesc si eu sa rezolv probleme de acest tip. Va multumesc !

P.S. Am citit descrierea solutiei de pe liis dar nu inteleg nimic

O sa incerc sa explic eu.. desi am luat doar 10p  :oops: dupa concurs am reusit sa fac o sursa care merge de max.
Am construit o matrice bst[j] = diferenta maxima de scor Ana - Ion, daca incepe Ana din pozitia (i, j) si o matrice C[j] = valoarea casutei (i ,j) (0 pt '.' 1 pt bomboana, 3 pentru suc si 5 pentru ciocolata)

Prima observatie este ca bst[j] poate fi considerat si ca diferenta de scor Ion-Ana daca incepe Ion.
Daca Ana muta din (i, j) in (i+1, j), atunci vom lua in considerare valoarea -bst[i + 1][j], fiindca presupunem ca in casuta (i+1, j) incepe Ion deci bst[i+1][j] va fi diferenta de forma Ion-Ana, iar -bst[i+1][j] va fi de forma Ana-Ion. La -bst[i+1][j] vom aduna C[i+1][j]. Analog se procedeaza si pt (i,j+1) si (i+1, j+1).

Rezumand
bst[j] = max(C[i+1][j] - bst[i+1][j],
                       C[j+1] - bst[j+1],
                       C[i+1][j+1] - bst[i+1][j+1])

Pentru a trata cazul cand diferenta de scor e 0, am mai construit o matrice move[j] care imi zice paritatea numarului de mutari de la (i, j) la o casuta din care nu se mai poate muta. Daca move[j]=1 atunci ultima mutare a facut-o Ion, altfel a facut-o Ana. move[j] ne ajuta la departajare cand alegem maximul dintre cele 3 variante, daca 2 sunt egale de exemplu, alegem pe cea cu valoarea move[j] cat mai mare (pentru ca sa piarda Ion). Sper ca ai inteles, daca vrei iti dau si sursa.  :D

Mersi mult, Mircea !!

Incerc sa implementez eu si daca nu reusesc iti cer din nou ajutorul.

Thanx again!

Chiar daca ai luat 10 p nu ai iesit din cursa pt finala. Bafta in continuare!

Mircea,
poti sa-mi dai si mie testul doi de la problema trapez?
Nu stiu unde naiba gresesc, ca iau numai 10 puncte.

thanx

Nu mai vreau testul. Simt ca innebunes! La concursul de duminica am folosit produs incrucisat si am luat 10 puncte acuma am facut direct impartire pe numere reale si am luat 100 puncte. Ce naiba inseamna asta? Ai zis ca nu merge cu impartire directa!!!

Eu cand am facut surse nu mergea sursa cu impartiri reale... foloseam double.. eu stiu care o fi faza.. era un sfat in problema, nu era o obligatie! oricum cu intregi sigur iei 100... vezi ca e o sursa a lui JEULETZ pe unde pe forum care aproape merge.. are un mic bug dar in rest e ok.. poate te lamuresti acolo... nu stiu exact ce produs incrucisat ai facut tu acolo... ma rog... bine ca ai luat 100 in sfarsit :)

As vrea si eu un link de unde pot invata formule de numarare, stirling si alte kestii de recurenta?

Cartea "Probleme de combinatorica si teoria grafurilor" de Ioan Tomescu , Bucuresti 1981 e de baza .. destul de multe probleme din cartea respectiva s-au dat nealterate la olimpiada nationala sau la lot deci daca vrei sa te pregatesti in combinatorica ai putea sa o parcurgi ... desi daca o faci nu e garantat ca faci orice problema de combinatorica si mie parcurgerea ei completa mi se pare ca cere multa vointa. Un exemplu de problema ar fi problema Siruri 23 monotone, ea a fost data la baraj in 2001 si la campion si acum e pe infoarena in cartea respectiva e problema 12.21.

Alta chestie ... Forumu asta are optiunea de a face un thread nou, cand aveti o intrebare noua faceti un thread nou pentru ca cei nou veniti curiosi in o anumita chestie sa dea un search si sa gaseasca threaduri interesante nu sa fie obligati sa citeasca un thread imens.

Am o idee:Sa pun la incercare sistemul de securitate de la infoarena.devnet.ro adik sa fac un programel in c++ care sa stearga tot ce poate de pe toate hardurile pe care le gaseste in cale pare interesant nu?
Desi pana la urma cred k nu merita efortul dar este idea mea.  \:D/

Super idee, tine-o tot asa!

pai tu ce crezi? nu ne-am gandit la asta?
 :D

vreau sa shtiti ca singura preocupare a acestui mare hacker implica warcraft sau poze porno (si  mâna lui drapta). Va puteti imagina ce idee geniala a putut avea acest intelect superior? "Sa faca un program ce sterge tot  "  oooaaauuuu..... ](*,).

ignore him