Алгоритмы

Студент Павел недавно приобрёл себе подержанный автомобиль и теперь ездит на нём в университет. На его пути в вуз имеется один загруженный перекрёсток, проезд через который регулируется светофором. Сделав ряд поездок, Павел обнаружил интересную закономерность: пока на светофоре горит зелёный свет, через перекрёсток успевает проехать не менее a, но не более b машин. Сверху над перекрёстком установлена уличная видеокамера. Павел может подключиться к ней со своего смартфона и сосчитать количество машин n, которые стоят перед светофором впереди него (свою машину он тоже считает). Назовём тактом светофора включение на нём зелёного сигнала. Напишите программу, определяющую минимальный и максимальный номер такта, на котором Павел проедет перекрёсток.
Формат входных данных
Впервых двух строках входных данных записаны целые числа a и b (1 ≤a ≤ b ≤ 10⁹). В третьей строке записано целое число n (1≤ n ≤ 10⁹).
Формат выходных данных
Выведите два целых числа минимальный и максимальный номер такта светофора, на котором Павел проедет перекрёсток.

Замечание
В примере из условия перед светофором стоят 10 машин. Если через перекрёсток будут проезжать по 5 машин на зелёный свет, то Павел проедет на втором такте. Если же будут проезжать по 3 машины, то он проедет лишь на четвёртом такте.

Современные компьютеры состоят из микроскопических транзисторов (электронных переключателей). Каждый из них может быть в двух состояниях:

• 1 (ВКЛ) — есть ток → True

• 0 (ВЫКЛ) — нет тока → False

Какое число соответствует True в двоичном коде?

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

• ·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
• ·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
•     - если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
•     - если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
•     - если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
• ·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
• ·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

• каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

               - если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта; 
               - если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

• забирающий карты забирает обе карты в свою колоду, кладясперва карту противника под низ колоды, затем свою карту также под низ колоды; 
• побеждает тот игрок, который останется без карт.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные: 
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

В школе в очередной раз заболел преподаватель физкультуры Виктор Дмитриевич. Поэтому директор принял решение, что кто-то из свободных учителей проведёт занятие. После долгих размышлений, самым свободным оказался учитель информатики Анатолий Иванович, который очень любит алгоритмы сортировки, что вызвало сразу проблему у учеников. Ведь Анатолий Иванович первым делом сказал ребятам построиться в шеренгу, но не как обычно (по убыванию роста, ), а так, чтобы каждое нечётное место было отсортировано по росту по убыванию (первое место - самый высокий ученик, третье место выше пятого, пятое выше седьмого и так далее)), а каждое чётное по возрастанию (второе место - самый низкий ученик, четвёртый второй по росту среди всех, шестой - третий по росту среди всех и так далее) (учеников Анатолий Иванович нумеровал с 1).
Помогите ученикам получить правильный порядок, как встать им в шеренгу так, чтобы Анатолий Иванович оказался доволен.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 121)– количество учеников в классе.
На N последующих строках подаются строки вида имя-рост (например, «Ivan 175»), где на первом месте указывается имя ученика – оно всегда одним словом на английском языке, без пробелов, а в конце указывается рост ученика (целое число от 100 до 220).
Формат выходных данных
Выведите имена учеников в одну строку через пробел, как они должны встать на уроке физкультуры.
Примечание:
Имена учеников у всех уникальны, рост ни у кого не повторяется.

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

• 1 + 1 = 0
• 1 + 0 = 1
• 0 + 1 = 0
• 0 + 0 = 1

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

Формат входных данных
На первой строке подаётся первое слагаемое – двоичное число без значащих нулей длины N (1 <= N <= 10⁵).
На второй строке подаётся второе слагаемое – двоичное число без значащих нулей также длины N.

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

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

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

Примеры

№	Входные данные	Выходные данные
1	2023 2007	32248

Напишите программу на Python, которая:

1. Считывает уравнение из строки.

2. Преобразует строку в символьное уравнение с помощью SymPy.

3. Решает уравнение.

4. Выводит корни уравнения.

Трое друзей — Аня, Боря и Саша — пришли на детскую площадку, чтобы покачаться на качеляхбалансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.

Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.

Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, — массы друзей. В четвёртой строке записано число D — наибольшая допустимая разница масс на концах качелей. Все числа — целые, положительные и не превосходящие 10⁹ .

Формат выходных данных
Программа должна вывести одно целое число — минимальную необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0. 

Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг. Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша — на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

Формат входных данных
Выведите количество подходящих пар квадратов.

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

Будем называть пару различных целых чисел похожими, если у них \(k\) последних цифр совпадает.

Дано число \(n\), найдите количество пар различных похожих чисел, состоящих из \(n\) цифр. Ведущие нули запрещены. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми.

Формат входных данных
На первой строке находится целое число \(n\) (\(1 \le n \le 10\)).

На второй строке находится целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно число — количество пар похожих чисел, состоящих из \(n\) цифр.

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

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї
 

Муми-Тролли хотят украсить свою ёлку гирляндами, чтобы она светилась во время новогоднего праздника. Известно, что длина всех витков гирлянды, необходимых для полного обвивания ёлки, составляет L метров. Каждая гирлянда имеет длину M метров. Помогите муми-троллям посчитать сколько всего гирлянд необходимо муми-троллям?

Формат входных данных
В первой строке записано натуральное число L (L < 10⁹). Во второй строке - натуральное число M (M < 10⁹).

Формат выходных данных
Выведите одно число - количество необходимых гирлянд

Кодоны — это триплеты нуклеотидов (три буквы), которые определяют аминокислоты в процессе трансляции (синтеза белка).

1. Старт-кодон — кодон, с которого начинается считывание белковой последовательности. В ДНК это всегда ATG.
2. Стоп-кодоны — кодоны, которые сигнализируют окончание считывания. В ДНК это:
   • TAA
   • TAG
   • TGA

 

Надо написать программу, которая:

1. Находит все стартовые (ATG) и стоп-кодоны (TAA, TAG, TGA) в последовательности ДНК.
2. Возвращает их позиции (индексы).

Формат входных данных
Строка содержит последовательность ДНК

Формат выходных данных
В первой строке вывести позиции старт-кодонов в порядке возрастания, во второй строке вывести позиции стоп-кодонов в порядке возрастания.

В биоинформатике часто требуется искать и подсчитывать конкретные последовательности нуклеотидов в ДНК. В данной задаче необходимо подсчитать количество повторений триплета "ATG" в заданной последовательности ДНК. Триплет "ATG" является важным мотивом, связанным с началом кодирования белков. Напишите функцию, которая принимает строку, представляющую последовательность ДНК, и возвращает количество вхождений триплета "ATG" в этой последовательности.

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

Напишите программу, которая:
1) в первой строке запрашивает ввод строки и сохраняет ее в переменной s;
2) во второй строке запрашивает ввод строки и сохраняет ее в переменную subs;
3) выводит на экран наименьший индекс, с которого начинается подстрока subs в строке s; если строка s не содержит подстроку subs, то программа должна вывести -1.

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

У вас есть массив points, где points[i] = [xi, yi] — координаты i-го зеленого насаждения на двумерной карте города.

Также у вас есть массив queries, где queries[j] = [xj, yj, rj] описывает j-ю круговую зоны, в которой необходимо оценить количество зеленых насаждений.

Для каждого запроса queries[j] вычислите количество зеленых насаждений, находящихся внутри j-й круговой зоны. Точки, находящиеся на границе зоны, также считаются входящими в эту зону.

Верните массив answer, где answer[j] — это количество зеленых насаждений в j-й круговой зоне.
 

По введенному натуральному числу K, не превосходящему 1 000 000, выдать K-ое по счету простое число.

Входные данные
Во входном файле находится одно натуральное число K.

Выходные данные
В выходной файл выведите K-е простое число.

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


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

В первой строке входного файла вводится одно натуральное число 𝑁≤100 — количество ступенек.
В следующей строке вводятся 𝑁 натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

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

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.