Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


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

Zadanie: wag
Autor: Krzysztof Onak
Waga

Zawody III stopnia, dzień pierwszy  
Plik źródłowy: wag.??? (np. pas, c, cpp)
Plik wejściowy: wag.in
Plik wyjściowy: wag.out

Mamy do dyspozycji wagę szalkową. Waga znajduje się w stanie równowagi wtedy i tylko wtedy, gdy obie szalki są puste lub gdy sumy mas odważników na obu szalkach są takie same. W danym zbiorze odważników należy znaleźć takie dwa rozłączne podzbiory, aby po położeniu wszystkich odważników z jednego z nich na jednej szalce, natomiast wszystkich odważników z drugiego zbioru na drugiej szalce, waga znalazła się w stanie równowagi. Ponadto żądamy, aby na wadze znalazł się odważnik o jak największej masie.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego wag.in masy dostępnych odważników,
  • wyznaczy dwa rozłączne zbiory odważników spełniające warunki zadania,
  • zapisze wynik do pliku tekstowego wag.out.

Wejście

W pierwszym wierszu pliku tekstowego wag.in znajduje się jedna liczba całkowita n, 2<=n<=1 000, równa liczbie dostępnych odważników. W każdym z następnych n wierszy znajduje się po jednej dodatniej liczbie całkowitej równej masie jednego odważnika za zbioru dostępnych odważników. Można założyć, że łączna masa odważników nie przekracza 50 000.

Wyjście

W pierwszym wierszu pliku tekstowego wag.out należy zapisać dwie nieujemne liczby całkowite p i q oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę odważników w pierwszym i w drugim zbiorze. W drugim wierszu powinno się znaleźć p liczb całkowitych oddzielonych pojedynczymi odstępami. Powinny to być masy odważników z pierwszego zbioru. Natomiast w trzecim wierszu powinno zostać wypisanych q liczb całkowitych odzielonych pojedynczymi odstępami i równych masom odważników w drugim zbiorze.

Przykład

Dla danych pliku wejściowego wag.in:

4
1
1
2
7

poprawną odpowiedzią jest plik wyjściowy wag.out:

2 1
1 1
2

Komunikat podczas zawodów

Spośród wszystkich układów odważników, dla których waga jest w równowadze należy wybrać ten, który zawiera odważnik o maksymalnej możliwej masie. W przypadku wielu takich rozwiązań trzeba podać tylko jedno z nich.




Wersja do druku