|
|
|
|
|
|
|
Вернуться
| 1 Васильев Алексей Андреевич, 24 июля 2024 г. 0:22:52 | |
|
Эта задача была на мкошпе в 2008 году
|
|
|
| 2 Гетманов Николай Николаевич, 27 июня 2024 г. 21:39:59 | |
|
Спасибо.
|
|
|
| 3 Терентьев Михаил Павлович, 27 июня 2024 г. 21:02:38 | |
|
Задача C, только почему-то в разборе называется "Найди отрицательное".
|
|
|
| 4 Терентьев Михаил Павлович, 27 июня 2024 г. 21:01:06 | |
|
Ну как же? Надо перейти по вашей ссылке, откроется задача. А справа снизу есть ссылка на документ с разбором в разделе "материалы соревнования".
|
|
|
| 5 Гетманов Николай Николаевич, 27 июня 2024 г. 20:57:20 | |
|
Я заходил в разбор тренировки. В документе нет такой задачи.
|
|
|
| 6 Терентьев Михаил Павлович, 27 июня 2024 г. 20:55:46 | |
|
Там разбор есть же. Через дп делают.
|
|
|
| 7 Гетманов Николай Николаевич, 27 июня 2024 г. 20:50:42 | |
Короче, ключевые идеи:
1. Если прежние номера футболистов не являются делителями n+1, то их номер остаётся прежним. Число вероятно меняющих номера футболистов O(n**1/3).
2. А значит, каноническое разложение прежних и новых номеров этих футболистов (которые меняют номера) содержит такие же простые множители, что и n + 1. Главное, исчерпать все варианты степеней в канон. разложении новых номеров.
Глубже копнуть не получается пока.
|
|
|
| 8 Гетманов Николай Николаевич, 27 июня 2024 г. 20:34:13 | |
В сборной команде Берляндии по футболу n человек. Каждый футболист имеет майку с его порядковым номером. Майки пронумерованы таким образом, что среди номеров маек встречаются все числа от 1 до n, формально говоря, номера маек образуют перестановку из n
чисел.
После проигрыша в чемпионате мира по футболу было принято решение о смене тренера команды. Тренер считает, что только он может быть первым номером, поэтому, он заменил майку с номером 1
на майку с номером n+1. Теперь, среди номеров маек встречаются все числа от 2 до n+1.
Игрок согласится продолжить играть в команде, если номер его новой майки будет нацело делится на номер его старой майки. Посчитайте, сколько существует способов раздать игрокам новые майки, чтобы все игроки согласились дальше играть в команде.
Входные данные:
Натуральные числа t (t <= 10^4) и n (t <= 10^5) - число наборов входных данных и число футболистов.
Выходные данные:
Для каждого набора построчно КОЛИЧЕСТВО СПОБОБОВ раздать игрокам майки.
Пример:
2
1
3
Отв:
1
2
Пояснение:
В первом наборе входных данных изначальная последовательность: {1}. После смены тренера: {2}. Можно сопоставить единственным образом
Во втором наборе входных данных изначальная последовательность: {1, 2, 3}. После смены тренера: {2, 3, 4}. Можно сопоставить двумя способами: {2, 4, 3} и {4, 2, 3}.
Задача взята с Codeforces https://codeforces.com/gym/105236/problem/C.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
