Loading [Contrib]/a11y/accessibility-menu.js
ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрано 11 задач
Версия для печати
Убрать все задачи

Из четырёх палочек сложен контур параллелограмма. Обязательно ли из них можно сложить контур треугольника (одна из сторон треугольника складывается из двух палочек)?

Вниз   Решение


На плоскости расположено N точек. Отметим середины всевозможных отрезков с концами в этих точках. Какое наименьшее число отмеченных точек может получиться?

ВверхВниз   Решение


В треугольнике АВС угол В равен 120°,  АВ = 2ВС.  Серединный перпендикуляр к стороне АВ пересекает АС в точке D. Найдите отношение  AD : DC.

ВверхВниз   Решение


В основании прямой призмы лежит прямоугольный треугольник с катетами 4 и 1 . Боковые ребра равны . Найдите объем цилиндра, описанного около этой призмы.


ВверхВниз   Решение


В ботаническом справочнике каждое растение характеризуется 100 признаками (каждый признак либо присутствует, либо отсутствует). Растения считаются непохожими, если они различаются не менее, чем по 51 признаку.
  а) Покажите, что в справочнике не может находиться больше 50 попарно непохожих растений.
  б) А может ли быть ровно 50?

ВверхВниз   Решение


В основании прямой призмы лежит прямоугольный треугольник с катетами 9 и 6 . Боковые ребра равны . Найдите объем цилиндра, описанного около этой призмы.


ВверхВниз   Решение


Дана функция    ,   где трёхчлены  x² + ax + b  и  x² + cx + d  не имеют общих корней. Докажите, что следующие два утверждения равносильны:
  1) найдётся числовой интервал, свободный от значений функции;
  2)  f(x) представима в виде:  f(x) = f1(f2(...fn–1(fn(x))...)),  где каждая из функций  fi(x) есть функция одного из видов:   kix + bi, x–1, x².

ВверхВниз   Решение


Двое лыжников шли с постоянной скоростью 6 км/ч на расстоянии 200 метров друг от друга. Потом они стали подниматься в большую горку, и скорость упала до 4 км/ч. Потом оба лыжника съехали с горки со скоростью 7 км/ч и попали в глубокий снег, где их скорость стала всего 3 км/ч.
Каким стало расстояние между ними?

ВверхВниз   Решение


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

ВверхВниз   Решение


Саша и Ваня родились 19 марта. Каждый из них отмечает свой день рождения тортом со свечками по количеству исполнившихся ему лет. В тот год, когда они познакомились, у Саши на торте было столько же свечек, сколько у Вани сегодня. Известно, что суммарное количество свечек на четырёх тортах Вани и Саши (тогда и сегодня) равно 216. Сколько лет исполнилось Ване сегодня?

ВверхВниз   Решение


Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v1 в v2 .

Входные данные

Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v1 и v2 , а строка N+3 – десятичную запись числа C (1 &le C < 1050).

Выходные данные

В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v1 в v2 не существует, ваша программа должна вывести -1.

Пример входного файла

3
010
001
100
1 1
555555555555555555555555555555555

Пример выходного файла

Yes
0

Вверх   Решение

Задачи

Страница: 1 2 >> [Всего задач: 7]      



Задача 102955

 [Длинное равенство]
Тема:   [ Длинная арифметика как инструмент ]
Сложность: 3+

Во входном файле записано равенство вида A = B, где A и B – это выражения, содержащие сколь угодно длинные целые числа и знаки операций +, - (бинарный и унарный) и *. Выражения не содержат скобок. Требуется проверить выполнение заданного равенства и вывести в выходной файл результат проверки в форме «Да, выполняется» или «Нет, не выполняется».
Длина входного файла данных не превосходит 60 килобайт. Числа и знаки операций в выражении могут разделяться пробелами и/или символами перевода строки.

Пример входного файла

2
                * 43 = 86

Пример выходного файла

Да, выполняется
Прислать комментарий     Решение


Задача 102778

 [Последовательности из 0 и 1 ]
Темы:   [ Динамическое программирование: классические задачи ]
[ Длинная арифметика как инструмент ]
Сложность: 3

Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Входные данные

Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные

В выходной файл вывести количество искомых последовательностей.

Пример входного файла

5

Пример выходного файла

13
Прислать комментарий     Решение


Задача 102781

 [Ход конем ]
Темы:   [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
Сложность: 3

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
7 8 9
4 5 6
1 2 3
  0  

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

Входные данные

Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные

Выведите в выходной файл искомое количество телефонных номеров.

Пример входного файла

2

Пример выходного файла

16
Прислать комментарий     Решение


Задача 102782

 [Дырокол ]
Темы:   [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
Сложность: 3+

Квадратный клетчатый лист бумаги 2N × 2N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.

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

Входные данные

Первая строка входного файла содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках записана матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

Выходные данные

Вывести в выходной файл искомое число частей.

Пример входного файла

4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла

11
Прислать комментарий     Решение


Задача 102790

 [Длинный путь в графе ]
Темы:   [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
[ Графы (прочее) ]
Сложность: 3+

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v1 в v2 .

Входные данные

Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v1 и v2 , а строка N+3 – десятичную запись числа C (1 &le C < 1050).

Выходные данные

В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v1 в v2 не существует, ваша программа должна вывести -1.

Пример входного файла

3
010
001
100
1 1
555555555555555555555555555555555

Пример выходного файла

Yes
0
Прислать комментарий     Решение


Страница: 1 2 >> [Всего задач: 7]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .