Подтемы:
-
Динамическое программирование
(46 задач)
Алгоритмы на графах
(28 задач)
Вычислительная геометрия
(16 задач)
Комбинаторика
(33 задачи)
Перебор
(14 задач)
Синтаксический разбор
(8 задач)
Структуры данных
(3 задачи)
Длинная арифметика
(7 задач)
Прочие задачи на сообразительность
(7 задач)
Прочие задачи на аккуратную реализацию
(3 задачи)
Сортировка
(15 задач)
Двоичный поиск
(3 задачи)
Фильтр
Задачи
Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 155]
Известна легенда, что в древней Лимонии любой претендент на должность
визиря при шахе должен был выдержать следующее испытание. Ему дается
доска размером M × M и некоторое количество шахматных фигур: ферзей, ладей,
слонов, коней и королей. Претендент должен расставить их на доске таким
образом, чтобы ни одна из фигур не била другие фигуры, и все фигуры были
выставлены на доске. Если претендент выдерживал испытание, он назначался
визирем, а если не выдерживал... то не назначался. Напишите программу,
которая будет решать эту головоломку.
Входные данные
Первое число во входном файле задает размер доски M (2 ≤ M ≤ 12). Следующие 5 целых неотрицательных чисел K, Q, R, B, N задают соответственно количество королей, ферзей, ладей, слонов и коней, которые требуется расставить. Общее количество фигур не превосходит M2 . Фигуры подобраны так, что искомая расстановка существует.
Выходные данные
Вывести в выходной файл доску с расставленными фигурами в виде M строк по M символов в каждой. Пустые поля обозначаются символом . (точка), поля с королями – K, ферзями – Q, ладьями – R, слонами – B, конями – N.
Пример входного файла
4 0 0 4 0 0
Пример выходного файла
R...
..R.
...R
.R..
Арифметический ребус – это зашифрованная запись сложения двух
натуральных чисел (например, КОМП+КОМП=СБОРЫ). При этом одинаковым
буквам должны соответствовать одинаковые цифры, разным – разные, и ни
одно из чисел не может начинаться с нуля. Требуется написать программу,
находящую все возможные решения такого ребуса.
Входные данные
Входной файл содержит единственную строку с записью ребуса. Длина строки не превышает 30 символов.
Выходные данные
Первая строка выходного файла должна содержать число возможных решений ребуса, а остальные – список решений в алфавитном порядке. Каждое решение должно быть выведено не более одного раза.
Пример входного файла
ЛЕТО+ЛЕТО=ПОЛЕТ
Пример выходного файла
1
8947+8947=17894
Игра «Жизнь» является упрощенной моделью развития колонии бактерий.
Игровое поле для этой игры представляет собой прямоугольник
M × N клеток. В начальный момент времени в некоторых клетках находятся бактерии. За один
шаг игры некоторые бактерии могут погибнуть, а некоторые родиться на
свободных клетках в соответствии со следующими правилами:
1) бактерия, у которой есть не более одной соседки, погибает «от скуки»;
2) бактерия, у которой есть более трех соседок, погибает «от тесноты»;
3) на свободной клетке, у которой есть ровно три соседние бактерии, рождается новая бактерия.
Все эти правила применяются одновременно ко всем клеткам игрового поля. Клетки считаются соседними, если у них есть хотя бы одна общая точка. Напишите программу, которая:
по заданной колонии находит ее предка, то есть колонию, чьим следующим поколением она является, либо сообщает, что это невозможно;
находит колонию, у которой нет предка, и которая погибает не ранее, чем через L шагов, либо сообщает, что такой колонии не существует.
Входные данные
Если во входном файле записана матрица M × N (2 ≤ M, N ≤ 15), то программа должна решать пункт 1 задачи для колонии бактерий, задаваемой этой матрицей. Бактерии обозначаются символом *, а пустые клетки – символом . (точка). Если во входном файле заданы три числа M, N и L (2 ≤ M, N ≤ 10, 0 ≤ L ≤ 10), то программа должна решать пункт 2 для этих параметров.
Выходные данные
Если искомая колония существует, то ее следует вывести в выходной файл в формате, приведенном в описании входных данных к пункту 1. В противном случае ваша программа должна записать в выходной файл сообщение «NOT POSSIBLE».
Пример входного файла для пункта 1
...
***
...
Пример выходного файла для пункта 1
.*.
.*.
.*.
Пример входного файла для пункта 2
2 2 10
Пример выходного файла для пункта 2
*.
**
На ось Ox плоскости Oxy положили N прямоугольников. Требуется найти
координаты вершин ломаной, огибающей это множество прямоугольников
сверху (см. рис.).
Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100). Далее следуют N строк, в каждой из которых записана тройка вещественных чисел, описывающих очередной из прямоугольников. Первое из них задает абсциссу левого нижнего угла прямоугольника, а остальные два – его длину и высоту.
Выходные данные
В первую строку выходного файла выведите количество вершин искомой ломаной. Далее укажите сами вершины в порядке неубывания абсциссы. Каждая вершина задается своими координатами, записанными через пробел в отдельной строке выходного файла. Никакие два звена ломаной не должны лежать на одной прямой.
Пример входного файла
2
0 4 2
2 4 5
Пример выходного файла
6
0 0
0 2
2 2
2 5
6 5
6 0
В картинной галерее, имеющей форму N-угольника, расположено M люстр,
которые мы будем считать точечными источниками света. Точка стены галереи
называется освещенной, если из нее видна хотя бы одна из люстр.
Неосвещенным участком будем называть максимальное связное множество
точек стены галереи, ни одна из которых не освещена (участок может содержать
углы галереи). Напишите программу, определяющую все неосвещенные
участки.
Входные данные
Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 30). В каждой из следующих N строк записаны координаты очередного угла галереи. Углы перечислены в порядке обхода стены по часовой стрелке. Далее идут M строк, каждая из которых содержит координаты очередной из люстр. Все координаты являются вещественными числами и разделяются пробелом.
Выходные данные
В первую строку выходного файла выведите количество неосвещенных участков S. Каждая из следующих S строк должна содержать описание очередного из участков в виде тройки чисел, разделенных пробелом. Первые два числа определяют координаты начальной точки участка, третье – его длину. (Участок должен продолжаться на указанную длину в направлении обхода стены по часовой стрелке. Никакие два участка не должны иметь общих точек.) Числа, определяющие участок, должны быть выведены не менее чем с 3 верными значащими цифрами.
Пример входного файла
5 1
0 0
0 5
4 5
2 3
5 0
3.0 1.0
Пример выходного файла
1
1 5 5.82843
Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 155]
Задача 102925[Испытание шаха ] |
|
|
Входные данные
Первое число во входном файле задает размер доски M (2 ≤ M ≤ 12). Следующие 5 целых неотрицательных чисел K, Q, R, B, N задают соответственно количество королей, ферзей, ладей, слонов и коней, которые требуется расставить. Общее количество фигур не превосходит M2 . Фигуры подобраны так, что искомая расстановка существует.
Выходные данные
Вывести в выходной файл доску с расставленными фигурами в виде M строк по M символов в каждой. Пустые поля обозначаются символом . (точка), поля с королями – K, ферзями – Q, ладьями – R, слонами – B, конями – N.
Пример входного файла
4 0 0 4 0 0
Пример выходного файла
R...
..R.
...R
.R..
|
|
Решение |
Задача 102926[Ребус ] |
|
|
Входные данные
Входной файл содержит единственную строку с записью ребуса. Длина строки не превышает 30 символов.
Выходные данные
Первая строка выходного файла должна содержать число возможных решений ребуса, а остальные – список решений в алфавитном порядке. Каждое решение должно быть выведено не более одного раза.
Пример входного файла
ЛЕТО+ЛЕТО=ПОЛЕТ
Пример выходного файла
1
8947+8947=17894
|
|
|
Решение |
Задача 102930[Жизнь бактерий ] |
|
|
1) бактерия, у которой есть не более одной соседки, погибает «от скуки»;
2) бактерия, у которой есть более трех соседок, погибает «от тесноты»;
3) на свободной клетке, у которой есть ровно три соседние бактерии, рождается новая бактерия.
Все эти правила применяются одновременно ко всем клеткам игрового поля. Клетки считаются соседними, если у них есть хотя бы одна общая точка. Напишите программу, которая:
по заданной колонии находит ее предка, то есть колонию, чьим следующим поколением она является, либо сообщает, что это невозможно;
находит колонию, у которой нет предка, и которая погибает не ранее, чем через L шагов, либо сообщает, что такой колонии не существует.
Входные данные
Если во входном файле записана матрица M × N (2 ≤ M, N ≤ 15), то программа должна решать пункт 1 задачи для колонии бактерий, задаваемой этой матрицей. Бактерии обозначаются символом *, а пустые клетки – символом . (точка). Если во входном файле заданы три числа M, N и L (2 ≤ M, N ≤ 10, 0 ≤ L ≤ 10), то программа должна решать пункт 2 для этих параметров.
Выходные данные
Если искомая колония существует, то ее следует вывести в выходной файл в формате, приведенном в описании входных данных к пункту 1. В противном случае ваша программа должна записать в выходной файл сообщение «NOT POSSIBLE».
Пример входного файла для пункта 1
...
***
...
Пример выходного файла для пункта 1
.*.
.*.
.*.
Пример входного файла для пункта 2
2 2 10
Пример выходного файла для пункта 2
*.
**
|
|
|
Решение |
Задача 102933[Прямоугольники ] |
|
|
Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100). Далее следуют N строк, в каждой из которых записана тройка вещественных чисел, описывающих очередной из прямоугольников. Первое из них задает абсциссу левого нижнего угла прямоугольника, а остальные два – его длину и высоту.
Выходные данные
В первую строку выходного файла выведите количество вершин искомой ломаной. Далее укажите сами вершины в порядке неубывания абсциссы. Каждая вершина задается своими координатами, записанными через пробел в отдельной строке выходного файла. Никакие два звена ломаной не должны лежать на одной прямой.
Пример входного файла
2
0 4 2
2 4 5
Пример выходного файла
6
0 0
0 2
2 2
2 5
6 5
6 0
|
|
|
Решение |
Задача 102934[Картинная галерея ] |
|
|
Входные данные
Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 30). В каждой из следующих N строк записаны координаты очередного угла галереи. Углы перечислены в порядке обхода стены по часовой стрелке. Далее идут M строк, каждая из которых содержит координаты очередной из люстр. Все координаты являются вещественными числами и разделяются пробелом.
Выходные данные
В первую строку выходного файла выведите количество неосвещенных участков S. Каждая из следующих S строк должна содержать описание очередного из участков в виде тройки чисел, разделенных пробелом. Первые два числа определяют координаты начальной точки участка, третье – его длину. (Участок должен продолжаться на указанную длину в направлении обхода стены по часовой стрелке. Никакие два участка не должны иметь общих точек.) Числа, определяющие участок, должны быть выведены не менее чем с 3 верными значащими цифрами.
Пример входного файла
5 1
0 0
0 5
4 5
2 3
5 0
3.0 1.0
Пример выходного файла
1
1 5 5.82843
|
|
|
Решение |
Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 155]
