Задача 1: Коровы - в стойла
Условие задачи:
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.
Задача 2: Правильная скобочная последовательность
Условие задачи:
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.
Пустая последовательность явлется правильной. Если \(A\) – правильная, то последовательности \((A), [A], \{A\}\) – правильные. Если \(A\) и \(B\) – правильные последовательности, то последовательность \(AB\) – правильная.
Задача 3: Все строки длины n из k различных символов
Условие задачи:
По данным числам \(N\) и \(K\) выведите все строки длины \(N\) из символов \(0..K-1\) в лексикографическом порядке.
Задача 4: Все двоичные строки длины n, содержащие ровно k единиц
Условие задачи:
По данным числам \(N\) и \(K\) выведите все строки из нулей и единиц длины \(N\), содержащие ровно K единиц, в лексикографическом порядке.
Задача 5: Все перестановки заданной длины
Условие задачи:
По данному числу N выведите все перестановки чисел от \(1\) до \(N\) в лексикографическом порядке.
Задача 6: Все возрастающие последовательности длины k из чисел 1..n
Условие задачи:
По данным числам \(N\) и \(K\) выведите все возрастающие последовательности длины \(K\) из чисел \(1..N\) в лексикографическом порядке.
Задача 20: Последовательность из 0 и 1
Условие задачи:
Требуется подсчитать количество последовательностей длины \(N\), состоящих из \(0\) и \(1\), в которых никакие две единицы не стоят рядом.
Задача 7: Разбиение на невозрастающие слагаемые, лексикографический порядок
Условие задачи:
Дано натуральное число \(N\). Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.
Задача 8: 2^n
Условие задачи:
Напишите программу, вычисляющую заданную степень числа 2, используя битовые операции.
Задача 9: Инвертировать бит
Условие задачи:
Напишите программу, которая инвертирует определенный бит в заданном числе (биты при этом нумеруются с 0, начиная с младших).
Задача 10: Установить значение бита в 0
Условие задачи:
Напишите программу, устанавливающую значение определенного бита числа в 0.
Задача 11: Обнулить все биты, кроме последних
Условие задачи:
Напишите программу, обнуляющие все биты числа, кроме нескольких последних
Задача 12: Определить значение бита
Условие задачи:
Напишите программу, определяющую значение \(i\)-го бита числа.
Задача 13: Сумма кубов
Условие задачи:
Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.
Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.
Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.
Задача 14: Обход в глубину
Условие задачи:
Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной (считая эту вершину).
Задача 15: Банкет
Условие задачи:
На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
Задача 16: Города и дороги
Условие задачи:
В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.
Задача 17: Светофорчики
Условие задачи:
В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от \(1\) до \(N\).
Примечание. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка \(i\) до него самого.
Задача 18: Цветной дождь
Условие задачи:
В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами. В некоторых местах падали красные капли, в некоторых – синие, а в остальных – зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитайте количество таких "плохих" мостов.
Задача 19: Издевательство
Условие задачи:
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...
Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.
Задача 21: Покупка билетов
Условие задачи:
За билетами на премьеру нового мюзикла выстроилась очередь из \(N\) человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу \(i\)-му человеку из очереди одного билета кассир тратит \(A_i\) секунд, на продажу двух билетов — \(B_i\) секунд, трех билетов — \(C_i\) секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
Задача 22: Максимальный - вперед
Условие задачи:
Требуется поменять местами первый элемент массива с максимальным.
Задача 23: Сортировка выбором максимума
Условие задачи:
Требуется отсортировать массив по неубыванию методом "выбор максимума".
Задача 24: Вставка числа
Условие задачи:
Требуется вставить в данный массив на данное место данный элемент, сдвинув остальные элементы вправо.
Задача 25: Сортировка вставками
Условие задачи:
Требуется отсортировать массив по неубыванию методом "вставок".
Задача 26: Исключающее ИЛИ
Условие задачи:
Напишите функцию
bool Xor (bool x, bool y) (C/C++),
function _Xor (x, y:boolean): boolean (Pascal),
def xor(x, y):(Python)
реализующую функцию "Исключающее ИЛИ" двух логических переменных x и y. Функция Xor должна возвращать true, если ровно один из ее аргументов x или y, но не оба одновременно равны true.
Задача 28: Быстрое возведение в степень
Условие задачи:
Напишите функцию быстрого возведения в степень. Количество действий должно быть пропорционально двоичному логарифму \(n\).
Задача 29: Подсчет чисел
Условие задачи:
Подсчитайте, сколько среди данных \(N\) чисел нулей, положительных чисел, отрицательных чисел.
Задача 30: Проверка на неориентированность
Условие задачи:
По заданной квадратной матрице \(n×n\) из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Задача 31: Петли
Условие задачи:
По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
Задача 32: Подсчет количества ребер неориентированного графа
Условие задачи:
Простой неориентированный граф задан матрицей смежности. Найдите количество ребер в графе.
Задача 33: Подсчет количества ребер ориентированного графа
Условие задачи:
Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.
Задача 34: От матрицы смежности к списку ребер, неориентированный вариант
Условие задачи:
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Задача 35: От списка ребер к матрице смежности, неориентированный вариант
Условие задачи:
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
Задача 36: От матрицы смежности к списку ребер, ориентированный вариант
Условие задачи:
Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Задача 37: От списка ребер к матрице смежности, ориентированный вариант
Условие задачи:
Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
Задача 38: Степени вершин
Условие задачи:
Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.
Задача 39: Степени вершин по спискам ребер
Условие задачи:
Неориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Задача 40: Полустепени вершин
Условие задачи:
Ориентированный граф задан матрицей смежности. Найдите полустепени захода и полустепени исхода всех вершин графа.
Задача 41: Полустепени вершин по спискам ребер
Условие задачи:
Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Задача 42: Очень Легкая Задача
Условие задачи:
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще \(N\) копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за \(x\) секунд, а другой – за \(y\). (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.
Задача 43: Скобки(2)
Условие задачи:
Вывести все правильные скобочные выражения длиной \(N\), состоящие из круглых и квадратных скобок.
Задача 44: Сообщение
Условие задачи:
В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.
Задача 45: Удаление клеток
Условие задачи:
Из прямоугольного листа клетчатой бумаги (\(M\) строк, \(N\) столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Задача 46: Провода
Условие задачи:
Дано \(N\) отрезков провода длиной \(L_1, L_2, ..., L_N\) сантиметров. Требуется с помощью разрезания получить из них \(K\) равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить \(K\) отрезков длиной даже 1 см, вывести 0.
Ограничения: \(1 <= N <= 10^4\), \(1 <= K <= 10^4\), \(100 <= L_i <= 10^7\), все числа целые.
Задача 47: Простая последовательность
Условие задачи:
Вычислите \(n\)-й член последовательности, заданной формулами: \(a_{2n} = a_n + a_{n-1}, a_{2n+1} = a_n – a_{n-1}, a_0 = a_1 = 1\).
Задача 48: Сортировка вагонов
Условие задачи:
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
Задача 55: Функция sign(x)
Условие задачи:
Напишите программу, которая будет считывать значение вещественной переменной x и выдавать значение следующей функции от \(x\):
\[sign(x) =
\begin{cases}
-1. x<0 \\
0, x=0\\
1, x > 0
\end{cases} \]
Задача 56: Точка на плоскости
Условие задачи:
Даны координаты точки на плоскости. Требуется определить, в какой координатной четверти она лежит.
Задача 49: Призы победителям сборов
Условие задачи:
Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.
Например, если размер холодильника должен быть 12, возможными вариантами являются:
Размеры баночек | Площадь поверхности
3 * 2 * 2 | 32
4 * 3 * 1 | 38
6 * 2 * 1 | 40
12 * 1 * 1 | 50
Лучшим вариантом является 3 × 2 × 2.
Помогите организаторам сборов выбрать оптимальную форму холодильника.
Задача 50: Без трех единиц
Условие задачи:
Определите количество последовательностей из нулей и единиц длины \(N\) (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.
Задача 51: Взрывоопасность
Условие задачи:
При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров \(N\) определить количество возможных типов безопасных стопок.
Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.
Задача 52: Самый дешевый путь
Условие задачи:
Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
Задача 53: Часы
Условие задачи:
Часовая стрелка повернулась с начала суток на \(d\) градусов. Определите, сколько сейчас целых часов \(h\) и целых минут \(m\).
Задача 54: Часы
Условие задачи:
Даны значения двух моментов времени, принадлежащих одним и тем же суткам: часы, потом минуты и секунды для каждого из моментов времени. Известно, что второй момент времени наступил не раньше первого. Определите, сколько секунд прошло между двумя моментами времени.
Задача 58: Сумма квадратов
Условие задачи:
Проверьте, можно ли представить число в виде суммы двух квадратов натуральных чисел.
Задача 59: Вклад
Условие задачи:
Вкладчик положил на банковский счет некоторую сумму. Каждый год на сумму вклада начисляется \(k\) процентов годовых (будем считать, что процент всегда округляется до целого числа рублей по формуле \((xk/100)\), где \(x\) — сумма вклада на начало года. Начисленные проценты добавляются к сумме вклада. Через сколько лет сумма вклада как минимум удвоится?
Задача 60: Тип последовательности
Условие задачи:
Определите вид последовательности.
При решении задачи массивы использовать нельзя.
Задача 61: Минимальное число в последовательности
Условие задачи:
Дана последовательность, состоящая из \(n\) чисел. Выясните, сколько раз в ней встречается минимальное число.
Массив в программе не использовать.
Задача 62: Разложение по Тейлору e^x
Условие задачи:
По заданному натуральному \(n\) и вещественному \(x\) вычислить \(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots+\frac{x^n}{n!}\).
Задача 63: Вычислить
Условие задачи:
По заданным натуральным числам \(n\) и \(m\) вычислите \(\sqrt{m+\sqrt{2m+\ldots+\sqrt{(n-1)m+\sqrt{nm}}}}\).
Задача 96: Дележ яблок - 2
Условие задачи:
\(n\) школьников делят \(k\) яблок поровну, неделящийся остаток остается в корзинке. Сколько яблок останется в корзинке?
Задача 64: Числа Фибоначчи
Условие задачи:
Числа Фибоначчи определяются следующими формулами:
\(f(0) = f(1) = 1;\)
\(f(n) = f(n–1) + f(n–2)\), при \(n >= 2\).
Массив в программе не использовать.
Задача 65: Квадраты индексов
Условие задачи:
Заполните числовой массив так, чтобы значения элементов были равны квадратам индексов.
Задача 66: Сдвиг массива
Условие задачи:
Напишите программу, которая будет циклически сдвигать заданный массив на один элемент вправо, последний элемент при этом должен оказаться на первом месте.
Задача 67: Поменять местами максимум и минимум
Условие задачи:
Найдите максимальный и минимальный элементы в массиве и поменяйте их местами.
Задача 68: Подсчет каждого числа
Условие задачи:
На вход программе подается последовательность чисел от 1 до 9, заканчивающаяся нулем. Всего будет введено не более 100000 чисел. Подсчитайте в этой последовательности количество единиц, количество двоек, количество троек и т.д. и выдайте результат. В выходных данных всегда должно быть 9 чисел.
Задача 69: Сумма подряд идущих
Условие задачи:
Дан массив целых чисел \(a[1], a[2], \ldots, a[n]\) и натуральные числа \(k\) и \(m\).
Укажите минимальное значение \(i\), для которого \(a[i] + a[i+1] + \ldots + a[i + k] = m\) (то есть сумма \(k + 1\) подряд идущих элементов массива равна \(m\)).
Если такого значения нет, то выведите 0.
Вложенные циклы и дополнительные массивы не использовать (требуется решить задачу за один проход исходного массива).
Задача 70: Отрезок с максимальной суммой
Условие задачи:
В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие \(i\) и \(j\) \((i <= j)\), что сумма всех элементов массива от \(a_i\) до \(a_j\) включительно будет максимальна.
Задача 71: Палиндром
Условие задачи:
Фраза называется палиндромом (перевертышем), если после удаления пробелов и замены всех букв на заглавные она читается одинаково, как слева направо, так и справа налево. Требуется определить, является ли введенная фраза палиндромом.
Примечание. Для русских букв, записанных в кодировке Windows- 1251, можно считать, что коды заглавных и строчных букв отличаются на 32.
Задача 72: Поменять два слова местами
Условие задачи:
Строка состоит из двух слов. Поменяйте эти слова местами.
Задача 73: Сколько букв в самом длинном слове
Условие задачи:
Определить, сколько букв содержит самое длинное слово во введенной строке символов.
Задача 74: Дипломы
Условие задачи:
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) — в ширину и \(h\) — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\) на \(h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
См. иллюстрацию к первому примеру.
Задача 75: Билеты
Условие задачи:
В одной театральной кассе есть в продаже билеты любой стоимости, выражающейся натуральным числом. При покупке билетов по цене за билет от \(A\) до \(B\) рублей включительно нужно дополнительно оплатить сервисный сбор в размере C процентов от номинальной стоимости билетов (сервисный сбор не обязательно выражается целым числом рублей, но всегда выражается целым числом копеек). При покупке билетов стоимостью менее \(A\) рублей за билет, а также более \(B\) рублей за билет, сервисный сбор не берется.
У вас есть \(X\) рублей и вам нужно \(K\) билетов одинаковой цены (цена обязательно должна выражаться натуральным числом рублей, \(0\) не считается натуральным). Билеты какого самого дорогого номинала вы можете себе позволить?
Задача 76: Калькулятор
Условие задачи:
Имеется калькулятор, который выполняет три операции:
1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Задача 77: Поиск в словаре
Условие задачи:
Словарь задан массивом отсортированных в лексикографическом порядке строк. Напишите программу эффективного поиска слова в словаре.
Задача 78: Улучшенный пузырек
Условие задачи:
Измените алгоритм "пузырьковой" сортировки так, чтобы он заканчивал свою работу в случае, когда на очередном проходе не произошло ни одного обмена (это означает, что массив уже отсортирован и дальнейшие проходы не нужны).
Задача 79: Сортировка подсчётом (2)
Условие задачи:
Реализуйте алгоритм сортировки подсчетом для произвольных чисел, по модулю не превосходящих 10000.
Примечание. Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!
Задача 80: Сортировка вставками
Условие задачи:
Реализуйте алгоритм сортировки вставками, который заключается в том, что мы просматриваем последовательно \(a_2,a_3,a_4, \ldots ,a_n\) и каждый новый элемент \(a_i\) вставляем на подходящее место в уже упорядоченную совокупность \(a_1,a_2,\ldots,a_{i−1}\). Это место определяется последовательным сравнением \(a_i\) с упорядоченными элементами \(a_{i−1},\ldots,a_1\)
и обменом с теми элементами, которые больше, чем \(a_i\).Такой алгоритм называется сортировкой вставками. Именно его обычно использует человек в быту при упорядочении предметов, например библиографических карточек в каталоге библиотеки.
Задача 81: Мелодия
Условие задачи:
Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.
Мелодия состоит из \(M\) нот \(b_1,b_2,\ldots,b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.
Задача 82: Проходной балл
Условие задачи:
Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:
Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
На второй тур можно пригласить не более \(M\) участников.
Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.
Задача 83: Вычислить 2^179
Условие задачи:
Вычислите \(2^{179}\). Выведите на экран вычисленное значение.
Задача 84: Факториал
Условие задачи:
Вычислите \(20! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 20\). Выведите на экран вычисленное значение.
Задача 85: Гипотенуза
Условие задачи:
Вычислите длину гипотенузы в прямоугольном треугольнике со сторонами 179 и 971.
Задача 86: Ряд Лейбница
Условие задачи:
Для вычисление числа \(\pi\) можно использовать следующее приближение (ряд Лейбница):
\[\pi = \frac{4}{1} - \frac{4}{3} + \frac{4}{5} - \frac{4}{7} + ...\]
Вычислите первые 10 членов этого ряда. Сколько получилось?
Задача 87: Дзета-функция
Условие задачи:
А вот другой ряд, в котором вычисляется значение дзета-функции для числа 2:
\[\frac{\pi^2}{6} = \frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+ \cdots\]
Вычислите приближение к числу \(\pi\), используя первые 10 членов этого ряда.
Задача 88: 100А
Условие задачи:
Запишите букву 'A' (латинскую, заглавную) 100 раз подряд. Сдайте на проверку программу, которая выводит эту строчку (только буквы, без кавычек).
Задача 89: Python
Условие задачи:
Запишите слово 'Python' 100 раз подряд. Сдайте на проверку программу, которая выводит эту строчку (только буквы, без кавычек).
Задача 90: Квадрат числа
Условие задачи:
Число 179 записали 50 раз подряд. Полученное 150-значное число возвели в квадрат. Сколько получилось?
Задача 91: Корень степени 10
Условие задачи:
Число \(179^{10}\) записали четыре раза подряд. Из получившегося числа извлекли корень степени 10. Сколько получилось?
Задача 92: Гипотенуза
Условие задачи:
Дано два числа \(a\) и \(b\). Выведите гипотенузу треугольника с заданными катетами.
Задача 93: Hello, Harry!
Условие задачи:
Напишите программу, которая приветствует пользователя, выводя слово "Hello", введенное имя и знаки препинания по образцу (см. пример входных и выходных данных). Программа должна считывать в строковую переменную значение и писать соответствующее приветствие. Обратите внимание, что после запятой должен обязательно стоять пробел, а перед восклицательным знаком пробела нет.
Задача 94: Следующее и предыдущее
Условие задачи:
Напишите программу, которая считывает целое число и выводит текст, аналогичный приведенному в примере (пробелы важны!):
Задача 95: Дележ яблок - 1
Условие задачи:
\(n\) школьников делят \(k\) яблок поровну, неделящийся остаток остается в корзинке. Сколько яблок достанется каждому школьнику?
Задача 97: МКАД
Условие задачи:
Длина Московской кольцевой автомобильной дороги — 109 километров. Байкер Вася стартует с нулевого километра МКАД и едет со скоростью \(v\) километров в час. На какой отметке он остановится через \(t\) часов?
Без использования условных операторов эту задачу существенно проще решить языке Python, чем на других языках программирования. Это связано с особенностями реализации целочисленных операций над отрицательными числами.
Задача 99: Число десятков двузначного числа
Условие задачи:
Дано двузначное число. Найдите число десятков в нем.
Задача 100: Число десятков
Условие задачи:
Дано натуральное число. Найдите число десятков в его десятичной записи.