Темы
    Информатика(2656 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
#1152
Информатизация садоводства
  

Дачный участок Степана Петровича имеет форму прямоугольника размером a × b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.

Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.

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


грядка №1



дом

сарай

грядка №2


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

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

В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2).

Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000).

Далее следуют n строк, каждая из которых содержит четыре целых числа xi,1 , yi,1, xi,2, yi,2 –координаты двух противоположных углов постройки (0 xi,1 < xi,2 a, 0 yi,1 < yi,2   b). Различные постройки не могут пересекаться, но могут касаться друг друга.

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

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

В случае, если в вашем решении Степану Петровичу следует расположить менее m грядок, необходимо вывести для грядок, которые не следует сажать, строку «0 0 0 0» (см. второй пример ниже).

Примеры
Входные данные
2 2
7 5
4 2 6 4
0 1 2 2
Выходные данные
0 2 4 5
2 0 7 2
Входные данные
3 2
4 4
0 0 4 1
0 1 1 4
3 1 4 4
Выходные данные
1 1 3 4
0 0 0 0
#1153
Две строки
  

Циклическим сдвигом строки s0s1…sn-1 на k позиций назовем строку sksk+1…sns1..sk-1. Например, циклическим сдвигом строки «abcde» на две позиции является строка «cdeab». В этой задаче далее будут рассматриваться только строки, состоящие из десятичных цифр от 0 до 9. Произвольной такой строке, первый символ которой не является нулем, можно сопоставить число, десятичной записью которого она является. Строкам, которые начинаются с нуля, никакое число сопоставляться не будет. Например, строке 123 сопоставляется число сто двадцать три, а строке 0123 не сопоставляется никакое число.

Пусть заданы две строки: s и t. Обозначим как S набор всех циклических сдвигов строки s, а как T – набор всех циклических сдвигов строки t. Например, если s = «1234», то S содержит строки «1234», «2341», «3412», «4123». Обозначим также как NUM(A) набор чисел, соответствующих строкам из набора  A.

Требуется написать программу, которая по строкам s и t определит, максимальное число, представимое в виде разности (x – y), где x принадлежит NUM(S), а y принадлежит NUM(T). Например, если s = «25», t = «12», то NUM(S) содержит числа 25 и 52, NUM(T) – числа 12 и 21; их попарными разностями будут: 25 – 12 = 13, 25 – 21 = 4, 52 – 12 = 40, 52 – 21 = 31. Из этих разностей максимальным числом является 40.

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

Первая строка входного файла содержит строку s, вторая строка входного файла – строку t. Обе строки непустые. Они содержат только цифры, из которых хотя бы одна не является нулем. Строки имеют длину не более 3000 символов.

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

В выходной файл выведите искомое число без ведущих нулей.

Примеры
Входные данные
25
12
Выходные данные
40
Входные данные
100
1
Выходные данные
99
#1154
Скользящая симметрия
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Движением плоскости называют такое преобразование плоскости, которое сохраняет попарные расстояния между точками, то есть если A1 и B1 – образы некоторых точек A и B при движении, то |A1B1| = |AB|.

Одной из разновидностей движения плоскости является скользящая симметрия. Скользящей симметрией называют композицию симметрии относительно некоторой прямой l и переноса на вектор, параллельный l (этот вектор может быть нулевым). На рисунке показан пример применения скользящей симметрии к отрезку.

 

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

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

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

В первой строке входного файла находятся четыре целых числа – координаты двух различных точек A и В. Во второй строке также находятся четыре целых числа – координаты двух различных точек A1 и В1. Гарантируется, что |A1B1| = |AB|. Все числа во входном файле по модулю не превышают 1000. Числа в строках разделены пробелом.

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

Выведите в выходной файл описание искомой скользящей симметрии, которое представляется в следующем виде.

В первой строке должны выводиться координаты двух различных точек, лежащих на прямой l, относительно которой выполняется симметрия, а во второй – координаты вектора, параллельного этой прямой, на который осуществляется перенос. Вещественные числа должны быть представлены не менее чем с 6 знаками после десятичной точки.

Примеры
Входные данные
1 1 3 2
-1 1 -3 2
Выходные данные
0.000000 0.000000 0.000000 1.000000
0.000000 0.000000
Входные данные
1 1 3 1
3 -1 5 -1
Выходные данные
0.000000 0.000000 1.000000 0.000000
2.000000 0.000000
#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
#1178
Оплата интернета
  

Витя подключен к интернет по следующему тарифному плану. Ежемесячная абонентская плата составляет A рублей, и в эту абонентскую плату включено B мегабайт трафика. Неизрасходованные мегабайты в конце месяца «сгорают». Если трафик превышает B мегабайт, то каждый мегабайт трафика сверх предоплаченных стоит C рублей.

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

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

Вводятся четыре натуральных числа A, B, C, D. Все числа не превышают 100.

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

Выведите одно число — сумму (в рублях), которую Витя должен заплатить за интернет.

Примеры
Входные данные
100 10 12 15
Выходные данные
160
Входные данные
100 10 12 1
Выходные данные
100
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест