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

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

Пожалуйста, не пишите нам, что вы не можете решить задачу.
Если вы не можете ее решить, значит вы не можете ее решить :-)
Показывать на странице:
Задачу решили: 6
всего попыток: 16
Задача опубликована: 04.07.09 09:14
Прислал: admin img
Вес: 1
сложность: 2 img
баллы: 100
Лучшее решение: TALMON (Тальмон Сильвер)

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

Задачу решили: 11
всего попыток: 30
Задача опубликована: 01.09.09 00:50
Прислал: admin img
Вес: 1
сложность: 2 img
баллы: 100

Шахматная доска пронумерована "змейкой": нижняя (первая) строка слева-направо числами 1-8, следующая (вторая) справа налево - 9-16, следующая снова слева направа - 17-24 и так далее.

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

Задачу решили: 6
всего попыток: 18
Задача опубликована: 10.09.09 09:02
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 2
сложность: 2 img
баллы: 100

На рисунке представлен неориентированный граф, содержащий семь вершин и 12 ребер, суммарный вес которых составляет 243.

Тот же граф можно представить следующей матрицей:

  A B C D E F G
A - 16 12 21 - - -
B 16 - - 17 20 - -
C 12 - - 28 - 31 -
D 21 17 28 - 18 19 23
E - 20 - 18 - - 11
F - - 31 19 - - 27
G - - - 23 11 27 -

Однако, некоторые ребра можно "сэкономить", не нарушая связности графа. Граф, в котором достигается максимальная экономия, представлен ниже. Его вес - всего 93, а "экономия" по сравнению с исходным графом составляет 243-93 = 150.

 

Пусть задан граф, содержащий 40 вершин, занумерованных числами от 0 до 39. Вес ребра, соединяющего вершины i и j, выражается формулой
wij =  wji = (69069(i - j)2(i + j))(mod 1000)

Какой максимальной экономии можно добиться, удаляя лишние ребра без потери связности графа?

Задачу решили: 51
всего попыток: 92
Задача опубликована: 28.06.10 08:00
Прислал: admin img
Источник: Санкт-Петербургский государственный университ...
Вес: 1
сложность: 2 img
баллы: 100
Темы: алгоритмыimg
Лучшее решение: katalama (Иван Максин)

Цепочки цифр (строки) создаются по следующему правилу:
Первая строка состоит из двух цифр "1". Каждая из последующих цепочек создается такими действиями: берется цифра, на единицу большая максимальной цифры, использовавшейся в предыдущей строке. Эта цифра вставляется в начало, в конец и между всеми цифрами предыдущей строки. Вот первые 4 строки, созданные по этому правилу:
(1) 11
(2) 21212
(3) 32313231323
(4) 43424341434243414342434

Таким образом, было построено еще 5 строк и в результате получена строка, содержащая цифры от 1 до 9 и состоящая из 767 цифр. Введите в ответ число состоящие из цифр стоящих на 300-м и 301-м местах от начала.

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

В игру "Погоня" играет четное количество игроков за круглым столом двумя игральными костями.
В начале игры два игрока, сидящие друг напротив друга, получают каждый по кости. Каждую секунду игроки, получившие кость, делают ход. Для этого они одновременно бросают кубик, и если выпадает 1, они передают кость соседу слева, а если выпадет 6 – соседу справа. В остальных случаях кубик остается у игрока до следующего хода. Игра заканчивается, когда оба кубика после очередного хода окажутся у одного игрока. Этот игрок считается проигравшим.
Однажды за стол сели играть 100 игроков. Их перенумеровали подряд по часовой стрелке. Спустя некоторое время кубики оказались у игроков № 33 и № 77.
Каково ожидаемое время до конца игры?
Ответ дайте в миллисекундах, округлив его до целого.

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

Лёва и Петя поспорили, у кого лучше память, и решили проверить. Для этого они обзавелись генератором случайных чисел, настроили его на получение случайных чисел от 1 до 10 и стали соревноваться, кто больше чисел запомнит. По условию игры участник получает очко, если очередное число все еще хранится в его памяти. Побеждает тот, кто набрал больше очков.

По ходу дела выяснилось, что и Лёва, и Петя могут удержать в голове не более пяти разных чисел. Если игрок уже помнит пять чисел, то чтобы запомнить следующее, не содержащееся к этому моменту в его памяти, он вынужден забыть одно из имеющихся. Однако оказалось, что забывание происходит несколько по-разному:

  • Лёва забывает то число, которое не выдавалось генератором наиболее продолжительное время
  • Петя забывает то число, которое первым попало в память.

В начале соревнования память игроков свободна.

Вот пример начала игры:

Тур

Очередное число

Память Лёвы

Очки Лёвы

Память Пети

Очки Пети

1

1

1

0

1

0

2

2

1,2

0

1,2

0

3

4

1,2,4

0

1,2,4

0

4

6

1,2,4,6

0

1,2,4,6

0

5

1

1,2,4,6

1

1,2,4,6

1

6

8

1,2,4,6,8

1

1,2,4,6,8

1

7

10

1,4,6,8,10

1

2,4,6,8,10

1

8

2

1,2,6,8,10

1

2,4,6,8,10

2

9

4

1,2,4,8,10

1

2,4,6,8,10

3

10

1

1,2,4,8,10

2

1,4,6,8,10

3

Обозначим количество очков, которые Лёва и Петя набрали после 50 туров через L и P, соответственно. Найдите математическое ожидание величины (L-P)2, результат умножьте на 108 и округлите до ближайшего целого.

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

 

Английский математик Джон Хортон Конвей изобрел множество математических развлечений, доставляющих не только удовольствие, но и пищу для серьезных размышлений. Одно из его изобретений – язык программирования FRACTRAN, о котором пойдет речь в данной задаче.

Память данных виртуальной машины языка FRACTRAN содержит одно единственное целое число, а программа представляет собой упорядоченную последовательность рациональных дробей. На каждом шаге выполнения программы машина просматривает эти дроби одну за другой слева направо и умножает каждую из них на число из памяти, пока произведение не окажется целым. Полученное целое число записывают в память вместо предыдущего. 

Вот, например, FRACTRAN-программа, предложенная Конвеем для получения последовательности простых чисел:

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1.

Записав в память исходное значение 2, получим в памяти ряд чисел в следующей последовательности:

15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

Оказывается, степени двойки в полученной последовательности встречаются только с простыми показателями: 22, 23, 25, ..., и можно проверить, что данная последовательность будет содержать в порядке возрастания все степени двух с простыми показателями.

Заметим, что для получения 22 из исходного числа 2 потребовалось 19 шагов программы, и при этом три раза происходило умножение на дробь 13/11.

А сколько раз придется выполнить умножение на 13/11 при переходе от исходного числа 2 к 2111119?

 

 

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

 eu315.gif

Сэм и Макс решили сделать из электронных часов прибор для демонстрации последовательности математических вычислений. Для испытания они запрограммировали его на расчет однозначной суммы цифр натуральных чисел. Напомним, что для вычисления однозначной суммы цифр суммируют все десятичные цифры числа, затем все десятичные цифры результата, и так далее, пока не получится однозначное число.

Когда в прибор передают очередное число, оно отображается индикатором, затем отображаются все промежуточные значения, и, наконец, - результат.

Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа.

Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке.

Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине.

Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии.

Сэм и Макс предложили разные конструкции прибора.

Работа прибора Сэма показана на картинке слева. Когда  этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет

В таблице приведен расчет энергопотребления прибора Сэма для числа 137.

"137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается).

"11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается).

"2":(5) × 2 = 10 переключений ("2" включается и выключается).

Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии.

Прибор Макса (изображен справа) работает по-другому. Он не выключает каждый раз весь индикатор, а выбирает только те отрезки, которые не понадобятся для следующего числа.

Вот, как он будет работать с числом 137:

"137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит)

"11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2").

"2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2").

Итого: 30 переключений.

Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии.

Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих  2×107.

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

На каждую клетку доски N×N положили по шашке, окрашенной в белый цвет с одной стороны и в черный цвет с другой.

Каждым ходом разрешается перевернуть одну шашку, а вместе с нею N-1 шашек, стоящих  на одной с ней вертикали, и N-1 шашек, стоящих  на одной с ней горизонтали. Таким образом, каждым ходом игрок должен перевернуть 2×N-1 шашку. Игра заканчивается, когда все шашки будут стоять белой стороной вверх. Ниже приведен пример игры для доски 5×5.

eu331.gif  

Несложно проверить, чтобы закончить игру из данной начальной позиции, нужно как минимум 3 хода.

Пусть строки и столбцы перенумерованы целыми числами от 0 до N-1.

Построим на доске N×N начальную конфигурацию CN. Для этого на клетку с координатами x и y положим шашку черной стороной вверх, если (N-1)2≤x2+y2<N2, и белой стороной вверх в противном случае. Конфигурацию C5 мы видели в приведенном примере.

Пусть T(N) – минимальное количество ходов, необходимых для окончания игры из начального положения CN (если это невозможно T(N) = 0).

Ясно , что T(1)=T(2)=1. Мы видели, что T(5)=3. Можно проверить, что T(10)=29, а T(1000)=395253.

Найдите сумму T(k!) для 1≤k≤12.

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