infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 19:58:03



Titlul: 003 Fractii
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 19:58:03
Aici puteţi discuta despre problema Fractii (http://infoarena.ro/problema/fractii).


Titlul: Raspuns: 003 Fractii
Scris de: Luca Alex-Dan din Martie 12, 2004, 22:41:08
Asa ca... La fractii trebui sa fie o formula nu? Yes or no answer please... :mrgreen:   8)


Titlul: Raspuns: 003 Fractii
Scris de: Mircea Pasoi din Martie 12, 2004, 23:39:26
Nu. Si nu mai scrie cu text mare ca nu suntem orbi...


Titlul: Raspuns: 003 Fractii
Scris de: Luca Alex-Dan din Martie 13, 2004, 00:03:58
Ok, mersi pentru raspuns. (si amabilitate  8) )


Titlul: Raspuns: 003 Fractii
Scris de: VladS din Martie 27, 2004, 14:19:16
Am si eu o intrbare ce dimensiune au testele de la problema asta. Eu
mi-am luat 0 cu un algoritm zic eu destul de eficient. Are o comlezitate
<n*n


Titlul: Raspuns: 003 Fractii
Scris de: Dan-Leonard Crestez din Martie 27, 2004, 14:58:04
n*n e enorm pentru problema asta.


Titlul: Raspuns: 003 Fractii
Scris de: Andrei G�nczi in C++ :D din Martie 27, 2004, 17:29:25
shi totushi... ce complexitate ar trebui sa aiba fractii?  :?: mersi...


Titlul: Raspuns: 003 Fractii
Scris de: Mircea Pasoi din Martie 27, 2004, 17:32:59
O complexitate O(N * lg N) intra in timp.. desigur, poti sa faci si mai putin  :lol:


Titlul: Raspuns: 003 Fractii
Scris de: Andrei G�nczi in C++ :D din Martie 27, 2004, 17:49:33
:roll: i'm a bit confused.... de unde imi apare mie logN? merg de la 1 la n shi calculez pt fiecare in logN? shi le adun? sec... dar faina problema..


Titlul: Raspuns: 003 Fractii
Scris de: Mircea Pasoi din Martie 27, 2004, 18:07:06
Nu e bine sa spui o complexitate si apoi sa incerci sa-ti imaginezi rezolvarea pornind doar de la complexitate... pur si simplu, incearca sa gasesti o rezolvare care se incadreaza in timp  :roll:


Titlul: Raspuns: 003 Fractii
Scris de: Liceul de informatica Stefan Odobleja , Craiova din Mai 05, 2004, 11:33:56
incercati ciurul lui Eratostemos. Merge in NlogN si da faci cum trebuie iese bine. Eu asa am facut de 100 de puncte


Titlul: Raspuns: 003 Fractii
Scris de: Anton Alexandru din August 20, 2004, 23:27:36
ce spune ciurul lui Eratostemos sau unde pot gasi informatii despre continutul ei?


Titlul: Raspuns: 003 Fractii
Scris de: Mircea Pasoi din August 23, 2004, 14:51:14
Citat din mesajul lui: LordAnta
ce spune ciurul lui Eratostemos sau unde pot gasi informatii despre continutul ei?


Ciurul lui Eratostene e o metoda de complexitate O(N*lg N) pentru a determina toate numerele prime <= N. Se invata la mate prin clasa a 5-a cred  :P . Ideea e sa tii un vector de true sau false si pt fiecare numar i sa marchezi toti multiplii sai <= N ca fiind true. Valorile care raman false vor fi numere prime. Complexitatea este O(N*lg N) fiindca 1/1 + 1/2 + 1/3 + ... + 1/N = O(lg N), iar memoria folosita este O(N). Ca fapt divers s-a demonstrat ca ciurul lui Eratostene are o complexitate Theta(N*lg lg N); de asemenea se poate reduce memoria folosita la O(sqrt(N)), dar asta n-are legatura cu problema  :)


Titlul: Raspuns: 003 Fractii
Scris de: Anton Alexandru din August 24, 2004, 00:12:57
Ideea cu ciurul lui Eratostene ii foarte interesanta, dar nu stiu cum de s-o ajuns de la Eratostene la Eratostemos. Sarmanul matematician, se invarte in mormant la cat i-am stalcit numele!!! :lol:


Titlul: Raspuns: 003 Fractii
Scris de: Cont de teste din Noiembrie 19, 2004, 19:32:43
http://mathworld.wolfram.com/TotientFunction.html

aici gasiti indicatii.

poate va ajuta la fractii   :D


Titlul: Raspuns: 003 Fractii
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 29, 2005, 14:45:54
Mircea, poti sa pui te rog un test de la problema asta (mai mic) pe forum. Am trimis nushtu cate rezolvari, cu doua metode total diferite si n-am luat nici un punct. Nu prea inteleg unde gresesc, tot ce am dat eu a mers. :(


Titlul: Raspuns: 003 Fractii
Scris de: Silviu-Ionut Ganceanu din Ianuarie 29, 2005, 19:29:02
N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783

Sper sa fi copiat bine :)
Succes!

Silviu


Titlul: Raspuns: 003 Fractii
Scris de: Liviu Bunda din Februarie 07, 2005, 11:42:42
pana la 1.000.000 sunt 78.498 de numere prime. am scris un algoritm pe baza ca stiu toate cele R numere prime <= N si ca numarul de fractii il memorez intr-un vector de 14 cifre. nuj cum ati facut voi exact dar io am folosit functia totentiala conform formulei rezultat(N)=1+2*(tot(2)+tot(3)+...+tot(N)); functia totentiala intoarce numarul de numere < N si relativ prime la N.
multumesc anticipat :)


Titlul: Raspuns: 003 Fractii
Scris de: Silviu-Ionut Ganceanu din Februarie 07, 2005, 12:12:30
Suna ceva mai complicat decat este necesar dar e pe aceeasi idee. Totusi, a mers pan la urma ?


Titlul: Raspuns: 003 Fractii
Scris de: Liviu Bunda din Februarie 07, 2005, 16:10:52
nu prea a mers...adik nu am dus-o pana la capat. folosind chestia care am postat-o mai devreme si un algoritm simplu de generare a numerelor prime am aplut vectorul cu numere prime...problema este ca a facut asta in 5,171 sec  :(  .... deci metoda asta pica ... nu era destul de clar post-ul precedent dar era vorba de o intrebare...cat de simplu se poate rezolva problema si cum.ma tot gandesc la chestia cu ciurul lui erastotene si o sa implementez o rezolvare sugerata mai sus cu 0 si 1. ramane insa intrebarea cu memoria, dc fac aja ajung sa folosesc 1 mega de HEAP numai pentru vectorul semafor. mi se pare exagerat de mult.pls dc stiti o idee mai simpla da-ti un reply pls.
tx again  :wink:


Titlul: Raspuns: 003 Fractii
Scris de: Silviu-Ionut Ganceanu din Februarie 07, 2005, 17:17:51
Pai ai memorie multa. E okay daca declari un vector de 1 milion de int-uri. Acum ca stii asta gandeste-te cum iti optimizezi solutia.


Titlul: Raspuns: 003 Fractii
Scris de: Cristian Strat din Februarie 07, 2005, 18:46:51
daca vrei sa folosesti functia totient si sa optimizezi timpul de executie te poti folosi de urmatoarele egalitati:

t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
si
daca p numar prim, p NU divide a,
t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)

deci, daca la un moment dat stii t(1), t(2) ... t(n) poti calcula t(n + 1) gasind un singur divizor prim al lui n + 1


Titlul: Raspuns: 003 Fractii
Scris de: Liviu Bunda din Februarie 07, 2005, 23:40:02
okay, de data asta am pus algoritmul in practica si merge...numai ca la 7 din 10 teste imi depaseste timpul d exec. incerc sa optimizez formula si algoritmul in sine. oricum, a mers vectorul de 1 mil de char...amazing  :P...
am citit si reply-ul tau wickedman...dupa ce am facut prima implementare si am scos si io formulele alea. m-am lovit insa de o noua problema. chiar vreau sa tin minte toate valorile obtinute in functiile totentiale precedente lui n+1 ? la fel, ma lovesc de probleme cu memoria si scrierea algoritmului. oricum as incerca sa fac sunt aproape convins ca nu pot sa scot 100 de puncte. voi ce alta abordare a problemei imi recomandati ?


Titlul: Raspuns: 003 Fractii
Scris de: Silviu-Ionut Ganceanu din Februarie 08, 2005, 01:44:51
Bai nene.. nu-ti fie frica sa folosesti memorie.. este la greu .. 16 Mega cel putin. Lafaiala :).. Declara vectori de care vrei cum vrei numai sa mearga mai bine. Ce a spus wickedman, daca implementezi direct, cu un vector de int-uri oricat de mare ti s-ar parea, intra in timp.

Asa ca treci la lucru :)


Titlul: Raspuns: 003 Fractii
Scris de: Liviu Bunda din Februarie 08, 2005, 10:13:47
am reusit intr-un final dar nu am mai folosit alea pt ca imi complicau mult treaba.pur si simplu calculam folosind ciurul lui eratostene si adaugam la numarul mare.am luat 100 de puncte.tx again pt sfaturi.


Titlul: Raspuns: 003 Fractii
Scris de: Anton Alexandru din Februarie 25, 2005, 21:38:04
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????


Titlul: Raspuns: 003 Fractii
Scris de: Bogdan-Cristian Tataroiu din Februarie 26, 2005, 09:50:04
YES! Am reusit s-o fac in sfarsit!  \:D/

@ 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  :)


Titlul: Raspuns: 003 Fractii
Scris de: Daniel Markovits din Martie 09, 2005, 22:14:13
poate cineva sa-mi dea un indiciu mai concludent..... fara chestii de genul Ciurul lui X ci o idee.... :shock:


Titlul: Raspuns: 003 Fractii
Scris de: Mircea Pasoi din Martie 09, 2005, 22:16:44
Citat din mesajul lui: dany3dx
poate cineva sa-mi dea un indiciu mai concludent..... fara chestii de genul Ciurul lui X ci o idee.... :shock:


 :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?  8-[


Titlul: Raspuns: 003 Fractii
Scris de: Munteanu Alexandru din Martie 09, 2005, 22:50:16
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:)


Titlul: Raspuns: 003 Fractii
Scris de: Zaharia Costin din Aprilie 11, 2005, 16:55:02
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?


Titlul: Raspuns: 003 Fractii
Scris de: Bogdan-Cristian Tataroiu din Aprilie 11, 2005, 17:41:08
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.


Titlul: Raspuns: 003 Fractii
Scris de: Rus Cristian din Iulie 06, 2005, 13:55:40
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...


Titlul: Raspuns: 003 Fractii
Scris de: lambda din Septembrie 14, 2005, 20:31:40
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).


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 14, 2005, 20:58:53
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:


Titlul: Raspuns: 003 Fractii
Scris de: lambda din Septembrie 15, 2005, 16:44:16
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.


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 15, 2005, 20:30:39
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. ](*,)


Titlul: Raspuns: 003 Fractii
Scris de: Cosmin Negruseri din Septembrie 15, 2005, 23:00:08
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


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 16, 2005, 12:51:49
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:


Titlul: Raspuns: 003 Fractii
Scris de: Cosmin Negruseri din Septembrie 16, 2005, 14:28:09
Numere mari???? Nu vad la ce ai avea nevoie de numere mari ...


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 16, 2005, 15:18:14
:-k 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.


Titlul: Raspuns: 003 Fractii
Scris de: Oltean Dorin din Septembrie 16, 2005, 15:37:57
eu am facuto pe numere mici si am luat 100
incearca pe numere mici poate asa o sa iti iasa :mrgreen:


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 16, 2005, 16:18:50
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 :D


Titlul: Raspuns: 003 Fractii
Scris de: Oltean Dorin din Septembrie 16, 2005, 16:34:20
nu are rost sa te enervezi pacat de tastatura si de monitor  :mrgreen:


Titlul: Raspuns: 003 Fractii
Scris de: u-92 din Septembrie 16, 2005, 17:53:53
Citat
n-am intalnit inca tipu de date care sa retina sute de miliarde.

tipul este long long


Titlul: Raspuns: 003 Fractii
Scris de: Cosmin Negruseri din Septembrie 16, 2005, 18:39:19
Si daca lucrezi in freepascal ai comp sau int64, pe care incap lejer sute de miliarde.


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 16, 2005, 19:22:06
mersi mult pentru long long (lucrez in c++), am trimis sursa si fara numere mari si guess what...tot raspuns gresit...e chiar trist...


Titlul: Raspuns: 003 Fractii
Scris de: Lucescu Andrei Bogdan din Septembrie 21, 2005, 16:44:53
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


Titlul: Raspuns: 003 Fractii
Scris de: Iorgulescu Calin din Septembrie 21, 2005, 19:26:09
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  :wink: Oricum... asta e diferenta... adica destul de mare.

Bafta!


Titlul: Raspuns: 003 Fractii
Scris de: Lucescu Andrei Bogdan din Septembrie 21, 2005, 21:08:49
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


Titlul: Raspuns: 003 Fractii
Scris de: Lucescu Andrei Bogdan din Septembrie 21, 2005, 21:12:22
am rezolvat problema totu se datora faptului ca nu poti atribiu unei variabile direct un numar mai mare de 32 biti , habar n-aveam de treaba asta , bine ca acuma stiu pe viitor


Titlul: Raspuns: 003 Fractii
Scris de: Cosmin Negruseri din Septembrie 21, 2005, 23:59:54
:) ba poti si faci asa: x = 1000000000000000L;


Titlul: Raspuns: 003 Fractii
Scris de: Lucescu Andrei Bogdan din Septembrie 22, 2005, 14:11:49
Am incercat faza cu 1000000000000L si nu merge


Titlul: Raspuns: 003 Fractii
Scris de: Cosmin Negruseri din Septembrie 22, 2005, 18:20:40
Nu am compilator aici da tre sa mearga, incearca cu ll in coada ... si nu mai astepta mura in gura pt chestii simple, deschide si tu o carte de C/C++ la tipul long long sau manualul cu documentatie sau cauta pe net. Faptul ca ti-am spus ca se poate ar fi trebuit sa te motiveze sa iti pierzi 5 minute cautand o solutie nu sa incerci ce am zis eu, vezi ca nu merge in 10 secunde si esti multumit sa scrii pe forum ca nu ai reusit sa te descurci.


Titlul: Raspuns: 003 Fractii
Scris de: Dan-Constantin Spatarel din Decembrie 04, 2005, 07:14:47
Eu fac alfel, si merge intotdeauna ;)

X = (__int64)1000000000 * 1000000000;
sau
X = (long long)1000000000 * 1000000000;
Incearca si:
X = (__int64)1000000000000000000;
sau
X = (long long)1000000000000000000;
dar nu garantez pentru asta.

Tipul folosit difera in functie de compilator ;)
Spor!


