Информатика

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

 

Формат входных данных
В первой строке задаются числа 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» в противном случае.

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

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

Формат входных данных

Вводится одно число N: 1 ≤ N ≤ 2*10⁹

Выводится одно число – количество секунд.

Ввод	Ввод
2	2

(с) Ковешников М., 2018 г.

Жил дотер по имени Ануфрий. И вдруг случилось так, что его заботливая мама отрубила ему интернет. И как назло на компьютере Ануфрия была всего одна офлайновая игра – Minecraft.

 

Во время увлекатейнешего разрушения своего разума мальчик не знал что в этой версии игры надо думать о еде. И тут ему пришла интереснейшая мысль насчет своей еды: так как у него был только торт(как ни странно он круглый), каким образом он может получить максимальное количество кусков торта при разрезаний n. Но так как, как типичный игрок в Dota 2, Ануфрий не отличался сообразительностью. HELP HIM!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

Гарантируется, что меч, которым он режет торт, прямой. Так как Ануфрий не учит математику, а играет в доту, то не гарантируется n – натуральное(если такое произошло то выведите смайлик «

 

-1»).

 

На вход подается n.

 

На выходе вы должны вывести ответ на задачу)))

Ввод	Вывод
-2	-1
0	0
3	7

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

 

Входные данные: Вводится список целых чисел. Все числа списка находятся на одной строке. Всего чисел не более 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

 

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

 

Входные данные: 
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке  - N чисел P1, P2, ..., PN;
- в четвертой строке - число M;
- в пятой строке - M чисел Q1, Q2, ..., QM.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

 

Выходные данные: если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинала покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.

Если они не могут рассчитаться, выведите строку Impossible.

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка – волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.

 

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

В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D – количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений: 1 ≤ N ≤ 10000, 1 ≤ D ≤ 100 (для каждого D), D ≤ K ≤ 1000 (для каждой пары D, K)

 

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

Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.

Ввод	Вывод
7 10 58 15 315 20 408 100 1000 32 63 32 63 11 121	31

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

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

Одно целое число N (1 <= N <= 10⁹).

 

Выведите одно целое число - N-й элемент последовательности.
 

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

Дано 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, по одному числу в строке.

 

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

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

 

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

 

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

 

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

 

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

 

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

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

 

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109 , 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).

 

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

Выходной файл должен содержать одно целое число — искомое количество дней.

Ввод	Вывод
2 4 3 3 25	7

Дан набор гирь массой 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), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).