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

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

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

Фруктовый сад имеет шестиугольную форму, а деревья в саду растут в вершинах треугольной решетки. На рисунке показан план такого сада со стороной n=5:

eu351.png

Из центра сада можно увидеть только часть деревьев, поскольку некоторые (они на рисунке обозначены зеленым цветом) заслонены другими, растущими ближе к наблюдателю. Легко подсчитать, что для сада со стороной n=5 количество заслоненных деревьев равно 30.
Обозначим через H(n) количество заслоненных деревьев для шестиугольного сада со стороной n.
Можно проверить, что H(5) = 30, H(10) = 138, а H(1000) = 1177848.
Найдите H(1234567890).

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

Известно, что некий вирус поражает 2% овец. Ветеринару нужно выявить зараженных животных в стаде из 25 голов. При этом в его распоряжении имеется достаточно дорогой, но очень чувствительный метод анализа, позволяющий обнаруживать инфекцию в крови при крайне низких ее концентрациях.

Чтобы сэкономить дорогостоящие реактивы, ветеринар решил не проверять каждую овцу, а разработал следующую программу действий:
Он разбил стадо на 5 групп по 5 овец в каждой. Пробы крови для каждой группы были объединены и проанализированы. Затем, если в объединенной пробе вирус не обнаружен, все овцы из данной группы считаются здоровыми. В противном случае анализируются пробы крови для каждого из пяти животных группы.
Поскольку вероятность заражения отдельной овцы равна 0,02, первый тест для каждой группы даст
• Отрицательный результат с вероятностью 0,985 = 0,9039207968. Для такой группы дополнительные тесты не понадобятся.
• Положительный результат с вероятностью 1 - 0,9039207968 = 0,0960792032. Для такой группы потребуется проанализировать еще 5 отдельных проб.
Тогда ожидаемое количество анализов для каждой группы составит 1 + 0,0960792032 × 5 = 1,480396016, а для всего стада – 1,480396016 × 5 = 7,40198008 тестов, то есть экономия составит более 70%!
Однако это не предел. Алгоритм можно еще усовершенствовать следующим образом:
• Сначала можно проанализировать объединенную пробу для всех 25 овец. Легко проверить, что примерно в 60,35% случаев результат будет отрицательный, и дальнейшее исследование не потребуется.
• Если групповая проба для 5 овец была положительной, и первые четыре овцы из группы оказались здоровы, то пятую можно не проверять – она наверняка инфицирована.
• Можно попробовать поварьировать размер и количество групп. Это позволит минимизировать ожидаемое количество анализов.
Чтобы не усложнять задачу, мы несколько ограничим круг рассматриваемых алгоритмов. Мы примем следующее дополнительное правило: если проанализирована объединенная проба для группы овец, то овцы, не входящие в данную группу, не исследуются, пока не поставлен окончательный диагноз каждой овце из данной группы.
Оставаясь в рамках данного правила, мы можем найти оптимальную стратегию, позволяющую ограничиться всего 4,155452 тестами в среднем для стада из 25 овец и вероятности заражения 0,02.
Обозначим через T(s,p) ожидаемое количество тестов при использовании оптимальной стратегии, когда стадо состоит из s овец, а вероятность заражения отдельной овцы равна p.
Тогда T(25, 0,02) ≈ 4,155452 и T(25, 0,10) ≈ 12,702124.
Найдите p, для которого T(10000, p)=5000. Результат умножьте на миллион и округлите вниз до целого.

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

Космонавты осваивают планету, имеющую радиус r. Они построили две станции на полюсах планеты, имеющих координаты (0,0,r) и (0,0,-r) в системе координат, связанной с центром планеты.
Также они установили несколько промежуточных станций, расположенных во всех точках поверхности планеты, имеющих целые координаты.


Все станции связаны дорогами, проложенными по кратчайшей дуге большого круга, однако путь между станциями требует больших затрат, равных (d/(π r))2, где d – протяженность дороги между двумя станциями. Если маршрут включает посещение нескольких промежуточных станций, затраты на все путешествие равны сумме затрат на отдельных участках.
Маршрут, проложенный между полюсами планеты и не проходящий через промежуточные станции, будет иметь длину πr, а затраты будут равны 1. Если же включить в маршрут одну промежуточную станцию с координатами (0,r,0), затраты уменьшатся вдвое:   (½πr/(πr))2+(½πr/(πr))2=0,5.
Будем называть оптимальным маршрут между полюсами планеты, если он требует минимальных затрат.
Например, при r=7 оптимальный маршрут будет проходить через 6 промежуточных станций, а затраты составят примерно 0,1784943998…
Подсчитайте, сколько промежуточных станций посетят космонавты, путешествуя по оптимальному маршруту между полюсами планеты с r=33333.

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

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

eu354.png

Одну из ячеек занимает пчелиная матка.
Обозначим через B(L) количество ячеек, удаленных от матки на расстояние L (в этой задаче мы будем измерять расстояния между центрами ячеек).
Считая соты достаточно большими, получим  B(√3) = 6, B(√21) = 12 и B(111 111 111) = 54.

Найдите количество таких L ≤ 3•1011, для которых B(L) = 378.

Ответ:

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

Рассмотрим множества, состоящие из взаимно простых натуральных чисел, не превышающих n.
Обозначим через Co(n) максимально возможную сумму элементов такого множества.
Например, Co(10)=30, и это значение достигается для множества {1, 5, 7, 8, 9}.
Можно проверить, что Co(30) = 193 и Co(100) = 1356.
Найдите Co(1000000).

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

Пусть a(n) – наибольший корень многочлена P(x) = x3 - 3nx2 + n, например a(2)=8,97517184...
Пусть t(n,p)=[a(n)p], где скобки […] означают округление вниз до целого.

Найдите восемь младших десятичных знаков суммы ∑t(i,333333333) для i=1,2,3,...30.

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

Возьмем натуральное число n и рассмотрим последовательность s(n)={1+n/1, 2+n/2, 3+n/3, …k+n/k,…}. Если эта последовательность не содержит целых составных чисел, будем говорить, что число n не порождает составных.
Легко проверить, что последовательность s(30)={31, 17, 13, 11.5, 11, 11, …} содержит только простые и нецелые числа. Поэтому число 30 не порождает составных.
Найдите количество восьмизначных чисел, которые не порождают составных.

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

Циклическим называют натуральное число из n знаков, обладающее следующим интересным свойством: если умножить его на 1, 2, 3, 4,…, n-1 или n, то произведение будет состоять из тех же цифр, но переставленных циклически.

Если не считать тривиального числа 1, наименьшим циклическим числом будет 142857:
142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

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

0588235294117647 × 1 = 0588235294117647
0588235294117647 × 2 = 1176470588235294
0588235294117647 × 3 = 1764705882352941
...
0588235294117647 × 16 = 9411764705882352

Найдите наибольшее циклическое число, которое начинается цифрами 00000000123 и заканчивается цифрами 56789 (то есть число вида 00000000123...56789, где многоточие означает некоторое неизвестное количество цифр). В качестве ответа укажите сумму его цифр.

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

В отеле "Инфинити" бесконечно много этажей, на каждом этаже бесконечно много комнат, а к администратору выстроилась бесконечно длинная очередь. И этажи, и комнаты на каждом этаже, и посетители перенумерованы подряд натуральными числами (1, 2, 3, …).
В начальный момент все комнаты отеля свободны. Чтобы поселить очередного гостя с номером n,  администратор выбирает самый нижний этаж, на котором либо пока никто не живет, либо последний поселившийся имеет такой номер m, что m+n является квадратом целого числа. Новый гость получает первый свободный номер на выбранном этаже.
 Гость №1 получает комнату №1 на первом этаже, поскольку на нем еще никто не живет.
 Гостя №2 нельзя поселить в комнате №2 на первом этаже, поскольку сумма 1+2=3 не является квадратом. Этого гостя можно поселить на втором, пока еще пустом этаже, в комнате №1.
 Гость №3 получает комнату №2 на первом этаже, поскольку сумма 1+3=4 является квадратом.
Таким образом, каждый гость получит свою комнату в отеле.
Обозначим через P(f, r) номер посетителя, живущего в комнате r на этаже f.
Тогда:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454
Найдите сумму P(f, r) для всех f и r, таких что f2 + r2 = 14234886498625 .

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