Автозаправки

Задача 4.  Автозаправки

Имя входного файла:	fuel. in
Имя выходного файла:	fuel. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта
Максимальная оценка за задачу:	100 баллов

Фирма «АйОйЛ» построила на скоростном шоссе Москва-Тверь N автозаправок. Каждая автозаправка имеет свой номер, который присваивался ей при строительстве, начиная с единицы. Кроме того, каждая автозаправка располагается на определенном километре шоссе. Километры на шоссе нумеруются от 0, начиная от Москвы.

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

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

Формат входных данных

Первая строка входного файла содержит количество автозаправок N (2 ≤ N ≤ 105). Вторая строка входного файла содержит N различных целых чисел xi – километр, на котором расположена автозаправка с номером i (1 ≤ i ≤ N). Числа в строке разделены пробелом. Значения всех xi не меньше ноля и не превосходят 109 по абсолютной величине.

Формат выходных данных

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

Примеры

fuel. in	fuel. out
5 1	4

Задача 5.  Перевес багажа

Имя входного файла:	baggage. in
Имя выходного файла:	baggage. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта
Максимальная оценка за задачу:	100 баллов

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W1 + W2 + … + Wi-1 ≤ Wi

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

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

Формат входных данных

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.

Формат выходных данных

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

Примеры

baggage. in	baggage. out
4 15 5	3
3 2 1 2 4 7 6 5	5

Задача 6.  ASCII-art

Имя входного файла:	ascii. in
Имя выходного файла:	ascii. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта
Максимальная оценка за задачу:	100 баллов

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

Википедия

Флатландия – необычная страна, и искусство у флатландцев тоже необычное. Особый интерес представляют их картины. Во-первых, флатландские художники используют для написания картин только ASCII символы, во-вторых, все картины исключительно квадратные.

Пете захотелось приобщиться к искусству Флатландии, однако, он столкнулся с очень серьёзной проблемой. Дело в том, что все картины защищены законом об авторских правах и кодируются следующим образом: над картиной последовательно выполняются K операций. Каждая операция – одно из четырёх зеркальных отражений:

 

I II III IV

1.  Ось отражения – горизонтальная прямая, делящая изображение пополам. При отражении первая строка меняется местами с последней, вторая – с предпоследней и т. д.

2.  Ось отражения – вертикальная прямая, делящая изображение пополам. При отражении первый столбец меняется местами с последним, второй – с предпоследним и т. д.

3.  Ось отражения – побочная диагональ (диагональ, соединяющая правый верхний и левый нижний угол изображения). При отражении левый верхний угол меняется с правым нижним и т. д.

4.  Ось отражения – главная диагональ (диагональ, соединяющая левый верхний и правый нижний угол изображения). При отражении правый верхний угол меняется с левым нижним и т. д.

A

B

C

D

M

N

O

P

D

C

B

A

P

L

H

D

A

E

I

M

E

F

G

H

I

J

K

L

H

G

F

E

O

K

G

C

B

F

J

N

I

J

K

L

E

F

G

H

L

K

J

I

N

J

F

B

C

G

K

O

M

N

O

P

A

B

C

D

P

O

N

M

M

I

E

A

D

H

L

P

Исходное изображение Операция I Операция II Операция III Операция IV

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

Формат входных данных

В первой строке входного файла находятся два натуральных числа N и K (1 ≤ N ≤ 1000,
1 ≤ K ≤ 1000000), где N – размер картины, K – число отражений, применяемых для кодирования. Во второй строке содержатся K натуральных чисел, обозначающих номера отражений (числа могут принимать только значения 1, 2, 3 или 4).

В следующих N строках описывается само закодированное изображение. В (i+2)-й строке записана i-я строка закодированной картины. В изображении используются символы с ASCII-кодами от 32 до 126 включительно.

Формат выходных данных

В выходной файл требуется вывести раскодированное изображение.

Примеры

ascii. in	ascii. out
5 1 1 UVWXY PQRST KLMNO FGHIJ ABCDE	ABCDE FGHIJ KLMNO PQRST UVWXY
7 8 RQZQQWD MFSUWDS YODIIKO KNECWHT YRQZQQW NMFSUWD SYODIIK	DSOTWDK WDKHQWI QWIWQUI QUICZSD ZSDEQFO QFONRMY RMYKYNS
11 2 1 4 [/| || . _=~||_ _ ]\ ||||| _ \_ _/ [/__ =_ _ _=_*OO=_(_ ]\__ =_)_ _ /_ _\ [/ ||||| _=~||_ _ ]\| || .	. . ___ / ()\ _|_____|_ | | === | | |_| O |_| || O || ||__*__|| |~ \___/ ~| /=\ /=\ /=\ [_]_[_]_[_]
36 7 |||||||||||||||||||||||||||||||||| - - - - - - - - - - - & &, & - - & 7&~BM M#6 - - M 4M_M MM&g - - !#8&@ M M M_MM - - *]44Q M # M8Mj - - M MMMMM! Mj - - * * - - - - - - - - - - - - - - r g 6 - - ^ ^ ^ FMg`X M& - -^&#&$# ~ f ~ ~ _7M " B00c - -~MMMMN ~MMMMM ^ ~ M_ _ "#M&- -~ " ~]]]]M ~g # , M& _ ^ Mj- - M&8#g N "0# ^! - - "0M0 Ej - - ] _ - - - - - - - - - - - - - - - - - ||||||||||||||||||||||||||||||||||	- | j& | | MMc | | ! #0 | | j^^"0& | | _E BM6 jMg | | MM& | | __ j8_M6 | | # "X MMMM# | | 0&_ ` *! M& | | "MMMg | | 7M | | N, _F | | M#MMM, | | M _B& | | g#~~^g MMMM~ | | 0# M 4& | | ]M8 M 7& | | 0& | | "Mg r | | ~^~^ | | *MQ@M& | | MMf 4& | | ]M 48 | | ]M ]# | | ]M *! | | ]M | | ~~~ | | | | "N#^ | | M$ | | M& | | M# | | M& | | ~~^ | -