|
Titlul: 079 Frac Scris de: Mircea Pasoi din Iulie 10, 2005, 23:42:48 Aici puteţi discuta despre problema Frac (http://infoarena.ro/problema/frac).
Titlul: 079 Frac Scris de: PopDragos din Decembrie 02, 2005, 17:25:21 Imi poate da cineva o idee la problema asta, io am incercat cu cmmdc si iau 20 de puncte cu TLE pe celelalte.
am cautat pe internet shi nu am gasit nimic mai rapid ,desi e cam greu cand nu stiu ce sa caut ](*,) ](*,) Titlul: 079 Frac Scris de: Filip Cristian Buruiana din Decembrie 02, 2005, 17:42:46 Hint: cautare binara
Titlul: 079 Frac Scris de: PopDragos din Decembrie 02, 2005, 18:06:24 Mai ce promt esti :)
Nu ma asteptam asa de repede la un raspuns. Multam de idee cine stie poate o sa iau si eu 100 p in cele din urma Titlul: 079 Frac Scris de: Adriana Sperlea din Decembrie 02, 2005, 22:10:36 Care-i complexitatea oficiala? :-k
Titlul: 079 Frac Scris de: u-92 din Decembrie 02, 2005, 22:34:05 probabil n*log(n)
Titlul: 079 Frac Scris de: Filip Cristian Buruiana din Decembrie 03, 2005, 12:31:35 Nu.. Nu e N log N... Complexitatea e un pic mai "ciudata"... :peace:
Titlul: 079 Frac Scris de: PopDragos din Decembrie 03, 2005, 18:09:10 Desi pare cam prosteasca intrebare o sa o pun sa nu mor prost
ce trebuie cautat binar ca eu tot nu m-am prins intre timp am gasit o rezolvare de 60p cu ajutorul unor obs matematice dar ce trebuie sa fac sa iau shi eu 100 la pb asta ca ma dispera deja Titlul: 079 Frac Scris de: Filip Cristian Buruiana din Decembrie 03, 2005, 19:05:36 Trebuie sa cauti binar rezultatul, ce altceva?... Oricum, pot sa te intreb ce observatie matematica ai gasit? :wink:
Titlul: 079 Frac Scris de: PopDragos din Decembrie 03, 2005, 20:25:39 1. am observat ca toate numerele prime cu n mai mari ca n sunt au forma
NrPrimcun[i+n]=NrPrimcun+n 2. am observat ca exista o simetrie intre nr prime cu n mai mici ca n (lucru care reduce cautarea la jumatate) Si am folosit un algoritm asemanator cu Ciurul lui Eratostene si descompunera in factori primi a lui n pentru a gasi nr prime cu n. Titlul: 079 Frac Scris de: Rus Cristian din Decembrie 03, 2005, 22:57:09 e destul de logica observatia ta...
Titlul: 079 Frac Scris de: u-92 din Decembrie 03, 2005, 23:00:14 alt hint: de fapt, m-am gandit mai bine si l-am scos ca ar deveni poate prea evident :P
Titlul: 079 Frac Scris de: BloodyDemon din Martie 13, 2006, 23:43:22 Folosesc unsigned long long si iau doar 80 de p. :? Long long n-ar trebui sa mearga, nu e pe 64 biti?
Am tot incercat sa schimb pe double, dar asa nu merge descompunerea in factori primi...mai exact operatia modulo. Corect me if I'm wrong. Voi cum ati facut? :-({|= Titlul: 079 Frac Scris de: u-92 din Martie 14, 2006, 00:44:20 daca ai rezolvat corect, ar trebui sa mearga cu long long fara nici o problema
Titlul: 079 Frac Scris de: BloodyDemon din Martie 14, 2006, 16:13:12 cred ca am rezolvat-o corect, din moment ce am luat 80 p.
Folosesc long long...nici nu-mi citeste numarul pe cel mai rau caz: 12000000000. :cry: :-({|= Titlul: 079 Frac Scris de: u-92 din Martie 14, 2006, 19:16:37 daca nu ai luat 100 sigur nu ai rezolvat-o corect :)
cum citesti un long long? eu am folosit Cod: scanf("%lld\n", &x)si a mers. Titlul: 079 Frac Scris de: Filip Cristian Buruiana din Martie 14, 2006, 20:05:44 Citat din mesajul lui: BloodyDemon cred ca am rezolvat-o corect, din moment ce am luat 80 p. Folosesc long long...nici nu-mi citeste numarul pe cel mai rau caz: 12000000000. :cry: :-({|= Ba ti-l citeste, daca citesti de exemplu scanf("%lld", &N). Cred ca tu totusi folosesti Borland, de aia nu poti vedea pe calculatorul tau daca citeste bine sau nu. Lasa long long indiferent daca esti in Borland, ca pe site oricum nu apare problema asta din moment ce se foloseste alt compilator. Oricum, mai trimite solutii in continuare poate iei 100 ;) Titlul: 079 Frac Scris de: BloodyDemon din Martie 15, 2006, 02:00:47 Finally...dupa 3 zile si 3 nopti de chiiin...100 puncte. :ok: la toate.
Folosesc Dev-Cpp. Citesc cu streamuri... Problema era aceasta: Cod: long long st = 1, dr = 100000000000000.0, mij; Daca scriu simplu dr = 100000000000000; da eroarea : integer constant is too large for 'long' type...deci am scapat cu un warning... Felicitari pt problema, filipb. :wink: Mersi de ajutor, u-92. :guitar: Titlul: 079 Frac Scris de: Cosmin Negruseri din Martie 15, 2006, 04:55:02 Daca pui x = 100..0L nu merge?
Titlul: 079 Frac Scris de: BloodyDemon din Martie 15, 2006, 12:10:12 Pe Dev-Cpp nu merge. In schimb, pe BorlandC merg toate variantele : 10...0, 100...0.0 si 100...0L.
:-k Titlul: 079 Frac Scris de: u-92 din Martie 15, 2006, 12:43:41 nu te baza pe long long in borlandc, ca nu este ;)
Titlul: 079 Frac Scris de: Lucian Boca din Martie 15, 2006, 16:04:43 cum se poate raspunde eficient la o intrebare de tipul "cate numere mai mici decat x sunt prime cu y?" (preferabil fara a-l factoriza pe y) :?
Titlul: 079 Frac Scris de: u-92 din Martie 15, 2006, 16:21:28 cam trebuie sa folosesti principiul includerii si excluderii.. altfel nu prea vad cum poti rezolva problema
Titlul: 079 Frac Scris de: Lucian Boca din Martie 15, 2006, 21:25:59 Citat din mesajul lui: u-92 cam trebuie sa folosesti principiul includerii si excluderii.. altfel nu prea vad cum poti rezolva problema exact la asta ma refeream :D inseamna ca solutia ar fi sa il factorizez pe n si pentru o intrebare de tipul "cate numere mai mici ca x si prime cu n sunt?" sa aplic includere/excludere pentru toti factorii primi obtinuti. numai ca apar s-ar putea sa apara prea multi factori primi in descompunerea lui n, si atunci aplicarea pricipiului includerii si excluderii e destul de :fighting: Titlul: 079 Frac Scris de: u-92 din Martie 15, 2006, 22:04:37 prea multi nu o sa apara ;) gandeste-te putin si o sa-ti dai seama de ce
Titlul: 079 Frac Scris de: spx4 din Martie 18, 2006, 16:21:52 daca se incearca principiul includerii si al excluderii apar
sume de produse care se identifica cu relatiile lui viette.se identifica polinomu pacolo si daca n=p1^a1 * p2^a2 *...*pk^ak atunci numarul de numere cu proprietatea cautata este phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk) probabil ca o abordare buna ar fi folosind stern-brocot tree sau secvente farey [Editat de bogdan2412: Nu mai posta de 2 ori consecutive.. Use the Edit button! ] Titlul: Raspuns: 079 Frac Scris de: Lucian Boca din Aprilie 02, 2006, 21:16:13 atunci numarul de numere cu proprietatea cautata este phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk) te referi la functia lui Euler phi(N), care returneaza numarul de intregi mai mici ca N si primi cu N. Problema era sa aflu cate numere mai mici ca x si prime cu n sunt.. Ideea ramane cam aceeasi, numai ca se modifica putin forma finala. Titlul: Răspuns: 079 Frac Scris de: Bozianu Ana din Septembrie 13, 2008, 06:57:36 Am si eu o nelamurire. Primesc urmatorul mesaj de eroare
Citat Compilare: user.cpp: In function 'void solve()': user.cpp:30: warning: left shift count >= width of type pentru linia : Citat left=0;right=1<<61; (0 puncte cu TLE pe toate testele dar asta se explica de moment ce am un while(right-left-1) si left=right=0) : Dupa ce inlocuiesc linia cu : Citat left=0;right=1;right<<=30;right<<=30;right<<=1; totul merge perfect (100 puncte ). Cele doua linii nu ar trebui sa aiba acelasi efect ? ( variabilele left si right sunt de tip long long ) L.E. 10x pauldb Titlul: Răspuns: 079 Frac Scris de: Paul-Dan Baltescu din Septembrie 13, 2008, 08:18:58 Operatia se calculeaza default pe int daca nu ai termeni ai ei long long (valoarea la care se face atribuirea nu conteaza).
Citat left=0;right=1;right<<=30;right<<=30;right<<=1; Asta poate fi inlocuit cu Cod: right = 1LL<<61 Titlul: Răspuns: 079 Frac Scris de: Petru Trimbitas din Mai 07, 2010, 16:30:26 Merge cu un euclid+ciur?
Titlul: Răspuns: 079 Frac Scris de: Alex Velea din Mai 30, 2011, 21:15:23 Tiberiu un ciur pana la 2^60 :-S
nu cred eu ma gandesc ca .. caut binar rezultatul ( sa il numai X ) ... X luand valoare intre 0 - 2^61 .. si pe un X anume calculez cate elemente se impart cu factorii primi ai lui N : ) folosind un pinex "clasic" daca X- nr care se divid > P .. x scade la jumatate : ) Titlul: Răspuns: 079 Frac Scris de: Paul-Dan Baltescu din Mai 30, 2011, 21:17:34 Bravo, rezolvarea ta e corecta! :) Dar nu are rost sa raspunzi la topicuri in care nu s-a mai scris de atata timp.
|