Polish version    English version  
  O olimpiadzie -> Zadania


 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
VIII Olimpiada Informatyczna 2000/2001

Zadanie: GOL
Autor: Wojciech Guzicki
Gorszy Goldbach

Zawody II stopnia, dzień próbny 6 luty 2001
Plik źródłowy: GOL.??? (np. pas, c, cpp)
Plik wykonywalny: GOL.exe
Plik wejściowy: GOL.in
Plik wyjściowy: GOL.out

W roku 1742 C. Goldbach w liście do L. Eulera napisał, że jego zdaniem każda liczba całkowita n>5 jest sumą trzech liczb pierwszych (Liczba pierwsza to liczba naturalna n>1, która ma tylko dwa dzielniki naturalne: 1 oraz n.). Euler odpisał, że jest to równoważne temu, że każda liczba parzysta n>=4 jest sumą dwóch liczb pierwszych. To jednak nie przybliżyło ich do rozwiązania podstawowego problemu: czy tak jest naprawdę. Dziś wiemy, że jest tak dla liczb aż do 4...1011 (wiemy też dużo więcej, ale cała hipoteza jest nadal problemem otwartym). Nie będziemy tego sprawdzać, postawimy sobie mniej ambitne zadanie. Okazuje się, że każda liczba naturalna n>=10 jest sumą różnych nieparzystych liczb pierwszych. Twoje zadanie polega na napisaniu programu, który:

  • wczyta z pliku tekstowego GOL.IN liczby całkowite,
  • znajdzie ich rozkłady na sumy różnych nieparzystych liczb pierwszych,
  • zapisze wyniki w pliku tekstowym GOL.OUT.
Takich rozkładów może być wiele. Twój program może znaleźć jakikolwiek z nich.

Wejście

W pierwszym wierszu pliku tekstowego GOL.IN zapisano jedną dodatnią liczbę całkowitą n, n<=40. W każdym z kolejnych n wierszy znajduje się jedna liczba całkowita z przedziału [10,...,2 000 000 000].

Wyjście

Rozkład liczby k musi być zapisany w dwóch wierszach. W pierwszym wierszu należy zapisać jedną liczbę całkowitą m>=1, będącą liczbą składników rozkładu. W drugim wierszu należy zapisać, w rosnącej kolejności, m różnych nieparzystych liczb pierwszych, których suma jest równa k, pooddzielanych pojedynczymi odstępami. Rozkłady powinny występować w kolejności zgodnej z kolejnością liczb w pliku wejściowym.

Przykład

Dla pliku wejściowego GOL.IN:
2
59
15
poprawną odpowiedzią jest plik wyjściowy GOL.OUT:
5
5 7 11 17 19
3
3 5 7



Wersja do druku