[es] - Glupi zadatak koji je bio na proslim natjecanjima :)

Passwd

Član broj: 54624
Poruke: 640
*.adsl.net.t-com.hr.

Profil

Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 17:12 - pre 229 meseci}

Evo ovako glasi zadatak, pa ako netko skuzi sta zadatak trazi neka mi objasni-NE treba pisat program vec neka normalno kaze sta zadatak trazi jer ga ja nista ne kuzim???

Code:

Neki grad posjeduje M tramvajskih stanica. Stanice su označene brojevima od 1 do M. Između tih stanica prometuje N linija. Sve linije su dvosmjerne, tj. putnik se može kretati u oba smjera.

Napišite program koji će za zadane tramvajske linije, izračunati koliko ima parova stanica između kojih se može doći koristeći točnu jednu tramvajsku liniju, tj. bez presjedanja.

Ulazni podaci

Ulazni podaci se učitavaju sa tipkovnice. U prvom retku se nalaze dva broja, M (2 ≤ M ≤ 100), broj stanica i N (1 ≤ N ≤ 100), broj linija. U svakom od slijedećih N redaka se nalazi opis pojedine linije. Opis počinje brojem K (2 ≤ M ≤ N) koji označava koliko ima stanica na toj liniji. Nakon toga slijedi točno K međusobno različitih brojeva odvojenih točno jednim razmakom. Ti brojevi predstavljaju stanice na toj liniji, redom od početne do konačne stanice.

Izlazni podaci

Rješenje treba ispisati na zaslon. U prvi i jedini redak treba ispisati traženi broj iz teksta zadatka.

Test primjeri1:
ULAZ:
5 1
5 4 3 2 5 1

IZLAZ:
10

Test primjer2:
ULAZ:
10 2
6 1 2 3 4 5 6
6 5 6 7 8 9 10

IZLAZ:
29

Test primjer3:
ULAZ:
5 3
3 1 2 3
3 2 3 4
3 3 4 5

IZLAZ:
7

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*

+1 Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 17:46 - pre 229 meseci}

Ne vidim sto se bunis. Znaci imas N tramvajskih linija i dve stanice su direktno povezane ukoliko se izmedju njih moze putovati samo kroz jednu liniju. Npr. u prvom slucaju imas da postoji jedna linija (4,3,2,5,1) i za nju vazi da iz svake stanice mozes stici u svaku tj. 4 + 3 + 2 + 1 = 10... (4-ta je povezana sa (3,2,5,1), 3-ca (2,5,1), jer si 3-4 vec brojao u 4...)
Npr. U drugom slucaju imas (1,2,3,4,5,6) i (5,6,7,8,9,10) pa je resenje
za prvu liniju: 5 + 4 + 3 + 2 + 1 = 15
za durg liniju: 5 + 4 + 3 + 2 + 1 = 15
pa je resenje 15 + 15 - 1 = 29, gde oduzimamo jedan jer su stanice 4-5 povezane obema linijama po smo ih kao para povezanih stanice brojali 2 puta...

P.S. Kad god neko stavlja neki Code neka pazi da mu linije koda ne budu ovoliko dugacke... Estetika :-)

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

Odgovor na temu

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.

+1 Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 17:55 - pre 229 meseci}

Generises sve kombinacije od M elemenata klase 2.

Posle svake generisane kombinacije proveris da li se u nekom skupu (a njih ima N komada) nalaze oba elementa. Ako da, uvecas brojac.

Skupovi se ucitavaju pocevsi od 2. reda.

Ovako nekako:

s: array[1..100] of set of byte;

Prazan skup: s[ i ]:=[];
Dodavanje u skup s:= s[ i ]+[broj];
Provera da li je u skupu: if broj in s[ i ]

Ma ovo je teze objasniti nego napisati program. :)

_{[Ovu poruku je menjao Toyo dana 20.06.2005. u 19:59 GMT+1]}

Odgovor na temu

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.

+1 Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 18:44 - pre 229 meseci}

Code:

var
   f: text;
   s: array[1..100] of set of byte;
   m,n, b, br, i, j, k, lin: Integer;
   nadjen: boolean;
begin
     assign(f,'ulaz.txt');
     reset(f);
     readln(f, m, n);
     for i := 1 to n do
         begin
              s[i]:=[];
              read(f,b);
              for j := 1 to b do
                 begin
                      read(f, br);
                      s[i] := s[i] + [br];
                 end;
              readln(f);
         end;
     close(f);
     lin := 0;
     for i := 1 to m-1 do
         for j := i+1 to m do
             begin
                  nadjen := false;
                  for k := 1 to n do
                      nadjen := nadjen or ((i in s[k]) and (j in s[k]));
                  if nadjen then
                     inc(lin);
             end;
     writeln(lin);
end.

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*

+1 Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 19:00 - pre 229 meseci}

Citat:

Passwd:... pa ako netko skuzi sta zadatak trazi neka mi objasni-NE treba pisat program vec neka normalno kaze sta zadatak trazi jer ga ja nista ne kuzim???

Toyo, procitaj... (mozda je decko samo zeleo da mu se objasni tekst zadatka a on sam da ga uradi...)

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

Odgovor na temu

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.

+1 Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 19:03 - pre 229 meseci}

Pa nek ne gleda kod :)

Odgovor na temu

Passwd

Član broj: 54624
Poruke: 640
*.adsl.net.t-com.hr.

Profil

Re: Glupi zadatak koji je bio na proslim natjecanjima :)

^{20.06.2005. u 19:21 - pre 229 meseci}

Dobro je, shvatio sam sto zadatak trazi...
Al priznajte da je program lakse napravit nego shvatit zadatak, al po mom misljenju bi trebalo biti obrnuto jer se radi o natjecanju u programiranju a ne u shvacanju zadataka

Odgovor na temu