003 Fractii

[•LordAnta]

Cu ciurul eratostene afla elementele care sunt prime. Cum aflii numarul de fractii ireductibile, formate din numere care nu sunt prime? de exemplu cum aflii dac /9 e ireductibila, folosind ciurul?

[•bogdan2412]

YES! Am reusit s-o fac in sfarsit!  

@ LordAnta: Nu folosesti ciurul lui Eratostene pt a genera numerele prime, folosesti doar parcurgerea din k in k a unui vector. Good luck, eu m-am chinuit destul la ea  

[•dany3dx]

poate cineva sa-mi dea un indiciu mai concludent..... fara chestii de genul Ciurul lui X ci o idee....

[•domino]

poate cineva sa-mi dea un indiciu mai concludent..... fara chestii de genul Ciurul lui X ci o idee....

 :lol: , pai gasesti mai sus insirate mai multe idei care te pot ajuta in rezolvarea problemei... si ciurui lui Eratostene se invata la mate prin a 5-a, chiar n-ai auzit de Eratostene?  

[•malex]

dupa parerea mea am folosit un algoritm cel putin la fel de  rapid ca ciurul si totusi imi iese din timp... Ma complic incercand sa calculezi din 1 in 1 cate fractii ireductibile mai apar? eu am gasit o legatura cu divizorii(atentie ca nu numai cu divizorii)... am sa incerc sa calculez si cu eratostene ceea ce calculez eu:)

[•c0styn]

Stiu ca poate parea dubioasa intrebarea mea, dar cum ai reusit sa declari un vector de 1 mil de char? Eu primesc ceva de genul Array size too large!.
  Se poate si altfel decat dinamic?

[•bogdan2412]

Iti afiseaza asta probabil pentru ca folosesti Borland C++/Pascal pentru ati compila sursa. Evaluatorul iti compileaza sursa cu GNU GCC/Free Pascal, compilatoare de linux, care iti permit sa aloci mult mai multa memorie (16 mega in general). Tu fa problema sa mearga pt limite mai mici si trimite sursa cu vectoru de 1000000. Daca vrei compilatoare pentru Windows, care iti ofera memorie vrei tu (bazate pe cele pt linux) cauta DJGPP+RHIDE pt C (Rhide e un mediu de dezvoltare asemanator cu cel de la Borland) sau Free Pascal pentru Windows.

[•cristy]

hmm...care este cea mai eficienta metoda sa calculezi tot(n)? ca eu nu reusesc nicicum...la ultimele 3 teste imi iese din timp...
am incercat cu optimizarea lui wickedman..dar tot nu imi iese...pls..ziceti ceva...

[lambda]

Am probleme cu evaluatorul
Cred ca solutia mea este corecta, insa cu toate acestea atunci cand imi este evaluata apare un mesaj ca nu exista fisierul de iesire sau este raspuns gresit. Am trimis sursa de doua ori si mi-a aparut ca nu exista fisier de iesire, si am mai trimis-o o data si mi-a aparut ca raspunsul este gresit (asta fara sa fi modificat solutia).

[•Adriana_S]

deci mie imi merg absolut toate testele pe care le dau eu, toate testele din exemplu si testele care sunt puse mai sus. Intr-adevar imi iese din timp peste 500000 dar problema e ca atunci cand trimit sursa la 7 teste imi da raspuns gresit si la ultimele 3 TLE. Chiar nu pot sa inteleg... :cry:

[lambda]

Ma poate ajuta vreun admin sa rezolv  problema ?
Adica am rezolvat-o da nu stiu care-i problema cu WA ?
Apropo de ce peste n>100000 compilatorul imi da exit code 201 sau ceva de genul.

[•Adriana_S]

deci io folosesc tot(n), testele mele merg, testele kre sunt puse mai sus pe forum merg, doar ca imi iese din timp la ultimele 2, dar stiu ca mai trebuie optimizata. Cum sa optimizez daca mie imi da WA? Jur ca o iau razna. Am dat sursa mea unor persoane care au luat 100 la pb asta si au ramas perplexe. Orice teste incerc acasa merg.

[•Cosmin]

Daca pe calculatorul tau testele merg si pe infoarena nu s-ar putea sa fie compilatorul folosit de vina, incearca sa folosesti acelasi compilator ca si cel de pe site cand testezi

[•Adriana_S]

been there, done that M-am gandit ca s-ar putea sa fie de vina compilatoru si desi io nu-l am i-am dat sursa cuiva care il are si la el merg. Asa ca nu e compilatoru...o sa incerc sa rescriu sursa pentru ca de cateva ori chiar a dat rezultate cand am facut asta, poate e de la implementarea pe numere mari si nu-mi dau seama si daca nici asa nu merge incerc alt algoritm dar problema asta imi da dureri de cap mai mari decat cand am invatat prima oara backtracking :cry:

[•Cosmin]

Numere mari? Nu vad la ce ai avea nevoie de numere mari ...

[•Adriana_S]

pai avand in vedere ca pentru 1 milion rezultatu este 607927104783....nu stiu cum as putea sa obtin asta fara sa folosesc numere mari ca n-am intalnit inca tipu de date care sa retina sute de miliarde.

[•Dorin]

eu am facuto pe numere mici si am luat 100
incearca pe numere mici poate asa o sa iti iasa

[•Adriana_S]

o sa incerc, de fapt am incercat si am trimis sursa dar evaluatoru nu pare sa mearga momentan...daca merge fara numere mari dau cu tastatura in monitor

[•Dorin]

nu are rost sa te enervezi pacat de tastatura si de monitor  

[u-92]

n-am intalnit inca tipu de date care sa retina sute de miliarde.

tipul este long long

[•Cosmin]

Si daca lucrezi in freepascal ai comp sau int64, pe care incap lejer sute de miliarde.

[•Adriana_S]

mersi mult pentru long long (lucrez in c++), am trimis sursa si fara numere mari si guess what...tot raspuns gresit...e chiar trist...

[•LucAnd]

mie tipul long long imi merge cam pana la in jur de 10 miliarde , si folosesc dev c++ , cum sa-mi mearga cu sute de miliarde ??
si de ce tipul long long , ca acelasi lucru se intampla si cu simplu long

[•calinux]

Pai... este o diferenta... daca vrei sa vezi singur care, ca poate nu ma crezi.... fa un:

Cod:

printf("%d %d\n",sizeof(long),sizeof(long long)); 

Asa iti va afisa marimea in bytes. Daca totul e ok, ar trebui sa dea 4 8. Adica 4*8=32 si 8*8=64. Cel putin asa da pe linux   Oricum... asta e diferenta... adica destul de mare.

Bafta!

[•LucAnd]

asa este si atunci totusi dece cand scrii programu
 

Cod:

#include <iostream.h>
#include <conio.h>
int main ()
{
  long long x;
  x=100000000000;
  cout<<x;
  getch();
  return 0;p
    
}

imi zice ca cica e prea mare numaru , normal 64 de biti presupune 20 de cifre iar 32 in jur de 10-11