[es] - Stari dobri USACO zadatak.. skoro pa gotov!

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.

+148 Profil

Stari dobri USACO zadatak.. skoro pa gotov!

^{17.07.2005. u 23:24 - pre 228 meseci}

Vidim da se nista ne desava na ovom dijelu foruma, pa reko' da malo pokrenem stvari sa mrtve tacke. Zanima me rjesenje sledeceg zadatka: Dat je beskonacan niz cifara (123456789101112...), odrediti n-tu cifru niza. Evo kako sam ja to rjesio (tacnije ovaj kod jos ne radi, ali mislim da sm koncept rjesenja dobro zamislio). Medjutim iako sam izbjegao koristenje niza, ipak je moj program teoretski ogranicen na maxlongint, jer je to max vrijednost brojaca. Da li bi se to priznalo na takmicenju?

Code:

program pas;
uses wincrt;
var br,cif,n,temp,vre:longint;

function Br_cifara (n:integer):integer;
var s:string;
begin
str (n,s);
Br_cifara:=length(s);
end;

function djelilac (n:integer):integer;
var i,st:integer;
begin
st:=1;
for i:=0 to n-2 do
    st:=st*10;
djelilac:=st;
end;

begin
cif:=0;  br:=0;   vre:=0;
write ('n='); {podaci se za sada ucitavaju sa tastature}
readln (n);
while cif<n do {radi dok ne dodjes do trazene cifre}
      begin
      inc(br,1); {povecaj pod-broj* za 1}
      temp:=br;
        repeat
        inc(cif,1);
        vre:=temp div djelilac(br_cifara(temp));  {vre pamti vrijednost za cifru cif}
        temp:=temp div 10; {omogucuje izracunavanje sledece cifre pod-broja}
        until temp=0;
      end;
write ('vre=',vre);
end.

*pod-broj je broj 1..beskonacno ciji niz zapravo cini zadani beskonacni broj.
Ponovo napominjem da rjesenje jos ne radi, ali koncept rjesenja bi trebao biti ovakav... ili ne? :)

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Stari dobri USACO zadatak.. skoro pa gotov!

^{18.07.2005. u 00:27 - pre 228 meseci}

Citat:

Da li bi se to priznalo na takmicenju?

Na takmicenju ti kompijuter testira program i u tvom kodu je dovoljno da si pogresio samo jedno slovo i da ti onda ceo zadatak porolazi (kad pomenis to slova), ali opet ti dobijas 0 poena.

Sto se tice algoritma, on je mnogo spor. Koliko se secam ovde je n mnogo veliki (o ovom zadatku se skoro diskutovalo, pre nekih 2-3 nedenje)... Ti uvek ovde dodajse novi broj tj. 1,2,3,...10,11,...100,101,...1001... Zato prvo mozes da vidis koliko zadnji broj koji si dodao tom tvom broju koji pravis, ima cifara pa npr. u kojoj se polovini nalazi... Jer inace program ce ti puci na vremenu... Nadam se da me razumes.

I (mada nebitno) kada neki brojac povecavas za 1 ne moras da pises

nego samo

...

Math is like love. A simple idea but it can get complicated.

Odgovor na temu