Информатика

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

 

Формат входных данных
В первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер. Далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).

 

Формат выходных данных
Выведите матрицу смежности заданного графа.

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

 

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – размер матрицы. Затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.

 

Формат выходных данных
Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

 

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – количество вершин графа. Затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.

 

Формат выходных данных
Выведите  «YES», если граф содержит петли, и «NO» в противном случае.

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

 

Входные данные: Вводится список целых чисел. Все числа списка находятся на одной строке. Всего чисел не более 100000.

Выходные данные: Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные
1	1 2 3 2 1	3

 

Напишите программу, которая будет выполнять последовательность запросов вида ADD num, PRESENT num и COUNT (без параметра). Программу обязательно следует писать с использованием шаблонного типа set.

 

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

 

При выполнении каждого запроса вида PRESENT num должно выдаваться сообщение «YES» или «NO» (большими буквами, в отдельной строке), соответственно тому, есть ли такой элемент во множестве; значение множества при этом не изменяется.

 

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

 

В первой строке стандартного входного потока задано количество запросов N (1 < N < 100000), далее следуют N строк, каждая из которых содержит по одному запросу согласно описанного формата.

 

Значения чисел не превышают по модулю 100000000.

 

Выводите на стандартный выход (экран) в отдельных строках результаты запросов PRESENT и COUNT; на запросы ADD ничего выводить не надо.

 

Примеры

№	Входные данные	Выходные данные
1	7 ADD 5 ADD 7 COUNT PRESENT 3 PRESENT 5 ADD 3 COUNT	2 NO YES 3

Дано N отрезков провода длиной L₁, L₂, ..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

 

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= L_i <= 10 000 000, все числа целые.

Программа должна работать быстрее, чем за линейный поиск

 

В первой строке находятся числа N и К. В следующих N строках - L₁, L₂, ..., L_N, по одному числу в строке.

 

Вывести одно число - полученную длину отрезков.
 

Дан набор гирь массой m­1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

 

- в первой строке вводится натуральное число N, не превышающее 100;

- во второе строке вводятся N натуральных чисел mi, не превышающих 100.

 

Выходные данные: выведите YES или NO.

Дано N предметов массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

 

- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второе строке вводятся N натуральных чисел mi, не превышающих 100.

 

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

Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

 

Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел mi, не превышающих 100.

 

Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. 

Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

 

Входные данные: 
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел mi, не превышающих 100;

- в третьей строке вводятся N натуральных чисел сi, не превышающих 100.

 

Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).

Требуется найти в связном графе остовное дерево минимально веса.

 

Первая строка входного файла содержит два натуральных числа n и m - количество вершин и ребер графа соответственно (1≤n≤20000, 0≤m≤100000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (1≤bi,ei≤n, 0≤wi≤100000).

 

Граф является связным.

 

Выведите единственное целое число - вес минимального остовного дерева.
 

Ввод	Вывод
4 4 1 2 1 2 3 2 3 4 5 4 1 4	7

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

 

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

 

Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.

 

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

Ввод	Вывод
4 5 1 2 1 3 2 3 3 4 4 1	4

 

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

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

голосов избирателей. Известны случаи (например, в 2016 году), когда из-за такой непрямой избирательной системы в выборах побеждал кандидат, за которого проголосовало меньше избирателей, чем за другого кандидата, проигравшего выборы. 

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

Программа получает на вход два целых числа N и K (1 ≤ N ≤ 10³ , 1 ≤ K ≤ 10⁶ ) и должна вывести одно целое число – искомое количество избирателей.

Ввод	Вывод	Примечание
5 3	6	Чтобы данный кандидат получил большинство в коллегии выборщиков, необходимо, чтобы 3 из 5 выборщиков проголосовали за него, то есть кандидат должен одержать победу в 3 округах. Каждый округ состоит из 3 избирателей, поэтому для победы в округе необходимо набрать 2 голоса в данном округе.

Дима – программист, поэтому на его компьютере всегда открыто много окон. Так как у Димы не очень большой монитор, на нём может отображаться только одно окно. В каждый момент времени оконный менеджер хранит список открытых окон, первое окно списка отображается на мониторе. Для переключения окон Дима использует сочетание клавиш Alt + Tab. Если удерживать эту кнопку нажатой в течение T секунд, то. T + первое по счёту окно в текущей нумерации переместится на первую позицию, а относительный порядок остальных окон не изменится. 

Например, на рисунке ниже показано, что произойдёт с порядком окон, если нажимать на Alt + Tab в течение 3 секунд. Если держать Alt + Tab N – 1 секунду, то первым станет последнее окно из списка. Список открытых окон «зациклен», за последним окном следует первое окно из списка, т. е. если удерживать Alt + Tab нажатым N секунд, то окно, которое было первым в списке, останется на первом месте.

Если удерживать Alt + Tab N + 1 секунду, на первое место переместится второе по счёту окно и т.д.

В начале рабочего дня любимая среда разработки Димы имела номер M в списке открытых окон. В течение дня Дима K раз использовал сочетание клавиш Alt + Tab. Определите, на какой позиции находится его любимая среда разработки в конце дня.

Входные данные:
Первая строка входных данных содержит целое число N, \(1 <= N <= 10^5\) – количество окон на экране.
Вторая строка содержит целое число M, \(1 <= M <= N \)– номер, который имела любимая среда разработки Димы в начале дня.
Третья строка содержит целое число K, \(1 <= K <= 10^5\) – количество раз, которое Дима нажимал Alt + Tab. В последующих K строках содержатся целые положительные числа, не превосходящие 10⁵  – длительность каждого нажатия в секундах.
Выходные данные:

Как известно, комета Бармалея видна с Земли каждые C лет. Любопытно, что это происходит в годы, кратные C, т.е. C, 2×C, 3×C и т.д. Не каждому суждено увидеть эту комету хотя бы однажды в жизни. Впрочем, находятся счастливые долгожители, заставшие её прилёт даже несколько раз.

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

Бармалео Бармалей родился 1 января в год A и умер 31 декабря в год B. Сколько раз за его жизнь комета была видна с Земли? Мы считаем, что он мог видеть комету, даже будучи младенцем или глубоким стариком, т.е. если она прилетала в год A или B.

Программа получает на вход три целых числа A, B и C (1 ≤ A ≤ B ≤ 2×10⁹ , 1 ≤ C ≤ 2×10⁹ ) и должна вывести одно целое число – количество раз, которое комета была

видна между годами A и B включительно.

Ввод	Вывод	Примечание
1850 1900 50	2	Комета пролетала около Земли в 1850 и 1900 годах. Бармалео Бармалей застал оба раза.