Темы
    Информатика(2656 задач)
---> 30 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Муниципальный этап --> Московская область
    Очный этап(18 задач)
    Интернет этап(12 задач)
Страница: << 1 2 3 4 5 6 >> Отображать по:
#111475
Обмен королей (O)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Шахматной Стране всегда пользовались популярностью различные спортивные соревнования: ферзебол, рокировочная борьба, эндшпилевые бега. Но наибольшую популярность в этом году получила спортивная игра «обмен королей».

Суть её заключается в следующем. Двух королей (белого и чёрного) ставят на прямоугольное шахматное поле, некоторые клетки которого отмечены как недостижимые. По правилам игры короли делают ходы по очереди (сначала белый, а затем чёрный), не наступая на недостижимые клетки. Игра считается успешно законченной, если черный и белый короли поменялись местами. В соревновании побеждает та пара королей, которая смогла поменяться местами за минимальное количество ходов.

Напомним, что в шахматах король имеет право переместиться из своей клетки в любую из 8 соседних по вертикали, диагонали или горизонтали, при условии, что она не является соседней для другого короля.

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

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

В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.

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

В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.

Примеры тестов

Входные данные
4 3
*.*
W.B
...
*.*
Выходные данные
8
Входные данные
2 3
W..
..B
Выходные данные
Impossible

Примечание

Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:

#111476
Последовательность (В)
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мальчику Пете очень нравится математика. Недавно он выписал открыл новую последовательность чисел и, назвав её в свою честь, тут же записал её на длинной ленте, чтобы не забыть. Всё бы хорошо, но у Пети есть младший брат Гена. Гене не очень нравится математика - он мечтает стать дизайнером. Вот и сейчас, увидев новую красивую ленточку, он решил вырезать её часть и украсить ей свою комнату. А чтобы украшению порадовался и Петя, Гена решил вырезать такую часть, чтобы сумма всех чисел на ней была бы как можно больше.

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

В первой строке входного файла записано число n (1 ≤ n ≤ 100000) - длина последовательности Пети. Во второй строке записаны числа a1, ..., an - сама последовательность( - 109 ≤ ai ≤ 109).

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

Выходной файл должен содержать два числа - максимальную сумму, которую может получить Гена, и количество вариантов получить данную сумму.

Примеры
Входные данные
5
-1 2 3 -2 2
Выходные данные
5 2
#111477
Камера
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Коля начинающий художник. Чтобы добиться популярности, он решил увековечить некоторые свои творения на партах в своей школе.

C недавнего времени директор велел установить в каждый класс камеру, которая будет следить за такими "художниками". Но, к счастью для Коли, наблюдательные способности камеры ограничены - она не может следить за всеми партами в классе.

Помогите Коле посчитать на скольких партах он сможет изобразить свои рисунки и при этом не будет замечен камерой.

Если изобразить класс на координатной плоскости, то он будет представлять собой прямоугольник MxN с координатами (0, 0), (N, 0), (N, M), (0, M). Камера находится в точке (0,0). Каждая парта - прямоугольник 2x1. Парты расположены так, что их стороны параллельны осям координат (большая сторона парты — оси OX, меньшая — OY). Расстояние между соседними партами - 1. Расстояние между стенами и крайними партами - 1.

Область обзора камеры ограничивается тремя точками — (0, 0), (X1, Y1), (X2, Y2). Три точки образуют невырожденный треугольник — область обзора камеры. Ученик находится в поле наблюдения камеры, если в ее угол обзора попадает внутренняя часть парты, за которой он сидит.

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

В первой строке вводятся два целых числа M и N — длина и ширина класса (1 ≤ M, N ≤ 200). Во второй строке вводятся 4 целых числа - точки X1, Y1 и X2, Y2 (0 ≤ X1, X2 ≤ M, 0 ≤ Y1, Y2 ≤ N).

Гарантируется, что M = 3k + 1 и N = 2l + 1, где k и l — натуральные числа.

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

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

Примеры тестов

Входные данные
7 7
2 5 7 4
Выходные данные
3

Примечание

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

#111478
Каркассон
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Недавно Петя купил себе новую увлекательную игру. Настольная игра «Каркассон» состоит из N карточек, которые по некоторым правилам выкладываются на игровое поле.

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

Игра пользуется большой популярностью среди друзей Пети, поэтому он очень боится потерять часть карточек и периодически проверяет, все ли карточки на месте. Делает он это раз в две игры, так как уверен, что между первой и второй игрой из пары карточки потеряться не могли (то есть обе партии из пары игрались с равным, но возможно меньшим, чем N количеством карточек). Проверка происходит следующим образом: перед началом игр, зная сколько человек будут принимать участие в обеих играх и количество карточек N, Петя вычисляет, какой игрок должен сделать последний ход (как опытному программисту, знающему, что такое остаток от деления, это не составляет ему труда). Далее он записывает, какой игрок делает последний ход в каждой из игр на самом деле, и сравнивает получившиеся результаты. Если Петины расчеты не сходятся с фактическими результатами, значит обе партии игрались с меньшим, чем N количеством карточек.

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

Помогите Пете найти исправленные строки.

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

В первой строке вводятся числа N — количество карточек в игре и M (1 ≤ M ≤ 10) — количество пар сыгранных в «Каркассон» партий. Далее следуют M строк, в каждой из которых записано по 4 числа через пробел: g1 — количество игроков в первой игре из пары, r1 (1 ≤ r1 ≤ g1) — номер игрока, сделавшего последний ход в первой игре из пары, g2 — количество игроков во второй игре из пары, r2 (1 ≤ r2 ≤ g2) — номер игрока, сделавшего последний ход во второй игре из пары. Все числа во входных данных не превосходят 2 * 109.

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

Для каждой пары партий выведите «YES», если соответствующая строка исправлена и «NO» иначе.

Примеры тестов

Входные данные
100 3
2 1 3 3
8 2 4 1
8 2 4 2
Выходные данные
NO
YES
NO

Примечание

В первом случае указанный результат возможно получить, если потеряна 1 карточка, то есть если пара партий игралась с 99 карточками.

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

Ситуация, сложившаяся в третьем случае, могла получиться в результате потери 2-х карточек (играли с 98 карточками).

#111479
Секрет осьминога Пауля
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Для того, чтобы сделать точный прогноз на финальный матч, Вася очень хочет узнать, как же именно Пауль разбивает команды на группы по силе. Немного подумав, мальчик понял, что разбиение возможно восстановить по прогнозам осьминога. Для этого достаточно несколько раз задать ему вопрос вида: "Сильнее или слабее команда a чем команда b". К сожалению, Вася может задать осьминогу ограниченное число вопросов (не более 106), иначе Пауль догадается, что мальчик хочет раскрыть его секрет.

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

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

Это — интерактивная задача. На стандартный вход участнику подается единственное число N(1 ≤ N ≤ 100000) — количество команд-участников в чемпионате. Затем участник начинает "общение" с осьминогом Паулем: необходимо последовательно подавать на стандартный поток вывода запросы вида a b, где a и b - номера команд, чье соотношение сил хочет узнать Вася (числа a и b должны быть разделены ровно одним пробелом, после числа b должен быть поставлен перенос строки). В ответ на запрос на стандартный поток ввода подается одно число — либо 1, если команда a сильнее команды b, либо -1, если команда a слабее, либо 0, если осьминог не знает какая команда победит. Участник должен считать данное число и вывести следующий запрос. Если программа делает запрос, ответ на который следует из предыдущих, то она завершается и ответ считается неверным.

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

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

При выводе запросов следует пользоваться следующими фрагментами: 


{язык Pascal/Delphi}
writeln(a, ' ', b); // вывод запроса.
flush(output);

//язык C
printf("%d %d\n", a, b);
fflush(stdout);


//язык C++
cout ≤≤ a ≤≤ " " ≤≤ b ≤≤ endl ≤≤ flush;

Примеры тестов

Входные данные
3
-1
-1
Выходные данные
1 2
2 3

Примечание

Пример общения программы участника с осьминогом Паулем: 


3    число команд, поступает на вход решению 
1 2  первый запрос
-1   ответ
2 3  второй запрос
-1   ответ
0    решение говорит о том что распределение команд установлено
1    число команд в самой сильной группе
3    список команд в самой сильной группе
1    число команд в средней группе
2    список команд средней группы

Страница: << 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест