3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
|
|
1 | |
Считалка. Олимпиадная задача по программированию09.01.2020, 18:36. Показов 2615. Ответов 11
Метки нет Все метки)
(
Ирочка попросила маму придумать новую считалочку. Мама тут же ей "выдала".
Пусть в кругу N человек. Это число N будем изменять следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы получаем число 1. На кого попадет один, тот - выходит. Теперь в кругу N-1 человек. Это число N-1 будем изменять следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы опять получаем число 1 На кого попадет один, тот - выходит. И т.д. Кто останется последним, тот и водит. Например, в кругу 3 игрока - N-3. Из числа 3 получается число 4 - первого пропускаем. Из числа 4 получается число 2 - второго пропускаем. Из числа 2 1 юлу чается число 1 - третий выходит. Теперь в кругу 2 игрока - N==2. Из числа 2 получается число 1 - первый выходит. Второй остался один - он водит. Входные данные: Количество игроков (1<=N<=32000) Выходные данные: Номер по порядку игрока, кому водить Пример 1. Входные данные: 3 Результат: 2 Пример 2. Входные данные: 4 Результат: 4
0
|
|
09.01.2020, 18:36 | |
Ответы с готовыми решениями:
11
Олимпиадная задача по программированию. PascalABC.NET Олимпиадная задача по программированию |
80 / 33 / 10
Регистрация: 14.06.2019
Сообщений: 516
|
|
09.01.2020, 18:47 | 2 |
Как это понять? Если я получу единицу, она ни в кого не попадает. Можно, пожалуйста, выдать условие не пересказом?
0
|
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
|
|
09.01.2020, 18:50 [ТС] | 3 |
Вроде я ничего не пропустил
0
|
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
|
||||||
09.01.2020, 19:12 [ТС] | 4 | |||||
Подскажите, пожалуйста, правильно ли будет работать эта программа?
0
|
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
|
|
10.01.2020, 10:00 | 5 |
тут фишка в том, что как в обычной считалочке произносятся поочерёдно слова для каждого игрока по кругу, так здесь выполняются вычисления. берём N вычисляем первое число if odd(N) then Inc(N) else N := N div 2;
если получилось 1 - то игрок, на котором это произошло - выбывает. потом "считалочка" повторяется заново, уже для нового числа игроков (теперь N стало на единицу меньше, т.к. один игрок выбыл) повторяем, пока не останется один единственный игрок. В задаче нужно определить номер этого игрока (номер - это порядковый номер в самом начале, перед первой считалкой)
1
|
80 / 33 / 10
Регистрация: 14.06.2019
Сообщений: 516
|
|
10.01.2020, 10:35 | 6 |
Какое-то странное условие в плане формулировки...
Да, я уже понял, но решить сильно не пытался
1
|
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
|
|
10.01.2020, 11:11 | 7 |
а кто-нибудь мне может объяснить, как из 4-х игроков по считалке остался водить игрок с номером четыре?
на мой взгляд - это глупость, т.к. игрок выбывает, а его место остаётся и на это место участвует в считалке! если считать, что из 4-х игроков по считалке будет водить четвёртый игрок, то да, программа работает верно.
1
|
Status 418
![]() |
||||||
10.01.2020, 13:30 | 8 | |||||
![]() Решение
дано:
1 2 3 4 2 1 - удаляем 2й остались: 3 4 1 4 2 1 - удаляем 3й остались: 3 4 1 - удаляем 1й остался: 4 счет не прерывается когда кто-то выходит. Добавлено через 13 минут mr-Crocodile, вот, но это не решение:
2
|
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
|
|
10.01.2020, 14:08 | 9 |
Спасибо. Именно этот момент и влияет. В условии задачи (тем более олимпиадной), имхо, это должно быть чётко сформулировано.
Добавлено через 14 минут а почему, собственно, это не решение? Если убрать промежуточный вывод - то вполне себе решение. или имеется в виду, что это "грубо" и "неэффективно"? Типа олимпиадные задачи "в лоб" не решают? ![]()
1
|
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
|
|
10.01.2020, 14:35 | 11 |
ну, так ограничения по времени в условии нет
![]() проверил. на n=32000 ответ примерно через 4 секунды. Если ограничение по времени есть, то не пройдёт.
1
|
Status 418
![]() |
|
10.01.2020, 22:46 | 12 |
У меня примерно 3 секунды выполняется.
Переписал решение на удаление элемента по индексу (RemoveAt) из списка (List) и сделал рекуррентный прекалк за O(n) для счёта, чтобы в цикле не считать постоянно на n = 32000 выполняется 0.033 секунды, а на n = 320000 выполняется 2.3 секунды.
2
|
10.01.2020, 22:46 | |
10.01.2020, 22:46 | |
Помогаю со студенческими работами здесь
12
Олимпиадная задача по программированию Олимпиадная задача по программированию Олимпиадная задача по программированию: Таджикские имена Олимпиадная задача по программированию.Ошибка в моем коде Олимпиадная задача Олимпиадная задача №4 Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |