Задания

ЗАДАНИЯ

A - Бизнес по-русски

Максимальное время работы на одном тесте: 2 секунды

Максимальный объем используемой памяти: 64 мегабайта

Имя входного файла: input. txt

Имя выходного файла: output. txt

Каждый, кто жил в деревне знает, как дорого стоят вещи из города. И все, кто жил в городе знает, насколько дорогие вещи из деревни. Юля решила использовать эти знания, чтобы организовать серьёзный бизнес. Она начинает свой путь к успеху в каком-либо городе или в деревне, закупает там вещи по дешевке, затем едет в населённый пункт противоположного типа (в деревню, если она начала в городе, или в город, если она начала в деревне) и продаёт эти вещи там с немалой наценкой, попутно покупая новые вещи для продажи в следующем населённом пункте (снова противоположного типа) и так далее. Вскоре после убытия Юли жители начинают понимать, что она их обманула и вспоминают её различными нехорошими словами, поэтому она не может посещать один и тот же населённый пункт дважды.

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

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

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

Входной файл представляет собой строку с населёнными пунктами, которые Юля может посетить. I-ым символом строки является 'V', если это место является деревней (village), или 'C', если это город (city).

Ограничения

Входная строка содержит от 1 до 50 символов включительно. Каждый символ входной строки будет или 'V' или 'C'.

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

Целое число - максимальное количество мест, которые Юля может посетить в соответствии с описанными выше правилами.

Примеры

input. txt	output. txt
CVVVC	5
VVV	1
VVVVCVV	3
CVCVCVC	7
V	1

В первом примере решением является начать в месте 1 (деревня), затем отправиться в место 0 (город), затем в место 2 (деревня), потом в место 4 (город) и наконец в место 3 (деревня).

B - Британские учёные

Максимальное время работы на одном тесте: 2 секунды

Максимальный объем используемой памяти: 64 мегабайта

Имя входного файла: input. txt

Имя выходного файла: output. txt

Интересное исследование британских учёных гласит: "На планете Земля, в случае если в отдельно взятой комнате есть по крайней мере 23 человека, то вероятность того, что у двух из них дни рождения совпадают, больше 50%". Вам не даёт покоя слава иностранных коллег, и вы решаете придумать ещё несколько результатов исследований аналогичного содержания. Даны два целых числа (minOdds и daysInYear), ваш алгоритм должен возвращать наименьшее количество людей (с планеты, где daysInYear дней в году), необходимое, чтобы быть не менее чем на minOdds% уверенным, что у двух человек дни рождения совпадают. См. пример ниже для дополнительной информации.

У двух человек может быть один и тот же день рождения, но при этом они не обязаны были родиться в одном и том же году. Можно считать, что шансы родиться в определенный день = (1 / daysInYear). Високосных годов нет.

Тот самый «пример ниже»:

input. txt	output. txt
75 5	4

Мы должны быть на 75% уверены, что по крайней мере у двух человек в комнате дни рождения совпадают. Это равносильно тому, что шансы каждого на уникальный день рождения составляет 25% или меньше.

Если в комнате только один человек, шансы 5/5 или 100%, что дни рождения ни у кого не совпадают. Если в комнате два человека, шансы 5/5 * 4/5 = 80%, что дни рождения ни у кого не совпадают. Это потому, что у второго человека 4 "безопасных" дня (из 5 возможных дней в году), на которые может выпасть его день рождения. Если в комнате три человека, шансы дням рождения не совпасть 5/5 * 4/5 * 3/5 = 48%. Если в комнате четыре человека, шансы 5/5 * 4/5 * 3/5 * 2/5 = 19,2%. Это означает, что можно быть на (100% - 19,2%) = 80,8% уверенным, что у двух или более из них дни рождения совпадают.

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

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

Два целых числа (minOdds и daysInYear)

Ограничения

minOdds в диапазоне от 1 до 99 включительно. daysInYear в диапазоне от 1 до 10000 включительно. Для любого числа людей N, вероятность того, что у двух человек день рождения будет в один и тот же день (в комнате, где N человек, на планете с daysInYear дней в году) не будет в пределе 1e-9 minOdds. (Другими словами, в этой задаче вам не нужно беспокоиться о точности вычислений с плавающей точкой.)

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

Целое число

Примеры

input. txt	output. txt
50 365	23
1 365	4
84 9227	184

В примере 1 рассмотрен случай из условия. Если в комнате 22 человека, шансы на совпадения дней рождения примерно 47.57%. В случае же 23 человек, шансы увеличиваются до 50.73%, что больше или равно требуемым 50%.

В примере 2 дан ещё один пример с планеты Земля. Шансы на совпадения дня рождения среди всего четверых человек примерно 1.64%.

C - Побег

Максимальное время работы на одном тесте: 2 секунды

Максимальный объем используемой памяти: 32 мегабайта

Имя входного файла: input. txt

Имя выходного файла: output. txt

Вы проходите компьютерную игру, где требуется выбраться из опасной зоны. На карте есть СМЕРТЕЛЬНЫЕ области, в которые вы не можете попасть, ВРЕДНЫЕ области, которые отнимают по 1 жизни за каждый шаг в них, и ОБЫЧНЫЕ области, которые не оказывают на игрока никакого воздействия. Вы начинаете в (0,0) и должны добраться до (500,500) используя только шаги Вверх, Влево, Вправо, и Вниз. Карта будет задана массивом, содержащим СМЕРТЕЛЬНЫЕ области, и массивом, содержащим ВРЕДНЫЕ области. Элементы каждого из них будут иметь следующий формат:

Формат ввода (кавычки для ясности): "X1 Y1 X2 Y2", где

(X1, Y1) является одним углом области, и (X2, Y2) представляет собой другой угол области.

Углы областей включены в области (т. е. (4,1) и (2,2), включают значения X от 4 до 2 включительно и значения Y от 1 до 2 включительно). Все неуказанные регионы считаются ОБЫЧНЫМИ. Если области перекрываются в каком-либо квадрате, то худшая область вступает в силу (например, СМЕРТЕЛЬНАЯ + ВРЕДНАЯ = СМЕРТЕЛЬНАЯ, ВРЕДНАЯ + ОБЫЧНАЯ = ВРЕДНАЯ, ВРЕДНАЯ + ВРЕДНАЯ = ВРЕДНАЯ, СМЕРТЕЛЬНАЯ + ОБЫЧНАЯ = СМЕРТЕЛЬНАЯ).

Полученные на каждом шаге повреждения рассчитывается по вредности квадрата, куда перемещается игрок, а не по исходному (например, если квадрат (500,500) ВРЕДНЫЙ, вы получите 1 единицу повреждений; если квадрат (0,0) ВРЕДНЫЙ, вы не получите никаких повреждений уходя с него. Аналогично и для СМЕРТЕЛЬНЫХ квадратов).

Если две ВРЕДНЫХ области пересекаются, полученные повреждения остаются такими же, если бы они не пересекались (т. е. эффект не суммируется, и пересекающиеся области по-прежнему отнимают ровно 1 жизнь)

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

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

2 массива из строк по 4 числа, разделённых пустой строкой. Числа разделены пробелом

Ограничения

Первый массив (ВРЕДНЫЕ области) будет содержать от 0 до 50 элементов включительно Второй массив (СМЕРТЕЛЬНЫЕ области) будет содержать от 0 до 50 элементов включительно Каждый элемент первого или второго массива будет состоять из 4 чисел, разделённых пробелом (кавычки для ясности): "X1 Y1 X2 Y2", где X1, Y1, X2, и Y2 - целые числа в диапазоне от 0 до 500 включительно, не содержащие нули перед числом Каждый элемент первого или второго массива не будет содержать лишние пробелы, пробелы в начале или в конце

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

Целое число

Пример

input. txt	output. txt
	0
	1000
0	1000
0	-1

D - Цветник

Максимальное время работы на одном тесте: 2 секунды

Максимальный объем используемой памяти: 64 мегабайта

Имя входного файла: input. txt

Имя выходного файла: output. txt

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

Вам даны следующие массивы: «высота» (height), «цветение» (bloom), и «увядание» (wilt). Индекс элемента в массивах соответствует типу цветка. height показывает высоту цветка, bloom определяет, в какой день цветок зацветает; wilt показывает, в какой день цветок высыхает и умирает. Каждый элемент массивов bloom и wilt —число от 1 до 365 включительно, причём wilt[i] всегда больше, чем bloom[i]. Вы должны посадить все цветы одного типа в один ряд для красоты, и вы также хотите, чтобы самые высокие цветы росли как можно ближе. Однако, если цветок одного типа выше, чем цветок другого типа, и оба типа могут цвести одновременно, более высокий цветок должен быть дальше, чтобы не загораживать более низкий. Цветы расцветают утром и увядают вечером, так что даже если один цветок цветёт в тот же день, когда другой увядает, они могут загораживать друг друга.

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

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

3 строчки: height, bloom и wilt

Ограничения

height может содержать от 2 до 50 элементов включительно; bloom содержит столько же элементов, сколько height; wilt содержит столько же элементов, сколько height; height не содержит одинаковых элементов; значения элементов height — от 1 до 1000 включительно; значения элементов bloom — от 1 до 365 включительно; значения элементов wilt — от 1 до 365 включительно; wilt[i] > bloom[i] для каждого i.

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

Строка, содержащая нужную последовательность

Примеры

input. txt	output. txt
365
5
5

Пример 1 - Все цветы зацветают первого января и увядают 31-го декабря. Поскольку все они могут загораживать друг друга, нужно высадить их в порядке увеличения высоты: низкие ближе, высокие — дальше.

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

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

Пример 4 - Отличие в том, что третий тип цветка увядает на день раньше, чем зацветает четвёртый. Поэтому можно высадить цветы в порядке 3, 4, 5, 1, 2. Заметьте, что можно было бы поместить 1-й тип вперёд, но в таком случае мы бы не выполнили условие о том, что высокие цветы должны находиться как можно ближе к наблюдателю.

E - Короткий палиндром

Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Имя входного файла: input. txt
Имя выходного файла: output. txt

Палиндром — это строка, которая читается одинаково как с начала, так и с конца. Из строки base, которая может быть или не быть палиндромом, всегда можно получить палиндром, добавляя к ней буквы. Например, добавив к слову «RACE» буквы «CAR» получим «RACECAR» (кавычки использованы только для ясности). Тем не менее, мы не ограничены добавлением букв в конец слова. Например, мы могли бы также дописать буквы «ECA» перед словом и получить «ECARACE». На самом деле, мы можем добавлять буквы в любом месте слова, так что мы могли бы также получить «ERCACRE», дописав «Е» в начало, «C» после «R» и ещё одну «R» перед последним «E».

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

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

Строка, которую нужно преобразовать в палиндром

Ограничения

base содержит от 1 до 25 символов включительно; base состоит из заглавных латинских букв («A»–«Z»).

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

Строка-палиндром, полученная из исходной строки

Примеры

input. txt	output. txt
RACE	ECARACE
Q	Q
MADAMIMADAM	MADAMIMADAM
ALRCAGOEUAOEURGCOEUOOIGFA	AFLRCAGIOEOUAEOCEGRURGECOEAUOEOIGACRLFA

Пример 1 - Чтобы получить из «RACE» палиндром, нужно добавить хотя бы три буквы. Однако, добавить три буквы можно восемью различными способами:
«ECARACE» «ECRARCE» «ERACARE» «ERCACRE»
«RACECAR» «RAECEAR» «REACAER» «RECACER»
Лексикографически минимальным вариантом является «ECARACE».

F - Белка в колесе

Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Имя входного файла: input. txt
Имя выходного файла: output. txt

У бизнесмена накопилось много задач. Он относится ко всем задачам с одинаковой степенью серьёзности, поэтому ему необходимо опеределить, какую из них следует выполнить первой.

Бизнесмен записывает каждую задачу на отдельный стикер и расклеивает их на стене по окружности по часовой стрелке, так что первая задача прилегает к последней. Затем он загадывает положительное число. Это число он называет N. Начиная с первой задачи, бизнесмен движется по часовой стрелке (от 1 стикера ко 2-му и т. д.), считая от 1 до N. Когда он достигает N, то снимает стикер, на котором остановился и начинает отсчет от 1 до N со следующего. Бизнесмен повторяет эту процедуру пока не останется один стикер. Задачу, записанную на этом последнем стикере он и выбирает для выполнения.

Учитывая список представленных задач T и N, требуется вернуть задачу, с которой бизнесмен решит начать работу.

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

Две строки: первая содержит подстроки, разделённые пробелами; вторая - целое число.

Ограничения

Список содержит от 2 до 50 элементов включительно. Каждый элемент в списке содержит от 1 до 50 символов включительно. Каждый элемент в списке содержит символы от 'a' до 'z'. n будет в интервале от 1 до включительно.

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

Строка с задачей, с которой бизнесмен начнёт работу

Примеры

input. txt	output. txt
a b c d 2	a
a b c d e 3	d
alpha beta gamma delta epsilon 1	epsilon
a b 1000	a
a b c d e f g h i j k l m n o p q r s t u v w x y z 17	n
zlqamum yjsrpybmq tjllfea fxjqzznvg nvhekxr am skmazcey piklp olcqvhg dnpo bhcfc y h fj bjeoaxglt oafduixsz kmtbaxu qgcxjbfx my mlhy bt bo q 9000000	fxjqzznvg

Пример 1 - Начинаем отсчет с задачи "a": "a" – 1, "b" – 2. Снимаем задачу "b", теперь порядок стикеров на стене такой – "a c d". Продолжаем с задачи "c": "c" – 1, "d" – 2. Снимаем "d" и список превращается в "a c". Следующая задача – "a": "a" – 1, "c" – 2. Снимаем "c" и на стене остается только стикер с задачей "a".