Polish version    English version  
  Historia OI -> III OI 1995/1996 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Olimpiada Informatyczna 1995/96

Zadanie: AGE
Autor: Marcin Kubica
Agenci

Zawody III stopnia  
Plik źródłowy: AGE.??? (np. pas, c, cpp)
Plik wykonywalny: AGE.exe
Plik wejściowy: AGE.in
Plik wyjściowy: AGE.out

 

W kraju działają agenci obcych wywiadów. Zajmują się oni nie tylko wykradaniem tajemnic, ale także nawzajem się szpiegują. Mówimy, że agent A rozpracował agenta B, jeśli A posiada dokumenty wystarczające do aresztowania B.

Niektórzy agenci są przekupni - w zamian za odpowiednią sumę pieniędzy są gotowi oddać wszystkie posiadane dokumenty. Aresztując agenta przechwytujemy wszystkie zgromadzone przez niego dokumenty. Przekupienie odpowiednio wybranych agentów może więc uruchomić łańcuch aresztowań prowadzący do zlikwidowania wszystkich agentów działających w kraju.

Rodzimy kontrwywiad dostarczył nam informacje o tym, jacy obcy agenci działają w kraju, którzy z nich są przekupni i za jaką cenę, a także, którzy agenci rozpracowali których. Liczba agentów n <= 3000; są oni ponumerowani od 1 do n.

Zadanie

Ułóż program, który:
  • wczytuje z pliku tekstowego AGE.IN dane zgromadzone przez kontrwywiad,
  • stwierdza, czy jest możliwe, by przez przekupienie odpowiednio wybranych agentów uzyskać informacje, uruchamiające łańcuch prowadzący do aresztowania wszystkich agentów w kraju i jeśli tak, oblicza minimalny koszt takiego zakupu, a jeśli nie, znajduje numer jednego z agentów, którego nie będzie można aresztować,
  • zapisuje wynik do pliku tekstowego AGE.OUT.

Wejście

  • W pierwszym wierszu pliku tekstowego AGE.IN jest zapisana jedna liczba naturalna n. Jest to liczba wszystkich działających w kraju agentów, 1 <= n <= 3000.
  • W drugim wierszu jest zapisana jedna liczba naturalna p. Jest to liczba wszystkich agentów przekupnych, 1 <= p <= n.
  • W kolejnych p wierszach są zapisane informacje o przekupnych agentach. W każdym takim wierszu są zapisane dwie liczby całkowite dodatnie oddzielone odstępem - pierwsza z nich jest numerem przekupnego agenta, a druga to suma, za którą można go przekupić - jest to liczba nie większa niż 20000.
  • Kolejny wiersz zawiera jedną liczbę r, gdzie 1 <= r <= 8000. Jest to liczba takich par (A,B), że agent A rozpracował agenta B.
  • W następnych r wierszach podane są wszystkie takie pary. W każdym z tych wierszy są zapisane dwie różne liczby ze zbioru {1, 2, ... , n} oddzielone odstępem - pierwsza, to numer agenta, który rozpracował, a druga, to numer agenta, który został rozpracowany.

Wyjście

  • W pierwszym wierszu pliku tekstowego AGE.OUT należy zapisać jedno słowo: TAK - jeśli istnieje możliwość aresztowania wszystkich agentów działających w kraju, albo NIE - jeśli taka możliwość nie istnieje.
  • W drugim wierszu należy zapisać jedną liczbę całkowitą dodatnią: minimalny koszt zakupu informacji wystarczających, by doprowadzić do aresztowania wszystkich agentów w kraju, albo numer dowolnego agenta, którego nie da się zaaresztować.

Przykłady
Dla pliku AGE.IN:
3
2
1 10
2 100
2
1 3
2 3
 
w pliku AGE.OUT należy zapisać:
TAK
110
 
Dla pliku AGE.IN:
4
2
1 100
4 200
2
1 2
3 4
 
w pliku AGE.OUT należy zapisać:
NIE
3

Twój program powinien szukać pliku AGE.IN w katalogu bieżącym i tworzyć plik AGE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę AGE.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku AGE.EXE.




Wersja do druku