Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.

Входные данные: Первая строка содержит одно натуральное число n — количество вершин (0 ≤ n ≤ 1 111).

Следующие n строк содержат матрицу смежности графа. Если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый ребра соединены ребрами, а если нолик, то не соединены. При этом ребро направленно из i-ого в j-ое ребро графа, и j-ое и i-ое ребро не соеденены ребрами.

Выходные данные: Первая строка должна содержать YES, если граф содержит цикл и NO — в противном случае.

Примеры

№	Входные данные	Выходные данные
1	8 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0	YES

Обход в глубину

✓ 68✗ 173700средняяВойти и решать

Длинный НОД#18692

Даны два числа. Найти их наибольший общий делитель.

Входные данные: Вводятся два натуральных числа, не превышающих 10^9, (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000).

Выходные данные: Выведите НОД введенных чисел

Примеры

№	Входные данные	Выходные данные
1	42 12	6

НОД и алгоритм Евклида Рекурсия

✓ 1 192✗ 2 048300лёгкаяВойти и решать

Короткий НОД#18691

Даны два числа. Найти их наибольший общий делитель.

Входные данные
Вводятся два натуральных числа, не превышающих 30000.

Выходные данные
Выведите НОД введенных чисел.

Примеры

№	Входные данные	Выходные данные
1	42 12	6

НОД и алгоритм Евклида

✓ 1 703✗ 2 600300лёгкаяВойти и решать

Число с максимальной суммой делителей#18688

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

Входные данные
На вход подается натуральное число.

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	5	4

Алгоритмы обработки Простые задачи на перебор

✓ 187✗ 664500лёгкаяВойти и решать

What's this#18539

What’s this

После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации. Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.

Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — a_iи b_i(1 ≤ a_i,b_i≤ N), описывыющие туннель из пещеры с номером a_iв пещеру с номером b_i. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации

графы Дерево отрезков, RSQ, RMQ Деревья

✓ 5✗ 251 200средняяВойти и решать

Negcycle. Отрицательный цикл#18440

Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.

Входные данные:
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно ( n ≤ 1 111, m ≤ 11 111).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.

Выходные данные:
Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.

Примеры

№	Входные данные	Выходные данные
1	4 4 2 1 -4 1 2 1 3 4 2 2 3 3	yes
2	4 6 2 1 4 1 2 1 3 4 2 2 3 3 1 1 2 1 2 2	no

Алгоритм Форда-Беллмана

✓ 70✗ 190600лёгкаяВойти и решать

Полярный угол точки#18377

Даны два числа - координаты точки, не совпадающей с началом координат. Найти полярные координаты точки, не совпадающей с началом координат.

Входные данные
Во входной строке содержится два целых числа - координаты точки. Числа целые, по модулю не превышающее 1000.

Выходные данные
Одно число - величина ее полярного угла (в радианах). Значение полярного угла должно принадлежать интервалу [0; 2*π).

Примеры

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

Вычислительная геометрия

✓ 282✗ 945500лёгкаяВойти и решать

Частоты букв#15824

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Сортировка подсчетом

✓ 968✗ 1 926500лёгкаяВойти и решать

Телефоны сотрудников#15680

На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Инициалы> <телефон>

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> – семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «–». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом.

Пример входной строки:

Иванов П.С. 555-66-77

Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами.
Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.
Ответ выводить с точностью 6 знаков после запятой.

Сортировка подсчетом

✓ 592✗ 1 397600лёгкаяВойти и решать

Средний балл по предметам#15581

Годовые оценки по девяти предметам за 9-й класс каждого из N учеников класса напечатаны в виде таблицы (в первой строке - оценки первого ученика, во второй - второго и т.д.). Фамилия ученика записана в первом столбце. Необходимо вывести данную таблицу в порядке убывания среднего балла. В случае равенства среднего балла, фамилии выводить в порядке их следования в исходных данных.

Входные данные
На вход программе подаются:
- в первой строке число N - количество учеников (1<=N<=25);
- далее идут N строк, в формате <фамилия (последовательность латинских символов)> <оценка за 1й предмет> <оценка за 2й предмет> ... <оценка за 9й предмет>.

Выходные данные
Вывести на экран таблицу, записанную в порядке убывания среднего балла по всем предметам в формате:
<Фамилия> <Средний балл (с точностью 6 знаков после запятой)>
В случае равенства среднего балла, фамилии выводить в порядке их следования в исходных данных.

Примеры

№	Входные данные	Выходные данные
1	3 Sidorov 1 1 1 1 1 1 1 1 1 Ivanov 5 5 5 5 5 5 5 5 5 Petrov 4 4 4 4 4 4 4 4 4	Ivanov 5.000000 Petrov 4.000000 Sidorov 1.000000

Алгоритмы обработки Использование сортировки

✓ 161✗ 687700средняяВойти и решать

15580#15580

Годовые оценки по девяти предметам за 9й класс каждого из N учеников класса напечатаны в виде таблицы (в первой строке - оценки первого ученика, во второй - второго и т.д.) Фамилия ученика записана в первом столбце. Необходимо вывести данную таблицу в алфавитном порядке (по возрастанию, начиная с A заканчивая Z)

Входные данные: на вход программе подаются
в первой число N - количество учеников, 1<=N<=25
далее идут N строк, в формате <фамилия-последовательность латинских символов> <оценка за 1й предмет> <оценка за 2й предмет>... <оценка за 9й предмет>

Выходные данные: вывести на экран исходную таблицу, записанную в алфавитном порядке от A до Z

Примеры

входные данные

Sidorov 1 1 1 1 1 1 1 1 1 
Ivanov 5 5 5 5 5 5 5 5 5
Petrov 4 4 4 5 4 5 5 5 5

выходные данные

Ivanov 5 5 5 5 5 5 5 5 5

Petrov 4 4 4 5 4 5 5 5 5

Sidorov 1 1 1 1 1 1 1 1 1

Алгоритмы обработки Использование сортировки

✓ 41✗ 104800средняяВойти и решать

15501#15501

Используя оператор выбора напишите программу к следующей задаче:
Дано натуральное число N (N>=4).
1) Если оно делится на 4, вывести на экран строку N=4*k (где k — соответствующее частное);
2) если остаток от деления на 4 равен 1, вывести на экран результат N=4*k + 1;
3) если остаток от деления на 4 равен 2, вывести на экран результат N=4*k + 2;
4) если остаток от деления на 4 равен 3, вывести на экран результат N=4*k + 3.

Пример 1

входные данные

выходные данные

12=4*3

Пример 2

входные данные

выходные данные

22=4*5+2

Остатки Условный оператор

✓ 77✗ 134600лёгкаяВойти и решать

Квадраты#12483

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, \(1 <= A, B <= 2^{31} - 1\)). Мальчик Сеня очень любит резать прямоугольники с особым цинизмом, и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты.
Сколько же он нарежет квадратов?

Входные данные
Числа A и B, задаются в одной строке через пробел.

Выходные данные
Количество получившихся квадратов.

Примеры

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

НОД и алгоритм Евклида

✓ 1 018✗ 2 634500лёгкаяВойти и решать

Упорядоченные дроби#12482

Вывести в порядке возрастания все несократимые дроби, заключённые между 0 и 1, знаменатели которых не превышают N.

Входные данные
В первой строке находится единственное число N (\(2 <= N <= 255\)).

Выходные данные
В каждой строке выводится одна дробь.

Примеры

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

НОД и алгоритм Евклида

✓ 382✗ 964700средняяВойти и решать

12453#12453

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А-00, Б-010, В-011, Г-101, Д-111
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б-01
2) это невозможно
3) для буквы В-01
4) для буквы Г-01

Конечные автоматы

1 200труднаяВойти и решать

7151#7151

Известны очки (3, 1 или 0), полученные футбольной командой за ряд игр в порядке их проведения. Известно, что команда как минимум одну игру выиграла и как минимум одну игру проиграла.
Что было раньше: первый выигрыш (3 очка) или первый проигрыш (0 очков)?
В первой строке вводится количество проведенных командой игр (не менее 2 и не более 15).
Во второй строке вводятся очки за каждую проведенную игру.
Если выигрыш встретился раньше, то вывести слово WIN.
Если проигрыш встретился раньше, то вывести слово LOSE.

Примеры

№	Входные данные	Выходные данные
1	4 1 0 1 3	LOSE

Одномерные массивы Перебор

✓ 254✗ 422500лёгкаяВойти и решать

5003#5003

Дан символ и текст. Подсчитать количество символов до первого вхождения заданного символа в тексте. Если такого символа нет, то вывести -1.

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	a test	-1
2	e test	1

Поиск подстроки в строке Строки

✓ 50✗ 442700средняяВойти и решать

1651#1651

Чтобы процессор смог выполнить программу, она должна быть записана:
1) в ОЗУ
2) в ПЗУ
3) в драйвере
4) процессор не выполняет программы

Задачи на моделирование

1 000средняяВойти и решать

1624#1624

Что мы увидим после выполнения команды Вставка/ Объект/ Microsoft Equation (Формула Math)

1) Редактор формул
2) Редактор символов
3) Скопированную формулу
4) Редактор текста

Конечные автоматы

600лёгкаяВойти и решать

1606#1606

Поиск слова в тексте по заданному образцу является процессом:

1. хранения информации

2. передачи информации

3. обработки информации

4. уничтожение информации

Задачи на моделирование

600лёгкаяВойти и решать