Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

USACO zadatak (help)

[es] :: Art of Programming :: USACO zadatak (help)

[ Pregleda: 4755 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon USACO zadatak (help)01.05.2005. u 01:35 - pre 214 meseci
Ako netko moze neka rjesi ovo, ili bar da ideju.Probao sam al ne ide.
Problem 12: Long Division [Traditional, 2005]

The cows know their math ability is weak. Help them learn to divide
by showing them the proper answer for several long division problems.

Read in a pair of positive integers (each of which fits in 27 bits) and
show their quotient to exactly 35 decimal places (even if many of those
decimal places are '0'). If the answer is less than one, output
exactly one leading 0 before the decimal point. Do not round the final digit.

PROBLEM NAME: ldiv

INPUT FORMAT:

* Line 1: A single integer: the numerator

* Line 2: A single integer: the denominator

SAMPLE INPUT (file ldiv.in):

489384
583

INPUT DETAILS:

Calculate 489384/583

OUTPUT FORMAT:

* Line 1: The quotient with exactly 35 decimal places.

SAMPLE OUTPUT (file ldiv.out):

839.42367066895368782161234991423670668

OUTPUT DETAILS:

Even though the next digit after ...0668 is 9, no rounding is performed
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.yu1.net.



+3 Profil

icon Re: USACO zadatak (help)01.05.2005. u 06:00 - pre 214 meseci
Kako bi olovkom i papirom izracunao 35 decimala kolicnika dva broja?
Code:

#include <iostream>
int main(void){
    unsigned int numerator, denominator;
    std :: cin >> numerator >> denominator;
    std :: cout << "\n" << numerator / denominator << ",";
    for(int i = 1; i <= 35; i++){
        numerator %= denominator;
        numerator *= 10;
        std :: cout << numerator / denominator;
    }    
    system("pause");
}

O_o
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Re: USACO zadatak (help)01.05.2005. u 12:41 - pre 214 meseci
Barem si mogao počekati da natjecanje prođe, pa onda pitati.
#include <D3adly.h>
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)01.05.2005. u 14:31 - pre 214 meseci
Hvala blaza. Nemozes vjerovati kako sam to sinoc zakomplicirao...
Deadly ne brini se, submitao sam ja svoje,al ne znam bash oce li proc.Pitao sam jer mi je dosta zivaca oduzeo zadatak, jer nisam mogao naci neko normalno rjesenje nego sam komplicirao...
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Re: USACO zadatak (help)01.05.2005. u 17:49 - pre 214 meseci
Dobro onda!

P.S. kad smo već kod toga, jeli netko riješio 3. zadatak?
#include <D3adly.h>
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)02.05.2005. u 00:00 - pre 214 meseci
Ja sam rješio treći.To ti je u biti DFS. Princip je sljedeći:
Uzmeš riječ iz rječnika. Nadješ joj prvo slovo u tabeli.Od tu ideš DFS-om okolo i tražiš drugo slovo,pa ako si našao drugo tražiš treće ...Cijelo vrijeme pamtiš koliko si slova iz te riječi našao i ako si našao sve ispišeš i returnaš. Treba tu još neke provjere radit ,ali to je to...
Ako te zanima kod mogu ti poslati na mail...
Reci mi kako si prvi rješio? neće mi sigurno proći u 0.3...
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Re: USACO zadatak (help)02.05.2005. u 18:51 - pre 214 meseci
Prvi je jednostavan. Napraviš si funkciju npr. tobin gdje pretvaraš brojeve u binarne i taj binarni zapis zapisuješ u string. Zatim prolaziš po tim stringovima i brojiš jedinice. Ako je manje od 5 povečaš brojac.

btw. ne razumijem kako si riješio 3., 1. nisi :-)

Možeš poslati kod na mail.

Ako želiš kod od 1. zadatka reci.
#include <D3adly.h>
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)02.05.2005. u 20:39 - pre 214 meseci
Evo ti na mailu moj kod za prvi,koji je dosta brži od tvoga,ali će pasti za neke testove (1-15000000), i treći.





















 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: USACO zadatak (help)03.05.2005. u 13:37 - pre 214 meseci
