infoarena

Aici puteţi discuta despre problema Suma (http://infoarena.ro/problema/suma).

sper ca va ajuta ce v-am zis desi nu prea are cum, dak nu stii solutia nu-ti dai seama da' va zic ca o gasiti in orice manual de clasa a-9a de matematica.

Succes sper ca va ajuta.

dar numai cu formula de inductie nu iei decat 20 de puncte.io am incercat si am luat 20.apoi am facut cu operatia de modulo pe numere mari si am luat 100.Deci nu-i asa de greu!

Operatie de modulo pe numere mari?!?!?! Woah... te-ai chinuit ceva... E o idee... Dar nu e nevoie... Mai schimba un pic formula... O sa vezi ca iese si fara numere mari.  :wink:

ok...am sa incerc si cum spui tu....sa vad daca iese!multumesc

Iei 100 shi cu formula simpla, numa ai grija sa transformi !toate! operatiile tale in operatzii modulo...

(a * b * c) mod x = ((((a mod x) * (b mod x)) mod x) * (c mod x)) mod x ?  :-s  se poate si o generalizare ?!  :D

pai da.. poti sa aplici mod de cate ori vrei si oriunde la adunare si inmultire..
practic operatiile normale devin acum operatii modulo

problema se poate rezolva folosind o 2 formule foarte simple + o parcurgere ... lungimea sirului, primul numar, si parcurgerea pt verificare.

parcurgerea nu cred ca iti va intra in timp.

Am gasit o formula...am aplicat modulo in toate felurile posibile, iau doar 50 de puncte si imi da incorrect pentru 50% din teste.. :?..dati mi va rog o idee, sau poate stie cineva un test mai cu susta...ca in situatia asta kiar nu stiu ce sa fak... ](*,)..pls

Test   Timp executie   Memorie folosita   Mesaj   Punctaj
1   4ms   8kb   OK!   5
2   0ms   8kb   OK!   5
3   0ms   12kb   OK!   5
4   4ms   8kb   OK!   5
5   4ms   12kb   OK!   5
6   0ms   12kb   OK!   5
7   0ms   12kb   OK!   5
8   8ms   116kb   OK!   5
9   8ms   116kb   OK!   5
10   8ms   116kb   OK!   5
11   8ms   152kb   OK!   5
12   4ms   152kb   OK!   5
13   12ms   180kb   OK!   5
14   12ms   180kb   OK!   5
15   4ms   188kb   OK!   5
16   4ms   188kb   OK!   5
17   12ms   144kb   OK!   5
18   12ms   148kb   OK!   5
19   8ms   120kb   OK!   5
20   0ms   148kb   OK!   5
Punctaj total:   100

se pare ca a intrat prea bine

depinde ce parcurgere faci. Nush exact cum ai rezolvat tu problema. Zi pana unde faci parcurgerea.
Banuiesc ca ai acolo un for (i=1;i<=x;i++) , x=??

dupa citire ... o formula da primul termen si nr termenilor (desigur ca daca nr termenilor nu e intreg nu am solutie)
apoi aflu restul termenilor
apoi verific daca celelate sume corespund termenilor gasiti

iar despre cum fac forul ... nu cred ca e permis pe forum

Nu este grea problema... Se poate face si cu formula de inductie si cu un for...dar oricum numarul gasit va depasi nr de cifre pt orice variabila intreaga...asa ca trebuie gasita o modalitate de a reduce n-ul. Eu am gasit :P si sper sa gasiti si voi. Bafta si spor la munca!  :thumbup:

Nu e nevoie de nicio reducere al lui n....sau ce ai vrut tu sa zici.... :Deu am luat o 100 doar cu formula, punand "mod p" la fiecare inmultire....dar tebuie variabile long long unsigned... :-'

pai...tocmai asta poti sa faci si inainte de inmultire......dar daca spun mai mult...si asa ii prea mult.... :oops:

Nici nu trebuie unsigned. Merge doar long long (pt C) sau int64 (pascal). Trebuie doar sa te prinzi sa faci un arficiu inainte de a aplica formula  :wink:

Cred ca vb de acelasi artificiu... :P  Oricum...Bafta!  :wink:

Nu e nevoie de niciun "artificiu" pt a lua 100. Ideea voastra e interesanta, dar merge doar ku formula. O sa incerc insa si varianta voastra. :ok:

ca sa bag si io in seama, unde folositi voi long long k long e mult prea de ajuns, asta bineinteles cumulat cu niste cunostinte de divizibilitate la nivelul clasei a 6-a.
PS: Despre ce inductie e vorba?? k nu imi dau seama de ce sa folosesti inductia. Un PM would do :P

   Intr-adevar! Intra si pe long. Inductia nu e folosita in algoritm, ci e folosita in demonstrarea formulei...a fost amintita k fapt divers..kred...

e vorba de demonstratia formulei intregii expresii sau o formula partiala? :-' (intreb ca sa fiu sigur ca e vorba de aceeasi demonstratie a formulei)

Depinde ce intelegi prin "intreaga expresie"...Dak e ceea ce inteleg si eu, da...e folosita pt demonstrarea intregii expresii...


Sfatul lui m-a ajjutat pe mine.. :thumbup:

Cred ca ai incurcat subiectul... probabil te'ai referit la problema 024 Sume ....

Din ce ati spus si voi,prin inductie formula este Am incercat sa pun mod la fiecare, dar tot 20 de puncte imi da...am incercat si long long si tot nimic...Parcurgerea nu intra in timp...si nu stiu ce ar putea sa mearga pentru problema asta...Chiar nu se poate face??

Eu am luat 100 cu formula aia, punand mod la fiecare si folosind long long... ar trebui sa scoti formula de pe forum... una din regulile forumului e sa nu postezi solutii prea explicite  [-X

Nu mai posta formule explicite pe forum.

Ai grija ca (a/b)%c nu e tot una cu (a % c)/b . (exemplu 12/6 % 5 = 2; 12 % 5 / 6 = 0 ), % = modulo pentru cine nu stie C.
Trebuie sa ai grija cum faci impartirea in formula.

Multam pt sfaturi.Am luat si eu 100. :D

am citit toate remarcile..si am incercat si prin inductie..si o parcurgere si cu % la fiecare parte din formula ...si tot mai mult de 20 nu reusesc sa iau...la aia cu parcurgerea imi da time limit exceded...iar la restul incorrect..pls...help

Ce incerci tu prin inductie? Inductia o folosesti ca sa demonstrezi corectitudinea formulei, deci nu are nicio treaba cu programul tau. Singura kestie la problema asta, e sa vezi cum faci operatia modulo, ca sa iti dea corect. Nu vad de ce ai primi tle daca nu faci altceva decat sa aplici formula => O(1) timp si memorie. Poate ca nu am inteles eu bine, dar la ce te referi prin parcurgerea aia cu % ? Daca stii formula, ca sa iti dea corect, trebuie sa faci cv de genu ( (t1%x)*(t2%x) / y ) %x. (dar in formula sunt putin mai multi termeni... :P ).

nu prea cred eu ca am facut gresit poate...
dar ar trebui sa mearga chestia:
despart sigma(i * (i - 1)) in sigma(i^2) - sigma (i)
deci... DC NU MERGE?!
 :annoyed: ](*,) :fighting: :-k

un test mai jmecher ceva... plzzzz :bomb: :'(

 Editat de moderator: Nu posta consecutiv pe aceeasi tema!

Pai fa un brute si testeaza-ti pentru valori mici ale lui P.

Problema se rezolva folosind invers modular. Stii sa calculezi invers modular?

 :shock: multam, am reusit sa iau 100

10 x^2 Andrei Grigorean =D&gt; :D

cum adik invers modular  :? ? 
eu folosesc cele 2 formule si pun % dupa fiecare operatie :( ce e gresit

Pai sa zicem ca lucrezi modulo 7 si ai operatiile:

3*4/2 = 12/2 = 6 % 7 = 6.

Cand lucrezi modulo faci 3*4 = 12 % 7 = 5. Apoi faci 5/2 = 2 % 7 = 2.

Corect e 6, tie iti da 2.

Cauta pe net mai multe despre invers modular sau in cormen la capitolul de teoria numerelor.

Cred ca merge si daca imparti fiecare factor si abia apoi faci modulo, adica:

3*4 / 2 = E

3 nu se divide la 2, il ignori
4 se divide, il imparti => E = 3*2

Acuma faci modulo 3 mod 7 = 3, 2 mod 7 = 2 3*2 = 6, 6 mod 7 = 6.

Ceea ce zici tu este sa simplifici fractia. Insa ce faci daca ai recurente in matrice care se folosesc de operatia de impartire?

vreau si eu sa stiu ceva...e o solutie buna si asta in exemplul dat de voi?
3*4/2 modulo 7  = ((3 modulo 7+4 modulo 7)/2)modulo 7?

Nu e corect ce ai scris tu:
3*4/2 modulo 7  = ((3 modulo 7+4 modulo 7)/2)modulo 7

3*4/2 % 7 = ((3 % 7 + 4 % 7) / 2) % 7
=> 6 = (7 / 2) % 7
=> 6 = 3  ..... nu prea e bine.

asa e bine :
3*4/2 modulo 7  = ((3 modulo 7) * (4 modulo 7)/2)modulo 7

nu e bine nici asa. La impartire nu poti sa faci modulo pur si simplu.
adik (a/b)%c != ( (a%c)/b )%c.

Ca sa faci modulo la impartire trebuie sa folosesti invers modular, insa la problema asta nu e nevoie de asa ceva, deoarece poti sa faci niste simplificari inainte.

Eu i'am raspuns referitor la exemplul lui.

pai cred ca vroia sa stie pe cazul general, ptr ca pe exemplul dat de el, atata in formula lui cat si in a ta modulo nu face nimic, ptr ca numerele vor fi mai mici ca 7.

pai pe cazul general vroiam sa stiu .... deki
(a*(a+1)/2) mod x =?

Nu poti sa faci imparti modulo x. Trebuie sa folosesti invers modular. Poti citi mai multe despre invers modular in Cormen la teoria numerelor.

ms mult de tot iau 100 pct:*

Mozol.  :?

Cum as putea sa scot un timp mai bun eu am facut o cu o parcurgere de la 1 la n si dupaia suma = s+ i%p*((i-1)%p)%p pe ex acela e raspunsul bun daar pentru numere mai mari imi da time limit exces si iau doar 20 de p daca ati putea sa imi dati un sfat ptr a obtine un timp bun. MS  :-k

Este o formula pe care trebuie sa o gasesti.  :peacefingers:

Unde pot sa gasesc mai multe detali despre operatia de invers modular?

Articolul despre Teorema Chineza a Resturilor (http://infoarena.ro/teorema-chineza-a-resturilor) explica destul de bine. In principiu daca aplici Algoritmul lui Euclid extins (http://infoarena.ro/problema/euclid3) pentru c=1, vei obtine inversul modular.  :thumbup:

Mersi sima...Sper sa ma ajute.

Aici gasesti detalii despre teorema mica a lui Fermat (din care poti afla inversul modular al unui numar) http://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Deci simt ca innebunesc. Am trimis nu stiu cate surse la problema asta si maximul pe care l-am putut scoate a fost 80. Nu mai suport. ](*,)

incearca sa te calmezi, si incepe prin a ne spune cum faci ca sa poti fi ajutat :D

Calculez suma si o aduc la forma generala si bag mod peste tot. Imi pica la 2 teste. Habar nu am ce e ala invers modular si nu inteleg nimic din teoria care s-a spus mai sus.

Tin sa va anunt ca sunt la inceputul  drumului in a inteleg si a folosi C/C++ la nivel de olimpiada.

Nu'ti trebuie invers modular. Ai grija sa bagi mod chiar peste tot si sa folosesti long long.

Am pus chiar peste tot. Nu vad unde am gresit...

Imparte la constate unde poti. Daca de exemplu ai de calculat ceva de forma n*(n+1)*(n+2) / 2 calculeaza in ordinea aceasta n*(n+1)/2 * (n+2).

This guy is a good guy! Thanks.  :peacefingers:

Buna am incercat sa fac cu modulo peste tot, dar iau doar 50 pct. Imi puteti da o sugestie?

Ai grija in ce ordine faci impartirile. Daca de exemplu ai doua numere impare pe care le inmultesti si le imparti la 2 si apoi inmultesti cu un numar par, iti va da rezultatul gresit.

Mai citeste ce sfaturi au fost date in acest subiect, poate te ajuta.

Deci am luat pe cazuri, ca sa fac ceva de genu: pe 6=2*3 si sa vad care termen se imparte la fiecare: am luat 80 pct. Ceva sugestii
EDIT: Am luat 100. Merci Dan pentru sugestie

Imi puteti da si mie testul 3?

Testele, daca nu au fost facute pana acum publice, nu se dau. Spune-ne cum faci / unde suspectezi ca gresesti ca sa te putem ajuta.

Am inteles treaba cu testele,oricum am luat 100,ms de raspuns.

Dupa cum ziceau si ceilalti formula se gaseste in manualul de matematica de cl 9. Trebuie luata in considerare diferenta dintre i(i-1) si i(i+1). 

pauldbFMI - Paul-Dan Baltescu •pauldb
Imparte la constate unde poti. Daca de exemplu ai de calculat ceva de forma n*(n+1)*(n+2) / 2 calculeaza in ordinea aceasta n*(n+1)/2 * (n+2).
ms de sfat, am schimbat ordinea si intradevar am luat 100, pe cind cu ordinea obisnuita luam doar 50 :ok:

Imi puteti spune si mie va rog de ce nu pot face % pe variabile de tip long long? Cand rulez imi afiseaza tot felul de valori gresite.


PS: Daca folosesc long iau 60, daca folosesc long long iau 0, cu operatii pe numere mari 40 :fighting:.




LE: Am reusit, trebuia citit cu cin ca sa mearga, nu cu scanf.

Nu am nicio idee de ce nu poti face % pe long long, dar N este mai mic decat 10^9, deci nu ai nevoie de long long pentru a-l memora.Trebuie doar sa gasesti formula prin inductie matematica si sa aplici fiecarui coeficient %p.

Am gasit formula, am aplicat %p peste tot si iau 60. Am incercat si cu operatii pe numere mari si iau 40.

ce e gresit in formula mea?

Nu merge formula aia fiindca (a / b) % n != (a % n) / (b % n).
Data viitoare cand postezi, te rog expune-ti ideea si explica ce pare sa nu functioneze la ea. Nu pune lumea sa-ti caute sursa (aici nici macar nu-s deschise sursele). Nu prea e politicos sa ceri efort in plus de la ceilalti, avand in vedere ca tu esti cel care are nevoie de ajutor.

Da, scuze ca nu am pus linkul cu sursa mea. Si ba da , sunt deschise sursele pentru cei care au razolvat problema.

Eu am facut asta pe hartie, dupa fiecare termen al produsului am pus "%p" si mi-a dat.
Sursa este asta : http://infoarena.ro/job_detail/730396

Ce spun eu e ca nu poti pune modulo asa la impartiri fiindca nu iti da bine.
(a / 6) % p nu este ((a % p) / 6) % p.
Daca vrei sa folosesti formula trebuie sa simplifici numitorii ca sa poti folosi modulo-ul linistit apoi.

Ms de sfat. :peacefingers:

eu am folosit modulo si tot 20 am luat

Pai, trebuie sa scazi complexitatea....ceea ce faci tu cu for-ul pana la N, inseamna o complexitate O(N), dar se poate face foarte simplu cu formula de la inductie si scoti O(1).

Imi poate da si mie cineva testul 8.Iau 90 si nu inteleg ce gresesc ](*,).

Hint :
1. Vezi ca suma initiala o poti compune din 2 sume dupa ce o desfaci.
2. Ai grija la numitor. Poti scapa de de el.

Suma sumelor telescopice este o suma telescopica

Tu ai de gand sa te opresti din a posta aiurea?


LE: @Mihai: Ok  :roll:
Prin aiurea nu m-am referit la testele puse de el.

@Radu
Te rog sa fii mai temperat in discutiile cu alti useri.

@Silviu
Sunt sigur ca ai intentii bune dar, dupa cum observi, unii useri se simt agasati de postarile de tip 'Mi-a fost usor sa o rezolv. Uitati un hint', in special fiindca nu te intreaba nimeni :). Am sa te rog si pe tine sa moderezi putin frecventa/tonul post-urilor, pentru a pastra forumul productiv.

Am observat. Un hint si o valoare de testare au rolul lor, nu este o postare aiurea... Si mie imi folosesc comentariile utile de pe forum.

Voi tine cont de sugestie. Sa nu zgandaresc naturelul simtitor al unora.

Are ceva special testul 4  ](*,)

hint: faceti %p dupa impartirea la 3 altfel nu se mai simplifica si da WA

Dc imi da time limit excedeed..Sa imi explice si mie cineva va rog  :thumbdown: ](*,)

Pentru ca solutia ta e prea inceata ca sa rezolve problema. Mai exact, solutia corecta are complexitate O(1), in timp ce solutia ta are complexitate O(N).

imi puteti zice si mie care este formula ca nu o gasesc , multumesc anticipat

Poate te ajuta articolul cu soluții: http://www.infoarena.ro/happy-coding-2005-1/solutii . Succes!

Am folosit formulele din solutia oficiala si totusi primesc wrong answer pe toate testele cu exceptia primelor doua. Ma poate ajuta cineva? E extrem de stresant.

1 ≤ N ≤ 10^9

Tu inmultesti tot odata si e normal sa iti faca overflow. Fa cate o inmultire si apoi modulo.

s=(n*(n+1)*(n-1))/3; si apoi ii dau comanda g << s%p;(s si n sunt long long int) de ce imi da "Killed by signal 8(SIGFPE)." ?

În primul rând, produsul nu încape în long long, trebuie să înmulțești câte 2 numere și să faci modulo după fiecare înmulțire.

De asemenea, ar fi indicat să pui
la sfârșitul funcției main :)

Am pus dar tot imi da aceeasi eroare

Înlocuiește
cu

și ai grijă la împărțirea în modul. (a / b) % p nu e echivalent cu ((a % p) / (b % p)) % p

Am folosit acum g << (n-1)%p*n%p*(n+1)%p/3; si iau 60 de puncte. La celelalte imi spune incorect dar nu imi dau seama ce conditie mai trebuie pusa

pune paranteze peste tot, adica asa: ((n%p)*((n-1)%p)*((n+1)%p)/3)%p;

esti f.f prost