Zadaci s natjecanja -> C,C++,Pascal

poruka: 65
|
čitano: 17.860
|
moderatori: Danny_HR, Lazarus Long, XXX-Man, vincimus
+/- sve poruke
ravni prikaz
starije poruke gore
9 godina
offline
Bomboni

Mala Zrinka slavi rodjendan i prijatelji joj dolaze na parti. Ona zeli svakom prijatelju dat nekoliko bombona, ali tako da oni najpametniji dobe najvise :). Napravila je robot koji moze ici samo u smjeru jug ili zapad (gornji lijevi kut je na sjevero-istoku) na i stavila ga na neku plocu dimenzija NxM podjeljena u kvadratice 1x1 tako da se na svakom kvadraticu nalazi odredjeni broj bombona. Svaki prijatelj mora odvoziti robot od pozicije (1,1) do pozicije (N,M). Robot skupi sve bombone s kvadratica kojima putuje. I ti dolazis na parti i jako volis bombone pa te zanima koliko ih mozes najvise skupit.

Ulazni podaci

U prvom redu dva prirodna broja N <= 100 i M <= 100, dimenzije ploce.

U sljedecih N redova nalazi se M prirodnih brojeva (ili nula) manjih od 1000 (broj bombona)

Izlazni podaci

U prvom i jedinom redu treba ispisati koliko mozes skupiti bombona.

 

Pomoć molim :)

logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Zadatak mozemo rijesiti primjenom klasicnog dinamickog programiranja.

 

dakle imamo array dp[ MAX_ROW ][ MAX_COL ];

dp[i][j] - oznacava maximalan broj bombona do pozicije i, j.

 

za svaku poziciju izracunamo :

dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) + A[i][j]; // A - broj bombona na i,j pos.

moramo paziti samo na granicne slucajeve za i == 1 || j == 1

 

rjesenje je dp[N][M];

 

HINT : Zadatak je moguce rijesiti vec pri ucitavanju.

Poruka je uređivana zadnji put uto 1.3.2011 17:16 (Budimir).
 
0 0 hvala 1
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal
Ok,hvala,napisao kod i radi :D.
E sad..to je dinamicko programiranje? Sto je to zapravo :p? Na cemu se temelji?
logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Dinamicko programiranje, hmm. Iako je poprilicno jednostavna ideja, tesko je objsniti sto je to zapravo.

Dinamicko programiranje, bio bi sistem razbijanja velikog problema na manje te potom rjesavanjem manjih, rijesiti veliki.

Dinamicko programiranje je razmjena, prostor za vrijeme. Tj. sve manje probleme koje izracunas, spremis tako da ih nemoras ponovno izracunat.

 

Napr, fibbonacijevi brojevi, ukoliko bi ih rjesavali rekurzivno.

fibo( 5 ) -> racunam fib(4) fib(3)

fib( 4 ) -> fib(3) fib(2)

...

kao sto vidmo u drugome redu, drugi puta racunam fib(3). Pa ako ga prvi puta spremim onda ga drugi puta samo vratim.

 

Ako se problem rjesava rekurzivno, tada se koristi memoizacija(spremanje).

No vijek je bolji bottom_up ako je moguc.

 

Mogao bi pisati jos satima, ali najbolje da pogledas ove zadatke, pa javis sto ti nije jasno.

 

Sto se tice naseg primjera :

U nizu dp, mi imamo rjesenja za sve pozicije, ne samo [N][M].

Dake dp[i][j] = max( dp[i][j-1], dp[i-1][j] ) + A[i][j], mi uzimamo bolje rjesenje između 2 postojeca.

Gledamo, jeli bolje doci do (i,j-1) pa skrenuti desno ili je bolje doci do (i-1, j) pa skrenuti dolje.

Dakle u nizu dp imamo spremljena SVA rjesenja od pozicije (1, 1).

 

Ovdje su klasicni primjeri.

http://forum.zrs.hr/index.php/topic,289.0.html

Poruka je uređivana zadnji put uto 1.3.2011 19:40 (Budimir).
 
1 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Hvala puno na linku :D!

Moj problem u ovom zadatku je bio što sam razmišljao da li je bolje s polja (x,y) ići na (x+1,y) ili (x,y+1),a tako ga je nemoguće rješit :/(trebao bi gledat sve kombinacije {#})

A dp moram proučit vjerojatno če zatrebat sad na županijskom {#}

logika ne postoji.
Poruka je uređivana zadnji put uto 1.3.2011 20:09 (KKristijan).
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Razred, skola, grad ?

 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

2.,MIOC,Zagreb {#}

logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Prouci zadatak BOND, HONI 1.kolo 2006/2007. Veoma cesto bude, takav nekakav sablonski zadatak. I prosle i ove godine je bio(II podskupina).

 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal
Rjesio prva 4 iz tog kola u 20min :D.Na ovom sam zapeo al nemoj rjesenje govorit da promislim jos malo :p.
logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

http://www.spoj.pl/problems/KNAPSACK/

 

Evo problem na kojem je razrađena ideja dinamickog p.

 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

#include <cstdio>
#include <algorithm>
using namespace std;

struct stvar{
    int size;
    int value;
    double koef;
};

stvar stvari[2002];


bool cmp( const stvar &x , const stvar &y){
    if( x.koef < y.koef ) return 0;
    return 1;
     }

int main(){

    int S,N;

    scanf("%d %d",&S,&N);

    for(int i = 0 ; i < N ; ++i)
    scanf("%d %d",&stvari[i].size,&stvari[i].value);

    for(int i = 0 ; i < N ; ++i) stvari[i].koef = stvari[i].value/stvari[i].size;

    sort(stvari,stvari+N,cmp);
    int o = -1;
    int TOT = 0;

    while( S != 0 ){

    ++o;

    if( o == N ) break;

    if( stvari[o].size > S ) continue;

    S -= stvari[o].size;
    TOT += stvari[o].value;

    }

   printf("%d",TOT);

    return 0;
}





 Ovako sam ja...al neradi :/

logika ne postoji.
 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal
Bi li ono gore radilo da sam jos jednom sortirao uzlazno,ali po stvar.size?(tj. Bolja je stvar 8 8 od stvari 9 9)
logika ne postoji.
 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal
ma ne.ovo je totalno krivo XD
logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Nemozes primjenjivat greedy rješenje, ovaj primjer se mora rjesavati DP-om.

http://www.dir.hr/pripreme/1998_1999/dinamicko.html

Ovdje je relativno dobro objasnjeno. S time da ovdje nije 1-0 knapsack.

 

Poruka je uređivana zadnji put sri 2.3.2011 19:12 (Budimir).
 
0 0 hvala 1
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Imam pitanje..ponovo :D

 

recimo imamo matricu[R][S]...koja ima upisan ulaz 'U' i izlaz 'I'.

Optimalnu putanju izmedu pocetka i kraja dobili bi občnim bfsom.

No recimo da imamo više ulaza,a opet samo 1 izlaz...Kako bi sada dobili tu opt.putanju?

(recimo da je R i S masovan broj,pa je nemoguće pozivat bfs za svaki ulaz)

Prijatelj mi je pričao da se tu koristi priority_queue,neke strukture,al se ne sjećam detalja {#}

 

logika ne postoji.
Poruka je uređivana zadnji put sub 12.3.2011 23:46 (KKristijan).
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Ne priority queue. Obicni Q na nacin da ubacis sve ulaze na pocetki.

 

for( int i = 0; i < R; ++i ) {

  scanf( "%s", mapa[i] );

  for( int j = 0; j < S; ++j ) {

    if( mapa[i][j] == 'U' ) {

      Q.push( make_pair(i, j) );

      p[i][j] = 0;

    }

  }

}

 

pa normalni bfs i dobit ces najkracu udaljenost izmedju svake tocke i

najblizeg ulaza. Mozda se moze sa PQ-om, ali ovo sigurno radi.

 
0 0 hvala 0
9 godina
offline
Re: Zadaci s natjecanja -> C,C++,Pascal
Budimir kaže...

Ne priority queue. Obicni Q na nacin da ubacis sve ulaze na pocetki.

 

for( int i = 0; i < R; ++i ) {

  scanf( "%s", mapa[i] );

  for( int j = 0; j < S; ++j ) {

   if( mapa[i][j] == 'U' ) {

    Q.push( make_pair(i, j) );

    p[i][j] = 0;

   }

  }

}

 

pa normalni bfs i dobit ces najkracu udaljenost izmedju svake tocke i

najblizeg ulaza. Mozda se moze sa PQ-om, ali ovo sigurno radi.

mhm.....Jel ideš na Honije redovito?

logika ne postoji.
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Ne , zasto ??

 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Mislio sam da ideš,jedan zadatak...VUK.Baš mi to tu treba,ne čini mi se da bi se tako mogao rješit :/

 

 

EDIT : evo link

logika ne postoji.
Poruka je uređivana zadnji put sub 12.3.2011 23:58 (KKristijan).
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

taj zadatak sam ja rjesio na taj nacin.

 

jednim bfs-om sam nasao udaljenos izmedju svake tocko i najblizeg stabla, pa binarnim pretrazivanjem nasao optimalan put.

 

Inace taj zadak se moze rjesiti PQ-om, ma da je slozenost skoro ista jer ubacivanje u Q kosta .

 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Cek..napravio si bfs za vuk -> jazbina? i dobio si on matricu integera punu brojeva..sta si onda tocno radio

logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Nakon sto napravis matricu udaljenosto, napr dist[x][y].

napr

+..

..+

...

...

 

dist izgleda ovako

011

110

221

332

 

tada radis binarno pretrazivanje.

Ako mozes doci do jazbine s udaljenoscu 4 tada sigurno mozes i sa 3 , 2 ...

 

neka je doljnja granica 0, a gornja dist[ vukx ][ vuky ]

probas s mid = (donja + gornja) / 2

 

ako moze onda donja = min

else gornja = min - 1

 

to radi dok god je donja < gornja

 

kako probas, tako sto radis bfs od vuka do jazbine, a uvjet je da udaljenost mora biti veca ili jednaka onoj s kojom probas.

 

rjesenje je donja granica.

 

 
0 0 hvala 1
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Shvaćam..Hvala {#}

logika ne postoji.
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

I kako je proslo zupanijsko... ako si bio

Poruka je uređivana zadnji put pon 14.3.2011 14:46 (Budimir).
 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Ne pitaj....{#}

 

 

Ti?

 

 

EDIT: rjesio prva 2.. 2 sata pokušao shvatit 3. zadatak koji nisam shvatio do kraja natjecanja i toeto :(

 

KAKO ROBOT KOJI SE GIBA U MATRICI DIMENZIJA 4 VISINE i 8 ŠIRINE MOŽE DOČI U POLJE (8,2) ???

 

Inteligencija nije znanje,već mašta
Poruka je uređivana zadnji put pon 14.3.2011 14:56 (KKristijan).
 
0 0 hvala 0
9 godina
neaktivan
offline
Zadaci s natjecanja -> C,C++,Pascal

Ma otkad ovaj DUMP priprema zadatke kvaliteta se srozala skroz. A ja nisam bio na ocjenjivanju, inace sam rjesio sva 4. pa bumo vidli. Zadnji zadatak II podskupine ima pre nizak time limit pa necu ima 100% na tom zadatku. A ostalo bi trebalo biti dobro.

EDIT: Koliko sam vidio zadnji zadatak I podskupine je bio MST(Minimum spanning tree, Kruskal / Prim) algoritam.
Poruka je uređivana zadnji put pon 14.3.2011 15:14 (Budimir).
 
1 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Ajde,puno sreće :D

Ja sam tek sad skužio onaj razvoj softwarea...Na to ću vjerojatno ić sljedeće godine,baš me zanima to {#}

Inteligencija nije znanje,već mašta
 
0 0 hvala 0
9 godina
offline
Zadaci s natjecanja -> C,C++,Pascal

Ja nisam ni pročitao 4.,Na 3. sam se davio ko stoka....što je najgore taj 4. bih možda i mogao rješiti,kolko tolko znam MST

Inteligencija nije znanje,već mašta
 
0 0 hvala 0
9 godina
neaktivan
offline
Re: Zadaci s natjecanja -> C,C++,Pascal
Ma i to Microsoft organizira, ja sam imao projekt za linux, nisam se ni usudio ici.
9 godina
offline
Re: Zadaci s natjecanja -> C,C++,Pascal
Budimir kaže...
Ma i to Microsoft organizira, ja sam imao projekt za linux, nisam se ni usudio ici.

Zasto?{#}

Inteligencija nije znanje,već mašta
Nova poruka
E-mail:
Lozinka:
 
vrh stranice