|
|
|
|
|
|
|
Вернуться
| 1 Тер-Саркисов Богдан Олегович, 01 мая 2025 г. 18:30:52 | |
|
В M я отсортировал массы гирь по возрастанию и рассматривал поочередно каждую гирю. На очередной итерации получал список из непересекающихся непрерывных отрезков сумм масс рассмотренных гирь. Понадеялся на то, что после каждой итерации количество таких отрезков не будет слишком большим. Может, если будут тесты посильнее, то решение завалится.
|
|
|
| 2 Яндулов Богдан, 01 мая 2025 г. 17:35:02 | |
|
А ещё интересно, как решается М. У меня зашла такая лажа на 100 баллов: если N * (сумма всех чисел) < 5e10, то с помощью битсета честно всё моделируем и находим все непредставимые числа. А если > 5e10, то моделируем процесс не полностью, а только для последних пары миллионов чисел. Код: https://pastebin.com/WQb9NNjU
|
|
|
| 3 Яндулов Богдан, 29 апреля 2025 г. 17:02:55 | |
|
Ну ведь если делается задача с вещественным выводом, то он должен быть посчитан максимально точно. А Владимир говорил, что он обычной точностью без decimal в питоне считался
|
|
|
| 4 Тер-Саркисов Богдан Олегович, 29 апреля 2025 г. 15:34:47 | |
|
Или там было ограничение в миллион даже
|
|
|
| 5 Тер-Саркисов Богдан Олегович, 29 апреля 2025 г. 15:33:50 | |
|
А там погрешности большие могут быть при вычислении. Взять какой-нибудь большой тест со значениями h=100000, k=100000, r=100000 и сравнить, что выдают программы с использованием вещественных типов двойной точности, четверной или decimal. Насколько помню, там результаты отличались уже после 4 знака после запятой.
|
|
|
| 6 Яндулов Богдан, 29 апреля 2025 г. 15:03:33 | |
Ещё непонятно, что там с авторским решением в F. У меня есть 2 решения, одно формула, другое интеграл, оба одинаково считают, но всё равно ~60 баллов: https://pastebin.com/BagAdVg2.
Если кривая действительно задаётся формулой (cos(2 * PI * k * t) * r * t, sin(2 * PI * k * t) * r * t, h * (1 - t)), 0<=t<=1, то видимо тесты тоже плохие из-за своей недостаточной точности.
|
|
|
| 7 Яндулов Богдан, 29 апреля 2025 г. 14:57:46 | |
|
Круто, что получилось так же. Но раз это набирает только 70 баллов, то видимо тесты там опять неправильные. Хотя кто-то умудрился 100 набрать.
|
|
|
| 8 Учиха Саске, 29 апреля 2025 г. 12:49:24 | |
|
А задачи потом будут помещены в раздел курсы? А то стало интересно, захотелось поглядеть.
|
|
|
| 9 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 23:13:56 | |
|
Получилось точно так же, как и у тебя, Богдан.
|
|
|
| 10 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 22:58:12 | |
|
Похоже, что и здесь тоже ошибся. Теперь вышло для минимума период 9 (min[i] = min[i-9] + 3), а для максимума период 4 (max[i] = max[i-4] + 7). Если и здесь ошибся, что ж...
|
|
|
| 11 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 15:11:06 | |
|
В итоге у меня получился паттерн с периодом 4 для минимума и с периодом 5 для максимума (если нигде не ошибся). Проверить бы в системе.
|
|
|
| 12 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 13:47:06 | |
|
Всё же у меня в составлении списка ребер косяк.
|
|
|
| 13 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 13:24:27 | |
|
А, нет. Тут что-то не так посчитал.
|
|
|
| 14 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 13:21:07 | |
02112112112220
Обновил: https://pastebin.com/zPzRWYib
|
|
|
| 15 Яндулов Богдан, 28 апреля 2025 г. 12:50:22 | |
|
А для какой изначальной строки получится в итоге x = 3 и y = 9?
|
|
|
| 16 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 12:32:17 | |
Паттерн по модулю 9. https://pastebin.com/wWXtkJR6
Саму задачу свёл к графовой, где в процессе обработки строки есть состояния:
(balance = количество просмотренных единиц - количество просмотренных двоек;
x = количество созданных единиц;
y = количество созданных двоек;
index = номер инструкции в цикле, которая выполнится следующей).
Если index = 1 или index = 3, то сейчас будем обрабатывать единицы (или уже конец). Если index = 2 или 4, то двойки (или уже конец строки).
Из каждого состояния 4 ребра:
1) взять три единицы или двойки и продолжить рассматривать их;
2) взять три единицы или двойки и закончить их рассматривать - начать новый блок с другой цифрой;
3) взять две единицы или двойки и закончить их рассматривать;
4) взять одну единицу или двойки и закончить их рассматривать.
И таким образом вычисляем всевозможные значения y, которые получились в процессе в состоянии (balance = 0, x = X, y <= highY, index = {1, 2, 3, 4}).
Выполняется то, что y имеет одинаковый остаток от деления на 3, что и x. А все получившиеся значения y идут непрерывно с шагом 3 (isCont=1 везде).
|
|
|
| 17 Яндулов Богдан, 28 апреля 2025 г. 12:08:10 | |
А что у тебя за паттерн? У меня такой получился: https://pastebin.com/5E0tVRMf
Набирает ~70 баллов. Если закомментить 31 строчку, получается 91 баллов.
|
|
|
| 18 Яндулов Богдан, 28 апреля 2025 г. 12:01:59 | |
|
Только заифать тесты уже не получится, когда их обновят)
|
|
|
| 19 Тер-Саркисов Богдан Олегович, 28 апреля 2025 г. 11:41:49 | |
|
Да обновят тесты когда-нибудь. Меня интересует еще задача G. Кто решал, понимает, что там получается некоторый паттерн, который надо закодить вместо медленного решения. До первых 200 значений X всё работает, по идее. А дальше с большой вероятностью паттерн сохраняется. Но все равно 88 баллов.
|
|
|
| 20 Яндулов Богдан, 28 апреля 2025 г. 11:24:46 | |
|
:-/
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
