Srodne teme
Kliknite za generisanje liste srodnih tema...
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Riding the fences

[es] :: Art of Programming :: Riding the fences

[ Pregleda: 3160 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stf

Član broj: 51276
Poruke: 65
*.188.eunet.yu.



Profil

icon Riding the fences06.09.2005. u 13:48 - pre 225 meseci
Evo konacno stigoh do treceg nivoa na USACO...

Tacnije, ne mogu da resim ovaj zadatak. Iso sam preko Ojlerovog puta, ali ne ispisuje tacno resenje za 7. test primer. Zatim sam pustio DFS ali opet na 7. test primeru se zaustavlja, jer prelazi vremensko ogranicenje.

Ako moze neka pomoc, bio bih veoma zahvalan.

Riding the Fences

Farmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing the broken parts.
Farmer John is as lazy as the next farmer and hates to ride the same fence twice. Your program must read in a description of a network of fences and tell Farmer John a path to traverse each fence length exactly once, if possible. Farmer J can, if he wishes, start and finish at any fence intersection.
Every fence connects two fence intersections, which are numbered inclusively from 1 through 500 (though some farms have far fewer than 500 intersections). Any number of fences (>=1) can meet at a fence intersection. It is always possible to ride from any fence to any other fence (i.e., all fences are "connected").
Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude.
There will always be at least one solution for each set of input data supplied to your program for testing.

PROGRAM NAME: fence

INPUT FORMAT
Line 1: The number of fences, F (1 <= F <= 1024)
Line 2..F+1: A pair of integers (1 <= i,j <= 500) that tell which pair of intersections this fence connects.
SAMPLE INPUT (file fence.in)
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

OUTPUT FORMAT
The output consists of F+1 lines, each containing a single integer. Print the number of the starting intersection on the first line, the next intersection's number on the next line, and so on, until the final intersection on the last line. There might be many possible answers to any given input set, but only one is ordered correctly.
SAMPLE OUTPUT (file fence.out)
1
2
3
4
2
5
4
6
5
7



If you don't live for something, you will die for nothing.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*



Profil

icon Re: Riding the fences06.09.2005. u 18:33 - pre 225 meseci
Reshenje je definitivno da se nadje Ojlerova shetnja ...
Probaj da prvo na stek stavish cvor broj 1. Pa onda sledeci cvor na steku da ti bude najmanji cvor koji je susedan sa brojem 1, itd ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.172.EUnet.yu.



Profil

icon Re: Riding the fences07.09.2005. u 12:51 - pre 225 meseci
Bas sam tako i uradio. Ali ne moze da prodje kroz sedmi test primer. Mozda sam pogresno imlementirao Ojlerov put? Evo, postovacu kod, pa ako budes mogao, ukazi mi na gresku.

Code:
program fence;
var
  i,j,k,s,x,y,n,br,w:integer;
  m:array[1..500,1..500] of integer;
  no:array[1..500] of integer;
  t:array[1..100000] of integer;
  f:text;
procedure p(i:integer);
  begin
    if no[i]=0 then begin
      inc(w);
      t[w]:=i;
    end else begin
      for j:=1 to n do
        if m[i,j]>0 then begin
          dec(m[i,j]);
          dec(m[j,i]);
          dec(no[i]);
          dec(no[j]);
          p(j);
        end;
      inc(w);
      t[w]:=i;
    end;
  end;
begin
  assign(f,'fence.in');
  reset(f);
  readln(f,br);
  for i:=1 to br do begin
    readln(f,x,y);
    inc(m[x,y]);
    inc(m[y,x]);
    inc(no[x]);
    inc(no[y]);
    if x>n then n:=x;
    if y>n then n:=y;
  end;
  close(f);
  s:=1;
  for i:=n downto 1 do begin
    k:=0;
    for j:=1 to n do
      if m[i,j]>0 then k:=k+m[i,j];
    if odd(k) then s:=i;
  end;
  p(s);
  assign(f,'fence.out');
  rewrite(f);
  for i:=w downto 1 do
    if t[w]>0 then writeln(f,t[i]);
  close(f);
end.


Verujem da je ovaj program lako citljiv. U matrici m se pamti broj veza izmedju dva cvora. U nizu no je sadrzan broj susednih cvorova svakog cvora, a u nizu t se pamti Ojlerov put.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

boba5555
Slobodan Mitrovic
Deronje

Član broj: 49685
Poruke: 37
*.metrohive.net.

Sajt: www.kaziprst.com/slobodan


Profil

icon Re: Riding the fences12.09.2005. u 20:10 - pre 225 meseci
Malo je naporno citati tudj kod, ali Rajko (RooTeR) je u pravu. Ja sam prosao taj zadatak i treba da stavis na stack prvi cvor od koga se moze poceti Ojlerova setnja (treba da ima paran broj grana) i uvek kad ides dalje, ides od cvora sa najmanjim brojem i to je to.
Ovaj tvoj kod mi ne lici na dovoljan kod za Ojlerov graf, ali nije ni bitno. Ova ideja je sigurno tacna!
Prijatno,
....
Slobodan
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Riding the fences13.09.2005. u 07:55 - pre 225 meseci
Da, preko te ideje sam radio zadatak, ali izgleda da ovaj kod nije bio dovoljan. Rekurzija je u redu, samo je trebalo jos neki red koda u glavnom programu da se ubaci. Sredio sam to u medjuvremenu, tako da je sad OK.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

[es] :: Art of Programming :: Riding the fences

[ Pregleda: 3160 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
Kliknite za generisanje liste srodnih tema...
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.