|
Titlul: 184 Mult Scris de: Mircea Pasoi din Martie 02, 2006, 01:19:56 Aici puteţi discuta despre problema Mult (http://infoarena.ro/problema/mult).
Titlul: 184 Mult Scris de: Alexandru Simion din Martie 03, 2006, 10:00:07 Pentru exemplul:
2 7 7 7 raspunsul ar trebui sa fie 3 nu? Adica cele doua moduri de a obtine 7 se numara separat nu? Titlul: 184 Mult Scris de: ditzone din Martie 03, 2006, 12:33:14 Da raspunsul e 3... Zice clar in enunt
Citat Aflati numarul de posibilitati de a obtine un multiplu a lui K din numarul initial daca singura operatie permisa este stergerea unei cifre pentru ca cei doi copii sa se impace. Titlul: 184 Mult Scris de: sorin fagateanu din Martie 05, 2006, 11:48:38 cam ce complexitate ar trebui ? :(
Titlul: 184 Mult Scris de: u-92 din Martie 05, 2006, 13:49:36 am scos N*K*c ... c o constanta suficient de mica sa intre in timp :P
Titlul: Raspuns: 184 Mult Scris de: Paul-Dan Baltescu din Iunie 10, 2006, 14:35:55 Constanta aia c vine de la numere mari nu? :-k
Cum ai redus-o? Eu folosesc baza 10^9 si iau doar 30 de puncte... :sad: Titlul: Raspuns: 184 Mult Scris de: Filip Cristian Buruiana din Iunie 10, 2006, 15:09:16 Nu e constanta de vina, eu am baza 10^8 si mi-a intrat destul de lejer. Ai grija la complexitatea dinamicii, toata faza e sa faci dinamica inainte si nu inapoi.
Titlul: Răspuns: 184 Mult Scris de: Puni Andrei Paul din Iunie 15, 2007, 20:44:26 enuntul are o mica greseala :)
Cod: ... nici o cifran din el ... Titlul: Răspuns: 184 Mult Scris de: Adrian Diaconu din Iunie 16, 2007, 22:48:44 S-a corectat.
Titlul: Răspuns: 184 Mult Scris de: Cezar Mocan din Ianuarie 17, 2008, 11:59:31 Imi dati si mie ceva idei de optimizare? Fac cu dinamica, in complexitate N*K, pastrez doar ultimele 2 linii ale matricii, la numerele mari folosesc baza 10^8, fac cu scaderi in loc de modulo si iau doar 75 de puncte... :fighting:
Titlul: Răspuns: 184 Mult Scris de: Andrei Grigorean din Ianuarie 17, 2008, 12:20:39 1. Lucreaza cu baza 10^9
2. Tu la fiecare pas initializezi x cu 0, iar la sfarsit ai y := x. Lucreaza cu o matrice de 2 * Kmax * BigInt, ca sa eviti copierea asta. 3. Declara matricile cu dimensiuni puteri ale lui 2. 4. Nu mai scrie in Pascal. Chiar, de ce nu ai trecut dupa JBOI pe C++? Titlul: Răspuns: 184 Mult Scris de: Cezar Mocan din Ianuarie 17, 2008, 13:00:08 Pai unele le scriu in C... depinde de dispozitie...uneori scriu in C, alteori in Pascal... asta am scris-o in Pascal ca in C nu am implementate operatii pe numere mari cu baza mare :oops:. Tot nu reusesc sa iau 100, doar 85. Cu ce ma ajuta daca declar la matrici puteri ale lui 2??
Titlul: Răspuns: 184 Mult Scris de: Gogu Marian din Ianuarie 17, 2008, 14:12:34 Cum ai facut initial ar fi trebuit sa merga de 100 de puncte lejer. Trebuie sa te uiti si la warning-uri: :)
"user.fpc(15,9) Warning: Mixing signed expressions and longwords gives a 64bit result" Atunci cand amesteci intregi cu semn si intregi fara semn ai nevoie de intregi cu semn pe 64 de biti ca sa retii rezultatul, daca iti poate da overflow, si cateodata compilatorul iti face asta automat. Incearca sa lucrezi numai cu longword si cred ca nu ar trebui sa ai problema asta. Titlul: Răspuns: 184 Mult Scris de: Andrei Grigorean din Ianuarie 17, 2008, 14:22:50 Invata STL. O sa te ajute mult.
Titlul: Răspuns: 184 Mult Scris de: Cezar Mocan din Ianuarie 17, 2008, 18:25:20 Multumesc mult Gogu si Wefgef... am reusit sa iau 100 :yahoo:
Titlul: Răspuns: 184 Mult Scris de: Andrei Grigorean din Ianuarie 17, 2008, 18:33:32 Cu ce ma ajuta daca declar la matrici puteri ale lui 2?? Pai sa zicem ca tu vrei sa accesezi A[ i ][ j ]. Matricele se aloca liniar, deci elementul care te intereseaza este de fapt al (i-1)*M+j-lea de la adresa de unde s-a alocat A[0][0] - primul element. Daca M este putere de 2, atunci operatia (i-1)*M este de fapt o shiftare si ia semnificativ mai putin timp de calculat. S-ar putea sa mai fie o explicatie legata de cum foloseste un calculator memorie.. nu stiu :). Vezi ca uneori daca declari prea multa memorie, iti merge mai incet programul. Se pare ca asa e in cazul de fata :). L. E.: Mai Cezarel, cum te chinuiai tu degeaba. Pai de ce scoti tu operatia mod, daca o lasi pe aia de div? Ca sunt la fel de proaste. Am scos instructiunea Cod: t := aux div baza; Titlul: Răspuns: 184 Mult Scris de: Posea Elena din Decembrie 16, 2011, 08:54:38 nu cred ca am inteles bine cerinta
"singura operatie permisa este stergerea unei cifre pentru ca cei doi copii sa se impace." de fapt, din exemplu, pot sa sterg oricate, si din subsirul care ramane scris, fac un numar. daca e div cu k, il numar. eu am facut cu dinamica, asa: (dp[ i ][j]=numarul de numere care restul j la impertirea cu k, considerand doar primele i cifre=> raspunsul va fi, la final, in dp[n][0]) //initializarea/ v[] e sirul initial de cifre... Cod: for(i=1;i<=n;i++)dp[i][v[i]%k]=1;//cifra asta pot sa iau si singura, neimperecheata cu nimic din fata cerinta s-a schimbat semnficativ in ultimul timp? va ca se vorbeste de numere mari; in plus, sunt multe surse de 100p care au un timp de aproape 2secunde Titlul: Răspuns: 184 Mult Scris de: Paul-Dan Baltescu din Decembrie 16, 2011, 09:46:02 Problema e ca rezultatul poate sa fie pana la 2N si trebuie folosite "numere mari (http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai)" in dinamica.
Titlul: Răspuns: 184 Mult Scris de: Posea Elena din Decembrie 16, 2011, 10:03:46 a da, asa e. de data asta nu cere rezultatul modulo ceva, ci chiar numarul. multumesc!
Titlul: Răspuns: 184 Mult Scris de: Simoiu Robert din Decembrie 16, 2011, 16:18:24 Va puteti uita sa vedeti daca e buna limita de timp ?
[PS] : Si daca e buna, am 95 puncte, si nu stiu ce sa mai optimizez, am facut dinamica cu baza 109, dar tot nu iasa... Titlul: Răspuns: 184 Mult Scris de: Salajan Razvan din Septembrie 04, 2012, 21:15:55 Salut!
Am o complexitate de N*K*Const (const fiind de la numerele mari) dar iau maxim 90 de puncte! Ultima sursa de 100 de puncte a fost la inceputul anului. De vina e : evaluatorul sau implementarea mea ? Titlul: Răspuns: 184 Mult Scris de: Dumitru Andrei Georgian din Septembrie 05, 2012, 12:11:26 Si eu iau maxim 95 cu TLE pe testul 10. Din cate vad, din februarie nu a mai luat nimeni 100. Cred ca trebuie marita limita putin.
Titlul: Răspuns: 184 Mult Scris de: Adrian Budau din Septembrie 05, 2012, 12:34:40 Fixed :D
Titlul: Răspuns: 184 Mult Scris de: Adrian Budau din Noiembrie 09, 2013, 22:16:07 Am vazut ca limita de timp era un pic prea stransa. A fost marita la 0.8.
|