Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 37 38 39 40 41 42 43 >> Отображать по:
#1212
Перестановки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
K-перестановкой чисел называется такая перестановка, в которой НОД соседних чисел не меньше K. Заданы числа из которых необходимо построить N-ую перестановку в лексикографическом порядке.

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

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

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

Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

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

В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Разбалловка для личной олимпиады

Тесты 1-3 — из условия. Оцениваются в 0 баллов.

Тесты 4-17 — \(n\le 4\). Группа тестов оценивается в 28 баллов.

Тесты 18-28 — \(n\le 10\). Группа тестов оценивается в 22 балла (вместе с предыдущей группой — 50 баллов).

Тесты 29-53 — дополнительных ограничений нет. Группа тестов оценивается в 50 баллов (вместе с предыдущими группами — 100 баллов).

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

Примеры
Входные данные
4 1 2
6 8 3 9
Выходные данные
3 9 6 8
Входные данные
4 4 2
6 8 3 9
Выходные данные
9 3 6 8
Входные данные
4 5 2
6 8 3 9
Выходные данные
-1
#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
Страница: << 37 38 39 40 41 42 43 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест