Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#598
Маджонг
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Цель игры состоит в том, чтобы сделать как можно больше ходов.

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

Входные данные

Первая строка входного файла содержит размеры доски: два целых числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 300, хотя бы одно из этих чисел четно). Далее следуют \(m\) строк по \(n\) чисел в каждой, \(j\)-е число в \(i\)-й из этих строк представляет собой номер цвета \(j\)-й слева фишки в \(i\)-й горизонтали. Цвета пронумерованы натуральными числами от 1 до \(n\)*\(m\) / 2. На доске ровно две фишки каждого цвета.

Выходные данные

В первой строке выходного файла выведите \(k\) — максимальное количество ходов, которое может сделать Петя из заданной начальной позиции. Во второй строке выходного файла выведите разделенные пробелами \(k\) чисел — номера цветов фишек в том порядке, в котором они должны сниматься с доски. Если возможных ответов несколько, выведите любой.

Примеры
Входные данные
1 2
1 1
Выходные данные
1
1
Входные данные
4 1
1
2
2
1
Выходные данные
2
2 1
#1035
Часы с боем
  

Старинные часы бьют каждые полчаса. Причем в начале каждого часа они бьют столько раз, сколько сейчас часов (по 1 разу – в час ночи и в час дня, по 2 раза – в два часа ночи в два часа дня и т.д., в полночь и в полдень они бьют, соответственно, по 12 раз). И еще 1 раз они бьют в середине каждого часа.

Дан промежуток времени (известно, что прошло строго меньше 24 часов). Напишите программу, определяющую, сколько ударов сделали часы за это время.

Входные данные

В первой строке записан начальный момент времени, во второй строке — конечный. Моменты времени задаются двумя целыми числами, разделяющимися пробелом. Первое число задает часы (от 0 до 23), второе — минуты (от 1 до 59, при этом оно не равно 30).

Выходные данные

В выходной файл выведите одно число — сколько ударов сделали часы за этот отрезок времени.

Примеры
Входные данные
5 20
10 25
Выходные данные
45
Входные данные
10 25
5 20
Выходные данные
135
#1155
Трехмерный тетрис
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Игра в трехмерный тетрис происходит на поле, имеющем вид прямоугольного параллелепипеда размером W×D×H единичных кубиков. Введем координатную систему так, чтобы один из углов параллелепипеда находится в точке (0, 0, 0), противоположный ему – в точке (W, D, H), а ребра параллелепипеда были параллельны осям координаты. Каждый единичный кубик поля можно задать максимальными координатами его углов, тогда кубики будут иметь координаты от (1, 1, 1) до (W, D, H).

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

Игрок может сделать несколько действий с фигурой. Каждое действие является либо перемещением ее на один в направлении одной из осей координат, либо поворотом ее на 90 градусов вокруг одной из координатных осей. Один из кубиков в фигуре является базовым – при поворотах он остается на месте. При повороте фигура сначала исчезает с игрового поля, и затем появляется снова, уже в новом положении. Направления поворотов показаны на рисунке, при повороте вокруг оси OX ось OY переходит в ось OZ, при повороте вокруг оси OY ось OZ переходит в ось OX, при повороте вокруг оси OZ ось OX переходит в ось OY. Базовый кубик при повороте остается на месте.

 

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

Входные данные

В первой строке входного файла содержатся размеры игрового поля – три целых числа W, D и H (1 ≤ W, H, D ≤ 100).

Во второй строке входного файла задано целое число n – количество фигур, которые были размещены на игровом поле. (0 ≤ n ≤ 100). Каждая фигура задается следующим образом: на первой строке задано натуральное число m - количество кубиков в фигуре. (1 ≤ m ≤ 100) Далее следуют m строка, в i-й из которых содержится тройка целых чисел xi, yi, zi – координаты i-го кубика в фигуре в ее начальном положении. Базовый кубик описывается первым.

Следующая строка содержит целое число k – количество операций, которые были проведены игроком с данной фигурой (0 ≤ k ≤ 100). Далее следуют k строк. Каждая из них начинается либо со слова «shift», либо со слова «rotate».

В первом случае далее следует одна из букв «x», «y» или «z», обозначающая, вдоль какой из осей был выполнен сдвиг, после чего через пробел идет либо символ «+», если сдвиг был осуществлен в положительном направлении данной оси, либо «–», если сдвиг был осуществлен в отрицательном направлении.

Если же строка начинается со слова «rotate», то далее идет одна из букв «x», «y» или «z», обозначающая, вокруг какой из осей был выполнен поворот.

Выходные данные

Выведите в выходной файл в произвольном порядке координаты всех кубиков, которые будут заняты фигурами. На каждой строке должно содержаться три числа, разделенных пробелом – координаты кубика в формате «x y z».

Примеры
Входные данные
2 2 2
1
2
1 1 1
2 1 1
1
shift z +
Выходные данные
2 1 2
1 1 2
Входные данные
3 3 3
1
4
2 2 2
3 2 2
2 3 2
2 2 3
2
rotate y
rotate z
Выходные данные
2 2 2
2 3 2
2 2 1
1 2 2
#1206
Газон
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Входные данные

В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).

Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

Выходные данные

В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

Иллюстрация к примеру

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-21 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.

Примеры
Входные данные
0 0 5 4
4 0 3
Выходные данные
14
#1207
Трамвай
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.

Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — ai и bi. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется ai, если же он стоит, то прибавляется bi.

Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них ai < bi).

Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины ai и bi, а также номера остановок, на которых он садится и выходит из трамвая.

Входные данные

Первая строка входного файла содержит разделенные пробелом три целых числа N, M и P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно (1 ≤ N, M,  P ≤ 100 000; 2 ≤ P).

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел ai, bi, ci, di:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−106 ≤ ai, bi ≤ 106; 1 ≤ ci < di ≤ P).

Выходные данные

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

Комментарий к примеру тестов

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

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-31 — числа M, N, P не превосходят 100. Группа тестов оценивается в 60 баллов.

Тесты 32-41 — число P не превосходит 100. Группа тестов оценивается в 20 баллов (вместе с предыдущей группой — 80 баллов).

Тесты 42-51 — дополнительных ограничений нет. Группа тестов оценивается в 20 баллов (вместе с предыдущими группами — 100 баллов).

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.

Примеры
Входные данные
4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4
Выходные данные
28
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест