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
Картинка
Отражение Отражение Картинка Картинка
отражение
Лента событий: Lec добавил решение задачи "Девятый восьмиугольник" (Математика):
Рисунок
Rss

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

Пожалуйста, не пишите нам, что вы не можете решить задачу.
Если вы не можете ее решить, значит вы не можете ее решить :-)
Показывать на странице:
Задачу решили: 23
всего попыток: 79
Задача опубликована: 29.05.09 09:45
Прислал: admin img
Вес: 1
сложность: 2 img
класс: 8-10 img
баллы: 100
Лучшее решение: Anton_Lunyov

Вы собираете теннисные мячи в корзины, сотоящие из трех отделений, при этом раскладываете их по следующим правилам:

1. во всех отделениях всех корзин разное (ненулевое) количество мячей;

2. во всех корзинах в сумме по отделениям одинаковое количество мячей;

3. количество мячей в корзинах минимально возможное для данного количества корзин.

Например, если у вас 2 корзины, то в отделения первой корзины последовательно разещаем 1, 3 и 7 мячей, а в отделения второй - 2, 4 и 5 мячей. В результате в каждой корзине будет по 11 мячей, и это число минимально возможное.

У вас 100 корзин, найти сумму мячей в одной корзине.

Задачу решили: 35
всего попыток: 65
Задача опубликована: 01.06.09 18:55
Прислал: admin img
Вес: 1
сложность: 2 img
класс: 8-10 img
баллы: 200
Лучшее решение: casper

Пусть f(n) для натурального числа n равно количеству различных представлений в виде сумм степеней 2, при этом каждая степень не может использоваться более двух раз. Например, f(10)=5 так как 10=1+1+8=1+1+4+4=1+1+2+2+4=2+4+4=2+8.
Чему равно f(2009)?

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

Прямоугольная сетка 3 × 2 на рисунке содержит 18 прямоугольников:

 

Определим функцию f(a,b) как число прямоугольников, содержащихся в сетке a × b.

Сколько различных значений принимает f(a,b) при 0<a<1000 и 0<b<1000?

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

Если мы знаем только k членов последовательности, мы не можем однозначно описать следующий ее член с помощью многочленов.
Для примера давайте рассмотрим последовательность кубов натуральных чисел. Она порождается функцией un = n3: 1, 8, 27, 64, 125, 216, ...
Допустим, нам известны только два первых члена последовательности. Руководствуясь принципом "чем проще, тем лучше", мы можем воспользоваться линейной функцией и предсказать, что следующее за 1 и 8 значение будет равно 15. Если мы знаем три члена последовательности, то, пользуясь все тем же принципом простоты, мы можем описать ее квадратичным многочленом.
Обозначим через OP(k, n) n-ый член последовательности, порожденной оптимальным полиномиальным приближением, основанном на знании первых k членов последовательности. Ясно, что значения многочлена OP(k, n) точно совпадут с первыми k членами последовательности, а первым несовпадающим членом (ПНЧ), если есть такой, будет OP(k, k+1); если у многочлена имеется OP(k, n), который при некотором n несовпадает с соответствующим членом последовательности, мы будем называть недостаточным.
Выпишем первые OP для кубической последовательности:
k=1 OP(1, n) = 1 : 1, 1, 1, 1, ...
k=2 OP(2, n) = 7n-6 : 1, 8, 15, ...
k=3 OP(3, n) = 6n2-11n+6 : 1, 8, 27, 58, ...
k=4 OP(4, n) = n31, 8, 27, 64, 125, ...
Ясно, что для кубической последовательности есть только три недостаточных многочлена.  Их ПНЧ показаны в таблице синим цветом. Вычислив сумму ПНЧ для всех нехороших многочленов, получим  1 + 15 + 58 = 74.
Рассмотрим последовательность, заданную следующим многочленом десятой степени:
un  = -n + 2n2 - 3n3 + 4n4 - 5n5 + 6n6 - 7n7 + 8n8 - 9n9 + 10n10
Найдите сумму ПНЧ всех недостаточных многочленов для данной последовательности.

Задачу решили: 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)

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

Задачу решили: 33
всего попыток: 57
Задача опубликована: 22.02.10 08:00
Прислал: admin img
Вес: 1
сложность: 2 img
класс: 8-10 img
баллы: 100
Лучшее решение: Kruger

Шахматный конь ходит буквой "Г" - сначала в одну сторону на 2 клетки, а потом влево или вправо на одну. Новая шахматная фигура баран ходит как и конь, только сначала он ходит на 3 клетки.

Баран начал ходить с поля a1. Какое максимальное количество клеток он может посетить (включая первую) и при этом не наступая ни на одну из клеток дважды.  

Задачу решили: 5
всего попыток: 22
Задача опубликована: 26.07.10 08:00
Прислал: admin img
Вес: 1
сложность: 2 img
класс: 8-10 img
баллы: 100

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

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

Сколько существует различных "круговых" цепочек состоящих из всех костяшек?

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

Рассмотрим граф, составленный из блоков A и B, показанных на рисунке:

A B

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

Вершины графа будем раскрашивать, используя не более c цветов таким образом, чтобы связанные ребром вершины были окрашены в разные цвета.

Теперь подсчитаем, сколько разноцветных графов можно составить, используя a блоков A, b блоков B и не более c цветов.
Используя один блок A и три цвета, можно получить 24 различных графа. (a=1, b=0, c=3)
Используя два блока B и четыре цвета, можно получить 92928 различных графа. (a=0, b=2, c=4)
Используя два блока A, два блока B и три цвета, можно получить 20736 различных графа. (a=2, b=2, c=3)
А сколько различных графов можно получить, используя не более c=2011 цветов и 100 блоков A или B (a+b=100), так, чтобы a и b были четными числами?
В качестве ответа укажите 8 последних цифр результата.

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

В зале театра 40 нумерованных мест, а продано всего 18 билетов. Сколькими способами можно рассадить зрителей так, чтобы ровно 8 из них сидели на своих местах?

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

Рассмотрим множество, состоящее из первых n натуральных чисел: {1,2,...,n}.
Обозначим через f(n,k) количество его k-элементных подмножеств, сумма элементов которых нечетна. Например, f(5,3) =4, поскольку множество {1,2,3,4,5} имеет четыре 3-элементных подмножества с нечетной суммой элементов: {1,2,4}, {1,3,5}, {2,3,4} и {2,4,5}.
Когда все три числа n, k и f(n,k) нечетны, будем говорить, что они образуют нечетный триплет, и обозначим через g(m) количество нечетных триплетов [n,k,f(n,k)] с n ≤ m.
Тогда g(10)=5, поскольку существует ровно 5 нечетных триплетов с n ≤ 10, а именно:
[1,1,f(1,1)=1], [5,1,f(5,1)=3], [5,5,f(5,5)=1], [9,1,f(9,1)=5] и[9,9,f(9,9)=1]
Найдите наименьшее m, при котором g(m) > 1018.

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