Страница: 1 Отображать по:
#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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест