In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Bajtazar postanowił zająć się produkcją naszyjników.
Udało mu się okazyjnie kupić bardzo długi sznur różnokolorowych korali.
Dysponuje on maszyną, która dla zadanego (
) potrafi pociąć sznur
na odcinki składające się z
korali (czyli pierwszy odcinek składa
się z korali o numerach
, drugi
, itd.).
Jeśli sznur korali ma długość, która nie jest wielokrotnością
, to
ostatni odcinek, który ma długość mniejszą niż
, jako
niepełnowartościowy, nie jest wykorzystywany.
Kolory korali oznaczamy dalej dodatnimi liczbami całkowitymi.
Bajtazar lubi różnorodność i zastanawia się, jak dobrać liczbę ,
tak by otrzymać jak najwięcej różnych sznurów korali.
Sznur korali, który ma zostać pocięty, ma wyraźnie określony koniec,
od którego zaczynamy odcinać krótsze sznury.
Jednak każdy odcięty sznur może zostać obrócony - inaczej mówiąc,
sznury
i
są dla Bajtazara takie same.
Napisz program, który pomoże mu wyznaczyć optymalną wartość parametru
.
Przykładowo, dla sznura korali postaci:
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
(
), oznaczająca długość sznura korali.
W drugim wierszu znajduje się
dodatnich liczb całkowitych
(
), pooddzielanych pojedynczymi odstępami i oznaczających
kolory kolejnych korali w sznurze Bajtazara.
W pierwszym wierszu standardowego wyjścia należy wypisać dwie liczby
całkowite oddzielone pojedynczym odstępem: liczbę różnych sznurów korali,
które można uzyskać przy optymalnym wyborze parametru , oraz liczbę
różnych wyborów parametru
prowadzących do uzyskania takiej liczby sznurów.
Drugi wiersz powinien zawierać
liczb pooddzielanych pojedynczymi odstępami:
wartości parametru
, dla których uzyskujemy optymalne rozwiązanie
- mogą one zostać wypisane w dowolnej kolejności.
Dla danych wejściowych:
21 1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1
poprawną odpowiedzią jest:
6 1 2
Autor zadania: Tomasz Waleń.