Темы
Информатика(2656 задач)
--->
61 задач
<---
#1317
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10-4.
Входные данные
Файл содержит в одной строке действительные числа X1 Y1 X2 Y2 X3 Y3, разделенные пробелами, – координаты вершин треугольника (-10000 X1, Y1, X2, Y2, X3, Y3 10000).
Выходные данные
Файл должен содержать одно число - длину L стороны искомого квадрата.
Примеры
Входные данные
0.0 0.0 1.1 0.0 0.0 1.1
Выходные данные
1.100000000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
Чтобы добраться до источника живой воды, путешественник должен пройти через лабиринт. Не всегда существует путь к источнику, но путешественник может проходить сквозь стены, используя магию. К сожалению, путешественник может использовать магию только ограниченное количество раз, а до источника необходимо добраться как можно быстрее.
Лабиринт имеет форму квадрата, который состоит из N на N квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.
В каждый момент времени путешественник может находиться в одной и только в одной клетке лабиринта.
Одним ходом считается перемещение путешественника в соседнюю по горизонтали или по вертикали клетку. Путешественник может K раз проходить сквозь стену и не может выходить за пределы лабиринта.
Составьте программу, которая вычислит минимальное количество ходов, за которое путешественник может добраться до источника с координатами (P, Q), начав путь в клетке с координатами (1, 1).
Входные данные
Входной текстовый файл в первой строке содержит числа N, K, P, Q (2≤N≤200, 0≤K≤250, 1≤P,Q≤N). Следующие N-1 строк содержат поN целых чисел — признаков наличия горизонтальных стен между клетками. Следующие N строк содержат N-1 целых чисел — признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 – присутствие.
Выходные данные
Единственная строка выходного текстового файла должна содержать найденное минимальное количество ходов, или число –1, если путь найти не удалось
Рисунок к примеру тестов
Примеры
Входные данные
3 1 2 3 0 0 0 0 1 0 1 0 1 0 0 0
Выходные данные
3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Пусть A — массив, состоящий из N элементов A1,...,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A>) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1 ≤ i ≤N. Такое преобразование массива A назовем операцией Confuse.
Напишите программу, которая по массиву B, полученному в результате K–кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).
Входные данные
Первая строка входного файла содержит целые числа N и K, где N — количество элементов массива B (2 ≤ N ≤ 10000), а K — количество применений операции Confuse к начальному массиву A, 1 ≤ K ≤ 100. Вторая строка файла содержит N элементов массиваB. Элементы массива B — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Выходные данные
Единственная строка выходного файла должна содержать целое число, которое есть разностью max(A) и min(A).
Примеры
Входные данные
3 2 5 6 7
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В спортивном турнире принимает участие N человек, с номерами от 1 до N. Турнир проходит по круговой системе: каждый участник должен сыграть с каждым другим участником по одной партии, которая заканчивается победой одного из игроков. Считается, что по окончании турнира участник занимает место P, если:
- у него выиграли (P-1) участников, и ему проиграли все остальные;
- все участники, которые победили его, выиграли свои партии у всех участников, которые ему проиграли.
Для остальных участников итоговое место определить нельзя.
Напишите программу , которая получает на вход число N и результаты сыгранных на данный момент партий турнира, и определяет количество участников, для которых по окончании турнира нельзя будет определить итоговое место, в независимости от результатов тех партий, которые еще будут сыграны.
Входные данные
В первой строке задаются два натуральных числа: N — количество участников турнира (1N100) и M — количество сыгранных партий. Следующие M строк описывают сыгранные партии. В строке задается два числа: номер победителя и номер проигравшего.
Выходные данные
В единственной строке выходного файла должно быть целое число — искомое количество участников.
Примеры
Входные данные
6 6 3 4 4 5 1 2 4 1 1 6 5 3
Выходные данные
3
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
| a | a | b | r | a | k |
| a | b | r | a | k | a |
| a | k | a | a | b | r |
| b | r | a | k | a | a |
| k | a | a | b | r | a |
| r | a | k | a | a | b |
Во время своей работы алгоритм сжатия данных методом «сортировки блока» применяет к блокам данных преобразование, которое определяется следующим образом.
Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, т.е. если S=a1a2…aN, где ai — i–ый символ строки S, то P=apap+1…aNa1…ap-1, где 1pN. Рассмотрим таблицу M размера NN, строками которой есть все ротации строки S, отсортированные в лексикографическом (словарном) порядке
по возрастанию.
Пусть строка L есть последний столбик таблицы M. Прямое преобразование получает на вход строку S, выдает строку L и число K — номер строки таблицы M, который содержит строку S. (Если таких строк несколько, выдается номер любой из них).
Для S='abraka' таблица M изображена на рисунке. Строка S находится во второй строке таблицы M, L=‘karaab’.
Напишите программу, которая выполняет обратное преобразование, т.е. получает на вход строку L и число K, и выдает строку S.
Входные данные
Первая строка входного файла содержит два целых числа: K и N, 1 ≤ N ≤30000, 1&let;K≤N. Вторая строка содержит N символов строки L — маленьких латинских букв.
Выходные данные
Единственная строка выходного файла должна содержать строку S.
Примеры
Входные данные
2 3 unn
Выходные данные
nun
Входные данные
3 7 jubcirt
Выходные данные
irtucjb
Выбрано
:
|