Runda 1 [Hard] - Fortepian

22.11.2010 - Damian Rusak
TrudnośćTrudność

Zadanie tygodnia

Runda 1; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 64MB


Fortepian

Mały Staś został zapisany przez rodziców na lekcje gry na fortepianie. Nie byłoby w tym nic niezwykłego, gdyby nie fakt, że jego nauczyciel jest zapalonym miłośnikiem matematyki. Nakazał Stasiowi grać bardzo nietypowe utwory. Mianowicie ponumerował klawisze fortepianu kolejnymi liczbami naturalnymi, począwszy od 1, i zapowiedział, że nie pozwoli, aby w jednym utworze Staś użył jakichkolwiek dwóch klawiszy, z których jeden ma numer podzielny przez numer drugiego.

Na przykład nie do pomyślenia jest, aby w harmonijnym utworze użyte zostały naraz klawisze o numerach 3 i 12, bądź 8 i 24. Staś wolałby grać coś bardziej klasycznego, planuje więc jak najszybciej zakończyć lekcje. Nauczyciel kazał mu jednak grać aż do momentu, gdy każdy klawisz fortepianu zostanie użyty chociaż raz. Staś potrafi zagrać jeden utwór na godzinę. Ile co najmniej godzin musi grać, aby każdy klawisz został użyty w ciągu choć jednej godziny?

Wejście:

Pierwsza linia wejścia składa się z jednej liczby naturalnej - $ n $ ($ 1 \leq n \leq 10^{5} $) - liczby klawiszy na klawiaturze fortepianu.

Wyjście:

W pierwszej linii wyjścia powinna pojawić się jedna liczba naturalna $ k $ - minimalna liczba godzin, przez jakie Staś musi grać na lekcji. W kolejnych $ k $ liniach powinny pojawić się numery klawiszy, których Staś użyje w kolejnych godzinach - w pierwszej linii klawisze użyte w godzinie pierwszej, w drugiej linii w drugiej itd w następującym formacie - pierwsza liczba danej linii oznacza liczbę klawiszy użytych do zagrania tego utworu, po czym następują numery tych klawiszy. Jeśli istnieje wiele poprawnych odpowiedzi, Twój program powinien wypisać dowolną z nich. Łącznie we wszystkich liniach nie powinno się pojawić więcej niż $ 2n $ liczb.

Przykład:

Wejście:

10

Wyjście:

4
4 7 5 2 9
1 1
4 4 10 6 7
2 3 8

Poprawnym rozwiązaniem jest na przykład rozwiązanie, w którym Staś w pierwszej godzinie gra na klawiszach o numerach 7,5,2,9, w drugiej na klawiszu nr 1, w trzeciej na klawiszach 4,10,6,7, i w czwartej na klawiszach 3 i 8.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski1006:20:31
2Przemek Komosa1008:55:41
3Wojciech Janczewski1010:14:36
4Szymon Stankiewicz1010:20:55
5Dariusz Sosnowski1011:41:55
6Maciej Szeptuch1014:26:18
7Adam Czapliński1033:48:27
8Krzysztof Drab1034:01:17
9Aleksandra Dębska1036:04:02
10Piotr Pakosz1036:08:38
11Maciej Andrearczyk1036:39:29
12Michał Adamczyk1041:34:59
13Marcin Smulewicz1054:55:11
14Arek Wróbel1057:59:56
15Łukasz Hanuszczak1060:18:40
16Tomasz Richert1065:08:12
17Marcin Skiba1078:44:46
18Jakub Sygnowski1081:11:12
19Jadwiga Andryszak1083:30:10
20Kuba Skałecki1088:14:22
21Bartłomiej Gajewski1089:19:04
22Krzysztof Stanisławek10101:35:10
23Kamil Łukasz10128:44:53
24Damian Straszak10128:51:39
25Piotr Bejda10131:09:48
26Robert Tomkowski10134:46:02
27Mateusz Markiewicz10147:40:55
28Maciej Kisiel10150:38:32
29Paweł Kubik10151:09:11
30Tomasz Gieniusz10157:12:48
31Bartek Dudek10159:33:37
32Wojciech Staszkiewicz10752:14:58
33Tomasz Wiatrowski10804:14:04
34Marcin Maslany10849:13:24
35Kamil Dębowski10855:30:50
36Witold Długosz102402:54:18
37Andrzej Białokozowicz9158:28:46
38Krzysztof Cirocki6107:21:17
39Michał Robaszyński511:44:55
40Artur Zochniak568:28:25
4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com