Contest problemset description

Show PDF Back

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Brakujące liczby (brakujace-liczby) Limit pamięci: 64 MB Limit czasu: 3.00 s Rozważmy tabliczkę mnożenia N × N. Znajduje się w niej N2 liczb, będących wynikami mnożenia każdej pary liczb i ⋅ j, dla 1 ≤ i, j ≤ N. Znajdź K-tą najmniejszą liczbę naturalną, która nie występuje w tabliczce mnożenia. Wejście W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne N oraz K, oddzielone pojedynczym odstępem. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – K-ta najmniejsza liczba naturalna, która nie występuje w tabliczce mnożenia N × N. Ograniczenia 1 ≤ N ≤ 1 000 000, 1 ≤ K ≤ 100 000. Przykład Wejście Wyjście Wyjaśnienie 3 2 7 Tabliczka mnożenia 3 × 3 zawiera następujące liczby: 1, 2 (dwa razy), 3 (dwa razy), 4, 6 (dwa razy) oraz 9. Najmniejsze liczby, które nie występują w niej to: 5, 7, 8, 10. Druga najmniejsza to 7. .desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Kody pocztowe (kody-pocztowe) Limit pamięci: 64 MB Limit czasu: 0.50 s Jasio, przechodząc przez miasto zauważył na murze graffiti. Nie było ono typowym kolorowym muralem lub bezsensownym tagiem autora. Na murze napisany jest bowiem ciąg cyfr i myślników. Jasio zastanawiał się jaki sens może mieć ten zapis. Czy chodzi o działanie odejmowania? Czy chodzi o liczby pooddzielane myślnikami? W końcu wymyślił! Na pewno autor chciał schować w graffiti kod pocztowy. Dla przypomnienia: format kodu pocztowego jest następujący [0-9][0-9]-[0-9][0-9][0-9], czyli dwie cyfry, następnie znak myślnika, następnie trzy cyfry. Przykładowo, 00-789 oraz 23-456 to poprawne kody pocztowe, zaś 12345, 123-45, 00-0001, 0-1234 nie są poprawne. Jasio zastanawia się teraz ile różnych kodów pocztowych może uzyskać, jeżeli by zamazać niektóre (być może żadnej) znaki, a pozostałe odczytać od lewej do prawej. Pomóż mu w tym zadaniu. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg cyfr oraz znaków -. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba różnych kodów pocztowych jakie można odnaleźć w napisie na wejściu. Ograniczenia Długość napisu na wejściu nie przekracza 100 000 znaków. Przykład Wejście Wyjście Wyjaśnienie 2111-3-411 8 W tym przypadku pasują następujące kody: 11-311, 11-341, 11-411, 13-411, 21-311, 21-341, 21-411, 23-411. .desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Powtarzające się ciągi (powtarzajace-ciagi) Limit pamięci: 256 MB Limit czasu: 2.00 s W Bajtocji niedługo wybory. Bajtek ma już dość słuchania przemówień, w których politycy ciągle powtarzają nazwiska przeciwników. Ostatnie przemówienie przedstawiciela Bajtockiej Zjednoczonej Partii Informatyków. podniosło mu ciśnienie: polityk ten w zasadzie ciągle powtarzał to samo. Bajtek zapisał sobie transkrypt przemówienia i chciałby policzyć ile jest w nim powtórzeń. Dokładniej, interesuje go liczba różnych spójnych podsłów przemówienia, które występują w nim co najmniej trzy razy. Pomożesz? Napisz program, który: wczyta transkrypt przemówienia, wyznaczy liczbę różnych spójnych jego fragmentów, które występują w przemówieniu co najmniej trzykrotnie i wypisze wynik na standardowe wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego (bez żadnych odstępów) – treść przemówienia polityka. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba różnych spójnych fragmentów przemówienia, które wystąpiły w nim co najmniej trzykrotnie. Ograniczenia Długość przemówienia nie przekracza 500 000 znaków. Przykład Wejście Wyjście Wyjaśnienie abaabab 3 W tym przypadku powtarzające się fragmenty przemówienia to: a, b oraz ab. Fragment a powtarza się nawet cztery razy.

Wejście	Wyjście	Wyjaśnienie
`3 2`	`7`	Tabliczka mnożenia 3 × 3 zawiera następujące liczby: 1, 2 (dwa razy), 3 (dwa razy), 4, 6 (dwa razy) oraz 9. Najmniejsze liczby, które nie występują w niej to: 5, 7, 8, 10. Druga najmniejsza to 7.

Wejście	Wyjście	Wyjaśnienie
`2111-3-411`	`8`	W tym przypadku pasują następujące kody: 11-311, 11-341, 11-411, 13-411, 21-311, 21-341, 21-411, 23-411.

Wejście	Wyjście	Wyjaśnienie
`abaabab`	`3`	W tym przypadku powtarzające się fragmenty przemówienia to: `a`, `b` oraz `ab`. Fragment `a` powtarza się nawet cztery razy.