Оптимальный поиск данных

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

Пронумеруем верхнюю строку таблицы числом 0, а нижнюю - числом 1. Также пронумеруем столбцы таблицы слева направо от 0 до N -1 и обозначим через A_{i , j} идентификатор объекта, хранимого в клетке на пересечении i -й строки и j -го столбца.

Известно, что данные хранятся в таблице в определенном порядке. А именно, выполняются следующие неравенства:
1. A _{0, j} < A _{1, j} для всех j от 0 до N -1 включительно.
2. A _{0, j} < A _{0, j +1} для всех j от 0 до N -2 включительно.
3. A _{1, j} < A _{1, j +1} для всех j от 0 до N -2 включительно.

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

Общение Вашего приложения с сервером происходит следующим образом. Приложение отправляет на сервер запрос, содержащий числа i, j и X. Здесь i и j - это номера строки и столбца в таблице, а X - это идентификатор объекта, поиск которого осуществляется. В ответ сервер посылает число -1, если A_{i , j} < X; число 0, если A_{i , j} = X; число 1, если A_{i , j} > X.

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

Напишите проограмму, получающую на вход число N и возвращающую количество запросов, затрачиваемых в худшем случае на поиск одного объекта, при оптимальной организации процесса поиска.

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

Во входном файле записано единственное натуральное число N (1 ≤ N ≤ 50).

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

Выведите единственное целое число, равное минимальному количество запросов, затрачиваемых в худшем случае на поиск одного объекта в хранилище.

Пример(ы)

input.txt	output.txt
1	2

 

input.txt	output.txt
2	3

 

input.txt	output.txt
5	5

Мудрецы

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

Каждый вечер M колпаков раскрашиваются в один из K разных цветов. Таким образом, M_i колпаков раскрашены в i -й цвет (i =1... K). Мудрецам эти данные известны. Пока мудрецы спят, каждому из них на голову цепляют один из колпаков, а оставшиеся прячут. Когда мудрецы просыпаются, они садятся в круг, так чтобы каждый из них видел колпаки всех остальных, и начинают думать о цвете своего колпака. Это выглядит таким образом. Каждый мудрец пишет на листочке, знает ли он цвет своего колпака. После этого все демонстрируют свои листочки. Если кто-то написал, что знает цвет - процедура заканчивается, и все идут на завтрак. Если никто не смог определить цвет, то мудрецы начинают думать снова, операция с листочками повторяется.

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

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

Первая строка входного файла содержит целые числа N (1 ≤ N ≤ 10⁶) - количество мудрецов, M (N ≤ M ≤ 10⁶) - количество колпаков, и K (1 ≤ K ≤ 10⁶) - количество разных цветов. Вторая строка содержит K целых чисел, каждое из которых задает количество колпаков определенного цвета. Третья строка состоит из N целых чисел, которые представляют цвета колпаков каждого из мудрецов. Цвета пронумерованы от 1 до K.

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

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

Пример(ы)

input.txt	output.txt
3 5 2 3 2 1 1 2	1 2 2

 

Пояснение к примеру

Пусть в королевстве всего три мудреца, два из которых имеют белый колпак (цвет 1) и один - черный (цвет 2). При этом еще один белый и один черный колпаки спрятаны. На первом этапе никто не сможет определить цвет своего колпака. На втором этапе каждый из владельцев белого колпака будет размышлять так: Если б я имел черный колпак, то коллега, который имеет белый, догадался бы о цвете своего колпака еще на первом шаге, однако этого не произошло, поэтому мой колпак белый!. А владелец черного колпака все еще не сможет определиться. Т.е., первыми догадаются мудрецы 1 и 2 с белыми колпаками и листочки для этого будут продемонстрированы два раза.

 

Переправа

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

1. Изменить состояние части моста с заданным номером A (0 ≤ A < N). Если часть с номером A была опущена, то после нажатия кнопки она станет поднята, и наоборот, если часть с номером A была поднята, то после нажатия кнопки она станет опущена.

2. Поменять местами состояния частей моста с заданными номерами A и B (0 ≤ A < B < N). Если часть с номером A была опущена, а часть B - поднята, то после нажатия кнопки часть с номером A станет поднята, а часть с номером B - опущена. Наоборот, если часть с номером A была поднята, а часть B - опущена, то после нажатия кнопки часть с номером A станет опущена, а часть B - поднята. Если обе части A и B были одновременно подняты или опущены, то после нажатия кнопки ничего не изменится.

Чтобы герой смог перейти через мост, необходимо, чтобы все из его N частей находились в поднятом положении.

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

В первой строке входного файла записана строка из N (1 ≤ N ≤ 100) символов, каждый из которых D или U. Символ D соответствует опущенной части моста, а символ U — поднятой части. Во второй строке записано целое число M. Далее в M строках содержатся описания кнопок на пульте у героя. Кнопки, выполняющие действие первого типа описываются в виде строки, содержащией число A (0 ≤ A < N), а кнопки, выполняющие действие второго типа - в виде строки, содержащей два числа A и B (0 ≤ A < B < N). Описания всех кнопок различны.

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

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

Пример(ы)

input.txt	output.txt
UUDUD 3 2 3 4 3	3

 

input.txt	output.txt
DDDDD 6 2 4 1 4 0 1 3 0 2 0 3	11

 

input.txt	output.txt
UUDUU 0	-1

Живопись

ограничение времени на тест: 2 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

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

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

Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1 ≤ N, M ≤ 70 - высота и ширина картины, 1 ≤ w, b, g ≤ 1000 - цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W - белому.

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

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

Пример(ы)

input.txt	output.txt
3 2 3 3 2 BB WW WB	7

 

Пояснение к примеру
Необходимо перекрасить нижнюю правую черную клетку в белую.

 

Автомобилист Петя

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Недавно Петя получил водительские права, и вот он совершил первую поездку к бабушке на дачу. Выезжая из дома, он заметил, что счетчик показывает A км, а когда Петя приехал на дачу, на счетчике было B км. Петя не силен в устном счете, зато у него есть программа, которая помогла определить, сколько километров он проехал. Петя одинаково хорошо пишет на Pascal и C++, поэтому для проверки написал программы на каждом языке программирования.

var a, b: longint; begin assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output); read(a, b); writeln(b - a); close(input); close(output); end.

#include <stdio.h> int main() { int a, b; freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); scanf("%d %d", &a, &b); printf("%dn", b - a); fclose(stdin); fclose(stdout); return 0; }

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

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

В первой строке входного файла записаны два целых числа A и B (0 ≤ A < B ≤ 10000) через пробел.

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

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

Пример

Ввод

Пример 1
3000 3010

Вывод

Пример 1
3020