Citat:
D3adly: Prvi je jednostavan. Napraviš si funkciju npr. tobin gdje pretvaraš brojeve u binarne i taj binarni zapis zapisuješ u string. Zatim prolaziš po tim stringovima i brojiš jedinice. Ako je manje od 5 povečaš brojac.

btw. ne razumijem kako si riješio 3., 1. nisi :-)

Možeš poslati kod na mail.

Ako želiš kod od 1. zadatka reci.


Sad sam pogledao zadatke i po meni je prvi najveca misterija. Ovaj straight forward nacin koji si ti napomenuo radi sporo.

Drugi je klasicno delenje 2 velika broja, treci je dfs (kao sto rece microsoft) i cetvrti je bezveze i lak.
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Re: USACO zadatak (help)03.05.2005. u 14:09 - pre 214 meseci
Rofl, ne znam kako nisam vidio limit! Neznam kako mi je to promaklo. Bilo mi je čudno da je 1. zadatak na Usaco najlakši, ali .... Ne samo da sam radio ovom jaaako sporom tehnikom, nego sam stavio i integere! LOL. Sad kad malo bolj e pogledam zadatak tek shvaćam koliko je kompliciraniji.

btw. sorry na krivim savjetima!!

#include <D3adly.h>
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)03.05.2005. u 20:27 - pre 214 meseci
Točno, prvi je najveći ujeb, a četvrti je prelagan.
Htio sam sad testirati zadatke, al ne moze se submitat. Jedva čekam da vidim za koliko će mi proći prvi...
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: USACO zadatak (help)04.05.2005. u 10:37 - pre 214 meseci
Moja ideja za prvi je da se radi obrnuto od onog straight-forward nacina tj. da generisem se moguce binarne brojeve koji imaju 4 i manje keceva i onda da pogledam koji se nalaze u datom opsegu i prebrojim ih.
To bi moglo lako da se uradi generisanjem kombinacija bez ponavljanja. Posto je 15 000 000 24-bitini broj (valjda sam dobro izracunao) onda bi broj kombinacija bio (25*24*23*22) / (4*3*2*1) = 12650. 25 sam stavio zbog mogucnosti da se neki kec uopste i ne pojavi tj da moze biti i manje od 4 keca.
Tako da mi ovo deluje kao razumno resenje, generisanje 12000 brojeva radi brzo!
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)04.05.2005. u 14:27 - pre 214 meseci
Prošlo mi je sve osim tri test primjera na prvom. Ajde iskodiraj to generiranje soulmate,submitaj pa cemo vidjeti...
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: USACO zadatak (help)04.05.2005. u 15:40 - pre 214 meseci
Evo otkucah ga za 20-tak minuta i proslo je sve za 0.01 - 0.02 sec.
Ispade na kraju jako lak zadatak, al trebalo je malcice mucnuti glavom
Evo i koda..

Code:

{
PROB: cnums
LANG: PASCAL
}

program pera;
var
  min,max:longint;
  rez:longint;
  niz:array[1..4] of integer;
  
procedure DatIN;
var
  f:Text;
begin
    assign(f,'cnums.in'); reset(f);
    read(f,min,max);
    close(F);
end;    

procedure DatOut;
var
  f:Text;
begin
    assign(f,'cnums.out'); rewrite(f);
  writeln(f,rez);
  close(f);
end;

procedure PostaviPrvu(n:integer);
var
  i:integer;
begin
    for i:=1 to n do niz[i]:=i;
end;

function Poslednja(n:integer):boolean;
var
  i:integer;
  ok:boolean;
begin
    i:=n;
    ok:=true;
    while ok and (i>=1) do
    begin
        if niz[i]=25-n+i then dec(I)
        else ok :=false;
    end;
    poslednja:=ok;
end;

procedure postavisledecu(n:integer);
var
  i,j:integer;
begin
    i:=n;
    while niz[i]=25-n+i do dec(i);
    inc(niz[i]);
    for j:=i+1 to n do niz[j]:=niz[j-1]+1;
end;

function st(n:integer):longint;
var
  rez,x:longint;
begin
    if n>=0 then
    begin
        rez:=1;
        x:=2;
        while n>0 do
        begin
            if odd(n) then rez:=rez*x;
          n:=n div 2;
          x:=sqr(x);
        end;        
        st:=rez;
    end
    else st:=0;
end;

function konv(n:integer):longint;
var
  sum:longint;
  i:integer;
begin
    sum:=0;
    for i:=1 to n do sum:=sum + St(niz[i]-1);
    konv:=sum;
end;

procedure Solve;
var
  br:longint;
  i:integer;
begin
    rez:=0;
    for i:=1 to 4 do
    begin
      PostaviPrvu(i);
        br:=konv(I);
        if (br>=min) and (br<=max) then    inc(rez);
        while not Poslednja(i) do
        begin
            PostaviSledecu(i);
            br:=konv(i);
            if (br>=min) and (br<=max) then inc(rez);
        end;
    end;
end;

begin
    DatIN;
    Solve;
    DatOut;
end.

Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com


Profil

icon Re: USACO zadatak (help)05.05.2005. u 16:39 - pre 214 meseci
stha je usaco ? :I

zadaci su zanimljivi ...
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: USACO zadatak (help)05.05.2005. u 18:25 - pre 214 meseci
Pa ti ne znas?? :)

www.usaco.org

To je kao sajt americke olimpijske ekipe iz informatike. Oni imaju tu odlican trening deo gde resavas zadatke i prelazis nivoe, a i organizuju svakog meseca takmicenje. Idi na sajt i procitaj za vise informacija.
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481


Profil

icon Re: USACO zadatak (help)07.05.2005. u 15:22 - pre 214 meseci
--SOULMaTe-- :
Citat:



Evo otkucah ga za 20-tak minuta i proslo je sve za 0.01 - 0.02 sec.
Ispade na kraju jako lak zadatak, al trebalo je malcice mucnuti glavom
Evo i koda..



možeš malo objasniti kako ti funkcionira kod. ;-)
#include <D3adly.h>
 
Odgovor na temu

Microsoft
Split

Član broj: 41316
Poruke: 31
*.cmu.carnet.hr.



Profil

icon Re: USACO zadatak (help)07.05.2005. u 19:45 - pre 213 meseci
Bio sam 18 - 16 ih je imalo perfect score...
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.



Profil

icon Re: USACO zadatak (help)08.05.2005. u 12:15 - pre 213 meseci
Bravo Microsoft!

@Deadly
Prvo ide jedna for petlja koja govori koje duzine(tj. od koliko jedinica) da generise kombinacije. Znaci u nasem slucaju od 1 do 4. A zatim generise sve moguce kombinacije duzine i (gde je i brojac for petlje). Jedna kombinacije npr. duzine 4 bi izgledala ovako 3 13 15 22 (uvek je sortirana) i to znaci da ako pogledas binarno broj da se kecevi nalaze na mestu 3, mestu 13, mestu 15 i mestu 22, a na svim ostalim mestima su logicno nule. Zatim pozovem proceduru "konv" koja taj broj pretvori u decimalan broj tako sto za ovaj nas primer uradi: 2^(3-1) + 2^(13-1) + 2^(15-1) + 2^(22-1). To -1 ide svudge zato sto u binarnom zapisu na prvom mestu je stepen nula a na drugom jedan i tako dalje. Kontas?
I to sve radi dok ne vidi da je poslednja kombinacija a to bi za duzinu 4 bilo 22 23 24 25, dok je prva naravno 1 2 3 4. Procedura PostaviSledece naravno generise sledecu kombinaciju.

Ako nesto nije jasno pitaj slobodno...
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

[es] :: Art of Programming :: USACO zadatak (help)

[ Pregleda: 4755 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.