Алгоритмы

606 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
ГАИ#18782
ГАИ
 
Вдоль шоссе в точках X1,X2,...,XN расположены посты ГАИ. 
В точке X произошло мелкое ДТП (дорожно-транспортное происшествие).
Требуется определить, какой из постов ГАИ расположен ближе всего
к этой точке, чтобы с него послать к месту происшествия наряд милиции.
 
Входные данные
Во входном файле записано сначала число N - количество пунктов ГАИ. (1<=N<=100)
Далее следуют координаты расположения постов ГАИ на прямом шоссе
(целые числа от -10000 до 10000). Далее идет координата точки,
в которой произошло ДТМ (целое число от -10000 до 10000).
 
Выходные данные
В выходной файл требуется вывести одно число - номер поста ГАИ,
с которого нужно послать наряд к месту ДТП. Если несколько постов
ГАИ находятся на одинаковом расстоянии от точки ДТП, выведите любой из них.
 
Пример входного файла
5
10 2 8 -7 3
7
 
Пример выходного файла
3
Алгоритмы обработкиЛинейный поиск
✓ 70✗ 174700средняяВойти и решать
Сортировка#18730
Сортировка
 
Во входном файле задано сначала число N (1<=N<=100),  а затем N целых
чисел, по модулю не превышающих 1000.
 
Выведите N чисел в порядке неубывания.
 
Пример входного файла
5
3 1 2 4 2
 
Пример выходного файла
1 2 2 3 4
Использование сортировки
✓ 140✗ 130400лёгкаяВойти и решать
Задача Иосифа Флавия#18727
Задача Иосифа Флавия
 
Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. 
В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили 
выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. 
Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места 
в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.
 
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только 
один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
 
Задача: определить номер уцелевшего.
 
Входные данные: числа N и k вводятся из строки. 
Ограничения: 1<=N<=500, 1<=k<=100.
 
Выходные данные: Программа должна выдавать номер уцелевшего человека.
 
Пример входного файла:
10 3
 
Пример выходного файла:
4
Динамическое программирование: один параметр
✓ 93✗ 192700средняяВойти и решать
Поиск циклов в графе#18701
Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.
 
Входные данные: Первая строка содержит одно натуральное число 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

 
Обход в глубину
✓ 71✗ 173700средняяВойти и решать
Длинный НОД#18692
Даны два числа. Найти их наибольший общий делитель.
 
Входные данные: Вводятся два натуральных числа, не превышающих 10^9, (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000).
Выходные данные: Выведите НОД введенных чисел

Примеры
№ Входные данные Выходные данные
1 42 12 6
НОД и алгоритм ЕвклидаРекурсия
✓ 1 247✗ 2 185300лёгкаяВойти и решать
Короткий НОД#18691
Даны два числа. Найти их наибольший общий делитель.
 
Входные данные 
Вводятся два натуральных числа, не превышающих 30000.
 
Выходные данные 
Выведите НОД введенных чисел.
 
 
Примеры
№ Входные данные Выходные данные
1 42 12 6
 
НОД и алгоритм Евклида
✓ 1 752✗ 2 664300лёгкаяВойти и решать
Число с максимальной суммой делителей#18688
По заданному числу N определите число из диапазона от 1 до N с максимальной суммой делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите максимальное из них.


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

Выходные данные
Выведите на экран ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 5 4
Алгоритмы обработкиПростые задачи на перебор
✓ 187✗ 664500лёгкаяВойти и решать
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
Вычислительная геометрия
✓ 289✗ 953500лёгкаяВойти и решать
Частоты букв#15824
На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.
Сортировка подсчетом
✓ 1 016✗ 2 013500лёгкаяВойти и решать
Телефоны сотрудников#15680
На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат: 
<Фамилия> <Инициалы> <телефон>
где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> – семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «–». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом.

Пример входной строки:
Иванов П.С. 555-66-77

Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами.
Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.  
Ответ выводить с точностью 6 знаков после запятой.
Сортировка подсчетом
✓ 633✗ 1 472600лёгкаяВойти и решать
Средний балл по предметам#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средняяВойти и решать
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
выходные данные
12=4*3
Пример 2
входные данные
22
выходные данные
22=4*5+2

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

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

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

Примеры
№ Входные данные Выходные данные
1 1 2 2
НОД и алгоритм Евклида
✓ 1 019✗ 2 636500лёгкаяВойти и решать
Упорядоченные дроби#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средняяВойти и решать
7151#7151
Известны очки (3, 1 или 0), полученные футбольной командой за ряд игр в порядке их проведения. Известно, что команда как минимум одну игру выиграла и как минимум одну игру проиграла.
Что было раньше: первый выигрыш (3 очка) или первый проигрыш (0 очков)?
В первой строке вводится количество проведенных командой игр (не менее 2 и не более 15).
Во второй строке вводятся очки за каждую проведенную игру.
Если выигрыш встретился раньше, то вывести слово WIN.
Если проигрыш встретился раньше, то вывести слово LOSE.


 
Примеры
№ Входные данные Выходные данные
1 
4
1 0 1 3
 
LOSE
Одномерные массивыПеребор
✓ 255✗ 422500лёгкаяВойти и решать
5003#5003
Дан символ и текст. Подсчитать количество символов до первого вхождения заданного символа в тексте. Если такого символа нет, то вывести -1.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 a
test		 -1
2 e
test		 1

Поиск подстроки в строкеСтроки
✓ 50✗ 442700средняяВойти и решать
1624#1624

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

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

Конечные автоматы
600лёгкаяВойти и решать
1606#1606

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

1.    хранения информации
2.    передачи информации
3.    обработки информации
4.    уничтожение информации
 

Задачи на моделирование
600лёгкаяВойти и решать
Поделиться
Класснуть