Темы
    Информатика(2656 задач)
---> 13 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап --> Московская областная олимпиада
    2007(7 задач)
    2008(6 задач)
Страница: 1 2 3 >> Отображать по:
#1221
Клетчатые фигуры
  

На поле, состоящем из M*N белых квадратных клеток единичного размера, некоторые клетки покрасили в чёрный цвет, в результате чего образовалось одна или несколько закрашенных фигур. Фигура называется связной, если из любой ее клетки можно

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4‑х соседних по стороне клеток. Несвязные фигуры считаются различными. Например, на данном рисунке приведены 3 фигуры. Периметр фигуры — это сумма длин ее внешних и  внутренних (при наличии) сторон. Периметр фигур, изображенных на рисунке: 28, 6 и 4. Суммарный периметр фигур равен 38.

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

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

Первая строка входных данных содержит два целых числа M и N
(0 < M , N ≤ 100) — количество строк и столбцов, из которых состоит клетчатое поле. Во второй строке находится одно число K (0 ≤ K ≤ M*N) – количество клеток, закрашенных в черный цвет.

В последующих K строках содержатся координаты закрашенных клеток в формате:

<номер строки><пробел><номер столбца>.

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

Выведите одно число — суммарный периметр всех фигур.

Примеры
Входные данные
5 5
13
1 1
1 2
1 3
2 2
2 4
3 2
3 3
3 4
4 2
4 4
5 3
5 4
5 5
Выходные данные
28
#1222
Алгоритм Евклида
  

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

1.Пусть a, b — числа, НОД которых надо найти.

2.Если b = 0, то число a — искомый НОД.

3.Если b > a, то необходимо поменять местами числа a и b.

4. Присвоить числу a значение a – b.

5.Вернуться к шагу 2.

Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Требуется написать программу, которая решает эту задачу.

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

Первая строка входных данных содержит количество наборов входных данных K (1 ≤ K ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 1018). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 1018).

Все числа в строках разделены пробелом.

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

Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры
Входные данные
2
20 10
10 10
10 7
2 4
Выходные данные
YES
NO
#1223
Авторитетное сообщество
  

На шахматный турнир в Нью-Васюках съехалось N игроков со всего света. Каждый игрок имеет свой шахматный рейтинг. Разумеется, на такой престижный турнир не допускались игроки с отрицательным рейтингом. В связи с разногласиями некоторых игроков по поводу регламента проведения матчей, после окончания турнира Председатель Шахматной Ассоциации решил собрать авторитетное сообщество шахматных игроков, для того чтобы внести изменения в регламент проведения будущих шахматных соревнований.

Авторитетность сообщества определяется суммарным рейтингом игроков, входящих в него. Но Председатель понимал, что нельзя приглашать на собрание всех игроков — иначе они увязнут в спорах, и никакого итогового решения принято не будет. Но чтобы соблюсти приличие, ему необходимо аргументировать свой выбор перед общественностью, а именно – это должно быть как можно более авторитетное (наибольшее) по рейтингу сообщество игроков. Кроме того, поскольку шахматисты — люди обидчивые, нельзя допустить и того, чтобы среди приглашенных игроков были проигравшие игроку, который приглашения не получил.

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

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

Первая строка содержит два целых числа: N (0 < N ≤ 1000) — число игроков, и M (0 < M ≤ 106) — число сыгранных на турнире партий. Следующие N строк содержат по одному целому неотрицательному числу Ai (0 < Ai ≤ 106) — рейтинг i-го игрока. Затем идет M строк с результатами партий (ничейные партии не приводятся, одни и те же игроки могли играть между собой несколько раз). Каждая строка состоит из номеров двух игроков через пробел: это значит, что в данной партии игрок, номер которого идет в строке первым, победил второго игрока. Все входные данные корректны.

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

В первой строке выведите количество игроков K (K < N) в наиболее авторитетном сообществе. В последующих K строках выведите номера игроков, входящих в это сообщество (в любом порядке, каждый игрок должен быть указан ровно один раз).

Примеры
Входные данные
2 1
1
1
1 2
Выходные данные
1
Входные данные
6 6 
1
1
1
5 
6
1
6 1
1 2
2 3
3 4
4 5
3 4
Выходные данные
9
#1224
Математическое казино
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Например, пусть Саша правильно решил первую задачу (выиграл начальную ставку в 1 мани, поставил на следующий раунд 1 мани), затем неправильно решил вторую задачу (проиграл 1 мани и удвоил ставку), неправильно решил и третью задачу (проиграл 2 мани и снова удвоил ставку), но четвертую задачку ему все-таки удалось решить правильно (выиграл 4 мани, сбросил ставку на 1 мани). Затем он правильно решает и пятую задачу (выиграл 1 мани) и заканчивает игру. Итого на его счету после игры: 1 – 1 – 2 + 4 + 1 = 3 мани.

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

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

Первая строка содержит целое число N (0 < N ≤ 2000) — количество задач, которое решал Саша. Во второй строке располагаются N чисел 0 или 1 через пробел: 0, если Саша решил очередную задачку неправильно, и 1 – если правильно.

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

Выведите одно целое число — выигрыш или проигрыш Саши (выигрыш определяется положительным числом, а проигрыш – отрицательным).

Примеры
Входные данные
5
1 1 0 1 1
Выходные данные
4
#1225
Склад
  

На роботизированном складе имеется N отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di.

Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Свободное место в пустом отсеке совпадает с его вместимостью. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.

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

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

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

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

Первая строка содержит два целых числа: N — количество отсеков, и M — количество грузов (1 ≤ N ≤ 10, 1 ≤ M ≤100). Вторая строка содержит N целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие M строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.

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

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

Возможны следующие сообщения:

put cargo X to cell Y — положить груз с номером X в отсек с номером Y;

move cargo X from cell Y to cell Z — переложить груз с номером X из отсека с номером Y в отсек с номером Z;

take cargo X from cell Y — достать груз с номером X из отсека с номером Y.

cargo X cannot be stored — если груз с номером X разместить невозможно.

Примеры
Входные данные
1 2
3
2 1 2
4 3 4
Выходные данные
put cargo 1 to cell 1
take cargo 1 from cell 1
cargo 2 cannot be stored
Страница: 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест