Admin je rekao da je najbolje reshenje ovog zadatka malo pretesko, i da je zato podigao vremensko ogranichenje.
Admine, kako ide to malo pretesko resenje? :)
Admine, kako ide to malo pretesko resenje? :)
Z-cifre
A zar ti ne mozes da vidis to najbolje resenje?
Pa trenutno adminovo resenje je isto kao i moje... pa me zanima da li je to najefikasnije resenje ...
A kako ide to tvoje?
Mislim koja je ideja?
Ja sam iskucao nesto sto radi mnooooogo sporo pa je proslo samo 5 test primera :(
Mislim koja je ideja?
Ja sam iskucao nesto sto radi mnooooogo sporo pa je proslo samo 5 test primera :(
dinamicko programiranje ... ako hocesh malo detaljnije resenje, obrati mi se na mail ( rajkon@gmail.com ), da ne bi ovde kvarili zabavu ostalima :)
Poenta je da za desnu stranu nadjes samo proizvode koje je moguce dobiti, videces da je to mali procenat (265 od 5000) koje je moguce dobiti na levoj strani. To mozes naci u M*logM vremenu, gde je M=5000. Posle toga radis normalno dinamicko za desnu stranu samo moras da pazis kakve strukture koristis (malo je pipavo), ne bi li skratio vreme.
Ako je K (K=265) broj proizvoda/zbira koji se mogu dobiti na obe strane onda ti je slozenost K*N gde je N-duzina broja.
Sve u svemu, resenje nije toliko tesko koliko ga je mozda tesko implementirati.
Pozdrav,
Z
Ako je K (K=265) broj proizvoda/zbira koji se mogu dobiti na obe strane onda ti je slozenost K*N gde je N-duzina broja.
Sve u svemu, resenje nije toliko tesko koliko ga je mozda tesko implementirati.
Pozdrav,
Z
Zaboravio sam jedan detalj, koji nije bas detalj.
Elem, znaci kada nadjes tih K brojeva, dinamicko radis samo za desnu stranu, dok za levu radis sledecu stvar:
- Na koliko nacina se moze napraviti zbir A od N cifara, gde prva cifra nije nula.
- Resenje: To je koeficijent uz x^A u razvoju polinoma ( 1 + x + x^2 + x^3 + ... + x^9 )^N, minus koeficient us x^A u razvoju polinoma ( 1 + x + x^2 + x^3 + ... + x^9 )^(N-1). Kao sto vidis ovo je samo reformulacija problema, medjutim, sada mozes da stepenujes polinom binarno. I tako nadjes sve sto ti je potrebno :)
Pozdrav,
Z
Elem, znaci kada nadjes tih K brojeva, dinamicko radis samo za desnu stranu, dok za levu radis sledecu stvar:
- Na koliko nacina se moze napraviti zbir A od N cifara, gde prva cifra nije nula.
- Resenje: To je koeficijent uz x^A u razvoju polinoma ( 1 + x + x^2 + x^3 + ... + x^9 )^N, minus koeficient us x^A u razvoju polinoma ( 1 + x + x^2 + x^3 + ... + x^9 )^(N-1). Kao sto vidis ovo je samo reformulacija problema, medjutim, sada mozes da stepenujes polinom binarno. I tako nadjes sve sto ti je potrebno :)
Pozdrav,
Z
Nakon toga uradis isto sto si i ti uradio... :)
Pozdrav,
Z
Pozdrav,
Z
Submitovao sam bolje resenje, pa mozes da ga pogledash.
hm , i ja sam hteo da radim slicno ali nisam znao kako da izracunam levu stranu.
pozdrav.
pozdrav.
imam pitanje za admina:
kako bi, na primer, islo pronalazenje broja kombinacija tih "desnih" brojeva ciji proizvod moze da bude NEKI broj? cini mi se da si rekao da se radi dinamicki, ali jel moze jos neki uput? :) naime, ja sam, bar tako mislim, pronasao kombinatornu formulu koja racuna broj kombinacija "levih" brojeva tako da im je suma NEKI broj, ali za ovo mi nista korisno ne pada na pamet!!!
kako bi, na primer, islo pronalazenje broja kombinacija tih "desnih" brojeva ciji proizvod moze da bude NEKI broj? cini mi se da si rekao da se radi dinamicki, ali jel moze jos neki uput? :) naime, ja sam, bar tako mislim, pronasao kombinatornu formulu koja racuna broj kombinacija "levih" brojeva tako da im je suma NEKI broj, ali za ovo mi nista korisno ne pada na pamet!!!
Leva strana:
Da, postoji matematicka formula, ne znam kako se tacno zove na srpskom, ... to je isto sto i binomna formula, ali ne za binome nego za polinome, mozda se zove polinomialna formula.. To se vidi iz teksta koji sam gore napisao. U svakom slucaju, i ta formula sadrzi sumu u sebi..
Desna strana:
Razmisljaj na ovaj nacin:
- Kako da dobijem proizvod = A pomocu N cifara... ?
- mogu da imam proizvod A/9 od N-1 cifru, pa dodam devetku...
- ili mozda A/8 pa dodam 8...
- ili....
Best,
Z
Da, postoji matematicka formula, ne znam kako se tacno zove na srpskom, ... to je isto sto i binomna formula, ali ne za binome nego za polinome, mozda se zove polinomialna formula.. To se vidi iz teksta koji sam gore napisao. U svakom slucaju, i ta formula sadrzi sumu u sebi..
Desna strana:
Razmisljaj na ovaj nacin:
- Kako da dobijem proizvod = A pomocu N cifara... ?
- mogu da imam proizvod A/9 od N-1 cifru, pa dodam devetku...
- ili mozda A/8 pa dodam 8...
- ili....
Best,
Z
Cekaj, cekaj...
@ nalism
Kako si nasao tu formulu, otkucaj je ako znas LaTex (otkucaj kod koji odgovara toj formuli u LaTexu)
@ nalism
Kako si nasao tu formulu, otkucaj je ako znas LaTex (otkucaj kod koji odgovara toj formuli u LaTexu)
pa da... postoji naziv i cak mislim da se broj mogucnosti za "levo" naziva: "broj uredjenih razbijanja broja N" (u kombinatorici)!
al' opet za "desno": zar sada nece biti problem rasclanivanje slucajeva da se u posmatranju A/9 dodaje jedna 9 za N-1 ili dve trojke za N-2; ili za 8 - umesto 8 mogu se dodati tri dvojke...
mozda nisam lepo svatio! :[
al' opet za "desno": zar sada nece biti problem rasclanivanje slucajeva da se u posmatranju A/9 dodaje jedna 9 za N-1 ili dve trojke za N-2; ili za 8 - umesto 8 mogu se dodati tri dvojke...
mozda nisam lepo svatio! :[
m@re_m@re:
koja ti je email adresa!
koja ti je email adresa!
salji na smallfish@ptt.yu
Admine, sto ti ne radi kompajler kako valja?
#include <iostream>
using namespace std;
int main(void)
{
char array[1000]="0";
char buffer[50];
int i;
cin >> i;
for(int n = 1; n<=i; n++){
itoa(n,buffer,10);
strcat(array,buffer);
}
cout << array[i];
return 0;
}
Kod je dobar, a tvoj kompajler ne prepoznaje itoa f-ju.
Sramota stvarno.
#include <iostream>
using namespace std;
int main(void)
{
char array[1000]="0";
char buffer[50];
int i;
cin >> i;
for(int n = 1; n<=i; n++){
itoa(n,buffer,10);
strcat(array,buffer);
}
cout << array[i];
return 0;
}
Kod je dobar, a tvoj kompajler ne prepoznaje itoa f-ju.
Sramota stvarno.