Страница: 1 2 3 4 5 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Из множества всех натуральных чисел от $1$ до $N$ требуется выделить такое подмножество, чтобы в нем не было бы никаких двух чисел, отличающихся ровно в два раза (то есть если некоторое число $X$ входит в это подмножество, то число $2X$ заведомо в него не входит).

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

Например, для $N=8$ ответ $5$, подмножество может быть таким: $1, 3, 4, 5, 7$.

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

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

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

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

Примеры
Входные данные
8
Выходные данные
5
Входные данные
50
Выходные данные
33
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

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

В этом графе вычислили длины кратчайших путей между всеми парами вершин и записали их в виде таблицы. В этой таблице число на пересечении $i$-ой строки $j$-ого столбца равно длине кратчайшего пути из вершины номер $i$ в вершину номер $j$.

После этого исходный граф был утерян.

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

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

Вводятся числа $N$ и $M$, а затем таблица кратчайших расстояний ($1 ≤ N ≤ 300, 0 ≤ M ≤ 1000$, элементы таблицы кратчайших путей — целые неотрицательные числа, не превышающие $10^6$).

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

Если такой граф существует, выведите в первой строке сообщение YES, в противном случае — сообщение NO. Если граф существует, то начиная со второй строки выведите $M$ троек чисел, описывающих ребра. Каждое ребро описывается номерами вершин, которые оно соединяет, и весом. Веса всех ребер не должны превышать $10^6$.

Примеры
Входные данные
4 4
0 1 2 5
1 0 3 4
2 3 0 7
5 4 7 0
Выходные данные
YES
1 2 1
1 3 2
2 4 4
1 4 5
Входные данные
3 2
0 1 1
1 0 1
1 1 0
Выходные данные
NO
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Петя занимается разведением дракончиков. У него есть $M$ зеленых дракончиков и $K$ желтых. У Пети есть $N$ двухместных аквариумов для дракончиков и $M+K–2N$ одноместных.

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

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

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

Вводятся числа $M, K, N$ ($M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200$). Будем считать, что зеленые дракончики пронумерованы числами от $1$ до $M$, а желтые – числами от $M+1$ до $M+K$.

Далее идет число $T$ ($0 ≤ T ≤ MK$) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет $T$ пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число $Q$ ($0 ≤ Q ≤ M + K$)– количество дракончиков, не переносящих одиночества. Далее идет $Q$ чисел, задающих номера этих драконов.

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

В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие $N$ строк выведите $N$ пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.

Примеры
Входные данные
2 1 1
1
1 3
1
1
Выходные данные
NO
Входные данные
2 2 1
1
1 3
1
2
Выходные данные
YES
2 4
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вася увлекается изобретением новых последовательностей и их исследованием. В этот раз он выписал на доске последовательность:

1 2 3 2 3 4 3 4 5 4 5 6 5 6 7...
После этого Вася задался вопросом, на каком месте в ней впервые встретится число $k$?

Напишите программу, которая ответит на его вопрос.

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

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

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

Выведите одно число – искомую позицию, на которой первый раз встретилось число $k$. Члены последовательности нумеруются с единицы.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
2
Входные данные
4
Выходные данные
6
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Теперь он ломает голову над загадкой – сколько всего сотрудников работает в этом офисе. Напишите программу, которая ответит Васе на этот вопрос.

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

Вводится 31 целое неотрицательное число. Эти числа описывают количество работников, пришедших в офис в соответствующие дни месяца. Гарантируется, что входные данные корректны.

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

Выведите единственное число – общее количество работников офиса. Гарантируется, что ответ не превышает 100.

Примеры
Входные данные
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0
Выходные данные
10

Страница: 1 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест