184 Mult

[•domino]

Aici puteţi discuta despre problema Mult.

[•sims_gl]

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?

[ditzone]

Da raspunsul e 3... Zice clar in enunt

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.

[•cyron]

cam ce complexitate ar trebui ?

[u-92]

am scos N*K*c ... c o constanta suficient de mica sa intre in timp

[•pauldb]

Constanta aia c vine de la numere mari nu? 

Cum ai redus-o? Eu folosesc baza 10^9 si iau doar 30 de puncte...

[•filipb]

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.

[•crawler]

enuntul are o mica greseala 

Cod:

... nici o cifran din el ...

[•DITzoneC]

S-a corectat.

[•CezarMocan]

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... 

[•wefgef]

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++?

[•CezarMocan]

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  . Tot nu reusesc sa iau 100, doar 85. Cu ce ma ajuta daca declar la matrici puteri ale lui 2??

[•gogu]

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.

[•wefgef]

Invata STL. O sa te ajute mult.

[•CezarMocan]

Multumesc mult Gogu si Wefgef... am reusit sa iau 100 

[•wefgef]

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;

din procedura aduna si uite ce timpi am obtinut: http://infoarena.ro/job_detail/123929. Rapid nu? (si e sursa ta )

[•blue_phoenix]

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

  for(i=1;i<n;i++){
     for(j=0;j<k;j++){
        dp[i+1][j]+=dp [ i ] [j];
        dp[i+1][(j*10+v[i+1])%k]+=dp [ i ] [j];//daca consider a (i+1)-a cifra
     }
  }

dar iau doar 10 puncte cu incorect pe restul
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

[•pauldb]

Problema e ca rezultatul poate sa fie pana la 2^N si trebuie folosite "numere mari" in dinamica.

[•blue_phoenix]

a da, asa e. de data asta nu cere rezultatul modulo ceva, ci chiar numarul. multumesc!

[•SpiderMan]

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 10⁹, dar tot nu iasa...

[•vendetta]

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 ?

[•Schumi]

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.

[•freak93]

Fixed 

[•freak93]

Am vazut ca limita de timp era un pic prea stransa. A fost marita la 0.8.