zapocet 5.6.2006
Napsal: 5. 6. 2006 15:29
Zapoctova pisemka 5.6.2006
http://nenya.ms.mff.cuni.cz/~holub/testa.html
Zadani
Pro dany graf a vrcholy vypiste 1 pokud jsou dosazitelne a 0 jinak. Volani programu bude vypadat takto:
najdi.exe -f filename -n maxcislo b1 e1 b2 e2 b3 e3 [...]
kde:
* maxcislo je nejvyssi cislo vrcholu
* filename je soubor s grafem, na kazdym radku je dvojice cislo cislo (orientovana hrana)
* bi ei jsou dvojice vrcholu pro ktery se ma urcit dosazitelnost
Nikde nesmite spolehat na jakekoli horni hranice cehokoli, co exaktne nezjistite.
Priklad 1
Volani programu
najdi.exe -f graf1.txt -n 5 0 3 5 2 4 3 2 4
a grafem graf1.txt:
0 3
3 5
4 5
5 1
3 4
2 0
1 0
vypise
1011
Priklad 2
Volani programu
najdi.exe -f graf2.txt -n 19 1 5 6 5 5 6 14 16 6 8 19 8 11 4 4 0
a grafem graf1.txt:
2 0
11 14
10 12
12 5
4 5
19 14
13 14
3 1
4 2
3 7
14 7
6 10
16 15
10 15
6 11
16 11
4 3
17 15
0 9
4 8
7 8
15 17
16 18
8 7
2 4
11 16
8 13
4 9
18 14
4 1
14 18
vypise
01001101
***********************************************************
Takze boli na to dve hodiny casu. Dalo sa to riesit nasledovne:
Vitvori sa seznam nasledniku, potom prechod do hlbky alebo sirky, pricom prejdene vrcholi si oznacime inou farbou(koli moznym cyklom).
No ja som o tomto rieseni vedel, ale usiloval som sa to spravit inak a tak to dopadlo tak ako dopadlo. Sice nie tazke zadanie, ale aj to sa do zmrvit. O konecnych statistikach neviem, ale z pozorovania to asi viac ludi nedalo ako dalo. Tak prajem vela stastia v dalsich terminoch tym, ktory to este nemaju.
http://nenya.ms.mff.cuni.cz/~holub/testa.html
Zadani
Pro dany graf a vrcholy vypiste 1 pokud jsou dosazitelne a 0 jinak. Volani programu bude vypadat takto:
najdi.exe -f filename -n maxcislo b1 e1 b2 e2 b3 e3 [...]
kde:
* maxcislo je nejvyssi cislo vrcholu
* filename je soubor s grafem, na kazdym radku je dvojice cislo cislo (orientovana hrana)
* bi ei jsou dvojice vrcholu pro ktery se ma urcit dosazitelnost
Nikde nesmite spolehat na jakekoli horni hranice cehokoli, co exaktne nezjistite.
Priklad 1
Volani programu
najdi.exe -f graf1.txt -n 5 0 3 5 2 4 3 2 4
a grafem graf1.txt:
0 3
3 5
4 5
5 1
3 4
2 0
1 0
vypise
1011
Priklad 2
Volani programu
najdi.exe -f graf2.txt -n 19 1 5 6 5 5 6 14 16 6 8 19 8 11 4 4 0
a grafem graf1.txt:
2 0
11 14
10 12
12 5
4 5
19 14
13 14
3 1
4 2
3 7
14 7
6 10
16 15
10 15
6 11
16 11
4 3
17 15
0 9
4 8
7 8
15 17
16 18
8 7
2 4
11 16
8 13
4 9
18 14
4 1
14 18
vypise
01001101
***********************************************************
Takze boli na to dve hodiny casu. Dalo sa to riesit nasledovne:
Vitvori sa seznam nasledniku, potom prechod do hlbky alebo sirky, pricom prejdene vrcholi si oznacime inou farbou(koli moznym cyklom).
No ja som o tomto rieseni vedel, ale usiloval som sa to spravit inak a tak to dopadlo tak ako dopadlo. Sice nie tazke zadanie, ale aj to sa do zmrvit. O konecnych statistikach neviem, ale z pozorovania to asi viac ludi nedalo ako dalo. Tak prajem vela stastia v dalsich terminoch tym, ktory to este nemaju.