Каталог по источникам

Задачи

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 67]

Задача 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

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

Задача 102947

[Острова ]

Тема:

[

Неопределено

]

Сложность: 4

Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные
В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

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

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

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

Задача 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

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

Задача 102948

[Микрофония ]

Тема:

[

Конечные автоматы

]

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

В драматическом театре им. Пушкина к юбилею Александра Сергеевича решили поставить оперу «Евгений Онегин». Артисты театра обладают красивыми, но не очень сильными голосами. По этой причине руководство театра дало указание приобрести радиомикрофоны. В начале и в конце спектакля все артисты находятся за кулисами. Артисты выходят на сцену и покидают ее через правую или левую кулису. Для того, чтобы петь на сцене, артист берет с собой один микрофон. Артист может выходить на сцену с микрофоном (одним), даже если ему не надо петь в этом выходе. Взяв микрофон, артист не может оставить его на сцене или передать другому артисту. При уходе артиста за кулисы микрофон остается за соответствующей кулисой до тех пор, пока его снова не возьмет какой-либо артист, выходящий на сцену.

Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе.

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

Входные данные
Первая строка входного файла содержит целое число N – количество артистов, участвующих в спектакле (1 ≤ N ≤ 1000). Во второй строке записано целое число K – количество выходов артистов на сцену (1 ≤ K ≤ 3000). Далее идут 2K строк, описывающих режиссерский план спектакля. Каждая из них содержит четверку A_iB_iC_iD_i (1 ≤ i ≤ 2K):
A_i – символ +, если в данный момент артист выходит на сцену, или символ -, если артист со сцены уходит;
B_i – номер артиста (целое число от 1 до N);
C_i – символ Л, если артист выходит (уходит) через левые кулисы, или символ П, если он выходит (уходит) через правые кулисы;
D_i – символ Д, если артист поет в данном выходе (пел перед данным уходом), или символ Н, если он не поет (не пел).

Выходные данные
Первая строка выходного файла должна содержать два целых числа. Первое число – количество микрофонов перед началом оперы с левой стороны, второе число – количество микрофонов с правой стороны. В каждой из последующих K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой микрофон очередной выходящий на сцену артист (1 - берет, 0 - не берет).

Пример входного файла
3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н

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

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

Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 67]