На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (6) 1 [2] 3 4 ... Последняя » все  ( Перейти к последнему сообщению )  
> головоломки на написание алгоритма
    Цитата ya2500 @
    в данный момент я думаю над доказательством того, что в шахматах есть беспроигрышная стратегия(по крайней мере у одного из игроков)


    у меня получилось :yes:

    Добавлено
    надо только продумать, как кратко это доказательство записать.
    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
      Цитата ya2500 @
      вот, куска (одна буква "н") в результирующем файле точно быть не может.

      Может :) "В этом файле ... двадцать одна буква "н" ..." (при этом в остальном тексте их 19). Но все же, мне кажется, можно подобрать файл, к которому решение просто не сойдется в данной формулировке.
      Долог путь в бессмертие... я еще вернусь.
      Профильный скилл "Телепатия" 8%
      ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
      Прошу потестить игру.
        Цитата Vesper @
        Но все же, мне кажется, можно подобрать файл, к которому решение просто не сойдется в данной формулировке.


        трудно сказать. ведь мы формируем доп.инфу, в тексте которой сотни букв. возможно, что обычно для входного файла задача имеет тысячи решений. и если окажется так, то я бы усомнился в том, что можно подобрать файл, к которому решения найти невозможно.
        "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
        "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
          да, вот ещё:
          Цитата ya2500 @
          менее известная игра "Конфета"

          Скрытый текст
          Выигрыш - откусить так, чтобы осталось 2^N-1, где N>=0. Если у самого 2^N-1, ты проиграл.
          Долог путь в бессмертие... я еще вернусь.
          Профильный скилл "Телепатия" 8%
          ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
          Прошу потестить игру.
            Vesper, есть пара вопросов:

            Скрытый текст
            действительно ли из любой выигрышной позиции возможно создать сопернику ситуацию 2^n-1?

            действительно ли нет такой ситуации 2^n-1, (при n>0), из которой возможно создать проигрышную позицию сопернику?


            Добавлено
            впрочем, ответом на эти вопросы будет любое доказательство твоей стратегии.
            "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
            "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
              ya2500
              Скрытый текст
              Что из 2^N-1 нельзя перейти в 2^(N-1)-1 - понятно, потому что разница между ними 2^(N-1) что больше желаемого остатка. То есть из множества 2^N-1 переход возможен только в точки, не принадлежащие множеству. Это ответ на второй вопрос.
              Ответ на первый вопрос - если число не равно 2^N-1, значит, из него можно перейти в 2^(N-1)-1, где 2^(N-1)<=X < 2^N-1, так как X-(2^(N-1)-1) меньше либо равна 2^(N)-2 - (2^(N-1)-1) = 2*(2^(N-1))-2-(2^(N-1)-1) = 2^(N-1)-1, то есть меньше или равна целевому числу, а значит, меньше или равна половине X. То есть, из любого числа, не имеющего вид 2^N-1, всегда есть ход в число из множества 2^N-1, т.е. из выигрышного всегда есть ход в проигрышное. Это ответ на первый вопрос.
              Хватит для доказательства?
              Долог путь в бессмертие... я еще вернусь.
              Профильный скилл "Телепатия" 8%
              ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
              Прошу потестить игру.
                Цитата Vesper @
                Хватит для доказательства?


                да.

                Добавлено
                далее мне таки хотелось бы раскурить стратегию какой-нибудь игры с блефом.. или из темы по ссылке или другую можно придумать. но хотелось бы разобраться с блефом.

                ...

                ну, или вот, обычная задачка на написание алгоритма: разрезание прямоугольника на квадраты:

                даны три числа: n, m, k. n и m- стороны исходного прямоугольника. найти минимальное количество квадратов, на которое его можно разрезать так, чтобы хотя бы один из квадратов имел сторону равную k.
                Сообщение отредактировано: ya2500 -
                "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                  Цитата
                  В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.

                  Больше всего решений на GNU C++ — 1516.
                  Решений на Java 7 — 333.
                  Решений на Java 8 — 106.


                  вот статья с Хабра с разбором задач: http://habrahabr.ru/company/mailru/blog/225743/

                  полная формулировка первой задачи (без решения) здесь: https://www.russiancodecup.ru/championship/...nd/9/problem/A/

                  там же можно перейти и на другие задачи.

                  Добавлено
                  в том числе и на задачи 4-х квалификационных раундов.
                  "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                  "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                    вот, например, простая задача из первого раунда: https://www.russiancodecup.ru/championship/...nd/7/problem/A/

                    но если стремиться найти максимально простой алгоритм, то можно и над ней подумать.

                    Добавлено
                    о! это же ежегодный конкурс и проходит уже четвёртый год. и на их сайте есть архив заданий за прошлые годы с решениями.

                    Добавлено
                    да, этот конкурс меня заинтересовал :yes:
                    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                      Цитата ya2500 @
                      да, этот конкурс меня заинтересовал

                      Поздно ты спохватился :)
                      Подпись была включена в связи с окончанием срока наказания
                        другой сайт с задачами на программирование:

                        http://codeforces.ru/contest/538/problem/B

                        про именно ту задачку, что по ссылке, открыта отдельная тема: Простая задача
                        "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                        "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                          пожалуй, помещу это сюда:

                          Цитата
                          Из аналогов codeforces выделяется разве что Topcoder - тот же codeforces (т.е. регулярные соревнования с рейтингом и общение), но исключительно на английском языке и с несколько более разнообразным форматом соревнований.
                          Если просто архивы задач, то их море:
                          http://acm.timus.ru/, http://acm.sgu.ru/, http://www.spoj.com/, http://acm.mipt.ru/judge - просто архивы задач сложности от "сумма двух чисел" до "а оно вообще решается?" :)
                          http://acmp.ru/ - архив простых задач, ориентированный на начинающих.
                          Куча сайтов соревнований, проводимых ежегодно различными компаниями (Яндекс, гугл, мейлру, фейсбук, КРОК, Вконтакте - только те, что вспомнил навскидку).


                          Добавлено
                          codeforces это вот: ссыль.
                          "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                          "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                            Цитата ya2500 @
                            а в данный момент я думаю над доказательством того, что в шахматах есть беспроигрышная стратегия(по крайней мере у одного из игроков). это не простая задача, но вполне посильная. наверное.

                            А это не очевидно?
                            На всякий случай спрячу
                            Допустим, у белых есть стратегия, позволяющая выигрывать, тогда данная стратегия является искомой. Если же её нет, то это означает, что на любой ход белых чёрные смогут ответить так, чтобы не проиграть. И тогда стратегия чёрных - искомая.
                            Подпись была включена в связи с окончанием срока наказания
                              Цитата ya2500 @
                              у меня получилось

                              Добавлено 29 мая 2014, 22:09
                              надо только продумать, как кратко это доказательство записать.

                              Цитата OpenGL @
                              А это не очевидно?
                              На всякий случай спрячу


                              ёксель-моксель, это же так просто :good: на самом деле то, что "у меня получилось", по-сути, включало в себя доказательство того, что в такой походовой игре с открытой информацией у одной из сторон обязательно существует беспроигрышная стратегия. то есть, то, на что ты неявно опёрся.

                              но, да- у меня такой замут вышел потому, что я не догадался до такого простого доказательства.
                              "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                              "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                                Цитата OpenGL @
                                На всякий случай спрячу
                                Да нечего там прятать.
                                Цитата OpenGL @
                                Допустим, у белых есть стратегия, позволяющая выигрывать, тогда данная стратегия является искомой. Если же её нет, то это означает, что на любой ход белых чёрные смогут ответить так, чтобы не проиграть. И тогда стратегия чёрных - искомая.
                                Увы, но тут изъян. Итак, рассматриваем второй вариант, когда выигрышной стратегии у белых нет. Да, чёрные могут будут ходить, не проигрывая, но белые могут начать так ходить, что ситуация будет повторяться и тогда зачтут ничью, или, допустим, поражение чёрным. А ведь может оказаться, что у чёрных есть шанс! Как быть? Это показывает, что наличие беспроигрышной стратегии всё же непонятно. Ну мне то точно. Допускаю, что OpenGL сможет поподробнее расписать. :blush:
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1376 ]   [ 17 queries used ]   [ Generated: 20.06.19, 09:14 GMT ]