Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
главы:
-
глава 1. Динамическое программирование
(14 задач)
глава 2. Перебор с возвратом
(10 задач)
глава 3. Алгоритмы на графах
(17 задач)
глава 4. Вычислительная геометрия
(12 задач)
глава 5. Комбинаторные алгоритмы
(3 задачи)
глава 6. Задачи на разные темы
(12 задач)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с левым уклоном и левыми рейсами. Для этого он запретил водителям выполнять левые повороты, установив штраф за каждый такой поворот в размере одного миллиона (разворот на 180o поворотом налево не считается). От тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему тотальной слежки, которая следит за каждым автомобилем, записывая его координаты каждый раз, когда тот меняет направление движения (включая начальную и конечную точки пути).
Решение
Убрать все задачи
Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с левым уклоном и левыми рейсами. Для этого он запретил водителям выполнять левые повороты, установив штраф за каждый такой поворот в размере одного миллиона (разворот на 180o поворотом налево не считается). От тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему тотальной слежки, которая следит за каждым автомобилем, записывая его координаты каждый раз, когда тот меняет направление движения (включая начальную и конечную точки пути).
Требуется написать программу, вычисляющую по записанной
последовательности координат автомобиля штраф, который должен быть
взыскан с водителя.
Входные данные
В первой строке входного файла содержится целое число N – количество
записанных пар координат (1 ≤ N ≤ 1000). В каждой из следующих N строк
записана очередная из этих пар.
Выходные данные
Выведите в выходной файл суммарный штраф водителя в миллионах.
Пример входного файла
4
0 0
1 0
1 1
2 1
Пример выходного файла
1
Решение
Задачи
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 67]
Известна легенда, что в древней Лимонии любой претендент на должность
визиря при шахе должен был выдержать следующее испытание. Ему дается
доска размером 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
*.
**
Новый градоначальник города Глупова решил с целью пополнения бюджета и
экономии горючего провести кампанию борьбы с левым уклоном и левыми
рейсами. Для этого он запретил водителям выполнять левые повороты,
установив штраф за каждый такой поворот в размере одного миллиона
(разворот на 180o поворотом налево не считается).
От тяжелого прошлого Глупову достались улицы, которые могут
пересекаться под любыми углами. Градоначальник приказал установить
компьютерную систему тотальной слежки, которая следит за каждым
автомобилем, записывая его координаты каждый раз, когда тот меняет
направление движения (включая начальную и конечную точки пути).
K членов Жюри Десятой Всероссийской олимпиады школьников по
информатике решили отметить столь круглую годовщину в одном из лучших
ресторанов на Невском проспекте. На десерт вниманию Жюри предложили
торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в
основании. Жюри вооружается десертными ножами и собирается справедливо
разделить торт на K частей равного объема. Ножами можно проводить прямые
вертикальные разрезы от одной границы торта до другой; различные разрезы
могут иметь общие точки лишь в своих концевых вершинах.
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 67]
Задача 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
*.
**
|
|
|
Решение |
Задача 102931[Сумма штрафа ] |
|
|
Требуется написать программу, вычисляющую по записанной
последовательности координат автомобиля штраф, который должен быть
взыскан с водителя.
Входные данные
В первой строке входного файла содержится целое число N – количество
записанных пар координат (1 ≤ N ≤ 1000). В каждой из следующих N строк
записана очередная из этих пар.
Выходные данные
Выведите в выходной файл суммарный штраф водителя в миллионах.
Пример входного файла
4
0 0
1 0
1 1
2 1
Пример выходного файла
1
|
|
|
Решение |
Задача 102932[Торт для Жюри ] |
|
|
Напишите программу, помогающую членам Жюри построить требуемые
K-1 разрезов.
Входные данные
В первой строке входного файла содержатся два целых числа K и N
(1 ≤ K, N ≤ 50). Далее следуют N пар вещественных чисел – координаты
последовательно расположенных вершин N-угольника.
Выходные данные
Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой
чисел – координатами своих концов. Все числа должны быть разделены
пробелами и/или символами перевода строки.
Пример входного файла
4 3
2 1
0 0.5
4 0.5
Пример выходного файла
2 1 1 0.5
2 1 2 0.5
2 1 3 0.5
|
|
|
Решение |
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 67]
