Темы
    Информатика(2656 задач)
---> 12 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Муниципальный этап --> Московская область --> Интернет этап
    2010(4 задач)
    2011(4 задач)
    2013(4 задач)
Страница: << 1 2 3 >> Отображать по:
#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    список команд средней группы

#111991
Волшебный квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

На день рождения Егору подарили волшебный квадрат.

Волшебный квадрат — это таблица 3 × 3, в каждой из ячеек которой находятся числа от 0 до 9. Егор придумал следующую игру с волшебным квадратом: он загадывает число N и пытается так поставить числа в каждую ячейку квадрата, чтобы сумма чисел в каждой строке и каждом столбце была равна в точности N.

Пусть расстановка — это волшебный квадрат, заполненный числами. Тогда расстановки A и B считаются различными, если хотя бы для каких-то строки x и столбца y выполняется неравенство Ax, y ≠ Bx, y, где Ax, y и Bx, y — это числа, находящиеся в строке x и столбце y в расстановках A и B соответственно.

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

Напишите программу, которая поможет ответить на вопрос Егора.

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

Единственная строка входных данных содержит целое число N (0 ≤ N ≤ 109).

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

Требуется вывести одно число — искомое количество расстановок.

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

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

Примечание

В примере из условия существует всего одна допустимая расстановка — это таблица 3 × 3, состоящая из нулей. Очевидно, что сумма элементов в любой строке или столбце в такой расстановке равна 0.

#111992
Олимпийский огонь — 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из N этапов, каждый длиной ai километров (1 ≤ i ≤ N). У организаторов имеется бесконечное количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении K километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.

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

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

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

В первой строке заданы 3 натуральных числа N, M и K (N ≤ 106, M ≤ 10, K ≤ 108).

Во второй строке заданы N натуральных чисел ai (ai ≤ 109).

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

В первой строке выведите одно натуральное число F — на сколько можно максимально сократить количество используемых факелов на протяжении всей эстафеты.

Во второй строке выведите одно натуральное число P — количество групп объединённых этапов.

Затем в P строках выведите сами группы — по 2 натуральных числа si и ci, где si — номер первого этапа в группе, а ci — количество этапов в группе. Все si должны идти в порядке возрастания, а ci не превосходить M. Если существует несколько оптимальных решений, разрешается вывести любое.

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

Входные данные
5 3 3
1 1 1 3 3
Выходные данные
2
1
1 3
Входные данные
6 3 3
1 1 1 1 1 1
Выходные данные
4
2
1 3
4 3
Входные данные
5 5 2
2 4 6 8 10
Выходные данные
0
0

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