Страница: << 40 41 42 43 44 45 46 >> Отображать по:
#1217
Стеклянный забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

В первой строке задано целое число n — количество вершин в многоугольнике (4 ≤ n ≤ 100 000, n четное). В каждой из следующих n строк заданы два целых числа — координаты очередной вершины при обходе этого многоугольника против часовой стрелки. Все числа не превосходят 109 по абсолютной величине. Никакие три последовательные вершины границы не лежат на одной прямой. Граница многоугольника не содержит самопересечений и самокасаний.

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

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

Примеры
Входные данные
8
0 0
9 0
9 9
6 9
6 3
3 3
3 6
0 6
Выходные данные
6
0 0
9 0
9 9
6 9
6 6
0 6
#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
Страница: << 40 41 42 43 44 45 46 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест