Темы
    Информатика(2656 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 10 11 12 13 14 15 16 >> Отображать по:
#1216
Школа танцев
  

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

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

В первой строке задано число n (1 ≤ n ≤ 106). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику).

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

В единственной строке должно содержаться единственное число — количество вариантов выбора требуемой группы.

Система оценки

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

  1. Тест 1. Тест из условия, оценивается в 0 баллов.
  2. Тесты 2–8. \(N \le 101\), оцениваются в 30 баллов.
  3. Тесты 9–14. \(N \le 6\,000\), оцениваются в 30 баллов.
  4. Тесты 15–20. Дополнительных ограничений нет, оцениваются в 40 баллов.

Примеры
Входные данные
8
aabbaabb
Выходные данные
10
#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
Страница: << 10 11 12 13 14 15 16 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест