Каталог по темам

Задачи

Страница: << 37 38 39 40 41 42 43 >> [Всего задач: 277]

Задача 102938

[Путь на параллелепипеде ]

Тема:

[

Задачи в пространстве

]

Сложность: 4

На поверхности прямоугольного параллелепипеда { (x, y, z) | 0 ≤ x ≤ L, 0 ≤ y ≤ W, 0 ≤ z ≤ H } отмечены две точки с координатами (x₁, y₁, z₁) и (x₂, y₂, z₂). Существует много путей, проходящих по поверхности параллелепипеда и соединяющих заданные точки. Требуется найти квадрат длины кратчайшего из таких путей.

Входные данные
Файл входных данных содержит (в указанном порядке) следующие 9 целых чисел: L, W, H, x₁, y₁, z₁, x₂, y₂, z₂ . Числа разделяются пробелами и/или символами перевода строки. Каждое из чисел L, W, H не превышает 100.

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

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

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

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

Задача 102940

[Вписанный, описанный и записанный ]

Тема:

[

Вычислительная геометрия (прочее)

]

Сложность: 4

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

У военных есть вполне естественное желание взорвать как можно более мощную атомную бомбу. При этом заместитель командира части по тылу настаивает, что забор полигона должен остаться целым. Тот же самый рачительный зам. по тылу хочет сэкономить как можно больше денег на электроэнергии, установив пеленгатор минимального радиуса действия, контролирующий весь полигон. Чтобы его не украли «зеленые», пеленгатор нужно установить на территории полигона. Напишите программу, определяющую минимальный радиус действия и точку установки пеленгатора, а также максимальный радиус поражения бомбы и точку ее взрыва.

Входные данные
Входной файл содержит вещественные координаты вершин N-угольника (1 ≤ N ≤ 50), записанные в порядке обхода по (или против) часовой стрелки.

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

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

Пример выходного файла
Установить пеленгатор в точке (5, 5) радиусом действия 7.0710678
Взорвать бомбу в точке (5, 5) радиусом действия 5.0000000

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

Задача 102944

[Отравленный пирог ]

Темы:	[	Динамическое программирование в игровых задачах	]
Темы:	[	Построение перечислителя	]

Сложность: 4

Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку.

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

Входные данные
Данные во входном файле расположены в следующем порядке: M, N (1 ≤ M, N ≤ 9), X₁, ..., X_M. Здесь X_i – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

Выходные данные
В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.

Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).

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

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

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

Задача 102956

[Типы данных ]

Тема:

[

Синтаксический разбор (прочее)

]

Сложность: 4

Тип данных в языке Pascal представляет собой древовидную структуру, в листьях которой записаны базовые (предопределенные) типы данных (такие, как Integer или Char), а во внутренних узлах – конструкторы, позволяющие из одних типов данных строить другие (например, Array или Record). Вершины, соответствующие листьям, называются элементами данного типа. Имеются описания типов данных, взятые из первых строк программы, написанной на языке Turbo Pascal 7.0 (см. пример входного файла), и последовательность запросов, каждый из которых касается одного из описанных типов.

Всего существует три вида запросов:
    SizeInBytes(<Имя типа>) – определить, какое количество байт памяти занимает переменная указанного типа;
    SizeInBits(<Имя типа>) – найти количество бит, необходимых для хранения переменной указанного типа при условии, что для каждого элемента этой переменной отводится минимально возможное число бит, способных закодировать все возможные значения этого элемента;
    <Имя типа>($<Последовательность 16-х цифр>) – по дампу (т.е. содержимому) участка памяти, занимаемому переменной указанного типа, определить значения всех элементов этой переменной.
Напишите программу, которая вводит описания типов данных и обрабатывает заданную последовательность запросов. Описания типов не будут содержать типов-указателей, типов-файлов, типов-объектов и процедурных типов.

Процесс разработки Вашей программы постройте по следующей схеме:
    А) Научите Вашу программу воспринимать стандартные типы данных, используемые в языке Turbo Pascal 7.0.
    Б) Введите перечислимый тип и тип-диапазон, граничные значения которого заданы константами.
    В) Реализуйте конструкторы типов данных.
    Г) Добавьте возможность использования функций и операций при построении константного выражения.
    Д) Реализуйте остальные возможности, допускаемые языком.

Входные данные
Входной файл начинается с ключевого слова «Definitions», за которым следуют описания типов данных. Далее следует ключевое слово «Queries» и список запросов. Каждый запрос записан в отдельной строке входного файла. Учтите, что длина строки с запросом может превышать 255 символов.

Выходные данные
Ваша программа должна вывести в выходной файл результаты обработки запросов в том же порядке, в котором запросы встречаются во входном файле.
На запрос первого или второго вида в отдельную строку выходного файла следует выдать сообщение «Type <Имя типа> requires x bytes/bits», где
x – искомое целое число. На запрос третьего вида необходимо перечислить значения всех элементов переменной указанного типа в том порядке, в котором эти элементы хранятся в оперативной памяти. Для каждого из элементов в отдельную строку выходного файла следует выдать строку «<Имя элемента> = <Значение>». Формат выходного файла должен соответствовать приведенному ниже примеру.

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

Definitions

Type TClass = 1..11;
TScore = 0..100;
TTour = 1..10;
TStrange =
Array [1..SizeOf(Input)
Div Ord('A')]
Of Boolean;
TExample =
Record a :
Array [1..2]
Of
Record b,c :
Set
Of 0..2
End

End ;
TShortStr =
String [3];

Type TParticipant =
Record
Sex : (Male, Female);
Name :
String [20];
Class : TClass;
Place : ShortInt;
TotalSum : 0..High(TScore)*(High(TTour)-Low(TTour)+1);
DayScores :
Array [TTour]
Of TScore;

End ;

{ Команда России для участия в международной олимпиаде }
TTeam =
Array [1..5]
Of TParticipant;

Queries
SizeInBytes(TStrange)
SizeInBits(TClass)
SizeInBits(TShortStr)
TParticipant( $ 01118AAEABECE6AEA2A02091A2A5E2ABA0ADA00000000A0B4501461D082319501C280A00 )
TExample( $01020304 )
SizeInBits(TParticipant)

Пример выходного файла
Type TStrange requires 3 bytes
Type TClass requires 4 bits
Type TShortStr requires 26 bits
Sex = Female
Name = 'Кольцова Светлана'
Class = 10
Place = 11
TotalSum = 325
DayScores[1] = 70
DayScores[2] = 29
DayScores[3] = 8
DayScores[4] = 35
DayScores[5] = 25
DayScores[6] = 80
DayScores[7] = 28
DayScores[8] = 40
DayScores[9] = 10
DayScores[10] = 0
a[1].b = [0]
a[1].c = [1]
a[2].b = [0,1]
a[2].c = [2]
Type TParticipant requires 258 bits

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

Задача 102941

[Маятник ]

Тема:

[

Выпуклая оболочка

]

Сложность: 4+

Рассмотрим математический маятник, прикрепленный к началу координат математической нитью. Начальное положение маятника (-r, 0). Если маятник отпустить, то он начнет колебаться, описывая полуокружность. Теперь представим себе, что в плоскость вбито несколько математических гвоздиков. Движение маятника в этом случае будет более сложным, но, в конце концов, он также начнет совершать некоторые периодические колебания.

Для нашего идеального математического мира считаются выполненными следующие условия:
    гвоздики и нить имеют нулевую толщину;
    энергия маятника не теряется (т.е. трение отсутствует);
    маятник никогда не сталкивается с гвоздиками (с ними входит в соприкосновение только нить);
    нить изгибается только при соприкосновении с гвоздиком.

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

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

Входные данные
В первой строке входного файла записаны целое число N – количество гвоздиков (0 ≤ N ≤ 500) и вещественное число r – длина нити. В каждой из следующих N строк через пробел указаны координаты одного из гвоздиков.

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

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

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

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

Страница: << 37 38 39 40 41 42 43 >> [Всего задач: 277]