Темы
    Информатика(2656 задач)
---> 246 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
#861
Медиана объединений
  

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

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

Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x1, d1, a, c, m. Элементы последовательности вычисляются по следующим формулам: x1 нам задано, а для всех i от 2 до L: xi = xi–1+di–1. Последовательность di определяется следующим образом: d1 нам задано, а для i≥2 di=((a*di–1+c) mod m), где mod – операция получения остатка от деления (a*di–1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 109.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример

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

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

Комментарии

3 6

1 3 1 0 5

0 2 1 1 100

1 6 8 5 11

7

10

9

Последовательности, объединения которых мы считаем, таковы:

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
#862
Перекраска N-угольника
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.

Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.

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

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

Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.

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

Выведите минимальное число действий, необходимое для того, чтобы перекрасить весь N-угольник и все его диагонали. Если перекрасить многоугольник указанным способом невозможно, выведите одно число –1 (минус один).

Примеры

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

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

3

–1

4

1 3

1
#863
Заполните массив
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

Напишите программу, которая для заданного N вычислит количество способов такого заполнения массива.

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

Вводится одно натуральное число N (1≤N≤60000).

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

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

Пример

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

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

Комментарии

2

1

Массив можно заполнить единственным способом:

3 2
#864
Медиана объединений
  
Дано N последовательностей. Требуется для каждой пары последовательностей найти медиану объединения этих последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

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

Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример 

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

3 6

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
	

	

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

7

10

9
#865
Свинки-копилки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан ориентированный граф, в котором у каждой вершины существует ровно одно исходящее ребро. Требуется найти количество циклов в нем.

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

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

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

В первой строке содержится число N — количество свинок-копилок (1≤N≤100). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

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

Пример

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

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

Комментарий

4

2

1

2

4

2

Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест