IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Правила раздела

Публикующим:
     1. Задачу можно опубликовать двумя способами:
          - создав для нее отдельную тему с информативным названием;
          - добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
     2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
     1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
     2. Правильность решения можно проверить, написав личное сообщение автору.

 
Ответить в эту темуОткрыть новую тему
> Мегамозг на краю обрыва, Возьму на себя смелость предложить задачу, кажется, подходящую для раз
L0st
16.4.2017, 23:14
Сообщение #1


Новичок
*

Группа: Пользователи Braingames
Сообщений: 7
Регистрация: 7.11.2009
Пользователь №: 17 549



Нашел эту задачку на одном из англоязычных каналов ютуба (пардон, если баян).
В общем, оккупанты опять издеваются над Мегамозгом. На этот раз его поставили на краю обрыва: два шага назад - он упадет, два шага вперед - будет съеден голодными туземцами. Оккупанты сохранят Мегамозгу жизнь, если он составит алгоритм из определенного количества команд вперед/назад, последовательно выполнив которые он бы не упал и не был съеден. К тому же, подлые оккупанты могут заставит выполнять команды не последовательно, а, к примеру, каждую 2ую, либо каждую 3ью, либо каждую 4ую и т.д. Каково максимальное количество команд в наборе, с помощью которого Мегамозгу гарантированно выживание?
ЗЫ Кажется, более логично спросить "каково минимальное количество команд, выполнение которого наверняка бы погубило Мегамозга?", но это противоречит духу сайта smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Owen
19.4.2017, 14:41
Сообщение #2


Kорифей
****

Группа: Администраторы Braingames
Сообщений: 1 977
Регистрация: 6.3.2013
Пользователь №: 43 989



Каждую 2ю, 3ю и т.д. - начиная с первой?
Т.е. возможны наборы команд "1, 2, 3, 4, ...", "1, 3, 5, ...", "1, 4, 7, ..."? Или как-то иначе?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
L0st
21.4.2017, 6:30
Сообщение #3


Новичок
*

Группа: Пользователи Braingames
Сообщений: 7
Регистрация: 7.11.2009
Пользователь №: 17 549



QUOTE(Owen @ 19.4.2017, 14:41) *
Каждую 2ю, 3ю и т.д. - начиная с первой?
Т.е. возможны наборы команд "1, 2, 3, 4, ...", "1, 3, 5, ...", "1, 4, 7, ..."? Или как-то иначе?

1 2 3 4...
2 4 6 8...
3 6 9 12...
4 8 12 16...
и т.п.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
fiviol
21.4.2017, 7:20
Сообщение #4


Участник
**

Группа: Пользователи Braingames
Сообщений: 107
Регистрация: 28.3.2009
Из: г. Трехгорный, Челяб. обл.
Пользователь №: 13 681



11 получается.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
L0st
21.4.2017, 20:43
Сообщение #5


Новичок
*

Группа: Пользователи Braingames
Сообщений: 7
Регистрация: 7.11.2009
Пользователь №: 17 549



QUOTE(fiviol @ 21.4.2017, 7:20) *
11 получается.

Верно. Для трех шагов вперед/назад предлагать не буду - не хочу грех на душу брать smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
fiviol
25.4.2017, 9:16
Сообщение #6


Участник
**

Группа: Пользователи Braingames
Сообщений: 107
Регистрация: 28.3.2009
Из: г. Трехгорный, Челяб. обл.
Пользователь №: 13 681



А ответ для трех шагов известен? Уже больше 120 команд проскочил, конца пока не видно. smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
L0st
25.4.2017, 10:19
Сообщение #7


Новичок
*

Группа: Пользователи Braingames
Сообщений: 7
Регистрация: 7.11.2009
Пользователь №: 17 549



QUOTE(fiviol @ 25.4.2017, 9:16) *
А ответ для трех шагов известен? Уже больше 120 команд проскочил, конца пока не видно. smile.gif

Да, для трех известен. Скажу лишь, что для четырех он уже выше 13000.
Могу даже сказать наименование обобщенной задачи. К слову, решение для общего случая было доказано в 2015.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
fiviol
25.4.2017, 14:41
Сообщение #8


Участник
**

Группа: Пользователи Braingames
Сообщений: 107
Регистрация: 28.3.2009
Из: г. Трехгорный, Челяб. обл.
Пользователь №: 13 681



Нет, случай 4 шагов и уж тем более обобщенная задача - это заведомо грех на душу по отношению к работе. smile.gif

Для трех шагов уперся в 164 команды.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Nikita146
7.5.2017, 16:14
Сообщение #9


Активный участник
***

Группа: Администраторы Braingames
Сообщений: 698
Регистрация: 21.9.2015
Пользователь №: 54 896



