ЗАДАЧИ
problems.ru 		О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Информатика >> Книги, журналы >> Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике >> глава 1. Динамическое программирование
Фильтр
Сложность с по   Класс с по  
Выбрано 5 задач
Версия для печати
Убрать все задачи 

Дана последовательность чисел. Найти в ней наименьшее число.

Входные данные.
Задано сначала число N (количество чисел в последовательности), а затем
N чисел.

Выходные данные.
Выведите наименьшее число.

Пример входного файла
7
4 2 5 -1 4 6 2

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

Вниз   Решение

Даны координаты двух полей шахматной доски
(координаты клетки - это 2 числа от 1 до 8: номер столбца и номер строки)

Одно ли цвета эти клетки на шахматной доске? Вывести в выходной файл
сообщение YES, если они одного цвета, и NO иначе

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

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


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

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

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

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

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

Даны два возрастающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти количество общих элементов в этих массивах, то есть количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j. (Число действий порядка k + l.)

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

Решить предыдущую задачу, если про массивы известно лишь, что x[1]≤...≤x[k] и  y[1]≤...≤y[l] (возрастание заменено неубыванием).

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

Задачи

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

  с решениями  

Задача 102778  (#1)

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

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

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

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

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

Пример выходного файла
13
Прислать комментарий     Решение

Задача 102779  (#2)

 [Восстановление скобок ]
Тема:   [ Динамическое программирование: классические задачи ]
Сложность: 3

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

Входные данные
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.

Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109 .

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

Пример выходного файла
2
Прислать комментарий     Решение

Задача 102780  (#3)

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

Задано уравнение вида A + B = C, где A, B и C – неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно.

Входные данные
Заданное уравнение содержится в первой строке входного файла. Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов.

Выходные данные
В выходной файл требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение «решения не существует».

Пример входного файла
??2?4+9?=355

Пример выходного файла
00264+91=355
Прислать комментарий     Решение

Задача 102781  (#4)

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

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

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

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

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

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

Пример выходного файла
16
Прислать комментарий     Решение

Задача 102782  (#5)

 [Дырокол ]
Темы:   [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
Сложность: 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
Прислать комментарий     Решение

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

  с решениями  

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

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