img img img img img img img img img img img img img img img img img img img img img img
Логотип Человек живет, пока думает.
Решайте задачи и живите долго!
Для участия в проекте необходимо
и достаточно зарегистрироваться!
Rss Регистрация || Вход
Вход
Diofant.ru
Картинка
Отражение Отражение Картинка Картинка
Рисунок
Rss

Задачи: Информатика   

Пожалуйста, не пишите нам, что вы не можете решить задачу.
Если вы не можете ее решить, значит вы не можете ее решить :-)
Показывать на странице:
Задачу решили: 0
всего попыток: 1
Задача опубликована: 20.08.12 08:00
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 1
сложность: 3 img
класс: 8-10 img
баллы: 100

Обозначим через C(x,y) окружность, проходящую через точки (x, y), (x,y+1), (x+1,y) и (x+1,y+1).

Обозначим через E(m,n) объединение m×n окружностей C(x,y), где 0≤x<m, 0≤y<n, а x, y, m и n – целые числа.

Эйлеровым циклом на E(m,n) называется замкнутый путь, включающий каждую дугу каждой окружности ровно один раз. В этой задаче мы будем рассматривать только те эйлеровы циклы, которые не имеют самопересечений. При этом участки цикла могут касаться друг друга в точках с целыми координатами, но не должны пересекаться.

На рисунке показан пример эйлерова цикла без самопересечений на E(3,3).

eu289.gif

Обозначим через L(m,n) количество эйлеровых циклов без самопересечений на E(m,n).

Например, L(1,2) = 2, L(2,2) = 37 и L(3,3) = 104290.

Найдите остаток от деления  L(6,13) на 613.

 
Задачу решили: 1
всего попыток: 2
Задача опубликована: 29.04.13 08:00
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 1
сложность: 3 img
баллы: 100
Темы: алгебраimg

В этой задаче рассматривается еще одна игра, похожая на ним, где два игрока по очереди берут камни из двух куч. Каждым ходом игрок берет камни из одной кучи в количестве, кратном количеству камней в другой куче. Как обычно, проигрывает тот, кто не может сделать очередной ход, т. е. когда  в одной из куч камней не осталось.

Опишем начальную позицию в виде упорядоченной пары чисел. Например, пара (6, 14) соответствует положению, при котором в меньшей куче 6 камней, а в большей — 14. В этом случае первый игрок может взять из большей кучи 6 или 12 камней.

Выигрышной называется позиция, которая позволяет первому игроку выиграть при верном выборе стратегии. Остальные позиции называются проигрышными. Например, позиции (1,5), (2,6) и (3,12) — выигрышные, поскольку первый игрок может первым же ходом забрать все камни из второй кучи.

Позиции (2,3) и (3,4) — проигрышные, поскольку при любом ходе первого игрока второй участник получает выигрышную позицию.

Обозначим через Z(N) сумму (yi-xi) для всех проигрышных позиций (xi,yi), 0 < xi< yi ≤ N. Можно проверить, что Z(10) = 27 и Z(104) = 24319983959.

Найдите остаток от деления Z(1016) на 710.

 
Задачу решили: 1
всего попыток: 4
Задача опубликована: 20.05.13 08:00
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 2
сложность: 3 img
баллы: 100
Темы: алгоритмыimg

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

  1. Ты назвал число меньше задуманного.
  2. Ты угадал!
  3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. 

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

 
Задачу решили: 6
всего попыток: 8
Задача опубликована: 23.09.13 08:00
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 1
сложность: 3 img
баллы: 100

Рассмотрим нечетное число 225 = 32 × 52.
2252 = 50625 = 34 × 54 = 92 × 252. Поэтому функция Эйлера φ(50625) = 2 × 33 × 4 × 53 = 23 × 33 × 53 .
Итак, число  50625 является квадратом, а φ(50625) является кубом.
Найдите сумму нечетных n, 1 < n < 1010 , для которых функция Эйлера φ(n2) является кубом натурального числа.

Задачу решили: 9
всего попыток: 18
Задача опубликована: 02.12.13 08:00
Прислал: Rep img
Вес: 1
сложность: 3 img
баллы: 100
Темы: алгоритмыimg
Лучшее решение: mikev

Степени двойки, как известно, редко начинаются с цифры 9 (см. задачу 316). Так, первый раз это случается только для 53-й степени (253 = 9007199254740992). С двух девяток подряд начинается 93-я степень, а с трех девяток - только 2621-я.

Найдите минимальный показатель степени n такой, что десятичная запись числа 2n начинается с десяти девяток подряд.

 
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.