Titlul: Raspuns: 003 Fractii
Scris de: Sima Mihai Cotizo -vechi din Decembrie 16, 2005, 22:15:34
scuze ca intrerup... dar int64 parca este tip cu semn... ia dati un qword in free pascal si aveti un tip fara semn pe 64 de biti care merge pana la 18446744073709551615 (vreo 18.446.744.073 miliarde...) Cred ca  e ceva mai mare...
Bine, nu cred ca ar fi diferenta semnificativa dar...


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Ioan Fanica din Ianuarie 19, 2006, 00:59:19
De ce cand scriu long long si ce vreau sa declar in c++5.02 imi da ceva de tipul too many types in declaration. De ce nu merge?
Si se poate declara ceva de genul int64 n,i,...,a[100] in c++5.02?
sau trebuie sa declar la fiecare variabila in parete x=(long long)100000000000 sau x=(__int64)100000000000000000?


Titlul: Raspuns: 003 Fractii
Scris de: Valentin Stanciu din Ianuarie 19, 2006, 19:14:55
scuze, dar eu nu am auzit de c++5.02.... fii si tu mai explicit! C++ este un limbaj; iar versiunea 5.02 de la ce e... ce compilator?! Borland C++ 5.02? Visual Studio C++ 5.02?! GNU C++ 5.02...


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Ioan Fanica din Ianuarie 19, 2006, 20:41:14
Este  versiunea Borland C++ 5.02 dar am uitat sa scriu acest lucru.
Am scris din nou __int64 x si merge, dar acum stiu de ce nu merge long long.Acesta nu merge decat in linux.Am sa scriu sursa cu long si am sa trimit cu long long. Multumesc oricum pentru informatii. :thumbup:


Titlul: Raspuns: 003 Fractii
Scris de: u-92 din Ianuarie 19, 2006, 21:01:34
si peste tot unde ai long o sa pui long long? sau eventual bagi un typedef, dar tot trebuie sa modifici la afisare.. e cam complicat

cel mai bine iti compilezi sursele cu gcc.. poti incerca sa folosesti RHIDE, este foarte asemanator cu borlandc, mai multe detalii aici: http://www.delorie.com/djgpp/


Titlul: Raspuns: 003 Fractii
Scris de: Condrea Andrei din Martie 07, 2006, 17:24:29
mircea am si eu o intrebare: am o rez in O(n*n)....am auzit ca e prea mare si trebuie in n log n
da da si u o idee  ....pls...nush de unde sa iau log n  ](*,) . doar in ciurul lui eratostene am cu log n da nush cum mi ar folosi asta aici........


Titlul: Raspuns: 003 Fractii
Scris de: u-92 din Martie 07, 2006, 18:28:58
topicul asta are 2 pagini.. daca citesti atent prima o sa gasesti o gramada de indicii.. avand ciurul lui eratostene poti determina pt un numar x, numarul de numere prime cu el mai mici decat el


Titlul: Raspuns: 003 Fractii
Scris de: Adrian Dobrescu din Aprilie 06, 2006, 11:37:25
Nu stiu de ce timpul maxim este 2 secunde la problema asta.
am facut problema asta fara sa trag timpul de par in vr-un fel.
Iata timpiii:::::

Cod:
TEST 1	...[0.05s]...	Ok!
TEST 2 ...[0.01s]... Ok!
TEST 3 ...[0.01s]... Ok!
TEST 4 ...[0.01s]... Ok!
TEST 5 ...[0.03s]... Ok!
TEST 6 ...[0.07s]... Ok!
TEST 7 ...[0.15s]... Ok!
TEST 8 ...[0.30s]... Ok!
TEST 9 ...[0.47s]... Ok!
TEST 10 ...[0.65s]... Ok!


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Aprilie 06, 2006, 12:42:03
pai ce complexitate ai scos?


Titlul: Raspuns: 003 Fractii
Scris de: Adrian Dobrescu din Aprilie 06, 2006, 14:02:52
Aprox. O(n+n*logn). Ceva mai mult.


Titlul: Raspuns: 003 Fractii
Scris de: Sfrent Andrei din Iunie 23, 2006, 12:33:11
Eu nu inteleg ce se intampla la problema asta...
Imi scapa vreun caz particular? (Exista asa ceva?) timpul de executie e bun, 4 teste merg, restul Wrong Answer... imi puteti da si mie un exemplu mai ciudat care sa imi fi scapat?
am rezolvat folosind descompunerea in factori primi a fiecarui numar <n si calculez functia totentiala pentru fiecare si o adun la rezultat... care sa fie problema? :? :-k


Titlul: Raspuns: 003 Fractii
Scris de: Filip Cristian Buruiana din Iunie 23, 2006, 12:48:59
Vezi k rezultatul tau depaseste int/long, trebuie sa pui long long la toate calculele ( sau int64 in Pascal ). De exemplu pentru 1 000 000 cat iti da?... Ar trebui sa obtii 607927104783...


Titlul: Raspuns: 003 Fractii
Scris de: vladut.forum din August 21, 2006, 10:29:38
thanks Cosmin.ro

inca cand eram in ro, incercam la asta cu include si exclude ... da luam niste TLE-uri :| si m-am lasat...

acum am vazut postu lui Cosmin.ro la top5 probleme, ca a facut cu include si exclude ... si am zis ca sigur mere... daca a facut cineva

asa ca m-am reapucat... si am scoso de 100  :yahoo: :yahoo: :yahoo:

traiasca I/E...

thanks Cosmin.ro again!!


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 26, 2006, 10:31:30
Am si eu o intrebare.Care este formula generala a functiei totient?O fi asta :
"
By induction, the general case is then
t(n)=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r))."
atunci cine sunt p1 p2 ..pr? :?
De asemenea explicati-mi si mie ce este logaritmul(sunt mai nou in acest domeniu al informaticii).Din cate stiu eu,logaritmul este o putere la care trebuie rdicat un nr,pt a obtine alt numar.Va rog explicati-mi si mie cum pot folosi aceascta proprietate pentru a obtine o complexitate mai mica ,adica n* log n,ca eu am n*n,care am inteles ca e prea mare,si imi iese din timp.De asemenea am mai vazut pe cineva care a scris ca avand ciurul lui Eratostene se poate obtine numarul de numere prime cu n si mai mici decat n.asta nu cumva e la functia totient? #-o Va rog ajutati-ma  :'(



Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Septembrie 26, 2006, 15:26:25
p1, p2 .. pr sunt numere prime.

Folosind ciurul lui eratostene poti afla in timp logaritmic numarele prime mai mici decat n.

Vezi ca tot undeva pe acest topic erau niste recurente postate de wickedman, care sunt foarte bune.

PS: poti sa cauti intrun manual de clasa a-X-a de mate despre logaritmi


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 26, 2006, 19:34:59
Am inteles esenta :cu ciurul lui Eratostene calculezi numerele prime mai mici decat n,iar valorile care le returneaza aceasta functie sunt folosite pentru a calcula tot(n).Dar am o indoiala in privinta functiei totient .De ex sa calculam tot(9):
-numerele prime mai mici decat 9 sunt 2,3,5,7.
-formula generala este tot(n)=n*(1-1/p1)*(1-1/p2)...(1-1/pr).inlocuind numerele obtinem: tot(9)=9*(1-1/2)*(1-1/3)*(1-1/5)*(1-1/7).Facand calculele obtinem rezultatul urmator: 432/210(fractia se mai poate simplifica),dar acest numar nu este intreg,cum se poate asa ceva?.De asemenea ce semnifica pr,cel mai mare numar prim care se afla in intervalul 1,2,3....n?
PS:abia am trecut intr-a 9a,nu am facut nici o ora de info inca,in afara ca ne-am cunoscut profesoru,si stii cum e in prima ora :thumbup:


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Septembrie 26, 2006, 19:52:01
nu e vb de numerele prime mai mici decat n ci de cele care se divid.

Ptr exemplu tau cu 9:
tot(9) = 9*(1-1/3) =  9*(2/3) = 6 (cele 6 numere sunt 1,2, 4,5,7,8)

Succes de aici inainte


Titlul: Raspuns: 003 Fractii
Scris de: Adrian Vladu din Septembrie 26, 2006, 19:59:11
Man, just an advice!  :peace:

Te sfatuiesc sa nu te apuci de problema asta daca nu stapanesti notiunile de matematica necesare, altfel toata munca ta s-ar reduce efectiv la implementare, ceea ce nu consideram ca are de a face cu Computer Science (scopul spre care se indreapta toate aceste probleme). Pentru cineva care abia a inceput a 9-a este onorabil ca te-ai incumetat la "Fractii"  :thumbup: dar asta presupune inainte si putina cercetare :)

Iata cateva notiuni de aprofundat si de inteles, necesare acestei probleme:
* numere relativ prime
* factorizarea numerelor naturale
* ciurul lui Erathostene
* formula generala (functia Totient a lui Euler), cand intelegi demonstratia si reusesti sa o refaci singur  :thumbup:
* formula recursiva pentru calculul numarului de numere relativ prime cu un numar dat, mai mici decat acesta
* solutia finala :D

Spor  :clover:


Titlul: Raspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Septembrie 26, 2006, 20:03:18
Se divid cu cine?  :eyebrow:

[cred ca vrei sa spui numerele prime cu N mai mici ca N, ca dupa stiinta mea, toate numerele se divid :) ]

Pentru eddy: Vezi ca sunt useri pe prima pagina in clasa IX-a, so give us a break.


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 26, 2006, 20:45:50
La matematica nu am de ce sa imi fac probleme,de fiecare am fost la judeteana la olimpiada(n-am trecut mai departe ce-i drept),dar am luat odata locul 4.In rest ce sa va spun,in C stiu notiunile de baza:variabile,matrici,functii,bactracking,pointeri,am stat mult si am muncit pana acum,toate astea le-am invatat in aprox 2 luni,dar sa nu credeti ca am trecut prin ele ca prin branza,am facut la fiecare exercitii,etc.
PS:PaulDB s-o crezi tu ca toate numerele se divid...de ex ce 4 se divide cu 3?am sa iti dau si definitia matematica:un nr a se divide cu alt nr b daca si numai daca exista un nr c ,astfel incat a=b*c.zi si mie in cazul tau daca a=4, b=3 ,care este c?si mai incetul cu fraze din astea so give us a break.
Pt ceilalti multumesc de ajutor,in special devilkind,si azotlichid.  =D&gt;


Titlul: Raspuns: 003 Fractii
Scris de: Valentin Stanciu din Septembrie 26, 2006, 20:50:18
Numere prime cu N? 3 nu e prim cu 9 :P
Vrea sa spuna ca P1, P2.. sunt numerele prime mai mici ca N, care se divid cu N

vezi exemplu: Tot(36) = Tot(2^2 * 3^2) = 36 * (1 - 1/2) * (1 - 1/3) = 36 * 1/2 * 2/3 = 12

mai multe informatii se pot gasi pe wikipedia: http://en.wikipedia.org/wiki/Euler's_totient_function
... sau pe mathworld: http://mathworld.wolfram.com/TotientFunction.html

Btw, Paul, nu trebuie sa fii rau!

Later edit: Eddy, prin faptul ca ai fost la judeteana la mate nu inseamna ca stii mate! (un exemplu este sa tocesti tipuri de exercitii, dar sa nu poti gandi probleme 'din afara tiparului'). Informatica se imparte in mai multe domenii. Unul dintre ele este 'computer science', dupa cum zicea si azotlichid, acesta se ocupa cu studiul algoritmilor si eficentei programelor (..altii pot sa iti detalieze mai bine decat mine; daca doresti sa aflii). Prin faptul ca tu stii C nu inseamna ca stii 'computer science'. Aceasta este, teoretic, independenta de limbajul de programare (intr-o anumita masura). De aceea am si inteles ca s-a restructurat materia si in cls 9 nu se mai preda nici un limbaj de programare (se lucreaza in pseudocod).
Ideea este sa intelegi de aceasta problema se face cu ciurul lui Erathostene, ce face functia Totient (eventual sa intelegi in mare formula) si abia apoi sa ai cunosctintele de C necesare ca sa pui in practica toate acestea.


Titlul: Raspuns: 003 Fractii
Scris de: nivan din Septembrie 26, 2006, 21:20:04
   Faza cu olimpiada de mate nu prea are legatura cu ce a scris azotlichid.
   Adica ce a vrut azot lichid sa zica e sa incerci sa si intelegi de ce rezolvarea merge. Sa nu citesti intr-o carte(sau pe forum) cum se face, sa o implementezi, sa iei un punctaj considerabil si sa nu inveti nimic din ea.
   Eu unu am inteles ideea, dar n-am reusit sa o implementez de 100 pct... sucess si spor la  :weightlift:


Titlul: Raspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Septembrie 26, 2006, 21:44:04
N-am vrut sa fiu rau. Dar...

TOATE NUMERELE SE DIVID.

4 se divide cu 1,2 si 4. Deci 4 se divide cu ceva.


Titlul: Raspuns: 003 Fractii
Scris de: Andrei Grigorean din Septembrie 26, 2006, 21:45:46
am sa iti dau si definitia matematica:un nr a se divide cu alt nr b daca si numai daca exista un nr c ,astfel incat a=b*c.

sa mori tu?


Titlul: Raspuns: 003 Fractii
Scris de: u-92 din Septembrie 26, 2006, 22:46:17
nici un motiv sa va certati  :ok:
:peacefingers:


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 26, 2006, 23:00:00
Citat
Eddy, prin faptul ca ai fost la judeteana la mate nu inseamna ca stii mate! (un exemplu este sa tocesti tipuri de exercitii, dar sa nu poti gandi probleme 'din afara tiparului').
Crezi ca daca mergi la olimpiada la mate,trebuie sa ai niste modele de exercitii,care sa le inveti pe de rost,si apoi sa lucrezi dupa model?Sau trebuie sa stii sa ai o gandire foarte buna?Habar n-ai ce se da pe la geometrie cred.ma faci tu sa inteleg altceva despre tine dar nu mai zic nimic,ca vad ca orice as zice sunt interpretat ca am spus ceva rau.Cine stie matematica ,cei care raman repetenti?am avut si media 10 pe toti anii,niciodata nu am avut probleme cu matematica.Adica daca am fost la judeteana la mate,si am luat si un loc onorabil,inseamna ca nu stiu mate?ma cam indoiesc
Citat
Adica ce a vrut azot lichid sa zica e sa incerci sa si intelegi de ce rezolvarea merge.
Voi chiar ma credeti prost adica,voi credeti ca un tocilar ar avea sanse la o olimpiada de mate sau informatica,in care singurul lucru important este sa ai o gandire si o logica foarte buna?
Am inteles foarte bine algoritmul,insa am apelat la ajutorul vostru sa aflu forma generala a functiei totient,ca nu prea am inteles din linkul ala,ca erau foarte multe cazuri particulare.
Citat
sa mori tu?
Ia si mai invata matematica.Ia uite si un link aici http://www.referatele.com/referate/matematica/online2/Definitie-DIVIZIBILITATE--Divizor-si-multiplu-propriu-si-impropriu--Numere-prime-referatele-com.php (http://www.referatele.com/referate/matematica/online2/Definitie-DIVIZIBILITATE--Divizor-si-multiplu-propriu-si-impropriu--Numere-prime-referatele-com.php),sa iti arat dovada.
Oricum multumesc ca m-ati ajutat,nu am sa mai apelez la ajutorul vostru,ca vad ca sunt inteles gresit;daca nu ma ajutati voi,stateam si nu dormeam o saptamana intreaga si tot o rezolvam.Acum ma duc sa incerc sa implementez algoritmul.


Titlul: Raspuns: 003 Fractii
Scris de: Valentin Stanciu din Septembrie 26, 2006, 23:14:03
Nu stiu de ce te-ai suparat asa tare... ce am vrut sa zic este ca daca o persoana are note mari la scoala si daca a fost la olimpiada la X, NU implica automat ca chiar stie X! Invatamantul este de departe perfect! Dar NU m-am legat de tine!
Cunosc persoane olimpice la info care iau 8 in teza la info, cunosc colegi din generala care au avut 10 pe linie in generala, insa chair ei recunosteau ca sunt persoane mai destepte in materii ca matematica. Atat am vrut sa zic, ca nu este o relatie directa intre note-clasa si cat stie cu adevarat acea persoana.

Am mai incercat sa clarific termenul de 'computer science'.. de ce? pentru ca gradul de cunostiinta al unui limbaj de programare nu implica direct ca "rupi" de olimpiada la info. (de ex pointeri pot fi evitati uneori prin alte implementari, dar algoritmul sa fie la fel)

Repet, nu vreau sa iei totul asa personal, nu am zis ca nu stii info, nu am zis ca nu stii mate; poate am incercat sa te fac sa privesti putin altfel lucrurile!

De ajutat te-am ajutat pe cat am putut.. mai este ceva ce nu ai inteles?


Titlul: Raspuns: 003 Fractii
Scris de: nivan din Septembrie 26, 2006, 23:16:36
 Ai inteles gresit ce am vrut eu sa zis (si cred ca si ce au vrut altii sa zica, desi eu vorbesc doar in numele meu). Ce ai scris mai sus cu tocilar si restu... poi eu nu te cunosc pe tine deci in nici un caz nu am incercat sa insinuez ca esti nici prost nici tocilar.
 Cat despre chestia cu faptul ca nu mai apelezi la ajutorul celor de pe forum... nu vad dc? Nu imi pare ca in topicul asta a scris cineva ceva ofensiv la adresa ta (cum observ ca ai interpretat tu)...... ce am scris eu cu intelesul rezolvarii, pur si simplu un sfat, mie imi pare mesajul scris chiar intr-o maniera calda.
 Nu vreau sa vorbesc in numele altora... dar mie si majoritatea celorlalte mesaje imi pare scrise tot intr-o maniera calda cu scopul de a te ajuta. 
 
 Oricum deja asta devine off-topic (nu mai are legatura cu problema)... ce vreau sa zic e ca nu am incercat sa te jicnesc in nici un fel (direct sau indirect).  :peacefingers:


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 26, 2006, 23:40:48
Mii de scuze celor care au vrut sa ma ajute,care au avut intentii bune,dar cred ca eu am fost cel care a interpretat gresit lucrurile.Si scuze si celorlalti care  poate i-am jignit fara sa vreau.


Titlul: Raspuns: 003 Fractii
Scris de: Sima Mihai Cotizo -vechi din Septembrie 27, 2006, 07:38:16
Iata cateva notiuni de aprofundat si de inteles, necesare acestei probleme:
* numere relativ prime
* factorizarea numerelor naturale
* ciurul lui Erathostene
* formula generala (functia Totient a lui Euler), cand intelegi demonstratia si reusesti sa o refaci singur  :thumbup:
* formula recursiva pentru calculul numarului de numere relativ prime cu un numar dat, mai mici decat acesta
* solutia finala :D
Spor  :clover:

:shock: numerele alea relativ prime sunt tot aia cu numerele aproape prime, notiune data, din cate stiu eu, de Ciucu la ONI 2006? :D

PS, pt Eddie: Cum au mai zis-o toti, nu o mai lua asa personal, iar daca gasesti o definitie in referatele de pe internet, nu o lua ca e cea mai buna... si pe de alta parte,  nu trebuie sa consideri ca toti de pe infoarena nu se pricep la nimica altceva decat informatica (cum ai adus aminte in faza cu problemele de geometrie) ;) crede-ne ca in liceu e un pic altfel decat in gimnaziu si ca uneori mai stie lumea ce vorbeste legat si de olimpiadele de la alte materii (si de multe ori nu doar din auzite ;) )...


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 27, 2006, 07:58:46
:shock: numerele alea relativ prime sunt tot aia cu numerele aproape prime, notiune data, din cate stiu eu, de Ciucu la ONI 2006? :D

In engleza numerele prime intre ele se cheama 'relatively prime', deci presupun ca la asta se referea, altfel nu prea vad legatura cu problema. :)


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 27, 2006, 22:53:50
OK,am reusit si eu intr-un final sa ma incadrez in timpul de executie,folosind un alt algoritm,deoarece cel care l-ati implementat voi imi lua si mai mult decat cel initial(nu stiu daca v-am spus dar prima data comparam fiecare 2 numere mai mici ca n,si vedeam daca sunt prime intre ele cu algoritmul lui Euclid,dar imi iesea din timp),si incredibil fiecare test nu dureaza mai mult de 0.1 secunde,cu exceptia ultimelor 2 ,care dureaza 0,4 secunde  \:D/.Cu toate acestea nu inteleg de ce la toate obtin raspunsuri gresite,cu toate ca Silviug a pus un test pe prima pagina a topicului in care se da n-> rezultat,iar eu am introdus si eu aceleasi valori si am obtinut acelasi raspuns:
Citat
N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783
Am sa va spun si algoritmul pe care l-am folosit ,si inca un avantaj in afara de cel al timpului ar fi ca nici nu trebuie sa introduci mai mult de 25 de randuri.Deci sa va spun cum am gandit:
- se porneste de la fractia 1 / 1, aceasta constituind primul nivel
- pe al doilea nivel se trece sub prima fractie 1 / 2 in stanga, si 2 / 1 in dreapta
...........................
- pe un nivel oarecare x, sub fiecare fractie i / j din nivelul precedent, se trece i / (i + j) in stanga si (i + j) / j in dreapta.
Ex. n = 3
1 / 1
1 / 2 2 / 1
1 / 3 3 / 2 2 / 3 3 / 1.
Totusi imi puteti spune de ce obtin raspunsuri gresite?


Titlul: Raspuns: 003 Fractii
Scris de: Sima Mihai Cotizo -vechi din Septembrie 28, 2006, 14:38:20
... sigur merge... CORECT ?!? Mai fii atent si la afisare... poate gresesti acolo...


Titlul: Raspuns: 003 Fractii
Scris de: ditzone din Septembrie 28, 2006, 15:08:54
Raspunsul poate fi foarte mare esti sigur ca ai dat si testul
1000000 -> 607927104783
?


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 28, 2006, 19:05:46
La testul cu 1.000.000 nu imi merge ,imi da o eroare;ma gandesc ca asta ar fi din cauza ca eu am alocat doi vectori ,unul se numeste numitor,altul numarator,fiecare are cate 1000000 de elemente,si ca dimensiunea lor ar fi prea mare(am mai vazut vorbindeu-se despre asta pe prima pagina).Totusi la celelalte teste am raspunsul corect,sunt sigur 100%.Nu am inteles ce ai vrut sa spui Coty ,sa fiu atent la afisare poate gresesc acolo.cum adica?


Titlul: Raspuns: 003 Fractii
Scris de: Sima Mihai Cotizo -vechi din Septembrie 28, 2006, 19:24:52
Pai zic si eu, daca folosesti long long sa pui la afisare "%lld" in loc de "%ld" sau "%Ld"... sau treburi d-astea, minore... zic si eu, nu stiu sursa ta si nu sugerez nimica.
Pe de alta parte, ai zis ca ai doi vectori de 10000000 de elemente... stai calm, daca elementele sunt long (si long long cred ca merg), iti incap in memorie. Daca nu incapea iti dadea Segmentation Fault sau Invalid Memory Refference, parca... era un articol legat de erori pe http://info.devnet.ro... incearca sa te uiti pe forum si prin articolele de pe info.devnet legate de rhide... o sa te ajute daca lucrezi in C / C++, pentru ca scapi de anumite limitari pe care le ai in Borland...


 :clover:


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 28, 2006, 19:51:44
Pai asta imi da Invalid Memory Reference.Am voie sa postez codul?Am compilat cu Visual C++ 6.0


Titlul: Raspuns: 003 Fractii
Scris de: ditzone din Septembrie 28, 2006, 20:29:44
problema este ca raspunsul este mult mai mare decat cat ai alocat tu in vectorii aia, nu poti sa tii 607927104783 de elemente intr-un vector de 10000000 elemente....


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 28, 2006, 22:54:17
Dar chiar daca introduc si 5000 tot imi da eroare


Titlul: Raspuns: 003 Fractii
Scris de: ditzone din Septembrie 28, 2006, 23:07:32
Pentru ca si raspunsul pentru 5000 depaseste 10 000 000...


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 00:11:43
Ba nu depaseste,ca nu am folosit un algoritm de complexitate (n*n) sau (n*log n).Pur si simplu fiecare pozitie a vectorului numitor si numarator retine o fractie.De ex numitor[4]=4 ,numitor[3]=3,iar fractia este 3/4.alt ex :numitor[6]=8 numarator[6]=3,iar fractia este 3/8.


Titlul: Raspuns: 003 Fractii
Scris de: ditzone din Septembrie 29, 2006, 00:39:52
Ce vreau eu sa zic este ca nu poti sa retii toate fractiile in memorie pentru ca sunt prea multe...


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 08:58:38
De ce nu pot?Din cauza compilatorului BorlandC?SIlviug a zis ca e okay sa declari un vector cu 1 milion de int-uri.Atunci exista vreo solutie?


Titlul: Raspuns: 003 Fractii
Scris de: Sima Mihai Cotizo -vechi din Septembrie 29, 2006, 09:57:25
Pe infoarena este compilator Gnu C / C++ ... incearca sa cauti niste detalii despre el, daca nu esti familiarizat.
Ideea e ca oricat de multe ar putea tine in memorie programele compilate cu gcc/g++, au si ele o limita, setata pe infoarena la 64MB. Ce zice Ditzone cred ca se refera la faptul ca numarul tau de fractii o sa fie mai mare decat poti retine... Incearca sa calculezi de cata memorie ai nevoie.


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 10:29:14
Si atunci cum pot sa fac sa imi mearga?dar totusi intrebarea mea initiala era de ce nu imi da raspuns corect la testele cu numere mici?


Titlul: Raspuns: 003 Fractii
Scris de: nivan din Septembrie 29, 2006, 11:06:22
Pentru testele cu numere mici, nu stiu... dar tie ti-ar trebui un vector de 607927104783 nu de 1000000. Incearca sa rezolvi problema fara a generea sau a numara fractiile. Nu cred ca o sa-ti mearga pe principiul asta.......  :) Ideea e ca, chiar daca ai putea sa aloci un vector de 607927104783, nu ti s-ar mai incadra in timpul de executie programul (din cauza numarului mare de operatii).  :P


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 11:12:27
Deci tu imi sugerezi practic sa ma gandesc la un nou algoritm?Cred ca daca mi-ar merge sa aloc memorie unui vector de 607927104783,mi s-ar incadra in timp.Cel putin asa cred.


Titlul: Raspuns: 003 Fractii
Scris de: nivan din Septembrie 29, 2006, 11:17:19
 Poi intrucat tu completezi un vector de 607927104783, inseamna ca faci cel putin 607927104783 operatii (cred... sper ca nu zic vreo tampenie) si nush daca 607927104783 oferatii intra in timp... imi pare un numar destul de mare.  :) Da poate reusesti sa completezi mai repede(desi nu prea vad cum).... explica cum completezi tu fractiile. :)
 Daca metoda ta e ca din fiecare fractie x/y derivi alte 2 fractii.... nu cred ca va intra in timp.

[Last Edit] Daca chiar vrei sa mergi pe varianta asta, poti sa retii doar penultimul si ultimul rand din triunghiul ala de l-ai reprezentat pe pagina 4. Astfel cred ca iti va ajunge memoria.


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 11:37:04
Da asa fac dintr-o fractie deriva doua.Deci eu pornesc de la fractia 1/1.(la primul apel i=1 si j=1).Apoi pun un while si dau conditia ca atata timp cat in vectorii numitor si numarator mai exista o fractie a caror suma sa fie mai mica ca n,din fractia gasita,sa derive alte doua.Sper ca m-am facut inteles destul de bine.Daca nu,am voie sa postez codul?


Titlul: Raspuns: 003 Fractii
Scris de: nivan din Septembrie 29, 2006, 11:45:28
Am inteles, cat despre cod... mai demult era voie, acum nu mai stiu. Oricum nu cred ca se supara nimeni ca-l posetezi, doar sa nu postezi solutii de 100 puncte.
Eu unu chiar as fi curios legat de codul tau, in primul rand ce complexitate are, desi mie imi pare destul de maricica, din cate ai postat pan' acu.  :)


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 12:00:36
asta e codul :

Cod:
#include <stdio.h>
int main()
{
unsigned long *numitor,*numarator;
numitor=new unsigned long[1000000];
numarator=new unsigned long[1000000];
int k,n;
numarator[1]=1;numitor[1]=1;k=1;
scanf("%d",&n);
int gata=0;
while(!gata)
{gata=1;
for(int i=k;i<=k;i++)
if(numarator[i]+numitor[i]<=n)
{k++;
numitor[k]=numarator[i]+numitor[i];
numarator[k]=numarator[i];
k++;
numarator[k]=numitor[i]+numarator[i];
                 numitor[k]=numitor[i];
                 gata=0;
}
}
printf("%ld\n",k);
return 0;
}


Titlul: Raspuns: 003 Fractii
Scris de: Adriana Sperlea din Septembrie 29, 2006, 17:59:47
Tu stii ca nu folosesti fisiere nu? Adica nu ai trimis codu' chiar asa, right? :)


Titlul: Raspuns: 003 Fractii
Scris de: Andrei Grigorean din Septembrie 29, 2006, 19:15:11
Deci tu imi sugerezi practic sa ma gandesc la un nou algoritm?Cred ca daca mi-ar merge sa aloc memorie unui vector de 607927104783,mi s-ar incadra in timp.Cel putin asa cred.

ti-ar intra in timp.. daca ar fi timpul de executie cateva luni :).

ca sa rezolvi corect aceasta problema cel mai bine e sa urmezi sfaturile pe care ti le-a dat azotlichid in topicul pe care l-ai creat tu.  :ok:


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Septembrie 29, 2006, 19:16:44
Bineinteles ca nu am trimis asa.
Deci trebuie sa ma gandesc din nou cum sa optimizez algoritmul care l-ati implementat voi.
Am o intrebare ,Ciurul lui Erastotene calculeaza numerele prime mai mici ca n ,dar mie imi trebuiesc numerele prime cu n.De asemenea alta intrebare ar fi daca trebuie sa folosesc ambele functii si totient si ciurul.


Titlul: Raspuns: 003 Fractii
Scris de: Valentin Stanciu din Septembrie 30, 2006, 10:06:36
Ai citit toate posturile de pe topicul asta? .. sunt multe indicii prin ele


Titlul: Raspuns: 003 Fractii
Scris de: Damian Alexandru din Februarie 06, 2007, 12:58:34
Nu stiu daca e locul bun unde sa postez, dar pot sa primesc un test oarecare cu raspunsul la aceasta problema?

