1. ZADATAK

35 bodova, program mora dati rješenje za mnje od 30 sekundi

Marko je preko ljeta radio u pekari. Pošto mu pečenje kruha baš i nije išlo, šef mu je dao da pakira vreće brašna po narudžbi. "Ajde, bar nešto lagano....baš mi se i neda razmišljat po ovakvoj vrućini!", misli si Marko. Kad tamo pekara ima samo vreće od 17, 19 i 23 kilograma, a kupac želi isključivo pune vreće i to onu kombinaciju koja ima najveći broj vreća od 23 kg. "Ajoj!!! Da sam bar malo više pazio na informatici, sad bih to znao riješiti."

Na svu sreću Markov brat (blizanac) Antonio sjetio se kako se to rješava i pomogao bratu odraditi svoj dio posla kako treba. Kupci su svi sretni dobivali naručenu količinu brašna (ako ju je bilo moguće na taj način isporučiti).

Napišite program koji će riješiti ovaj problem!

 

 

Ulazni podaci: količina željenog brašna u kilogramima

Izlazni podaci: broj vreća od 17, 19 i 23 kilograma potrebnih za isporuku ili odgovarajuća

poruka ukoliko ne postoji način da se ta količina upakira

Npr.

ULAZ

97

IZLAZ

2 x 23 kg, 0x19 kg i 3x17 kg.

 

 

RJEŠENJE

program brasno;

var n,x,y,z : integer;

BEGIN

write('Koliko brasna? '); readln(n);

for x:=n div 23 downto 0 do

for y:=n div 19 downto 0 do

for z:=n div 17 downto 0 do

begin

if (x*23 + y*19 + z*17)=n then

begin

writeln(x,'x23 ',y, 'x19

',z,'x17');

readln; halt;

end;

end;

writeln('nema rjesenja...'); readln;

END.

 

2. ZADATAK

45 bodova, program mora dati rješenje za mnje od 20 sekundi

Sav sretan Marko je dočekao kraj ljeta, jer mu se posao s pakiranjem vreća baš i nije sviđao. Uostalom, 28. rujna im je rođendan! Roditelji su se htjeli poigrati s njihovim horoskopskim znakom (vaga) pa su im kupili pet darova na koje su zalijepili cijene (u Kn) i rekli: "Tu su vam darovi. Raspodijelite ih međusobno tako da obojica dobijete što je moguće sličnije ukupne vrijednosti darova."

Marko i Antonio su par dana mozgali i na kraju su uspjeli pravedno raspodijeliti darove.

Napišite program koji će izračunati najpravedniju raspodijelu darova. Nije bitno tko od blizanaca je dobio koliko i koje darove, već samo ukupne vrijednosti.

 

 

Ulazni podaci: cijene za pet darova

Izlazni podaci: ukupna vrijednost darova koje je dobio svaki od blizanaca

Npr.

ULAZ 9, 8, 3, 4, 1 IZLAZ 12 i 13

RJEŠENJE

DIM cijene(5)

FOR x = 1 TO 5

INPUT "Cijena dara: ", cijena(x)

NEXT x

FOR i = 1 TO 5

FOR j = 1 TO 4

IF cijena(j) < cijena(j + 1) THEN SWAP cijena(j), cijena(j + 1)

NEXT j

NEXT i

s1 = cijena(1)

s2 = 0

FOR x = 2 TO 5

IF s1 < s2 THEN s1 = s1 + cijena(x) ELSE s2 = s2 + cijena(x)

NEXT x

PRINT s1; " , "; s2

Evo za promjenu jednog rjesenja u Basicu. Darove mozemo podijeliti tako da najveci damo prvome, prvi manji damo drugome, a dalje dijelimo onome tko ima manje i to sve manje i manje vrijedne darove. Tako cemo sigurno najpravednije podijeliti darove, a jedini problem ostaje onda na pocetku sortiranje darova po vrijednosti.

3. ZADATAK

55 bodova, program mora dati rješenje za mnje od 10 sekundi

Jedan od darova koje je Antonio dobio, nakon što su raspodijelili darove, bila je knjiga “Computer Networks". U njoj je pronašao dobar štos kako natjerati Marka da konačno počne malo upotrebljavati mozak. Od sad nadalje ostavljat će Marku isključivo šifrirane poruke i to metodom koju je pronašao u knjizi. Ključ za šifriranje je riječ sastavljena od različitih slova. Tekst koji se želi šifrirati upisuje se u retke ispod ključa (naravno bez razmaka, a ako na kraju ostane praznih mjesta upisuju se redom slova engleske abecede). Šifrirani tekst se dobije tako da se čitaju stupci po abecednom redu slova iz ključa. Antoniu ovo baš i nije bilo jasno pa je pogledao i primjer iz knjige:

Ključ - "megabuck"

Tekst - "pleasetransfermilliondollarstomybankaccountnumbertwotwosix"

Postupak šifriranja :

M E G A B U C K - ključ

7 4 5 1 2 8 3 6 - redni brojevi slova

- - - - - - - -

p l e a s e t r

a n s f e r m i

l l i o n d o l

l a r s t o m y

b a n k a c c o

u n t n u m b e

r t w o t w o s

i x a b c d e f

Šifrirani tekst :

"afosknobsentautctmomcboelnlaantxesirntwarilyoesfpallburierdocmwd"

Međutim Antonio je shvatio da to baš i nije lagano raditi ‘pješke’ pa je zamolio vas da mu taj problem riješite računalom.

 

Ulazni podaci: Nalaze se u tekstualnoj datoteci SIFRA.TXT tako da je u prvom retku ključ, a u drugom retku tekst kojeg treba šifrirati. Ključ će sigurno biti sastavljen od različitih slova, a sva slova u datoteci će biti mala slova engleske abecede napisana bez razmaka.

Izlazni podaci: Izlazni podatak predstavlja šifrirani tekst kojeg treba upisati u datoteku IZLAZ.TXT.

 

Npr.

SIFRA.TXT

megabuck

pleasetransfermilliondollarstomybankaccountnumbertwotwosix

IZLAZ.TXT

afosknobsentautctmomcboelnlaantxesirntwarilyoesfpallburierdocmwd

 

 

RJEŠENJE

program sifriranje;

var st, key, skey: string;

ulaz, izlaz:text;

procedure dodajslova;

var o,x:integer;

c:char;

begin

if length(key)>=length(st) then o:=length(key)-length(st)

else

begin

x:=length(st);

repeat

dec(x,length(key));

until x<=length(key);

o:=length(key)-x;

end;

if o>0 then begin

c:='a';

repeat

st:=st+c;

dec(o);

inc(c);

until o=0;

end;

end;

procedure sortkey;

var i,j:integer;

procedure swap(x,y:integer);

var c:char;

begin

c:=skey[j];

skey[j]:=skey[j+1];

skey[j+1]:=c;

end;

begin

for i:=1 to length(skey) do

for j:=1 to length(skey)-1 do

if skey[j]>skey[j+1] then swap(j,j+1);

end;

 

procedure sifriraj;

var m,x,y,i,j,ostatak:integer;

polje:array[1..100,1..100] of char;

begin

m:=length(st) div length(key);

i:=1;

j:=0;

 

 

while i<=m do begin

for x:=1 to length(key) do begin

inc(j);

polje[x,i]:=st[j];

end;

inc(i);

end;

j:=0;

for x:=1 to length(key) do

begin

i:=0;

repeat

inc(i);

until key[i]=skey[x];

for y:=1 to m do begin

write(izlaz,polje[i,y]);

write(polje[i,y]);

end;

inc(j,m);

end;

 

end;

 

begin

assign(ulaz,'sifra.txt');

assign(izlaz,'izlaz.txt');

reset(ulaz);

rewrite(izlaz);

 

readln(ulaz,key);

readln(ulaz,st);

skey:=key;

sortkey;

dodajslova;

sifriraj;

 

close(ulaz);

close(izlaz);

 

readln;

end.

 

 

4. ZADATAK

65 bodova, program mora dati rješenje za mnje od 5 sekundi

Marko i Antonio su dobili i veliki komad papira (roditelji su baš našli što im pokloniti !?) te su došli na zgodnu ideju da od njega naprave papirnate zmajeve. No u samom početku su se suočili s problemom koliko istih zmajeva mogu napraviti od tog komada papira.

Napišite program koji će za zadane dijagonale papirnatog zmaja i duljine stanica pravokutnog komada papira izračunati najveći mogući broj zmajeva.

Papirnati zmaj sastoji se od četiri posebno izrezana trokuta, sva četiri pravokutna od kojih 2 jednakokračna kateta duljine a i 2 trokuta duljina kateta a i b (kao na slici). Stranice platna neće prelaziti 1000.

 

 

Ulazni podaci: Ulazni podaci čitaju se iz tekstualne datoteke ZMAJ.TXT koja sadrži dva

retka. U prvom retku su duljine stranica papira, dok su u drugom retku

duljine dijagonala, prvo vodoravne tj. 2*a te iza toga okomite tj. a+b.

Izlazni podaci: Program treba na ekran ispisati najveći mogući broj zmajeva.

 

Npr.

ZMAJ.TXT

27 20

6 10

ISPIS

16

RJEŠENJE

#include <stdio.h>

float x,y,a,b,t;

void main()

{

FILE *f;

int i,st,bm=0,bv=0,as=0;

float stupci[100];

int mus[100], vus[100];

f=fopen("zmaj.txt","rt");

fscanf(f,"%f %f %f %f",&x,&y,&a,&b);

fclose(f);

if(x>y) {t=x;x=y;y=t;}

a/=2;

b-=a;

st=x/a;

bv=st*(int)(y/b);

for (i=0;i<st;i++)

{

vus[i]=bv/st;

stupci[i]=y-((bv/st)*b);

mus[i]=(int)(stupci[i]/a);

stupci[i]-=mus[i]*a;

bm+=mus[i];

}

while((bv>bm)&&(bv))

{

if (as==st) as=0;

if(vus[as])

{

stupci[as]+=b;

vus[as]--;

bv--;

t=(int)(stupci[as]/a);

mus[as]+=t;

stupci[as]-=t*a;

bm+=t;

as++;

}

}

printf("%d\n",bv);

}