В общем виде это гипотеза Эрдёша о расходимости, и, согласно этой статье (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
VitalyKolobkov
12.5.2017, 22:01
Сообщение #10


Участник
**

Группа: Пользователи Braingames
Сообщений: 242
Регистрация: 18.2.2011
Пользователь №: 23 171



Драма "Erdős discrepancy problem".

На форуме.
L0st: Нашел эту задачку на одном из англоязычных...
Я: Хмм, интересно, надо попробовать решить.

Через неделю.
Я: Эх, что-то я забыл, там же какая-то вроде забавная задачка была. Что там еще раз?
Открывается форум.
fiviol: 11 получается.
L0st: Верно. Для трех шагов вперед/назад предлагать не буду - не хочу грех на душу брать smile.gif
Я: Да, на самом деле, получается 11. Все довольно просто, дерево небольшое. Надо бы сделать для трех шагов.
Через 10 минут, исписав целую страницу.
Я: Не, на бумаге слишком долго получается. Проще запрогать. Что-то лень с++ проект создавать, сделаю ка я прямо на джава скрипте, в браузере запущу.
Внутренний голос (ВГ): Ой, неужели! Там же надо будет хитрую структуру в памяти строить, возможно оптимизировать придется. В плюсах ты через указатели все раскидаешь, если что, а в джава скрипте справишься?
Я: Да, это хороший аргумент, ладно, так и быть, создам проект в плюсах.

После нескольких часов кодинга и отладок всех мелочей.
Я: Ага, вроде все работает, на двух шагах 11 получается, на деструктор пока наплевать, там памяти кот наплакал, запускаем для трех шагов.
ВГ: Ну-ну wink.gif
Я: Пошло дело! Пойду домой.

На следующий день.
Я: Что? Кончилась память? Никогда такой ошибки не видел. Что значит, кончилась память.
ВГ: Лол, лошара laugh.gif
Я: Подожди, эта штука реально съела 12 гигов оперативы что ли?!
ВГ: А ты перед тем, как запускать хоть прикинул, как эта штука растет, сколько памяти надо, сколько операций на каждый шаг потребуется?
Я: Ок, щас все будет.
Запускается код с ограничение по количеству шагов, строится зависимость количества элементов в дереве от глубины, фиттится с очень хорошей точностью на exp(0.5*n).
Я: Эмммм...
ВГ: Ну, что дальше?
Я: Нда, экспоненту так просто не победишь. Ладно, придется переписать половину кода и сделать дерево, которое само себя удаляет на ходу, но запоминает самую длинную ветку.
ВГ: Го фор ит!

После нескольких часов кодинга и отладок.
Я: Ок, вроде работает. Смотри в таск менеджере: память не растет.
ВГ: Молодец! Посиди минут 20, посмотри, как эта музыка работает.
Я: Ок.
ВГ: Ну чё?
Я: Что-то оно заглохло как-то подозрительно на длине 258 шагов.
ВГ: Подожди еще.
Я: О! Новая длина 269, уже 272.
ВГ: На ночь оставь, может досчитает.

На следующий день.
Я: А ну ка! Чта? Всего 318? Что за фигня? А комп точно ночью пахал, а не спал?
ВГ: А сколько операций на каждый шаг тратится?
Я: Порядка exp(0.5n)*n^2, там проверка лобовая, то есть n/3 сумм считается каждый раз.
ВГ: Может n^2 можно как-то улучшить?
Я: Я об этом еще в самом начале думал, но... сложная какая-то задача уже становится. Я ее третий раз переписываю.
ВГ: А кто-то на джава скрипте вообще хотел в браузере запускать... cool.gif
Я: Заткнись!

Через несколько часов кодинга.
Я: Все, теперь это, грубо говоря, exp(0.5n)*log(n). Ну, от экспоненты я никак не уйду. Мне же придется пройтись по всем веткам дерева.
ВГ: Запускай на ночь.
Утром:
Комп: Привет, тут ночью питание отключали, добро пожаловать, введи логин, пароль, все дела tongue.gif
Я: #%$%@#$@#$^%&^*$@
ВГ: Лол, лошара laugh.gif Может быть надо в файл делать вывод, а?
Я: Ок...
ВГ: Еще кое-что: запусти стразу на два ядра, пусть одно с +1+1 начнет, а второе с +1-1.
Я: Это хорошая мысль. Запускаю.

Примерно через сутки.
Я: Посмотрим, что там. Вы серьезно? Глубина 389 при количестве элементов 2861030146 при заходе от +1+1 и глубина 379 при количестве элементов 1079400871 при заходе +1-1. Нда, такими темпами он будет еще долго считать. Если там искомая глубина 500, например, то я и за месяц до нее не доберусь. Тут придется на 1000 процессоров раскидывать. Ладно, проверим форум, может там кто-нибудь уже решил.
На форуме.
Nikita146: В общем виде это гипотеза Эрдёша о расходимости, и, согласно этой статье (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности.
Я: 1124! Ничесе! А что скажет Википедия? А она говорит, что длина 1161 (https://arxiv.org/pdf/1402.2184.pdf). 1161, Карл!
ВГ: Все, приплыли на барже...
Я: Обидно, да?
ВГ: Обидно. Иди лучше работой займись.
Я: И то верно. Ушел sad.gif

--------------------------------------------------
Мораль: если что-то делаете, то делайте сразу хорошо и правильно, а не кое-как на коленке... или не делайте вообще.

Сообщение было отредактировано VitalyKolobkov: 12.5.2017, 22:08
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Nikita146
13.5.2017, 0:49
Сообщение #11


Активный участник
***

Группа: Администраторы Braingames
Сообщений: 698
Регистрация: 21.9.2015
Пользователь №: 54 896



Да уж, темп роста функции впечатляет
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 22.10.2017, 16:39