Pe testele astea imi da corect, totusi iau 0 puncte..

N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783

Sper sa fi copiat bine Smile
Succes!

Silviu

e vreo problema cu evaluarea la problema asta ??


Titlul: Raspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Februarie 06, 2007, 14:41:05
Nu este nici o problema cu evaluarea la problema asta. Am luat 100 acuma.
Si te sfatuiesc sa folosesti citate cand copiezi mesajele altor utilizatori. :)


Titlul: Raspuns: 003 Fractii
Scris de: Damian Alexandru din Februarie 06, 2007, 23:09:42
hmz ... ciudat pentru ca acu vreo 2 luni am trimis sursa unui prieten care lua 100 pcte la el si eu tot 0 luam :|

poti sa verifici niste teste randomed?

123456 - 9265674079
847325 - 436467869023
648812 - 255911628103
999999 - 607926304783
71354 - 3095252991

ms anticipat.

ps: nu e nevoie de operatii pe numere mari, nu ?
ps2: era cu copy paste sry... :)


Titlul: Raspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Februarie 06, 2007, 23:58:31
Sunt bune rezultatele tale. Nu inteleg de ce iei 0.  :?
Cat despre numere mari, e clar ca solutia este <= N^2 (deci nu e nevoie de numere mari).


Titlul: Raspuns: 003 Fractii
Scris de: Damian Alexandru din Februarie 07, 2007, 08:27:45
mda, ciudat


Titlul: Raspuns: 003 Fractii
Scris de: Jecan Daniel Valerian din Februarie 12, 2007, 22:47:39
Mie nu mi se uploadeaza sursa...
E cam mare ce-i drept(534kb)...dar ar trebui sa functioneze...nu?


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Februarie 12, 2007, 22:52:06
da ce ai scris ma acolo :-o?? romane, jurnalu tau intim ;)), just kiddin :D

oricum eu te sfatuiesc sa incerci sa mai reduci dimensiunea sursei si sa incerci din nou.


Titlul: Raspuns: 003 Fractii
Scris de: Bondane Cosmin din Februarie 12, 2007, 22:57:05
@Jecan Daniel Valerian

Tu ai precalculat tot ?  ???


Titlul: Raspuns: 003 Fractii
Scris de: Jecan Daniel Valerian din Februarie 12, 2007, 23:15:31
Nu am precalculat...doar ca am declarat un vector cu 78498 de constante...cred ca stii cu ce...
Si tocmai de aceea e asa mare...

As putea incerca si cu jurnalul dar nu cred ca o sa-mi compileze... :D


Titlul: 003 Fractii
Scris de: Jecan Daniel Valerian din Februarie 12, 2007, 23:18:02
Are rost sa incerc sa-l uploadez sau incerc alta metoda...?



Titlul: Raspuns: 003 Fractii
Scris de: Airinei Adrian din Februarie 12, 2007, 23:23:18
S-a pus la un moment dat o limita pe dimensiunea sursei 128 sau 256kb nu mai stiu exact, dar oricum sub 534kb


Titlul: Raspuns: 003 Fractii
Scris de: Adrian Vladu din Februarie 13, 2007, 02:34:51
Mai bine te gandesti la o rezolvare fara constante (care iti va fi cu siguranta folositoare si in viitor)  :surf:


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Februarie 13, 2007, 07:44:55
si cea cu constante poate fi folositoare, la urma urmei dak arunci o privire pe sursa lui mihai patrascu de la oni 2002 la problema sumdiv ai sa vezi un vector de constate de 9901 elemente. Oricum u ai cam exagerat la faza asta cu 78498 constante.


Titlul: Raspuns: 003 Fractii
Scris de: Filip Cristian Buruiana din Februarie 13, 2007, 09:38:15
Citat
Nu am precalculat...doar ca am declarat un vector cu 78498 de constante

Daca tu ai precalculat numerele prime, poti sa faci fara constante in O(NlogN) folosind ciurului lui Eratostene.


Titlul: Raspuns: 003 Fractii
Scris de: Jecan Daniel Valerian din Februarie 13, 2007, 17:21:26
Ok...mersi de sfaturi...

O sa folosesc altceva atunci...


Titlul: Raspuns: 003 Fractii
Scris de: Andrei Grigorean din Februarie 13, 2007, 19:19:54
http://infoarena.ro/Ciurul-lui-Erathostene


Titlul: Raspuns: 003 Fractii
Scris de: Sima Cotizo din Februarie 13, 2007, 21:57:25
Citat
Nu am precalculat...doar ca am declarat un vector cu 78498 de constante

Daca tu ai precalculat numerele prime, poti sa faci fara constante in O(NlogN) folosind ciurului lui Eratostene.

Parca ciurul din articol e O(N) [ adica O(sqrt(N) * sqrt(N) )] ... plus o parcurgere a intregului sir unde marchezi daca e prim sau nu [ inca O(N) ]... L-am inteles eu gresit?  ???


Titlul: Raspuns: 003 Fractii
Scris de: Andrei Homorodean din Februarie 14, 2007, 14:23:41
Eu am o alta problema. Nu inteleg de ce vector de constante, eu la precalculari folosesc vector normal. Nu-mi explica si mie careva care e treaba? Va rog :D


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Februarie 14, 2007, 14:49:23
pai cred ca nu precalcula programul acele nr prime. Cred ca si-a facut un progam separat care a scris in sursa programului sau
const int prime[9901] = {2,3,5,7,11 bla bla bla}

astfel a obtinut si acea marime astronomica a sursei. La urma urmei asa poti sa rezolvi aproape orice problema de pe infoarena facand un back care sa iti calculeze rezultatu ptr n luand valori de la 1 la nmax si sa iti scrie apoi in sursa unui alt program a[ x ]=rez; x - o valoare intre 1 si nmax iar rez fiind rezultatul intors de back ptr valoarea x :D. Ce idee smekera :))


Titlul: Raspuns: 003 Fractii
Scris de: Andrei Homorodean din Februarie 14, 2007, 14:57:40
Mi-e clar ca si-a generat nr prime cu un alt program. Intrebarea mea e de ce const int? Ce ar avea mai special? ...sau e doar asa de 'fitze' ;)


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Februarie 14, 2007, 15:14:31
sincer sa fiu nush dak e vreun avantaj la memorie sau timp, doar ca dak il declari const int atunci zona de memorie va fi read only dar cum am mai zis nush dak ofera vreun avantaj.


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Februarie 24, 2007, 14:27:47
am si eu o intrebare.cum se pun constantele alea in sursa?ca doar nu introduci 78498 numere prime manual?sau le ati luat din fisierul ala cu primele 100000 numere prime?


Titlul: Raspuns: 003 Fractii
Scris de: Adrian Vladu din Februarie 24, 2007, 14:36:24
Daca tii neaparat sa iti declari un vector de constante, poti sa iti faci un program care sa iti genereze respectiva bucata de cod. Oricum, la concursuri nu vei avea de unde altundeva sa iti iei fisiere cu numere prime.
Cu toate astea e de preferat (pentru eleganta si simplitate) sa iti construiesti vectorul de numere prime direct in sursa cu un ciur micut care se implementeaza in cateva linii  :banana:


Titlul: Raspuns: 003 Fractii
Scris de: Iacob Eduard din Februarie 24, 2007, 15:20:12
si cum faci programelul ala?nu,eu am facut problema ,dar intreb asa ca fapt divers.


Titlul: Raspuns: 003 Fractii
Scris de: Filip Cristian Buruiana din Februarie 24, 2007, 15:56:10
Pur si simplu faci un program care sa genereze numerele prime si sa le scrie intr-un fisier oarecare ( cu , intre ele eventual), si le copii din fisierul respectiv in codul tau sursa.


Titlul: Raspuns: 003 Fractii
Scris de: Ivan Nicolae din Februarie 24, 2007, 16:00:29
si cum faci programelul ala?nu,eu am facut problema ,dar intreb asa ca fapt divers.
   Ceea ce nu vad ce rost are.... poti sa faci ciurul si in programul tau, nu e nevoie sa il faci seaparat si sa faci constanta si etc.....


Titlul: Raspuns: 003 Fractii
Scris de: Savin Tiberiu din Februarie 24, 2007, 18:35:48
de fapt adrian vladu cred ca se referea sa faci un program care sa iti scrie direct in codu sursa: a[1]=2;a[2]=3;a[3]=5 bla blabla
Adik ceva de genu un program care sa iti scrie programu.


Titlul: Răspuns: 003 Fractii
Scris de: Iacob Eduard din Martie 01, 2007, 18:35:17
Am inteles.


Titlul: Răspuns: 003 Fractii
Scris de: Suciu Adrian din Martie 03, 2007, 20:22:50
Am facut problema fractiilor , imi merge pentru cazurile prezentate anterior (in afara de cel cu 1000000000 pt ca folosesc borland) si imi da raspuns gresit la 4 din teste, la restul luand TLE .. care ar putea fi problema ? folosesc ciurul si numarul de fractii il calculez  folosind
Cod:
i->n 
        2*(tot(i))+1



Titlul: Răspuns: 003 Fractii
Scris de: Luca Vlad din Martie 03, 2007, 20:40:44
well si eu am incercat dupa cum scriati pe forum, am implementat ciurul lui erathostene si functia totiene, si pentru toate exemplele date in problema si de voi pe forum obtin raspunsul corect. la teste totusi, primesc 9 TLE-uri... vreo idee ce sa mai optimizez la algoritm? sunt sigur ca e o chichitza ce nu vad eu... aveti vreo idee ce as putea face?


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan P. din Martie 07, 2007, 20:09:35
O intrebare :
este posibil sa apara erori daca atribui unei variabile de tip long long int valoarea unei variabile de tip float inmultita cu o variabila de tip int? (nu stiu prea multe despre g++. in borland c nu am probleme).


Titlul: Răspuns: 003 Fractii
Scris de: Ivan Nicolae din Martie 07, 2007, 22:25:55
 N-ai probleme.... dar rezultatul o sa fie int evident.... desi ar fi de preferat sa folosesti asa:
Cod:
 float a;
 int b,rez;
 rez=((int)a) * b;


Titlul: Răspuns: 003 Fractii
Scris de: HighScore din Martie 09, 2007, 07:00:29
mie imi face toate exe bine, dar incepe sa crape p undeva p unde n depasiste 100.000, any ideeas? :?


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Martie 09, 2007, 08:52:58
Aloci vreun vector mai mic decat trebuie? ... in windows mai crapa cand accesezi memorie unde nu trebuie... in linux crapa sigur ;)


Titlul: Răspuns: 003 Fractii
Scris de: HighScore din Martie 09, 2007, 09:43:14
aloc un vector char de Nmax unde Nmax e 1000010 (sa fiu sigur k nu aloc prea mult)
LE: Sursa e scrisa in BC 3.1 si e compilata cu gnu (as fi scris-o in rhide, dar tot nu imi dau seama de ce nu vrea sa creeze fisier d tip object), deci nu prea pot sa fac debug pt n>65000


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Martie 09, 2007, 09:56:37
Puteai sa o scrii si in notepad, conteaza doar unde o compilezi ;)...

Ok, daca nu iti iese din vector, detaliaza in ce sens "crapa" programul?...
Cateva probleme posibile:
  • daca faci ceva recursiv (nu cred ca e nevoie in pr asta) iti "crapa" stiva;
  • daca imparti la 0 ar trebui sa primesti FPE si sa crape
  • daca aloci mai mult decat ai disponibil la un moment dat mi se pare ca iar face urat
  • poate fi de la faptul ca nu ai compilat cum trebuie... (eu stiu, poate ai pus vreun flag care nu trebuia)


Titlul: Răspuns: 003 Fractii
Scris de: HighScore din Martie 09, 2007, 09:59:57
prin a crapa ma refer la faptul k o ia rezultatu razna, adik nu da nici o eroare, si ceea ce nu inteleg e cum de imi da pt primele 100.000 de numere si pt restu pana la un mil incepe sa devieze.
LE: acuma imi da sigsegv.....  ](*,)
LLE: solved sigsegv(era un for pt ciur kre incepea de la i*i si knd i era mai mare k 1000 imi iesea din vector), mai ramane doar partea cu rezultatul incorect :annoyed:


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan P. din Martie 09, 2007, 15:57:09
Am reusit cu problema  :D Nu credeam ca daca voi declara doi vectori de 1000000 de elemente de tip long long int, problema va rula, dar se pare ca am obtinut 100 de puncte!  :yahoo: Cum a spus cineva inaintea mea pe forum (nu mai stiu exact cine) e memorie "fara numar"  :P


Titlul: Răspuns: 003 Fractii
Scris de: Marius Stroe din Martie 09, 2007, 16:25:31
Nu, e "lafaiala"!  :)


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan P. din Martie 09, 2007, 16:40:33
Nu, e "lafaiala"!  :)

Asa  :D Scuze  :P


Titlul: Răspuns: 003 Fractii
Scris de: HighScore din Martie 09, 2007, 18:57:47
poate sa imi trim si mie cineva care a facut de 100 exele sa vad mai exact de la ce numar o ia p aratura  :roll:
p [email protected]

LE: Nevermind found it(dupa un indelung debug pe fisiere)


Titlul: 003 Fractii
Scris de: Eros Lorand din Martie 11, 2007, 13:34:05
Multumesc pentru sfaturi :ok: - am reusit si eu!  :yahoo:


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Martie 11, 2007, 20:28:51
Problema asta e groaznica... :fool:m-am kinuit foarte mult timp la ea...dar in zadar..am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele...pt k asta imi trebuie...si cu brute force (adik cu calcurarea cmmdc-ului la fiecare pas, ceea ce cu siguranta nu e indicat) iese doar 10 puncte ???


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan P. din Martie 12, 2007, 13:46:44
am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele

citeste despre functia totient in special. aia te ajuta  :wink:


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Martie 27, 2007, 20:56:57
Multumesc pt sfat Bogdan...am inteles ce e aia functie totient,  :weightlift: insa pierd precizie in afisare....adik imi afiseaza cu 1 in plus..sau cu 2 in minus (fata decat ar trebui)...help me careva..pls...


[edit later]....nu.....m-am inselat..din ce am inteles eu, functia totient returneaza toate nr relativ prime cu i , care insa sunt mai mici k i. Dar trebuie sa fac cumva sa-mi returneze nr relativ prime cu i care sunt mai mici sau egale cu n. (unde 1<=i<=n); deci..ar putea cineva sa-mi dea vreun sfat cum as putea sa fac lucrul asta?? pls...multumesc anticipat,,


Titlul: Răspuns: 003 Fractii
Scris de: Luca Eduard din Martie 28, 2007, 16:14:17
Killed by signal 11(SIGSEGV)... asta imi zice la problema Fractii si imi da 10 pct. Ce inseamna signal 11? Mersi!


Titlul: Răspuns: 003 Fractii
Scris de: Airinei Adrian din Martie 28, 2007, 16:19:29
Citat
Killed by signal: Cea mai frecventa eroare cand ai un bug in program. Cand un program incalca anumite conventii in UNIX acel program primeste un "semnal" care de cele mai multe ori il opreste. Cateva semnale comune:
    * 11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.
    * 8(SIGFPE): Floating point error. Cauza cel mai frecvent de impartiri la 0.


Titlul: Răspuns: 003 Fractii
Scris de: Ionescu Victor din Martie 28, 2007, 23:43:33
eu am incercat cu indicatorul lui euler...however...am dekt 30 :(


Titlul: Răspuns: 003 Fractii
Scris de: Pandia Gheorghe din Martie 29, 2007, 14:56:08
Am folosi ciurul lui eratostene si functia totient, dar imi sare din timp pe 7 teste. Cum se poate face mai optim ?


Titlul: Răspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Martie 29, 2007, 15:07:28
Ai citit articolul? http://infoarena.ro/Ciurul-lui-Erathostene


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Martie 30, 2007, 16:37:47
Am inteles si functia totient, dar nu pot optimiza ciurul lui eratostene. Iau doar 30 de puncte amarate. Ar putea cineva sa-mi trimita algoritmul cu ciurul optimzat, kre sa poata sa scoata 100?? vreau doar ciurul..fara restul sursei..pls... ](*,)pls...


Titlul: Răspuns: 003 Fractii
Scris de: Pandia Gheorghe din Martie 30, 2007, 18:14:52
Ai citit articolul? http://infoarena.ro/Ciurul-lui-Erathostene
Aici este codul de la ciur optimizat. L-am folosit si eu pe cel mai rapid, dar nu de acolo era problema (cum de altfel ma asteptam) ci de la functia totient, pe care eu o calculez dupa formula, nu reusesc sa gasesc rezolvarea buna pentru a construi un vector cu valorile date de totient in acelasi timp cand fac ciurul.

P.S. la linkul de mai sus gasesti codul in java, dar daca scoti antetul functiilor (specific java) ramane cod C. Iar transformarea (la ultima optimizare) sa nu mai numere valorile prime ci sa le puna intr-un vector creezi un alt vector inlocuind "nr++" cu "vector[2*i+1] = 1" si obtii ciurul.
si mai e o chestie: "vector[2] = 1"

Sper ca nu am scris prostii sau prea explicit. Daca e asa, va rog sa-mi stergeti post-ul.


Titlul: Răspuns: Raspuns: 003 Fractii
Scris de: George Guraliuc din Aprilie 19, 2007, 17:53:17
daca vrei sa folosesti functia totient si sa optimizezi timpul de executie te poti folosi de urmatoarele egalitati:

t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
si
daca p numar prim, p NU divide a,
t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)

deci, daca la un moment dat stii t(1), t(2) ... t(n) poti calcula t(n + 1) gasind un singur divizor prim al lui n + 1
Indiciul e mai mult decat suficient pentru rezolvare! De fapt, textul problemei se poate reduce la:
determinati phi(i) pentru i = 2 pana la 1000000.
WM, you are great!


Titlul: Răspuns: 003 Fractii
Scris de: Stan Alexandru Dan din Aprilie 23, 2007, 21:17:07
Te chinui putin la problema asta pana o faci, la fel imi dadea la 7 teste TLE,asa k am optimizat  luand fiecare numar prim si folosind functia totient pt toate numerel divizibile cu el...intra lejer in timp si iei 100 pct :peacefingers:


Titlul: Răspuns: 003 Fractii
Scris de: parcalabescu maria daniela din Aprilie 26, 2007, 22:11:51
am citit tot topicul...am facut problema, dar pt 1000000imi ruleaza f mult(vreo 2 min cel putin)...am luat 30 de pcte, restu TLE...ma ajuta si pe mine cineva s-o optimizez ca nu stiu cum...pls... :dontgetit:
ms anticipat!
LE:nu vad la ce imi folosesc relatiile date de Cristian George Strat...:dontgetit: :'( :-k


Titlul: Răspuns: 003 Fractii
Scris de: HighScore din Aprilie 27, 2007, 15:45:58
cu respectivele formule se gaseste rezultatul ca sa iti intre in timp...o explicatie mai amanuntita gasesti la http://mathworld.wolfram.com/TotientFunction.html


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Mai 02, 2007, 09:07:42
Ei bine..am inteles ciurul...si am reusit sa fac de 100! 10x Gheorge Guraliuc..cu indiciul tau am reusit, insa si cu ajutorul celor care au postat informatii referitoare la functia totient!! Multumesc! :yahoo:


Titlul: Răspuns: 003 Fractii
Scris de: Gabriel Bitis din Iunie 19, 2007, 15:06:55
    phi(n)=(p1-1)p1k1-1 ... (pr-1)prkr-1
E buna formula pt functia totient? ???


Titlul: Răspuns: 003 Fractii
Scris de: Radulea Adrian din Iulie 06, 2007, 13:34:13
    phi(n)=(p1-1)p1k1-1 ... (pr-1)prkr-1
E buna formula pt functia totient? ???
Formula pentru functia totient e foarte buna  :)


Titlul: Răspuns: 003 Fractii
Scris de: Gabriel Bitis din Iulie 06, 2007, 17:08:18
 :) Merci pt raspuns :P a trecut mult de cand am pus intrebarea respectiva :P
Am facut problema pana la urma  :peacefingers: chiar era buna formula ...:P


Titlul: Răspuns: 003 Fractii
Scris de: Simionescu Andrei din Septembrie 10, 2007, 17:01:55
(http://upload.wikimedia.org/math/a/f/1/af1384d48a6710276bfc5003f0d0777e.png)
asta e formula, mai usor de inteles si/sau folosit  :wink:
exemplu:
(http://upload.wikimedia.org/math/9/4/1/941ffe88d716c7b76c05c80eb8554766.png)

edit:
1. oops, nu am vazut ca a mai fost postata formula asta...
2.imi da raspuns gresit 7/10, de la tipurile de int, dar nu`mi dau seama ce poate avea... timp oriqm scot<0,3s si pt valori mici merge bine  :?

re-edit: am rezolvat  :-' uitasem sa pun long long undeva


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan-Alexandru Stoica din Septembrie 10, 2007, 18:30:04
incearca ca rezultatul pe care-l calculezi sa-l memorezi intr-o variabila de tip "long long", iar cand vrei sa adaugi o valoare care are timp intreg faci conversie de tip pentru acea variabila:

Cod:
long long rez;
int a = 100;
rez += (long long)a;
printf("%lld\n", rez);

in rest eu am folosit tipul "double" pentru a lucra cu numere reale.


Titlul: Răspuns: 003 Fractii
Scris de: Mazilu Victor din Ianuarie 03, 2008, 11:35:16
Am si eu o intrebare..cu ce invat la scoala pot sa fac problema asta???
Sau trebuie sa mai invatz pe langa ce se preda la scoala (sunt la profil mate-info) ca sa inteleg si eu ceva.. Sunt clasa a 11-a,  am 17 ani, si n-am auzit de ciurul lui eratostene si nici de functia totient...si ce-i aia complexiatate doamne fereste, nu mai inteleg nimik...dar programarea este viata mea..si nu ma voi lasa...va rog frumos ajutati-ma..!! :weightlift:


Titlul: Răspuns: 003 Fractii
Scris de: Bondane Cosmin din Ianuarie 03, 2008, 12:57:57
Am si eu o intrebare..cu ce invat la scoala pot sa fac problema asta???
Sau trebuie sa mai invatz pe langa ce se preda la scoala (sunt la profil mate-info) ca sa inteleg si eu ceva.. Sunt clasa a 11-a,  am 17 ani, si n-am auzit de ciurul lui eratostene si nici de functia totient...si ce-i aia complexiatate doamne fereste, nu mai inteleg nimik...dar programarea este viata mea..si nu ma voi lasa...va rog frumos ajutati-ma..!! :weightlift:

Ah se pare ca trebuie sa inveti si din alte surse decat cele de la scoala. Am impresia ca la scoala ta nu se fac prea multe. Despre complexitate s-a mai vorbit pe forum, da-i un search. Legat de ciur ai mai multe informatii aici : http://infoarena.ro/Ciurul-lui-Erathostene.


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Ianuarie 03, 2008, 16:48:06
http://infoarena.ro/forum/index.php?topic=2512.0

Poate te ajuta.


Titlul: Răspuns: 003 Fractii
Scris de: Catalin din Ianuarie 19, 2008, 02:08:02
am citit toate indiciile de pe forum, dar tot nu inteleg cum sta treaba cu ciurul lui eratostene...nu ma prind kum m`ar ajuta generarea numerelor prime pentru cazul in care eu trebuie sa verific dak a si b sunt prime intre ele

citeste despre functia totient in special. aia te ajuta  :wink:

Pai o fractie este ireductibila daca cel mai mare divizor comun este 1.

Revenind la problema, care e treaba cu testele , imi ia timp de executie > 2secunde , iar codul este destul de simplu.


Titlul: Răspuns: 003 Fractii
Scris de: Airinei Adrian din Ianuarie 19, 2008, 03:23:30
Poate ca este simplu, dar nu este destul de performant. Citeste tot topicul la problema asta, sunt o gramada de sfaturi utile.


Titlul: Răspuns: 003 Fractii
Scris de: Anonim din Martie 20, 2008, 22:07:02
Daca as face cu doua for-uri si dupaia sa calculez ptr i si j cel mai mare divizor comun ar intra in timp ???


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Misarca din Aprilie 02, 2008, 13:22:24
Daca as face cu doua for-uri si dupaia sa calculez ptr i si j cel mai mare divizor comun ar intra in timp ???
Nu. Iei km de 10 puncte asa.
Se rezolva cu functia lui euler... gasesti mai multe despre functia asta dak citesti toate paginile de pe forum despre problema


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Misarca din Aprilie 02, 2008, 14:01:54
http://infoarena.ro/forum/index.php?topic=2512.0 (http://infoarena.ro/forum/index.php?topic=2512.0)
Acilea arata qm se calculeaza mai simplu phi(n)  :)

Offtopic: Cine ti-i diriga k vad k esti din bv, din liceu de info :D


Titlul: Răspuns: 003 Fractii
Scris de: Barna Bogdan din Aprilie 16, 2008, 10:44:31
Am facut programul cu 2 "For" si am verificat daca sunt prime intre ele (adica daca cmmdc=1,prin scaderi repetate). Am pus in fractii.in toate exemplele de la pag1, inafara de 1000000 si imi da bine, dar la evaluare dc iau 0 ?
Borland Pascal--


Titlul: Răspuns: 003 Fractii
Scris de: Gabriel Bitis din Aprilie 16, 2008, 10:56:54
Rezolvarea ta nu este una optima, de aia iei pe cateva teste Time limit exceeded. Pentru raspunsurile gresite nu stiu ce explicatie sa'ti dau daca zici ca iei toate testele.


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan-Alexandru Stoica din Aprilie 16, 2008, 10:58:39
raspunsul poate sa fie destul de mare si ar trebui sa folosesti tipul de date 'extended' (nu mai tin minte exact daca acesta iti retinea numerele pana in 2^64). downloadeza-ti free pascal, deoarece borlandul are multe restrictii (incepand cu memoria si terminand cu tipurile de date). citeste intai documentatia (http://infoarena.ro/documentatie) (in special la evaluator), apoi downloadeaza-ti compilatoarele folosite de infoarena si, in cele din urma, citeste acest forum si incearca sa gasesti o rezolvare care se incadreaza in timp.

Spor!  :thumbup:


Titlul: Răspuns: 003 Fractii
Scris de: Barna Bogdan din Aprilie 16, 2008, 11:26:56
Eu acum sunt la info, si am intrebat`o si pe dira ..si am mai optimizat`o si am luat numa 10...cand ajung acasa, o fac in free pascal


Titlul: Răspuns: 003 Fractii
Scris de: Savin Tiberiu din Aprilie 16, 2008, 12:08:55
in pascal ptr numere pana la 2^64 foloseste int64, bineinteles asta in freepascal, borlandul nu cred ca stie.
@Bogdu: Ti s-a zis si mai sus ca algoritmul tau nu este optim. Degeaba incerci sa optimizezi o sa iei maxim 30 de pct sa zicem, ca sa iei 100 trebuie sa schimbi algoritmul cam de pe la radacina.


Titlul: Răspuns: 003 Fractii
Scris de: Andrici Cezar din Noiembrie 03, 2008, 19:58:25
am o intrebare? cum arata ultimul test. Mie imi da doar 90 de puncte. Aveti vreo ideie cum pot inbunatati acest timp de 2048 de ms si cum sa imbunatatesc problema pana la 100 de puncte?

in pascal ptr numere pana la 2^64 foloseste int64, bineinteles asta in freepascal, borlandul nu cred ca stie.
@Bogdu: Ti s-a zis si mai sus ca algoritmul tau nu este optim. Degeaba incerci sa optimizezi o sa iei maxim 30 de pct sa zicem, ca sa iei 100 trebuie sa schimbi algoritmul cam de pe la radacina.
mie nu mia mers cu int64 dar iti merge cu qword, dar intr-un fel ai dreptate deoarece trebuie sa schimbi programul ca altfel iti iese aiurea timpul la ultimul test. Oricum pe mn ma poate ajuta cineva? :readthis:

 Editat de moderator: Nu posta consecutiv pe aceeasi tema! Modifica mesajele precedente!


Titlul: Răspuns: 003 Fractii
Scris de: Cerneanu Cristian din Noiembrie 10, 2008, 20:09:30
cum poate fi gasit cel mai mare divizor comun a doua numere in turbo pascal?
   mersi anticipat...


Titlul: Răspuns: 003 Fractii
Scris de: Savin Tiberiu din Noiembrie 10, 2008, 20:21:47
cu algoritmul lui euclid, poti gasi mai multe detalii in topicul destinat problemei 001. CMMDC


Titlul: Răspuns: 003 Fractii
Scris de: Andrici Cezar din Noiembrie 21, 2008, 19:51:21
Pe mine cine ma poate ajuta ca tot nu primesc raspuns? De ce ia atat de mult si cum as putea sa inbunatatesc timpul


Titlul: Răspuns: 003 Fractii
Scris de: flufix belton din Februarie 01, 2009, 16:48:55
Salut,

Incerc si eu de cateva zeci de minute sa rezolv aceasta problema insa fara succes ( inca ). Am citit cam tot ce ati scris in acest topic .

Eu am ajuns pana la faza generarii tuturor fractiilor, mai exact :

 
Cod:
for (i=1;i<=n;i++)  
  { 
      for (k=1; k<=n; k++) 
      { 
         p = i; 
         q = k;   
         // cout<<"P/Q = "<<p<<" / "<<q<<endl;
      } 
  } 

Practic, ma intereseaza ca din aceste toate fractii sa le dau pe cele reductibile la o parte iar pe celelalte sa le adun intr-o variabila s pe care sa o salvez apoi in fractii.out .

Aveti un link unde as putea citi despre o solutie pentru situatia mea, please ?

Am observat ca link-ul de pe forum despre Ciurul lui Eratosthenes nu mai functioneaza .

Mersi,


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Februarie 01, 2009, 17:17:49
Daca ai citit intreg topicul, inseamna ca ai vazut faptul ca problema se rezolva utilizand functia totentiala. tot(n) este o functie care iti intoarce numarul de numere prime cu n si mai mici decat n. Din cauza faptului ca ai nevoie de toate tot(i) (cu i<=n), e mult mai bine sa precalculezi la inceput intr-un vector, valorile respective. Ca sa faci aceasta precalculare, te folosesti de  Ciurul lui Eratostene  (http://infoarena.ro/ciurul-lui-eratostene).

Functia totentiala este : tot(n) = n*(1-1/p1)*(1-1/p2)...*(1-1/pk), unde p1,p2,...,pk sunt factorii primi care apar in descompunerea lui n.

In legatura cu solutia prezentata de tine, complexitatea ei e O(n^2), si avand in vedere ca n este 1 milion, cu siguranta nu o sa iti intre in timp, indiferent daca iti va da corect. Succes!


Titlul: Răspuns: 003 Fractii
Scris de: Mocanu Marius din Februarie 20, 2009, 23:38:35
Lamuritima putin, deci.... atunci cand e sus numar impar atunci jos apar si impare si pare, si atunci cand e sus numar par atunci jos apar numai impare, cu conditia ca sa nu fie egale cu numaru de sus.
Alta regula nu gasesc, spunetimi voi....e greu :|

Spunetimi va rog care e formula completa, ca nu potsa o deduc.Eu cred ca e in felu urmator
Atunci cand e sus numar impar, atunci apar fractii care au numitor si par si impar
Cand numaratoru e par, atunci la numitor sunt numai fractii impare , cu conditia ca sa nu fie egale cu numaratoru . Ma insel ?

[edit] nu mai posta de 2 ori consecutiv, foloseste butonul "modifica"


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Februarie 21, 2009, 12:33:18
Problema nu are nicio treaba cu paritatea numerelor. In schimb, are treaba cu numarul de numere relativ prime cu n si mai mici ca n(n - un nr dat). Citeste tot topicul asta, si sunt sigur ca vei gasi rezolvarea. Succes!


Titlul: Răspuns: 003 Fractii
Scris de: Mocanu Marius din Februarie 21, 2009, 17:09:24
atunci nici nu ma apuc de ea...e grea si neinteresanta...nici macar nu stiu cum e ciuru' lu erastotene si nici nu inteleg nimic daca ma uit pe net..treb sa imi expl cineva..sunt doar cls a 9-a :\ ffs


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Februarie 21, 2009, 17:24:04
e grea si neinteresanta.

Atunci zi-mi motivul pt care ai cerut lamuriri referitor la aceasta problema 'neinteresanta'. Sunt foarte curios.


Titlul: Răspuns: 003 Fractii
Scris de: Maria Stanciu din Februarie 21, 2009, 18:02:03
nu stiu cum e ciuru' lu erastotene si nici nu inteleg nimic daca ma uit pe net..treb sa imi expl cineva..

Pentru ciur incearca sa te uiti in arhiva educationala aici : http://infoarena.ro/problema/ciur. Si ca sa intelegi mai bine pe sursele celor care au facut problema. Arhiva educationala este conceputa pentru incepatorii care vor sa invete lucruri noi.

Cat despre surse, inclusiv problema fractii are acces liber la sursele trimise. Daca e ceva ce nu intelegi, trimite-mi un mesaj personal si o sa-ti explic eu cum functioneaza ciurul.


Titlul: Răspuns: 003 Fractii
Scris de: Davide din Martie 10, 2009, 19:51:41
Este foarte simpla, insa exemplul este gresit, 1/1 nu este fractie ireductibila.

dACA bagati 4 si va da 8 e bine! 1/1, 2/1, 3/1 si 4/1 nu trebuie luate in calcul.

[editat de moderator] Nu mai posta consecutiv, foloseste butonul "Modifica".


Titlul: Răspuns: 003 Fractii
Scris de: Dragos Oprica din Martie 10, 2009, 19:57:31
Este foarte simpla, insa exemplul este gresit, 1/1 nu este fractie ireductibila.

dACA bagati 4 si va da 8 e bine! 1/1, 2/1, 3/1 si 4/1 nu trebuie luate in calcul.

[editat de moderator] Nu mai posta consecutiv, foloseste butonul "Modifica".

daca citesti cu atentie cerinta ai sa vezi ca fiecare fractie de forma nr/1 e considerata ireductibila si de aceea 1/1, 2/1 samd trebuie luate in considerare


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Martie 10, 2009, 22:26:24
Sa citim putin definitia unei fractii ireductibile (http://en.wikipedia.org/wiki/Irreducible_fraction).

Sa aruncam o privire asupra fractiei 4/2 (a = 4, b = 2). Daca am considera ca 2/1 (consideram toate cele 4 posibilitati in functie de semne: -2/1, 2/-1, -2/-1, 2/1) nu este fractie ireductibila, atunci nu am putea gasi alte doua valori c si d cu proprietatea ca a/b = c/d, |c| < |a| si |d| < |b|. De aici ar rezulta ca 4/2 este o fractie ireductibila - evident, fals.

Putem trage concluzia ca 2/1 este o fractie ireductibila.


Titlul: Răspuns: 003 Fractii
Scris de: alexandru din Martie 12, 2009, 20:44:56
imi explica si mie ce e gresit la rezolvarea asta:
in vectorul phi[ i ] -retin cate numere prime cu i is in sirul  1,2,....n.
Initial  vectorul are phi[1]=n si  restu  phi[ i ]=n-1,i>1;
Si aplic  ciurul lui eratostene , scazand din phi[ i ] si  phi[ i*j ] cate  1. Iar apoi rezultatul e suma lor.
Sursa implementata e aici (http://infoarena.ro/job_detail/279464?action=view-source).
:D
[later] Am  gasit  eroarea :)


Titlul: Răspuns: 003 Fractii
Scris de: Matei Apolzan din Martie 12, 2009, 22:12:29
Imi jice ca nam timp cu o formula n*n ce fac??


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Martie 12, 2009, 23:16:41
Imi jice ca nam timp cu o formula n*n ce fac??
Citesti o carte de limba romana inainte de a posta pe forumul infoarena.  :roll: [ E doar o sugestie nevinovata! ]


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Martie 12, 2009, 23:27:56
Cu alte cuvinte, nu prea se intelege din post-ul tau care este problema. Exprima-te mai clar si te vom putea ajuta.


Titlul: Răspuns: 003 Fractii
Scris de: Maria Stanciu din Martie 13, 2009, 07:17:15
Imi jice ca nam timp cu o formula n*n ce fac??
Citesti o carte de limba romana inainte de a posta pe forumul infoarena. 

Si dupa asta poti sa citesti si restul topicului. E destul de clar exprimat de ce nu e optima o complexitate patratica si ce trebuie sa faci :).


Titlul: Răspuns: 003 Fractii
Scris de: Dana-Maria Munteanu din Mai 18, 2009, 10:28:12
va rog mult, imi puteti spune si mie ce este gresit in algoritmul meu?? imi da eroare de compilare!!! VA ROG!!
 ](*,)
Cod:
#include<iostream.h>
#include<fstream.h>
fstream f("fractii.in",ios::in);
fstream g("fractii.out",ios::out);
int main()
{
int n,i,j,k=0,a,b,rest;
f>>n;
for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
   {
   a=i;
   b=j;
   rest=a%b;
  while (rest!=0)
  {
a=b;
b=rest;
}
if (b==1) k++;
}
g<<k<<endl;
return 0;
}

[editat de moderator] foloseste tag-ul "code" cand postezi cod


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Mai 18, 2009, 11:00:09
Citeste erorile de compilare. Eu de exemplu am dedus de acolo ca nu recunoaste bibliotecile (nici eu nu-mi dau seama de ce). Incearca asa:

Cod:
#include <iostream>
#include <fstream>
using namespace std;

fstream f...

Oricum, ma indoiesc ca programul tau functioneaza corect, de exemplu in while-ul pentru cmmdc cred ca ai uitat ceva :)


Titlul: Răspuns: 003 Fractii
Scris de: Pripoae Teodor Anton din Mai 18, 2009, 14:16:39
Pe gcc-urile noi nu mai exista fstream.h/iostream.h. Probabil s-a facut un update la compilator (acum e 4.3).


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iunie 28, 2009, 02:16:03
Ceva foarte simplu si eficient.....d.p.d.v matematic nu va chiuniti cu numere de miliarde :D

versiunea mea ( sunt doar un incepator.....voi stiti ma multe)
Cod:
#include<iostream.h>
#include<fstream.h>
int main ()
{
unsigned int p,q,n,c=0;
ifstream a("fractii.in");
a>>n;
a.close();
for(p=1;p<=n;p++)
{
for(q=1;q<=n;q++)
{
if(p%q!=0)
{
c++;
}
}
}
ofstream  v("adunare.out");
v<<c;
v.close();
return 0;
}

 Editat de moderator: Nu posta de doua ori consecutiv pe aceeasi tema. Editeaza-ti postul anterior. De asemenea foloseste tagul [ code ] cand vrei sa postezi cod sursa.


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Iunie 28, 2009, 08:23:26
Ma inchin in fata geniului tau!  :mrgreen:

1. Ce anume vrei sa zici/demonstrezi prin cele doua posturi ?
2. Nu ai voie sa postezi de doua ori consecutiv.
3. Nu ai voie sa postezi surse.
4. Sursa ta cu siguranta nu va functiona ( fisierul de iesire e "fractii.out"; complexitatea e prea mare;)
5. Ca sa rezolvi problema, citeste intreg topicul.
6. Numai bine!  :thumbup:


Titlul: Răspuns: 003 Fractii
Scris de: Savin Tiberiu din Iunie 28, 2009, 10:52:11
@Calin Florin: Ai trimis sursa aia inainte sa o postezi pe forum? Ma rog nu conteaza pentru ca sigur nu o sa ia 100. Problema fractii, desi nu pare sa stii ca este una din problemele destul de grele de pe infoarena din cauza limitelor foarte mari (N < 1000000). Mai citeste mesajele din acest topic si vei intelege :).
@Marcu Florian: Eu zic sa te linistesti si sa nu mai ataci lumea :P. Puteai sa ii explici mai frumos ca a gresit :P.


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iunie 28, 2009, 12:05:09
Multumesc....................
Imi cer scuze..............!


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iunie 29, 2009, 16:52:19
Cand aveti timp aruncati un ochi peste asta............... :fool:
http://infoarena.ro/job_detail/327637?action=view-source


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Iunie 29, 2009, 17:58:00
Mesajul de eroare provine de la faptul că tu nu iniţializezi pointerul v.

Uite un tutorial (http://home.netcom.com/~tjensen/ptr/pointers.htm) despre pointeri. În capitolul 9 găseşti informaţii despre alocarea dinamică a memoriei.


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iunie 29, 2009, 22:15:02
Nu prea am inteles........... ](*,)


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iunie 30, 2009, 00:13:41
adica declar pointerul v folosind functiile malloc() calloc() sau free()?


Titlul: Răspuns: 003 Fractii
Scris de: Pripoae Teodor Anton din Iunie 30, 2009, 07:46:31
Pentru declarare :

Cod:
 v = (int*) malloc (sizeof (int) * size);


Functia free () e pentru dezalocarea ulterioara a memoriei.


Titlul: Răspuns: 003 Fractii
Scris de: Porcescu Alexandru din Iulie 01, 2009, 17:55:19
Am o intrebare .........
Deci cu ciurul lui Erathostene gasesti toate numerele  prime mai mici ca n (ex)
Ca sa calculezi cu functia totentiala ai nevoie  de numerele prime care se divid cu n........
deci trebuie sa facem o selectie a numerelor prime generate de ciurul lui Erathostene le luam doar aleacare se divid cu n,nu?


Titlul: Răspuns: 003 Fractii
Scris de: Mihai Calancea din Iulie 01, 2009, 23:04:04
Nu :)
http://infoarena.ro/forum/index.php?topic=2512.0


Titlul: Răspuns: 003 Fractii
Scris de: Balan Radu Cosmin din August 19, 2009, 23:40:54
am facut o sursa care imi rezolva bine problema.
am folosit eratostene si totient. numai ca imi da o eroare de compilare p care eu nu stiu sa o rezolv.
complilatoru folosit de mine e cel borland m-am obisnuit cu cateva diferente dintre cele doua si m-am adaptat, dar p asta nu o mai stiu.

invalid types 'int [10001][double]' for array subscript

si nu am declarat nimic double. toate variabilele care lucrez sunt declarate long sau int. am o secventa de cod unde fac o impartire dar rezultatu impartirii este int cu siguranta. borlandu nu imi da eroare... gnu c++ imi da:( ajutor


Titlul: Răspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din August 19, 2009, 23:49:53
Functia pow pe care o folosesti tu returneaza double. Ai putea sa convertesti rezultatul la int si apoi sa-l folosesti, adica in loc de
Cod:
T[pow(i,j)] = ...
sa folosesti
Cod:
T[int(pow(i,j))] = ...


Titlul: Răspuns: 003 Fractii
Scris de: Balan Radu Cosmin din August 19, 2009, 23:53:45
multumesc sa vad daca merge.

L.E.: asta era. multumesc. de acum am sa stiu.:)

L.L.E.: dar mai am de lucrat cu totientu... acolo am o buba... am gresit la rationament putin si mai trebe si optimizata...

Editat de admin: Nu mai posta consecutiv, foloseste butonul modifica.


Titlul: Răspuns: 003 Fractii
Scris de: Postavaru Stefan din Septembrie 26, 2009, 17:08:13
As dori sa stiu mai multe date de intrare cu rezultatele respective. Programul meu returneaza toate valorile ca in exemplele de pe site insa evaluatorul nu mi-a dat nici un punct pe problema.


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Septembrie 27, 2009, 03:38:50
M-am uitat peste sursa ta si codul pare in regula.

Algoritmul gasit de tine este ineficient, si ca urmare nu obtii niciun punct. O alta problema este ca tu folosesti tipuri de date pe 32 de biti - integer, iar rezultatul trebuie memorat intr-un intreg pe 64 de biti - int64.


Titlul: Răspuns: 003 Fractii
Scris de: Postavaru Stefan din Septembrie 27, 2009, 13:26:05
Am incercat to longint in loc de integer dar acum a aparut alta problema. Programul meu ruleaza intr-o fractiune de secunda pentru n<100 insa cand am incercat cu n=500, programul a stat 3 secunde pana sa dea rezolvarea. Pentru n=1000 ii ia cam 10 secunde. Daca evaluatorul incearca valori asa de mari, va da Time Limit Exceeded. 


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan Ionut din Septembrie 29, 2009, 20:15:18
Am si eu o intrebare referitor la o sursa, inca nu am trimis-o dar o probez pe niste exemple si nu imi da bine. nu prea stiu regulile, daca pot sau nu sa postez o sursa ...

am folosit indicatorul lui euler, o functie numita fi:
Cod:
while(n>1)
       if(n%d==0)
       {  pr=pr*((d-1)/d);
          while(n%d==0) n/=d;
       }
       else d++;

si returneaza pr, pr ii initializat cu N.

si in int main() am:
Cod:
v[1]=1;
  for(i=2;i<=n;i++)
    v[i]=v[i-1]+2*fi(i);
si afisez v[n].
ce nu este corect? solutia nu este in v[n] ?


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Septembrie 29, 2009, 20:24:53
In loc de "pr=pr*((d-1)/d)" incearca " pr -= pr/d ". E acelasi lucru, doar ca am desfacut parantezele. Si sterge "else"-ul "d++"-ului din while, ca altfel va cicla la primul factor prim gasit. Scuze pt exprimare  :)


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan Ionut din Septembrie 29, 2009, 20:46:55
asa nu mai merge. nu scrie nimic in fisier, se si blocheaza sau dureaza mult timp executia ...


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Septembrie 29, 2009, 21:54:15
Cu
Cod:
d = 2;
while(n>1)
  {
     if(n%d==0)
       { 
          pr = pr - pr/d;
          while(n%d==0) n/=d;
       }
  d++;
  }
se blocheaza?  :eyebrow:


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan Ionut din Septembrie 30, 2009, 13:33:05
ah, scuze. credeam ca fara ++d, acum am vazut ca l-ai pus in afara ifului.
asa merge dar nu da pentru toate, merge pe 3,4 si inca, cateva mici, dar pe altele da prost. de ex pentru 31, imi da 647... ii ceva in neregula cu functia ? si la un milion imi iese din timp ...


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Septembrie 30, 2009, 14:56:06
Ca sa intre in timp pt 1 milion, trebuie sa te folosesti de Ciurul lui Eratostene. Codul pare ok. Nu stiu exact unde gresesti. poti renunta la vectorul v[]. Eu am asa:
Cod:
sol = 1;
for(i=2;i<=N;i++)
          sol += 2*phi[i];



Titlul: Răspuns: 003 Fractii
Scris de: Bogdan Ionut din Septembrie 30, 2009, 15:51:42
modificasem inainte programul si aveam niste erori, l-am facut iar si merge si scot 30 pct. acum incerc cu ciurul lui eratostene


Titlul: Răspuns: 003 Fractii
Scris de: Andrei din Septembrie 30, 2009, 22:27:23
Salut.

Prima data am incercat o metoda foarte greoaie, si m-am uitat prin alte surse, recunosc, si am vazut ciurul, si m-am gandit sa-l optimizez. Algoritmul meu memorie foloseste clar mai putina, si timpii ar trebui in mod normal sa fie mai mici, dar e de 0 puncte. Pe exemplele alea cu 3,4,5 imi da bine, dar pe numere mai mari nu da bine (spre exemplu la 10 da 84 in loc de 64). Problema e ca daca x*i >= N, din nr-le ala nu se mai scade nimic, automat depaseste.

Any ideas?


Cod:
#include <fstream>
using  namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
long N,i,x,nr;
long eratostene() {
long nr;
nr=N;
for(x=2; x*i<N; x++)
nr--;
return nr;
}
int main() {
in>>N;
nr=0;
for(i=2;i<=N;i++)
nr+=eratostene();
out<<nr;
return 0;
}


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Octombrie 01, 2009, 05:36:40
De multe ori, in loc sa ii intrebi pe ceilalti "De ce nu merge?", ar trebui sa te intrebi pe tine insuti "De ce ar trebui sa mearga?". Daca nu ai inteles cum se rezolva problema, nu castigi nimic, chiar daca te uiti prin alte surse si reusesti sa iei 100 de puncte.


Titlul: Răspuns: 003 Fractii
Scris de: Andrei din Octombrie 01, 2009, 11:18:07
Hm... Doar ca idee, nu am intrebat de ce nu merge ci daca are cineva vreo idee. Am inteles cum se rezolva, dar solutia mea iesea rau din timp. Si m-am uitat la o singura sursa si am vazut eratostenele. Oricum nu l-am copiat, am facut un ciur al meu, care clar e mai potrivit problemei. Cred ca imi lipseste un if, sau am intervalele din for-uri prea mari.

P.s: nu prea ma descurc la genul asta de probleme, si vreau sa ma obisnuiesc cu ele, chiar nu trebuie sa te porti asa.


Titlul: Răspuns: 003 Fractii
Scris de: Bogdan Ionut din Octombrie 01, 2009, 18:23:34
Cod:
long N,i,x,nr;
long eratostene() {
long nr;
nr=N;
for(x=2; x*i<N; x++)
nr--;
return nr;
}

si eu sunt la inceput, sper sa nu gresesc ce zic dar:
ai declarat i global, si in for ai conditia x*i<N ... care ii mereu adevarata daca N>0
nu stiu cum iti iese pe numere mici.
zic eu ca mai intai ar trebui sa inveti baza (notiuni elementare) si pe urma sa treci la probleme.


Titlul: Răspuns: 003 Fractii
Scris de: Andrei din Octombrie 02, 2009, 08:46:03
Nu cred ca acolo e problema, pentru ca e ciurul lui eratostene pentru a afla numerele prime intre ele. Ideea e ca atunci cand 2*i>N, nu mai intra in for si imi aduna in plus. Am incercat cu un if(x*i>=N), ia sa incerc si cu un if(2*i>=N) nr=0; :D

L.e: hmmmmmmm no. this shit need some thinkin nigga.


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Grigorean din Octombrie 02, 2009, 10:24:00
http://infoarena.ro/forum/index.php?topic=2512.0  :-'


Titlul: Răspuns: 003 Fractii
Scris de: Andrei din Octombrie 02, 2009, 18:50:18
Trebuie sa diger putin algoritmul, ca nu inteleg foarte bine de ce phi-=phi[j]; o sa ma uit pe un exemplu la el. Dea dumnezeu sanatate wefgef.

Inteleg ca scade atat i cat si primele cu i, dar nu cred ca am inteles eu prea bine.


Titlul: Răspuns: 003 Fractii
Scris de: Vlad Tarniceru din Noiembrie 20, 2009, 17:57:18
definitie:pentru ca o fractie sa fie ireductibila,(numarator,numitor)=1(cel mai mare divizor comun al numitorului si numaratorului trebuie sa fie 1),adica numaratorul si numitorul sa fie prome intre ele :winner2:,locu 1 dupa ce o fac(eti).parerea mea,faceti cu subprogram,dar nu gatantez ca o sa va dea 100 de puncte.
 
Cod:
 int prim(long m,long h){
     while(m!=h)
     if(m>h) m-=h;
     else
     if(m<h) h-=m;
     return h;
 }           


bafta :peacefingers:


am uitat sa spun asta e var recursiva incercati s-o imbunatatiti(ca timp de executie)  cu modul in
Cod:
#include<math.h>
mod(....);


Cod:
include<math.h>
in C/C++.in pascal nu mai stiu

[editat de moderator] nu mai posta consecutiv, foloseste butonul "modifica"


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Noiembrie 21, 2009, 11:40:25
Ce e recursiv in ce ai scris si la ce te ajuta?  :-s

Cred ca mai bine citesti inainte prin topic idei de rezolvare si incerci sa bagi o sursa, problema nu e dintre cele usoare care pot fi trecute cu vederea...


Titlul: Răspuns: 003 Fractii
Scris de: Vlad Tarniceru din Decembrie 10, 2009, 15:25:10
problema asta e frumoasa,dar am alta idee.pt a vedea daca 2 nr sunt prome intre ele scadem din cel mai mare cel mai mic pana nr sunt egale (ex:12,8,12-8=4.ramane 4,8.8-4=4.ramane 4,4 =>(12,8)=4).asta e recursiva.dar mai e si altfel.de imparte cel mare la cel mic si se pastreaza restul,pana unul din resturi este 0.atunci afisam numarul nenul(ex:12,8,12%8=4.ramane 4,8.8%4=0.ramane 0,4 => (12,8)=4).poate o sa para absurd,dar e algoritmul lui euclid   :winner1:.si mai e ceva.ajutati-ma si pe mine,care e ideea cu ciurul lui eratostene?memoram toate nr si apoi verificam cu un for daca e sau nu prim? ca de exemplu numarele 4 si 21 nu sunt prime dar sunt prime intre ele


Titlul: Răspuns: 003 Fractii
Scris de: Sima Cotizo din Decembrie 10, 2009, 15:35:20
Exista deja pe forum un topic pe tema asta. (http://infoarena.ro/forum/index.php?topic=2512.0)

In plus, e a doua oara cand iti zic: chiar si topicul acesta are 10 pagini pline de idei. Ai incercat sa treci prin ele?


Titlul: Răspuns: 003 Fractii
Scris de: Vlad Tarniceru din Decembrie 10, 2009, 16:09:14
am incercat,dar tot nu prea am inteles(sunt in clasa a6-a  :)).Si pe sursa mea iau doar 10 puncte.
Cod:
#include<fstream.h>
 int prim(long n,long m){
     while(m!=0 && n!=0)
         (m>n?m=m%n:n=n%m);
     if(n!=0) return n;
     return m;
 }
 ifstream f("fractii.in");
 ofstream g("fractii.out");
  int main(){
      long t,n,m,nr=0;
      f>>t;
      nr+=t*2-1;
      for(n=2;n<=t;n++)
          for(m=2;m<=t;m++)
              nr+=(prim(n,m)==1);
      g<<nr;
      g.close();
      return 0;
  }
asta e prog meu,poate isi da cineva seama....BAFTA:peacefingers:


Titlul: Răspuns: 003 Fractii
Scris de: Andrei Misarca din Decembrie 10, 2009, 18:50:11
Algoritmul tau obtine 10 puncte pentru ca este ineficient. Citeste toate paginile acestui topic si cu siguranta vei gasi destule indicii necesare.


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Decembrie 27, 2009, 22:07:13
Nu stiu ce are, imi da raspuns gresit la cateva teste, imi spuneti de ce? Merci
http://infoarena.ro/job_detail/378202?action=view-source
GATA am depistat era nr care trebuia int64 merci.


Titlul: Răspuns: 003 Fractii
Scris de: yonootz321 din Ianuarie 30, 2010, 15:43:30
M-am apucat sa rezolv problema si mi-e venit o idee...(nu stiu daca se poate rezolva asa)
Am ajuns la concluzia ca
nr fractii = n + suma_fractiilor_cu_numarator_par + suma_fractiilor_cu_numarator_impar ;
unde:
suma_fractiilor_cu_numarator_par = (n div 2) * (n - n div 2)
suma_fractiilor_cu_numarator_impar  = (n - n div 3) + (n - n div 5) + (n - n div 7)... + (n - n div i)
i trecand prin toate numerele impare <= n
Mai ramane doar sa scad exceptiile: 6/3 6/9 9/3 9/6 10/5 12/3 ...
adica fractiile cu numitor impar si care se pot simplifica...dar aici m-am impotmolit
Oare se poate duce la capat problema prin metoda asta?
Asta e sursa din care nu am scazut exceptiile:
Cod:
program fractii;
var f:text;
    n,i,s:1..1000000;
begin
  assign(f,'fractii.in');
  reset(f);
  readln(f,n);
  close(f);
  assign(f,'fractii.out');
  i:=3;
  s:=n+(n div 2)*(n - n div 2);
  while i<=n do
    begin
      s:=s+(n-n div i);
      i:=i+2;
    end;
  rewrite(f);
  writeln(f,s);
  close(f);
end.

Stiu ca nu functioneaza pe numere foarte mari...nu asta ma intereseaza ci daca se poate rezolva asa sau m-am chinuit degeaba (am umplut cateva pagini de formule)...


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Ianuarie 30, 2010, 16:56:00
Nu cred ca e "corecta" si "eficienta" rezolvarea, pentru ca tu oricum trebuie sa aflii fractiile ireductibile, deci faci in plus anumite chestii.


Titlul: Răspuns: 003 Fractii
Scris de: yonootz321 din Ianuarie 31, 2010, 13:22:06
defapt tot ce calculez in plus sunt acele exceptii de care ziceam, formulele pe care le-am gasit sunt pentru fractii ireductibile...deci daca cumva pot sa scad exceptiile, rezolvarea ar fi mai eficienta decat altele (am o singura structura repetitiva)... ;)
Problema este ca nu vad un tipar pentru exceptii, nu gasesc o formula...


Titlul: Răspuns: 003 Fractii
Scris de: Florian Marcu din Ianuarie 31, 2010, 13:28:53
Fara demonstratie matematica, nu poti spune ca solutia e corecta.  :P


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Ianuarie 31, 2010, 13:47:12
Poti sa scrii cum ai ajuns la acest lucru (poti sa-l demonstrezi cumva?), eventual da-mi niste exemple sa vad ..


Titlul: Răspuns: 003 Fractii
Scris de: yonootz321 din Februarie 03, 2010, 19:51:02
Imi cer scuze in primul rand ca am raspuns asa de greu
In ceea ce priveste raspunsul cerut, poti sa alegi o valoare pentru n si sa verifici pur si simplu formulele...Nu vad ce alt exemplu as putea sa dau... ???

Am gandit in felul urmator:

Fractii cu numaratorul par:
1) Stim ca pana la n sunt n div 2 numere pare...
2) Pentru un n par sunt n div 2 fractii cu numaratorul par care se pot simplifica...deci mai raman n - n div 2 care nu se pot simplifica...
din 1 si 2 => (n div 2) * (n - n div 2) fractii cu numarator par care se pot simplifica...

Fractii cu numaratorul impar:
Pentru x care trece prin toate numerele impare de la 3 la n:
1) Sunt n div x fractii care au numaratorul si numitorul divizibile intre ele...raman deci n - n div x care nu se simplifica.
Acest calcul l-am facut in "while".

Mai raman deci doar cateva exceptii...(daca am gandit bine...si e posibil sa fi gresit, nu neg)
Exceptiile sunt de forma: 6/3 6/9 9/3 9/6 10/5


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Februarie 03, 2010, 19:55:46
Incearca sa faci cu metoda asta si vezi ce punctaj iei  :thumbup:


Titlul: Răspuns: 003 Fractii
Scris de: Paul-Dan Baltescu din Februarie 03, 2010, 23:14:12
Imi cer scuze in primul rand ca am raspuns asa de greu
In ceea ce priveste raspunsul cerut, poti sa alegi o valoare pentru n si sa verifici pur si simplu formulele...Nu vad ce alt exemplu as putea sa dau... ???

Am gandit in felul urmator:

Fractii cu numaratorul par:
1) Stim ca pana la n sunt n div 2 numere pare...
2) Pentru un n par sunt n div 2 fractii cu numaratorul par care se pot simplifica...deci mai raman n - n div 2 care nu se pot simplifica...
din 1 si 2 => (n div 2) * (n - n div 2) fractii cu numarator par care se pot simplifica...

Fractii cu numaratorul impar:
Pentru x care trece prin toate numerele impare de la 3 la n:
1) Sunt n div x fractii care au numaratorul si numitorul divizibile intre ele...raman deci n - n div x care nu se simplifica.
Acest calcul l-am facut in "while".

Mai raman deci doar cateva exceptii...(daca am gandit bine...si e posibil sa fi gresit, nu neg)
Exceptiile sunt de forma: 6/3 6/9 9/3 9/6 10/5


Nu cred ca vei reusi sa rezolvi problema cu aceasta abordare. Acele fractii pe care le numesti tu exceptii sunt de fapt o multime foarte de mare de fractii. Mai bine incerci alta abordare (pentru indicii poti citi acest topic).


Titlul: Răspuns: 003 Fractii
Scris de: yonootz321 din Februarie 06, 2010, 16:41:41
da...intradevar...sunt cam multe "exceptii" mai ales pentru n foarte mare... :D


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Februarie 06, 2010, 17:02:29
Aceasta problema se rezolva usor cu indicatorul lui Euler (http://ro.wikipedia.org/wiki/Indicatorul_lui_Euler), explicat mai bine aici (http://infoarena.ro/forum/index.php?topic=2512.0).


Titlul: Răspuns: 003 Fractii
Scris de: Halalai Tudor Andrei din Februarie 15, 2010, 17:27:54
am o intrebare care s-a pus (presupun) de 1000000 de ori.
Care e metoda Euler?
pls help!! :'(


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Februarie 15, 2010, 17:32:07
am o intrebare care s-a pus (presupun) de 1000000 de ori.
Care e metoda Euler?
pls help!! :'(
Ti-am trimis P.M. , fa ce ti-am zis acolo si e ok ;)


Titlul: Răspuns: 003 Fractii
Scris de: Nume complet din Martie 03, 2010, 16:09:04
auziti.. uitati cum am facut eu

Cod:
#include<fstream>
using namespace std;
int N,P,Q,k;

int cmmdc(int a, int b){
while(a!=0)
{
           int r;
           r=b%a;
           b=a;
           a=r;} return b;}
int main()
{
    ifstream fin("fractii.in");
    ofstream fout("fractii.out");
    fin>>N;
    for(P=1;P<=N;P++)
    for(Q=1;Q<=N;Q++)

    if(cmmdc(P,Q)==1) k++;

    fout<<k;
    return 0;
}

poate sa`mi spuna cineva dc am luat numai 10 puncte? :|

Editat de admin: Foloseste tagul "code" cand postezi surse.


Titlul: Răspuns: 003 Fractii
Scris de: Dragos-Alin Rotaru din Martie 03, 2010, 16:11:41
Pentru ca solutia ta nu e eficienta (sunt cateva pagini din acest topic din care ai cateva indicii si ceva de invatat).


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Martie 03, 2010, 16:12:06
E ineficient, oare de ce? Cauta prin topic Indicatorul lui Euler.
[LE] Am scris in acelasi timp :)


Titlul: Răspuns: 003 Fractii
Scris de: Nume complet din Martie 03, 2010, 16:38:29
am facut ca acolo... o mers... dar acu am 0 puncte!! :| dc?

http://infoarena.ro/job_detail/409332?action=view-source

la toate testele zice Killed by signal 11(SIGSEGV).


Titlul: Răspuns: 003 Fractii
Scris de: alexandru din Martie 03, 2010, 16:39:36
am facut ca acolo... o mers... dar acu am 0 puncte!! :| dc?

http://infoarena.ro/job_detail/409332?action=view-source

la toate testele zice Killed by signal 11(SIGSEGV).
pentru ca tu aloci un vector de 0 numere......


Titlul: Răspuns: 003 Fractii
Scris de: Nume complet din Martie 03, 2010, 16:40:36
 ups.. n`am observat.. mc :)

L. E.: nu e bun? :| dc? am verificat.. si merge

Editat de admin: Nu posta consecutiv, foloseste butonul "Modifica"


Titlul: Răspuns: 003 Fractii
Scris de: alexandru din Martie 03, 2010, 16:54:33
nu e bun? :| dc? am verificat.. si merge
Scuze, eram cu gandul la altceva ....


Titlul: Răspuns: 003 Fractii
Scris de: Nume complet din Martie 03, 2010, 16:56:08
oricum nu era bun :) am corectat acuma si am 100 puncte


Titlul: Răspuns: 003 Fractii
Scris de: Muresanu Gabriel Ionut din Aprilie 23, 2010, 10:49:06
Nu se vede nimic. ](*,)


Titlul: Răspuns: 003 Fractii
Scris de: Adrian Craciun din Aprilie 23, 2010, 17:12:49
Ce vrei sa zici cu asta?(nu ai priceput ideea?)


Titlul: Răspuns: 003 Fractii
Scris de: abababbab abababab din Aprilie 30, 2010, 21:29:32
sirul dat nu trebuia sa fie 1/1 1/2 1/3 1/4 2/1 2/2 2/3 2/4 3/1 3/2 3/3 3/4 1/4 2/4 3/4 4/4?  :-k :-k


Titlul: Răspuns: 003 Fractii
Scris de: Gabriel Bitis din Aprilie 30, 2010, 22:15:37
Nu. Sirul este format doar din fractii ireductibile.


Titlul: Răspuns: 003 Fractii
Scris de: abababbab abababab din Mai 04, 2010, 20:24:58
Ce am gresit? De afisat afiseaza bine! :sad:

Cod:
#include<fstream>
using namespace std;

int cmmdc(int a, int b)
{
   int x=a, y=b,r;
   while(x%y!=0)
   {
      r=x%y;
      x=y;
      y=r;
   }
   if(r==1)
      return 0;
   else
      return r;
}

int main()
{
   long N;
   int i,j;
   ifstream in("fractii.in");
   ofstream out("fractii.out");
   in>>N;
   int nr=N*N;
   for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
         if(cmmdc(i,j)!=0&&i!=1&&j!=1)
            nr--;
   out<<nr<<endl;
   out.close();
   in.close();
   return 0;
}

Editat de moderator : Nu mai posta de mai multe ori consecutiv, editeaza-ti posturile anterioare. Foloseste tagurile [ code ] [ /code ] cand postezi cod.


Titlul: Răspuns: 003 Fractii
Scris de: Gabriel Bitis din Mai 04, 2010, 20:32:52
De afisat afiseaza bine, dar nu afiseaza la timp.
Subiectul problemei are 11 pagini, sigur gasesti indicatii folositoare daca iti faci putin timp sa citesti.


Titlul: HELP!!!
Scris de: vasile paul emilian din Noiembrie 09, 2010, 19:30:11
ma poate ajuta cineva sa-mi dau seama unde am gresit   ](*,)
plz  :readthis:

Cod:
#include<iostream.h>
#include<fstream.h>
ifstream fin("fractii.in");
ofstream fout("fractii.out");
void fractii(long long n){
long long i,s=0;
for(i=2;i<=n/2;i++)
s=s+((n/i)-1)*(i+1);
s=s+n-1;
s=s-(n/2)+1;
fout<<n*n-s<<endl;
}
int main(){
long long n;
fin>>n;
fractii(n);
return 0;
}


Titlul: Răspuns: 003 Fractii
Scris de: Simoiu Robert din Noiembrie 09, 2010, 20:05:46
Nu e corecta rezolvarea, problema se face cu indicatorul lui euler (http://infoarena.ro/forum/index.php?topic=2512.0), si editeaza-ti codul cu tagul code .


Titlul: Răspuns: 003 Fractii
Scris de: pusherino TALENT din Martie 09, 2011, 12:19:21
Editat de admin: Te rog sa folosesti un limbaj civilizat pe forum si sa nu jignesti utilizatorii.

Editat de admin: Te rog sa folosesti un limbaj civilizat pe forum si sa nu jignesti utilizatorii.
De asemenea nu mai posta consecutiv, foloseste butonul "Modifica".


Titlul: Răspuns: 003 Fractii
Scris de: Popa Silviu din Ianuarie 09, 2014, 19:26:41
Din P/Q cu 1 ≤ P,Q ≤ N, se intelege CA : 1<=P si Q<=N

si 1/1 da 1 deci e reductibila si ar afisa doar 10 fractii.


Titlul: Răspuns: 003 Fractii
Scris de: Popa Silviu din Ianuarie 09, 2014, 19:53:43
de ce imi tot spune ca nu aveti pe server fstream.h si iostream.h??

Eu fac programele in Turbo C++ IDE .
Care este problema??


Titlul: Răspuns: 003 Fractii
Scris de: Patrick Sava din Februarie 14, 2014, 15:59:31
Am si eu o problema:am incarcat sursa asta(http://www.infoarena.ro/job_detail/1107827) acum 2 ore si jumatate si inca nu mi s-a evaluat..in cazul acesta,ce as putea face? ](*,)


Titlul: Răspuns: 003 Fractii
Scris de: Serban Cercelescu din Februarie 28, 2014, 14:12:35
Nu inteleg cum imi iese din timp sursa asta! :annoyed:
Cod:
#include <cstdio>
using namespace std;

int cmmdc(int a,int b){
    if(a==b)
        return a;
    else if(a>b)
        return cmmdc(a-b,b);
    else
        return cmmdc(a,b-a);
}

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    register int n,i,j,u;
    u=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(cmmdc(i,j)==1)
                u++;
        }
    }
    printf("%d",u);
    return 0;
}



Titlul: Răspuns: 003 Fractii
Scris de: Andrei Maxim din Aprilie 11, 2014, 14:05:46
Nu inteleg cum imi iese din timp sursa asta! :annoyed:
Cod:
#include <cstdio>
using namespace std;

int cmmdc(int a,int b){
    if(a==b)
        return a;
    else if(a>b)
        return cmmdc(a-b,b);
    else
        return cmmdc(a,b-a);
}

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    register int n,i,j,u;
    u=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(cmmdc(i,j)==1)
                u++;
        }
    }
    printf("%d",u);
    return 0;
}

Tu faci in O(n*n) , n = 1 000 000


Titlul: Răspuns: 003 Fractii
Scris de: Breahna David din Mai 30, 2014, 16:39:51
ma ajută și pe mine cineva ???
de ce nu intru în timp ???
 ](*,) ](*,) ](*,)
Cod:
#include <iostream>
#include<fstream>
  
  
  
using namespace std;
  
ifstream f;
ofstream g;
  
long int i,j,n;
 
long long t[1000002],k;
  
int main()
{
f.open("fractii.in");
g.open("fractii.out");
  
f>>n;
  
k=0;
for(i=2;i<=n;i++)
        {
        t+=i-1;
        for(j=i+i;j<=n;j+=i)t[j]-=t;
        k+=t;
        }
 
g<<k*2+1;
g.close();
}

... GAtA!!!! am rezolvat problema )))
habar n-aveam ca tipul long long merge mai greu decit int.. :)


Titlul: Răspuns: 003 Fractii
Scris de: Burcea Geanin-Mihai din Ianuarie 29, 2015, 22:02:22
Primesc doar 10 puncte la problema asta, si nu inteleg de ce. Ma poate ajuta cineva?
Cod:
 
#include<fstream>
using namespace std;
int a,b,n;

int cmmdc(int a,int b)
{ while((a!=b)&&(a>0)&&(b>0))
{if(a>b)a=a-b;
else b=b-a;
}
return a;
}

int main()
{int s=0;
ifstream f ("fractii.in");
ofstream g ("fractii.out");
f>>n;
f.close();

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(cmmdc(i,j)==1)s+=1;
}
g<<s;
g.close();


return 0;
}



Titlul: Răspuns: 003 Fractii
Scris de: Pirtoaca George Sebastian din Ianuarie 29, 2015, 23:03:33
Programul tau nu este suficient de rapid si de aceia primesti Time Limit Exceeded. Rezolvarea ta nu este cea optima, adica ordinul de complexitate este prea mare. Pentru 100p trebuie sa folosesti indicatorul lui Euler.  :ok:


Titlul: Răspuns: 003 Fractii
Scris de: Bargan Cristian Andrei din Aprilie 11, 2015, 21:19:49
rezultatele la problema sunt bune dar nu stiu cum sa fac sa pot rula si nr. 1000000?


Titlul: Răspuns: 003 Fractii
Scris de: Matei Alexandru din Iunie 02, 2015, 11:18:21
mie personal in opinia mea mie nu mi-a placut aceasta problema dupa mine dupa parerea mea :fighting:


Titlul: Răspuns: 003 Fractii
Scris de: Lucian Maciuca din Decembrie 07, 2015, 19:05:29
O problema frumoasa, dar "catchy" asa :P


Titlul: Răspuns: 003 Fractii
Scris de: Donciu Mircea din Decembrie 21, 2015, 21:30:58
Fac un ciur care da si indicatorul lui euler pt nr de la 2 la un milion apoi adun totul pana la n, imultesc cu 2 adun 1, imi da la toate testele mele dar pe problema imi da 0. Ati putea sa-mi explicati de ce. ](*,) ](*,) ](*,) ](*,) ](*,) :fighting:


Titlul: Răspuns: 003 Fractii
Scris de: rusti paula din Ianuarie 02, 2016, 18:52:57
Hei, imi spuneti, va rog, daca e buna rezolvarea asta? (am incercat sa trimit dar nu am nicio sansa  ](*,)) multumesc.


Titlul: Răspuns: 003 Fractii
Scris de: rusti paula din Ianuarie 02, 2016, 18:53:40
#include <iostream>
using namespace std;

bool sunt_prime (int a, int b)
{int r;
while (b!=0)
{r=a%b;
 a=b;
 b=r;
}
 if (a==1)
return true;
else
return false;
}


int main()
{
    int numa, numi,rezult,n;
    rezult=0;
    cin >> n;
    for (numa=1 ; numa<=n; numa++)
    {
        for (numi=1; numi<=n; numi++){
            if (sunt_prime(numa, numi)==true)
                {
                    rezult ++;
            }
        }
    }
    cout << rezult ;

}


Titlul: Răspuns: 003 Fractii
Scris de: Nicolae Elisei din Ianuarie 03, 2019, 17:12:33
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin("fractii.in");
    ofstream fout("fractii.out");

    int N, numarator, numitor, i, contor = 0, gasit;
    fin >> N;

    for(numarator = 1; numarator <= N; numarator++){
        for(numitor = 1; numitor <= N; numitor++){
            gasit = 1;
            for(i = 2; i <= numitor; i++){
                if(numarator % i == 0 && numitor % i == 0){
                    gasit = 0;
                    break;
                }
            }
            if(gasit == 1){
            //  fout<<numarator <<"/"<<numitor<<"  ";
                contor++;
            }
        }
    }
    fout<<endl << contor;

    return 0;
}


Ce ar trebuii sa fac sa ma incadrez in timp? Iau 20 p


Titlul: Răspuns: 003 Fractii
Scris de: Galatanu Bogdan Ioan din Ianuarie 20, 2019, 10:25:38
Dar, 1/1 e ireductibil? Rezultatul e 1.


Titlul: Răspuns: 003 Fractii
Scris de: Manea Dumitru din Aprilie 18, 2019, 22:27:34
Dar, 1/1 e ireductibil? Rezultatul e 1.

1/1 e ireductibil, pentru ca nu poti sa-l mai simplifici, de exemplu 2/2 simplifici prin 2 si primesti 1/1 ... simplificand 1/1 prin 1 tot 1/1 iti da.


Titlul: Răspuns: 003 Fractii
Scris de: Pica Horia din Aprilie 20, 2019, 23:31:28
ce e gresit??
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
enum{RED,IRED};
int fr_red(int i,int j)
{
    int r;
    do
    {
        r=i%j;
        i=j;
        j=r;
    }while(r);
    if(i==1)
        return IRED;
    return RED;

}
int nr_fractii(int N)
{
    int nr=0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
            if(fr_red(i,j)==IRED)
                nr++;


    }
    return nr;
}
int main()
{
    int N;
    fin>>N;
    fout<<nr_fractii(N);
    return 0;

}