Набор для торта

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).

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

Примеры

Сломанный принтер

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет.  Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области.  В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей.  Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей.  Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.

Примеры

Громозека и Алиса - 2

Алиса и Громозека пошли гулять по городу. Заходя в первое кафе, Алиса посмотрела на часы и запомнила время входа. Далее она запоминала только количество минут, которое они с Громозекой тратили между двумя посещенными кафе (от входа в одно кафе, до входа в другое). По окончании прогулки, Алиса решила восстановить хронологию - время входа в очередное кафе.
Напишите программу, которая определит, в какое время Алиса и Громозека заходили в очередное кафе. 

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.
 

Примеры

Три четыре пять корову поменять

N  коров (1 ≤ N ≤ 100) Фермера Джона выстроены в ряд. i-ая корова слева имеет метку i, для всех 1≤i≤N.
ФД приказал коровам повторить ровно K (1 ≤ K ≤10⁹) раз следующий двухшаговый процесс:

Последовательность коров в позициях A1…A2 слева реверсивно меняют свой порядок (1≤A₁<A₂≤N).
Затем последовательность коров в позициях B1…B2 слева реверсивно меняют свой порядок (1≤B₁<B₂≤N).
Выведите получившийся порядок коров для всех i 1 ≤ i ≤ N после выполнения этого процесса ровно K раз.


Входные данные
Первая строка содержит N и K. Вторая строка содержит A₁ и A₂, третья строка содержит B₁ и B₂.
Выходные данные
На i-ой строке выведите метку i-ой коровы слева после завершения процесса всех обменов.

Примеры

7 2
2 5
3 7

1
2
4
3
5
7
6

Книги Томми

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

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

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.

Примеры

Книжки с полки

Петя обладает обширной библиотекой книг. Сейчас он стоит возле полки с приключенческими рассказами. На ней расположены n книг. Все книги на полке у Пети всегда пронумерованы слева направо. Книга с номером i имеет ai страниц. На полке, возле которой сейчас стоит Петя, количество страниц в каждой книге различно.

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a1, a2, ..., an (1 <= ai <= 106) - количество страниц в книге.

Выходные данные
Выведите одно целое число — минимальное количество книг, которое необходимо Пете убрать с полки.

Примеры

5
1 5 4 3 2

2

8
2 1 3 4 5 6 8 7

4

Крестики-нолики

...
000
XXX
...
...

..0.
.XX0
.0X.
....

......
.XXX..
.0000.
..X...
......

Магические порталы

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

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

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

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

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:

Kotlin Island

There is an urban myth that Peter the Great wanted to make a rectangular channel-grid engineering masterpiece not only from Vasilyevskiy island, but also from Kotlin island (where the town of Kronstadt is located nowadays).

The following mathematical model was (allegedly) presented to the tsar. The island is considered a rectangular grid h cells high and w cells wide. Each cell is dry land initially but can become water.

Technologies of those days allowed engineers to dig a channel across the entire island. In that case an entire row or an entire column of cells became water. If some of these cells already were water, their status did not change.
Your task is to propose a plan of the island which has exactly n connected components of dry land cells.

Input
The only line of the input contains three integers h, w, and n — grid’s height, width and the desired number of connected components (1 ≤ h, w ≤ 100; 1 ≤ n ≤ 10⁹ )

Output
If there is no valid plan containing n connected components, output a single word “Impossible”. Otherwise output h lines of length w depicting the plan. Dot (‘.’) represents a dry land cell, hash (‘#’) represents a water cell.
 

Шифрование

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

Смех, да и только!

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

Лиса считает, что смех — это последовательность чередующихся букв «a» и «h». Так например, «ahahaha», «hah» и «a» являются смехом, а «abacaba» и «hh» — нет.

Колобок разговаривает очень быстро, поэтому все его слова сливаются в одно большое. Для исследования Лиса хочет понять, как долго он может смеяться. У неё есть строка — запись разговора Колобка. Лиса хочет узнать наибольшую длину смеха в этом разговоре.

Лиса просит вас помочь ей с этой задачей.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 105 ) — длина строки с разговором колобка. Во второй строке находится строка из строчных латинских букв длины n — запись разговора колобка.

Формат выходного файла
В выходной файл выведите одно число — наибольшую длину смеха в разговоре Колобка
 

Прямоугольное поле чудес (В, А',A)

Овечка Толя (C, B')

Организация конференции (С, B')

Коды Грея

На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2ⁿ различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

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

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2ⁿ строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 

The Lost Cow

Телефонный справочник

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

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 10⁶) 

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.
 

Пират Серёжа

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Маленький пират Серёжа скачал игру с разными видами головоломок. Среди них ему понравилась лишь одна, самая сложная.

Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в ячейках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.

Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением \(i\) рассмотрим позицию \(t_i\) — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).

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

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

За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, которое потребуется, чтобы головоломка стала решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий \(0\), \(1\), или же не менее \(2\). В случае, когда потребуется ровно \(1\) действие, найдите также количество подходящих пар клеток для обмена чисел.

Формат входных данных
В первой строке вводятся два целых положительных числа \(n, m\) (\(1 \leq n \cdot m \leq 400\,000\)) — длины сторон таблицы.

В каждой из следующих \(n\) строках вводятся \(m\) целых чисел \(a_{i1}, a_{i2}, \dots, a_{im}\) (\(1 \le a_{ij} \le n \cdot m\)).

Гарантируется, что каждое число от \(1\) до \(n \cdot m\) встречается ровно один раз.

Формат выходных данных
Пусть \(a\) — минимальное число действий, после которых головоломка станет решаемой.

Если \(a = 0\), выведите \(0\).

Если \(a = 1\), выведите \(1\), а также количество подходящих пар клеток.

Если \(a \ge 2\), выведите \(2\).

В первом примере из условия последовательность клеток \((1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)\), \((2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)\) решает головоломку, поэтому ответ \(0\).

Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями \((1, 5), (1, 6), (2, 6)\).

В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен \(2\).

Палиндромные числа

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Однажды во время прогулки Алина увидела длинное число, которое кто-то написал на асфальте. Алина захотела найти положительное число такой же длины без ведущих нулей, чтобы сумма этих двух чисел была палиндромом.

Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа \(121, 66, 98989\) являются палиндромами, а \(103, 239, 1241\) — нет.

После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(2 \leq n \leq 100\,000\)) — длина числа, которое увидела Алина.

Во второй строке вводится одно положительное целое число длины \(n\). Гарантируется, что оно не содержит ведущих нулей.

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

Если таких чисел несколько, вы можете вывести любое из них.

В первом примере из условия \(99 + 32 = 131\) — палиндром. Число \(12\) также будет являться ответом, так как \(99 + 12 = 111\).

Во втором примере из условия \(1023 + 8646 = 9669\).

В третьем примере из условия \(385 + 604 = 989\).

Поймать Халка

Телефонные номера

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

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

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ «+», код региона или оператора берется в скобки, номер абонента разделяется символами «-» на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
• если номер абонента состоит из трех цифр, то он представляет собой одну часть, состоящую из трех цифр;
• если номер абонента состоит из четырех цифр, то он разбивается на две части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из пяти цифр, то он разбивается на две части, первая из которых состоит из трех цифр, а вторая — из двух;
• если номер абонента состоит из шести цифр, то он разбивается на три части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из семи цифр, то он разбивается на три части, первая из которых состоит из трех цифр, а все остальные — из двух.

Естественно, что человек, заносящий новый номер в записную книжку своего телефона, не станет задумываться об этих правилах, а просто введет его как последовательность из 11 цифр. Однако, перед отображением номера на экране, программное обеспечение телефона должно выяснить, какая часть этого номера является кодом страны, какая — кодом региона или оператора, а какая — номером абонента, и отформатировать номер по правилам, описанным выше. Чтобы сделать эту задачу разрешимой, в память телефона записывается информация о том, какие в данный момент существуют коды государств и какие в этих государствах существуют коды операторов или регионов. Вам необходимо реализовать программу, которая, имея эту информацию, будет правильно форматировать номера, сохраненные в записной книжке телефона.

Формат входных данных
Первая строка файла содержит одно целое число n (1 ≤ n ≤ 100) — количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют n описаний этих государств, разделенных переводами строк. Первая строка описания каждого государства содержит два целых числа c и k (1 ≤ c ≤ 999, 1 ≤ k ≤ 100) — телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие k строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 — коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число m (1 ≤ m ≤ 10 000) — количество телефонных номеров, которые необходимо отформатировать. Следующие m строк содержат сами номера — строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.

Формат выходных данных
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле. Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово «Incorrect».
 

Перетягивание каната

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ a_i ≤ 1000) — длины имеющихся кусков каната.

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

Вирус

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из n × m ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через t секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

Формат выходных данных
Выведите количество различных возможных конфигураций таблицы после t секунд.
 

Римские числа

Один древнеримский торговец брал несколько раз ссуду в древнеримском банке. Каждый раз банкир записывал размер выданной ссуды на листе пергамента, используя римские числа. Но ввиду дороговизны пергамента запись производилась плотно и все числа оказались записанными подряд, без разделителей. Когда торговец пришёл возвращать ссуду, оказалось, что невозможно установить разбиение записи на числа.

Например, если на пергаменте записана строка «XIIV», её можно разбить на римскиечисла разными способами, например, XI + IV = 11 + 4 = 15 или XII + V = 12 + 5 = 17, возможны и другие варианты разбиения.

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

Программа получает на вход строку, длина которой не превосходит 250 символов. Строка состоит только из заглавных латинских букв I, V, X, L, С, D, M.

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

Правила записи римских чисел
Римскими цифрами можно записать целые числа от 1 до 3999. Число представляется в виде суммы тысяч, сотен, десятков и единиц. Далее из следующей таблицы берётся по одному элементу, соответствующему тысячам, сотням, десяткам, единицам ровно в таком порядке.



Если число тысяч, сотен, десятков, единиц равно 0, то из соответствующего столбца ничего не берётся. Например, число 1990 записывается, как 1000 + 900 + 90 = MCMXС.

Турнир

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.
 

Умный обогреватель

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

1. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше \(t_{min}\), то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.

2. Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

Гарантируется, что записи программы правильные, и такие два числа существуют.

Формат входных данных
В первой строке задано целое число \(n\) (\(5 \leq n \leq 10^5\)) — количество дней, в течение которых работала система.

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

В третьей строке входных данных задается строка из \(n\) символов, состоящая из 0 и 1 — если в \(i\)-й позиции данной строки записан 0, то это значит, что в \(i\)-й день обогреватель был выключен, а если 1, — то включен.

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

Преобразование строки

Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.

Посмотрим на следующий процесс. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После чего, для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в \(S\) на \(p(x)\). Определите, возможно ли в ходе такого процесса получить из строки \(S\) строку \(T\). При этом разные символы можно заменять на один и тот же символ или на символ, который заменяться не будет.

Например, пусть \(S =\) <<aabab>>, \(T =\) <<abbbc>>. Из \(S\) можно получить \(T\), если выбрать p(‘a’) = ‘b’, p(‘b’) = ‘c’ и заменить второе и третье вхождение ‘a’ на p(‘a’), второе вхождение ‘b’ на p(‘b’).

А если \(S =\) <<aabaс>>, \(T =\) <<bbbbb>>, то все вхождения ’a’ и ’c’ были заменены на ’b’.

Формат входных данных
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от ‘a’ до ‘z’.

Формат выходных данных
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите <<YES>>, на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите <<NO>>.

Магнитные игры

У Вовы есть любимый магнит. Вове очень нравится играть с ним на большой поляне, которую можно представить в виде прямоугольника \(n\) на \(m\) клеток.

Однажды он пришел играть на поляну с магнитом и потерял его в одной из клеток. Вова очень расстроился, но нашел решение — в каждую клетку поляны он положил компас, стрелка которого может принимать 8 положений: вверх, вверх-вправо, вправо, вниз-вправо, вниз, вниз-влево, влево и вверх-влево. Каждому положению стрелки соответствует его номер:

Стрелки принимают направление, близкое к направлению на магнит: если магнит лежит строго по диагонали от компаса, то его стрелка примет диагональное положение, иначе — более близкое к направлению на магнит из вертикального и горизонтального. Стрелка компаса в клетке с магнитом может быть направлена куда угодно.

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

Теперь Вова не знает, как ему найти свой магнит, и просит помощи у вас.

Формат входных данных
В первой строке входных данных записаны два целых числа через пробел \(n\) и \(m\) — размеры поляны (\(2 \le n, m \le 1500, nm \ge 6\)).

В следующих \(n\) строках описываются компасы на поляне.

В \(i\)-й строке записаны \(m\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le 8\)), \(j\)-е число в \(i\)-й строке обозначает направление стрелки компаса в \(j\)-й клетке \(i\)-й строки.

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

В первой строке выведите два числа \(x\) и \(y\) через пробел — номер строки и столбца клетки, в которой лежит магнит.

Во второй выведите два числа \(a\) и \(b\) через пробел  — номера горизонтали и вертикали, в которых действует аномалия.

В данном тесте магнит лежит в клетке \((2, 1)\), инвертируется горизонталь номер \(3\) и вертикаль номер \(3\).

Покраска холста

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из направления (вправо, вверх, влево, вниз) и цвета. Если \(S_{i,j} = (d, c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же смещается на одну клетку в направлении \(d\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на максимальное разрешенное число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<color \(i\) \(j\) \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

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

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<limit \(c\) \(x\)>> — выставить ограничение на максимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле уже больше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<block \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<settings \(i\) \(j\) \(d\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \((d, c)\), где \(d\) — направление перемещения, а \(c\) — цвет, в который затем будет раскрашена клетка, в которую робот переместится.

6. <<settings \(i\) \(j\) none>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = (\rightarrow, \mathtt{red})\), \(S_{1,2} = (\downarrow, \mathtt{blue})\), \(S_{2,2} = (\leftarrow, \mathtt{green})\) и \(S_{2,1} = (\uparrow, \mathtt{red})\), то при поступлении команды <<color \(1\) \(1\) blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Направления задаются строками <<right>> (вправо), <<up>> (вверх), <<left>> (влево), <<down>> (вниз). Цвета задаются заглавными буквами ‘R’ (красный), ‘G’ (зеленый), ‘B’ (синий) и ‘W’ (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд.

В первом примере из условия

1. Команда <<color 1 1 R>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = (\downarrow, \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = (\downarrow, \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<color 2 1 G>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \((\rightarrow, \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<limit B 0>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   RW
   GW
   RW

4. Затем <<color 2 2 R>> должен покрасить \((2, 2)\) в красный, но это бы привело к получению квадрата с цветами RWGR, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<color 2 2 B>> отрабатывает корректно, так как до этого было разрешено иметь на поле не больше \(1\) синей клетки. После чего, в соответствии с \(S_{2,2} = (\uparrow, \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   RG
   GB
   RW

Набор в космическую академию

Космическая Академия «Звёздный Путь» проводит ежегодный набор курсантов. Отбор кандидатов происходит по сумме баллов трёх вступительных испытаний (физическая подготовка, математика, астронавигация) и собеседования с приёмной комиссией.

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

Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом.

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

Для данного множества кандидатов определите полупроходной балл, а также ID кандидата с полупроходным баллом, который будет зачислен последним (займёт последнее свободное место).

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

В первой строке находятся два числа:

- N — количество кандидатов (натуральное число, не превышающее 10000)

- S — количество имеющихся мест (натуральное число, S ≤ N)

Каждая из следующих N строк содержит пять чисел:

- ID кандидата (натуральное число, не превышающее 10 000 000)

- три оценки по испытаниям (целые неотрицательные числа, не превышающие 100)

- балл за собеседование (целое неотрицательное число, не превышающее 10)

Гарантируется, что в исходных данных существует полупроходной балл.

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

Два целых числа через пробел: полупроходной балл и ID кандидата с полупроходным баллом, занявшего последнее место.
 

Примечание

В первом тестовом примере

- ID=1001: сумма экзаменов = 270, собеседование = 10 → проходит (проходной балл)

- ID=1002: сумма = 240, собеседование = 8 → полупроходной балл, проходит

- ID=1003: сумма = 240, собеседование = 5 → не проходит (собеседование меньше)

- ID=1004: сумма = 210, собеседование = 10

Мест: 2. Кандидат с ID=1001 проходит автоматически. Осталось 1 место, но с суммой 240 — два кандидата. Это полупроходной балл. Между ними выбираем по собеседованию: ID=1002 (собес 8) > ID=1003 (собес 5).

Во втором тестовом примере
Все кандидаты имеют одинаковую сумму баллов (240) и одинаковый балл за собеседование (5). Мест: 2. Выбираем по ID в порядке убывания: сначала 503, затем 502. Последний зачисленный — кандидат с ID=502.

Космический техосмотр

На орбитальной станции «Галактика-7» завершился ежегодный технический осмотр космических кораблей. По его результатам каждый корабль получил:

• Оценки трёх бортовых систем: двигательной, навигационной и системы жизнеобеспечения (по шкале от 2 до 5, где 2 — критическая неисправность, 5 — отличное состояние)
• Статус лицензии пилота: действующая или просроченная

Корабль допускается к полётам, если выполнены оба условия:

1. Все три бортовые системы имеют оценку 3 или выше
2. Лицензия пилота действующая

Корабль не допущен к полётам, если хотя бы одно из условий не выполнено.

Руководство станции решило предоставить возможность экстренного ремонта одной системы одному из кораблей. Корабль может претендовать на ремонт, если:

1. Лицензия пилота действующая
2. Ровно одна система имеет критическую неисправность (оценка 2), а две другие системы исправны (оценка 3 или выше)

Если таких кораблей несколько, выбирается тот, у которого наибольшая сумма оценок всех трёх систем (такой корабль ближе всего к допуску).

Гарантируется, что ровно один корабль удовлетворяет всем критериям отбора.
 

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

В первой строке находится число N — количество кораблей (1 ≤ N ≤ 1000).

Каждая из следующих N строк содержит пять целых чисел через пробел:

• ID — бортовой номер корабля (натуральное число, не превышающее 10⁸)
• S₁, S₂, S₃ — оценки трёх бортовых систем (каждая от 2 до 5)
• L — статус лицензии пилота (1 — действующая, 0 — просроченная)

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

Выведите два числа через пробел:

1. Количество кораблей, не допущенных к полётам
2. Бортовой номер корабля, который получит возможность экстренного ремонта

Сигналы со спутника

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

Элемент матрицы, который принял хотя бы один сигнал, считается активным. Элемент, который не принял ни одного сигнала, считается неактивным.

Для анализа качества связи нужно найти наибольшую непрерывную цепочку активных элементов в одной строке.

Определите наибольшую длину цепочки активных элементов, расположенных подряд в одной строке, и номер этой строки. Если таких строк несколько, укажите максимальный из их номеров.


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

В первой строке записано целое число N — количество принятых сигналов (1 ≤ N ≤ 10000).

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

Один и тот же элемент матрицы может получить несколько сигналов (координаты могут повторяться).

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

Два целых числа через пробел: наибольшая длина цепочки активных элементов и номер строки, в которой она находится.
 

Безлюдный отель

Закончился туристический сезон, и почти все отдыхающие разъехались. Теперь у Портье почти не осталось работы, и он уже успел заскучать. Поначалу он пытался скоротать время, снова и снова убирая номера, решая судоку и раскладывая пасьянсы. Но все это ему быстро надоело.

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

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

Например, если изначальное слово было <<letovo>>, то монетка будет перемещаться следующим образом (положение монетки в отражено жирным подчёркнутым шрифтом):

1. letovo

2. letovo

3. letovo

4. letovo

5. letovo

6. letovo

7. letovo

8. \(\dots\)

Обратите внимание, что в примере выше игра никогда не завершится: монетка будет бесконечно долго перемещаться между двумя буквами <<o>>.

Помогите Портье: по данному вам слову длины \(n\), состоящему только из строчных букв латинского алфавита, узнать завершается ли на этом слове придуманная им игра.

В первой строке дано число \(n\) (\(1 \le n \le 100\,000\)) — длина строки.

Во второй строке дана строка \(s\), строка состоит только из строчных букв латинского алфавита.

Выведите <<YES>>, если игра завершается, и <<NO>> — в противоположном случае.

A8.1 crosstab ячейки

pd.crosstab(df['Region'], df['income_level']) — что в ячейках полученной таблицы?

1. средние значения
2. суммы населения
3. количество строк (стран) для каждой пары (Регион, Доход)
4. проценты от общего

Найди баг

Аня открывает http://127.0.0.1:5050/hello и видит 404 Not Found. Её код:

from flask import Flask       # 1
app = Flask(__name__)         # 2
@app.route('Hello')           # 3
def hello():                  # 4
    return 'Привет, мир!'     # 5
app.run(port=5050)            # 6

В какой строке ошибка?

Форматирование текста: Московский Кремль

Ученик напечатал в текстовом процессоре следующий текст.

Далее он выполнил последовательно следующие действия:

1. Поставил курсор справа от точки после слова «метров».
2. Нажал клавишу Enter.
3. Выделил весь текст.
4. В свойствах меню «абзац» выставил значения:
   1) отступ первой строки: 1,5 см;
   2) выравнивание по ширине.

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

5. Выделил словосочетание «Московский Кремль» и нажал на кнопку Ж.
6. Выделил словосочетание «квадратных метров» и нажал клавишу backspace на клавиатуре. Напечатал «м2» (без кавычек).
7. Выделил цифру 2 в «м2» и нажал на кнопку x² (надстрочный символ).
8. Выделил словосочетание «Всемирного наследия ЮНЕСКО» и нажал на кнопку К.
9. Выделил весь текст.
10. Установил шрифт Times New Roman (с засечками).

Какой из предложенных вариантов текста мог получиться после выполнения этих действий? В ответе укажите номер варианта.

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Форматирование текста: Каспийское море

Ученик напечатал в текстовом процессоре следующий текст.

Далее он выполнил последовательно следующие действия:

1. Поставил курсор справа от точки после слова «километров».
2. Нажал клавишу Enter.
3. Выделил весь текст.
4. В свойствах меню «абзац» выставил значения:
   1) отступ первой строки: 1 см;
   2) выравнивание по ширине.

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

5. Выделил словосочетание «Каспийское море» (первое вхождение) и нажал на кнопку Ж.
6. Выделил словосочетание «квадратных километров» и нажал клавишу backspace на клавиатуре. Напечатал «км2» (без кавычек).
7. Выделил цифру 2 в «км2» и нажал на кнопку x² (надстрочный символ).
8. Выделил словосочетание «пяти государств» и нажал на кнопку К.
9. Выделил весь текст.
10. Установил шрифт Times New Roman (с засечками).

Какой из предложенных вариантов текста мог получиться после выполнения этих действий? В ответе укажите номер варианта.

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Какое из утверждений о ограничении уникальности данных (UNIQUE) в SQLite является верным?

Какое из утверждений о ограничении уникальности данных (UNIQUE) в SQLite является верным?

Ответы:

1. Ограничение UNIQUE допускает несколько одинаковых значений в столбце.
2. Ограничение UNIQUE применяется только к числовым столбцам.
3. Ограничение UNIQUE позволяет одному столбцу иметь несколько NULL значений.
4. В таблице можно применить несколько ограничений UNIQUE к разным столбцам.

ООП-6

Что называют атрибутами класса?

1. Только переменные класса
2. Экземпляры (объекты) класса
3. Только методы класса
4. Переменные и имена методов (ссылки на методы) класса

ООП-2

 Каким термином из ООП можно охарактеризовать ограничение доступа к элементам класса?

1. маскировка
2. наследование
3. инкапсуляция
4. скрытность
5. полиморфизм

Что такое Интегрированная среда разработки (IDE)?

Что такое Интегрированная среда разработки (IDE)?

1) Программа для создания графических интерфейсов.

2) Система управления базами данных.

3) Средство упрощения разработки и отладки программ.

4) Инструмент для автоматического тестирования кода.

Каким образом компилятор C++ обрабатывает файлы исходного кода при компиляции программы?

Каким образом компилятор C++ обрабатывает файлы исходного кода при компиляции программы?

1) Последовательно просматривает каждый файл .cpp, проверяя их соответствие правилам C++ и переводя код в инструкции машинного языка.

2) Переносит код на другие уровни компиляции для оптимизации производительности программы.

3) Использует файлы .obj для хранения только ошибок компиляции и их номера строк.

4) Импортирует код из файлов .obj в код других программ для многократного использования.

38457

Выберите неверное утвеждение:

1) Возможно инициализировать нестатические поля данных в статическом конструкторе.
2) Можно инициализировать статические поля данных в нестатическом конструкторе, но после этого они теряют свой статический характер.
3) Можно инициализировать статические поля данных как в статических, так и в нестатических конструкторах, но статические поля данных теряют свой статический характер.
4) Возможно инициализировать нестатические поля данных в нестатическом конструкторе.

31822

Выберите тип устройства Принтер

1) Память
2) Ввод
3) Вывод
4) Не знаю

24646

Готовый вариант оформления презентации называется

1. заготовкой
2. дизайном
3. монтажом
4. шаблоном

23357

Блок обработки данных в блок-схеме изображается с помощью ...

1. овала
2. параллелограмма
3. ромба
4. прямоугольника

21933

Группа смежных ячеек называется

1. столбцы
2. строки
3. ячейка
4. диапазон ячеек

21920

В табличном процессоре связи между числами организованы с помощью

1. формул
2. ссылок
3. адресации
4. гиперссылок

21917

Каково основное назначение табличного процессора?

1. представление числовой информации в табличной форме
2. создание таблиц и диаграмм
3. автоматизация расчетов в таблицах
4. создание таблиц

21808

Можно ли в текстовом процессоре создавать таблицы?

1. нет
2. да
3. не во всех

21799

Разбиение текста на несколько колонок называется

1. проверкой правописания
2. форматированием
3. редактированием
4. стилизацией

21797

Изменение нескольких букв или слов в тексте называется

1. проверкой правописания
2. форматированием
3. редактированием
4. стилизацией

21794

Программа, предназначенная для создания, просмотра, редактирования, форматирования, сохранения и печати текстовых документов, которая может содержать объекты
различной природы - это

1. текстовый редактор
2. текстовая программа
3. текстовый процессор
4. текстовый обработчик

21761

Можно ли открыть файл собственного формата в бесплатной программе?

1. да
2. нет
3. не всегда
4. в случае, если программа поддерживает этот формат

21705

Что из перечисленного является устройством ввода графической информации?

1. клавиатура
2. монитор
3. сканер
4. принтер

21519

Какое из расширений в списке используется для файлов архиватора:
1. doc;
2. jpeg;
3. zip; 
4. txt;

1649

Центральный процессор - "мозг" компьютера - входит в состав:
1) монитора
2) клавиатуры
3) системного блока
4) нет правильного ответа

1619

Всегда ли проверка правописания дает корректный результат?

1) Да, всегда.
2) Нет, она выдает только подозрения на ошибки.
3) Нет результат всегда неправильный.
4) Да, результат всегда корректный

1610

Как вставить таблицу?

1)Таблица - Вставить - Таблица
2) Вставка - Таблица
3) Сервис - Вставить - Таблица

1608

Указать команду(ы), при выполнении которой(ых) выделенный фрагмент текста попадает в буфер обмена:
1) вставить
2) заменить
3) проверить орфографию
4) вырезать и копировать

1604

     В текстовом редакторе при задании параметров страницы устанавливаются:

1601

Редактирование текста представляет собой:

1596

Как изменится текст "Маша мыла раму" после выполнения нижеприведенного алгоритма?
Алгоритм:
1) Подогнать курсор к началу слова "Маша"
2) Начать выделение
3) Подогнать курсор к концу слова "Маша"
4) Закончить выделение
5) Выбрать курсивное начертание

Варианты ответов:

1) Маша мыла раму
2) Маша мыла раму
3) Маша мыла раму
4) Маша мыла раму

1591

В процессе редактирования текста, изменяется

1) размер шрифта
2) параметры абзаца
3) последовательность символов, слов, абзацев
4) параметры страницы

1298

Пользователь работал с каталогом C:\Физика\Задачи\Кинематика . Сначала он поднялся на один уровень вверх, затем еще раз поднялся на один уровень вверх и после этого спустился в каталог Экзамен . Запишите полный путь каталога, в котором оказался пользователь.

1235

При перемещении или копировании в электронной таблице относительные ссылки:

1. преобразуются вне зависимости от нового положения формулы;
2. преобразуются в зависимости от длины формулы;
3. не изменяются;
4. преобразуются в зависимости от нового положения формулы.

1231

Использование маркера заполнения позволяет копировать в ячейки:

1)функции
2)форматы
3)данные
4)ответы 1-3 верны

1221

Основным элементом рабочего листа в электронных таблицах является:
1) ячейка;
2) столбец;
3) строка;
4) строка формул.

1213

Активная ячейка - это ячейка:

1)   для записи команд
2)   содержащая формулу, включающую в себя имя ячейки, в которой выполняется ввод данных
3)   формула в которой содержатся ссылки на содержимое зависимой ячейки
4)    в которой выполняется ввод команд.

1206

Электронная таблица - это

1) прикладная программа, предназначенная для обработки структурированных в виде таблицы данных
2) прикладная программа для обработки кодовых таблиц
3) устройство ПК, управляющее его ресурсами в процессе обработки данных в табличной форме
4) системная программа, управляющая ресурсами ПК при обработке таблиц

604

Что НЕ относится к режиму работы процессора?

1) запись-чтение данных из оперативной памяти
2) внесение изменений в программное обеспечение
3) пересылка данных на устройство вывода информации
4) обработка вводимых данных

137

Существует способ выбрать все экземпляры стиля в своем документе, нажав одну кнопку.

Шифр mint

Многие старейшие шифры основаны на замене букв на числа, например, в шифре A1Z26 каждая буква заменяется на её порядковый номер в алфавите. Вдохновившись этой идеей, первоклассник Петя решил придумать свой шифр-замену. Он хочет каждую букву от <<A>> до <<R>> (первые \(18\) букв латинского алфавита) заменять на одно из чисел \(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90\). Числа выбраны так, чтобы при дешифровке легко разделить последовательность цифр на коды букв, причём весь алфавит Петя не смог использовать, ибо сотни он ещё не узнал.

Если применить один из таких шифров к строке, он получит натуральное число. Если использовать разные шифры, удовлетворяющие условию, то будут получаться разные числа.

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

Программа получает на вход непустую строку \(s\), состоящую из прописных букв латинского алфавита от <<A>> до <<R>>, длина строки не превышает 1000 символов.

Программа должна вывести одно число — шифр строки \(s\). Обратите внимание, число может быть длинным.

Решения, правильно работающие, когда строка состоит не более чем из \(4\) символов, будут оцениваться в \(20\) баллов.

Решения, правильно работающие, когда строка состоит из букв <<A>> и <<B>>, будут оцениваться в \(20\) баллов.

Решения, правильно работающие, когда строка состоит из букв от <<A>> до <<I>>, будут оцениваться в \(44\) балла.

API: сводка погоды на сутки

Вам на вход подаётся JSON-ответ от API погоды с разделами current (текущая температура) и hourly (почасовой прогноз на 24 часа).

Составьте сводку погоды за сутки.

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

Одна строка — JSON-объект с разделами current и hourly.

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

Ровно 6 строк:

=== ПОГОДА НА СУТКИ ===
Сейчас: T°C
Максимум: X°C
Минимум: Y°C
Средняя: A°C
Размах: R°C

где T — текущая температура из current, X/Y/A — максимум, минимум и среднее по массиву hourly (среднее округлить до 1 знака), R — разница между максимумом и минимумом.

API: средняя температура

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом (раздел hourly, массив temperature_2m из 24 значений).

Посчитайте среднюю температуру за сутки, округлите до одного знака после запятой.

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

Одна строка — JSON-объект с разделом hourly.

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

Одна строка:

Средняя: X°C

где X — число с одним знаком после запятой.

API: температура в заданный час

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом (раздел hourly) и номер часа.

Раздел hourly содержит два параллельных массива по 24 элемента: time (время в формате "2026-04-16T15:00") и temperature_2m (температура).

Выведите строку:

Температура в HH:00: X°C

где HH:00 — время, X — целое число температуры.

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

Первая строка — JSON-объект с разделом hourly.
Вторая строка — целое число от 0 до 23 (номер часа).

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

Одна строка в указанном формате.

API: достань температуру

Вам на вход подаётся JSON-ответ от API погоды — это словарь с разделом current, внутри которого хранятся текущие метеоданные.

Выведите значение температуры (поле temperature_2m).

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

Одна строка — JSON-объект.

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

Одно число — температура (как оно записано в JSON, без дополнительного форматирования).

Примечание

В реальной программе эти данные вы бы получили через requests.get(...).json(), а здесь они подаются на вход. Парсить JSON можно так:

import json
data = json.loads(input())

Раскрытие скобок и вычисление

Дано алгебраическое выражение со скобками (полином степени не выше 3) и целое число \(x_0\). Выполните два действия с помощью SymPy:

1. Раскройте скобки — приведите выражение к стандартному виду полинома (без скобок, слагаемые по убыванию степени).

2. Вычислите значение выражения при \(x=x_0\).

Формат ввода

Строка 1: выражение в синтаксисе Python (** — возведение в степень, * — умножение, переменная x). Строка 2: целое число \(x_0\) (\(-100\le x_0\le 100\)).

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

Ровно 2 строки:

expanded: <выражение>
value: <число>

(x + 3)**2
2

expanded: x**2 + 6*x + 9
value: 25

Разбор. \((x+3)^2 = x^2+6x+9\). Значение при \(x=2\): \(4+12+9=25\).

Подсказки. Для разбора строки: parse_expr(s, ...). Раскрытие скобок: expand(expr). Подстановка: expr.subs(x, x0).

Полный анализ ДНК-фрагмента

Дана строка ДНК, состоящая из символов A, T, G, C. Длина строки кратна 3. Выполните следующие вычисления:

1. Длина последовательности.

2. GC-состав — процентная доля нуклеотидов \(G\) и \(C\): \[\mathrm{GC\%} = \frac{|G| + |C|}{n} \times 100,\] где \(|X|\) — количество символов \(X\), \(n\) — длина строки. Округлить до 2 знаков после запятой.

3. Обратная комплементарная цепь (reverse complement). Комплементарность: \(A \leftrightarrow T\), \(G \leftrightarrow C\); затем цепь разворачивается.

4. GC-богатые кодоны — количество кодонов (трёхбуквенных блоков), в которых два или три нуклеотида являются \(G\) или \(C\).

5. Наиболее частый нуклеотид. При ничьей вывести тот, который идёт первым в алфавитном порядке (A < C < G < T).

Формат ввода. Одна строка — последовательность ДНК (только заглавные A, T, G, C; \(6 \le n \le 300\); \(n\) кратно 3).

Формат вывода. Ровно 5 строк в следующем порядке:

length: <целое>
gc: <вещественное, 2 знака>
rc: <строка>
gc_rich_codons: <целое>
most_frequent: <символ>

Пример ввода:

ATGGGCCCTATGAAA

Пример вывода:

length: 15
gc: 46.67
rc: TTTCATAGGGCCCAT
gc_rich_codons: 2
most_frequent: A

Разбор примера. Последовательность: ATG GGC CCT ATG AAA.

GC-состав: \((3+3+2+1)/15 = 9/15 \approx 46.67\%\). Кодоны GGC (\(3\,G/C\)) и CCT (\(2\,G/C\)) — итого 2 GC-богатых кодона. Наиболее частый нуклеотид: \(A=5, G=4, C=3, T=3\) — лидирует \(A\).

Marathon

Беси участвует в марафоне.
Маршрут марафона состоит из N контрольных точек (3 <= N <= 500),
которые надо посетить по порядку, причём контрольная точка 1 -
старт, контрольная точка N - финиш.

Беси решил пропустить до K (K сократить себе маршрут. Она не может пропустить контрольные точки
1 и N.

Определите минимальное расстояние которое пробежит Беси, если она
может пропустить до K контрольных точек.

Поскольку марафон проводится на улицах Манхэттена, то и расстояние
между точками (x1, y1) и (x2, y2) нужно определять манхэттенское:
|x1-x2| + |y1-y2|.

INPUT: (файл marathon.in)

В первой строке задаются N и K.
Каждая из следующих N строк содержит два разделённых пробелом целых
числа x и y, представляющих контрольную точку (-1000 <= x <= 1000,
-1000 <= y <= 1000). Контрольные точки даны в порядке, в котором они
должны посещаться.

Заметим, что маршрут марафона может самопересекаться несколько раз
и некоторые контрольные точки могут быть в одной и той же позиции.
Когда Беси пропускает контрольную точку в некоторой позиции, она
пропускает только экземпляр контрольной точки, а не все контрольные
точки в этой позиции.

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

Выведите миниальное расстояние, которое Беси может пробежать,
пропустив до K контрольных точек. В данном примере, пропустив
точки (8,3) и (10,-5) она пробежит минимальное растояние, равное 4.

Crosswords

Беси любит разгадывать кроссворды.
Однако её сестра Эльза пролила молоко на кроссворд,
и теперь Вам предстоит его восстановление (номеров
загаданных слов).

Вам даётся кроссворд, как решётка N*M (3 <= N <=
50, 3 <= M <= 50). Некоторые из клеток пусты (обычно они
белые), а некоторые заблокированы (обычно они чёрные).

Теперь процесс присвоения номеров загаданным словам -
это простой процесс из двух логических шагов:

Шаг 1: Для каждой ячейки мы определяем, начинает ли она
горизонтальное загаданное слово, или вертикальное
загаданное слово. Чтобы ячейка начинала горизонтальное
загаданное слово, нужно, чтобы её левая соседка была
заблокированной ячейкой или лежала вне кроссворда и две
клетки вправо от неё должны быть пустыми. (То есть
горизонтальное загаданное слово всегда содержит 3 или более
символов). Правила для ячейки, начинающей вертикальное
загаданное слово аналогичны: ячейка сверху должна быть
заблокирована или вне кроссворда и две клетки вниз
должны быть пустыми.

Шаг 2: Мы назначаем номер каждой ячейке, которая начинает
слово, последовательно от 1 в том же порядке, в котором
мы читаем книгу.
В первой строке назначаем числа слева направо, затем во
второй строке назначаем числа слева направо и т.д.
Числа назначаются только ячейкам, начинающим слова.

Например, рассмотрим кроссворд, где пустые ячейки отмечены
символами '.'. а блокированные ячейки отмечены символами '#'.

...
#..
...
..#
.##

Ячейки, которым могут быт присвоены номера
горизонтальных или вертикальных загаданных слов
помечены символами !.

!!!
#..
!..
..#
.##

Номера должны быть таковы:

123
#..
4..
..#
.##

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

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

Первая строка ввода содержит N и M, разделённые
одиночным пробелом.

Последующие N строк ввода описывают строки
решётки. Каждая состоит из M символов, каждый из которых
либо '.' (пустая ячейка) либо '#' (блокированная ячейка).

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

На первой строке выведите количество загаданных слов.
На каждой из оставшихся строк выведите строку и колонку
дающую позицию одного слова (в порядке, описанном выше).
Верхняя левая ячейка имеет позицию (1,1). Нижняя правая
ячейка имеет позицию (N,M).

Cowmpetency

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует \(N\) (\(2 \leq N \leq 10^5\)) коров на эту позицию. После интервью \(i\)-го кандидата он назначает целое число "уровень компетенции" \(c_i\) от \(1\) дo \(C\) включительно (\(1 \leq C \leq 10^9\)).

Поскольку ФД интервьюировал много коров, он не помнит все \(c_i\). Однако он помнит \(Q\) (\(1 \leq Q < N\)) пар чисел \((a_j, h_j)\) где корова \(h_j\) компетенция которой была строго больше, чем уровень компетенции коров от \(1\) до \(a_j\) (\(1 \leq a_j < h_j \leq N\)).

ФД говорит Вам последовательность \(c_1, \dots, c_N\) (где \(c_i = 0\) означает, что он забыл уровень компетенции коровы \(i\), и \(Q\) пар \((a_j, h_j)\). Помогите ему определить лексикографически минимальную последовательность уровней компетенции, соответствующую этой информации или указать, что такой последовательности не существует. Последовательность чисел называется лексикографически меньше другой последовательности если в ней меньшее число не первой позиции, где эти последовательности различаются.

Каждый ввод содержит \(T\) \((1 \leq T \leq 20)\) независимых подтестов. Гарантируется, что сумма \(N\) по всем подтестам не превысит \(3 \cdot 10^5\).

Stamp Grid

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером \(N \times N\) ячеек, где определённые ячейки закрашиваются, а другие - нет. Этот холст может быть представлен массивом символов \(N\times N\) (\(1\le N\le 20\)). The \(i\)-ый вход \(j\)-ой колонки массива равен символу '*', если холст содержит чернила в этой ячейке и символ '.' в противном случае.

У Беси есть план рисунка, а Фермер Джон дал ей штамп размером \(K\times K\) (\(1\le K\le N\)) который она может использовать для закраски холста размером \(N \times N\). Беси может поворачивать штамп на \(90^{\circ}\) по часовой стрелке и применять его для закраски холста в любом месте, если штамп помещается целиком на холсте. Формально, Беси выбирает такие целые числа \(i,j\), что \(i \in [1,N-K+1]\) и \(j \in [1, N-K+1]\); и затем для каждого \((i',j')\) такого, что \(1 \le i', j' \le K\), ячейка холста \((i+i'-1, j+j'-1)\) закрашивается в чёрный цвет, если в штампе было чернило в позиции \((i', j')\). Беси может поворачивать свой штамп в любой момент между закрашиваниями. Если ячейку закрасили она остаётся закрашенной навсегда.

ФД интересно может ли Беси создать свой рисунок, используя его штамп. Для каждого из \(T\) (\(1 \le T \le 100\)) подтестов помогите ФД получить ответ.

Do You Know Your ABCs_

Коровы фермера Джона ежедневно собираются на "видео-болталки" на платформе "mooZ". Они придумали простую игру числами:

У Элзи есть три положительных целых числа \(A\), \(B\), \(C\) (\(A\le B\le C\)). Эти целые числа предполагаются как секретные, поэтому она не говорит их своей сестре Беси. Вместо этого, она говорит Беси семь необязательно различных целых чисел в интервале \(1 \ldots 10^9\), подсказывая, что они есть \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\), \(A+B+C\) в некотором порядке.

По заданному списку из этих 7 чисел, помогите Беси определить \(A\), \(B\), \(C\). Можно доказать, что ответ уникален.

Team Tic Tac Toe

У Фермера Джона 26 коров, имена которых начинаются с различных букв алфавита поэтому ФД обычно называет их по первым буквам \(A \ldots Z\).

Недавно эти коровы познакомились с игрой "крестики-нолики", но им не понравилась игра только с двумя участниками, поэтому они придумали модификацию этой игры чтобы одновременно множество коров могли играть. Как и в стандартной игре, игра ведётся на доске \(3 \times 3\) , только вместо X и 0 каждый квадратик помечается символом \(A \ldots Z\) той коровы, которая сделала ход в данное поле.

Пример доски с такой игрой:

COW
XXO
ABC

Коровы заполнили все 9 квадратиков, теперь они не могут понять, кто же победил в этой игре. Понятно, как и в обычной игре "крестики-нолики", если одна корова заняла строку, столбец или диагональ, она выиграла. Однако поскольку игроков может быть больше двух, они решили позволять коровам формировать команды из двух коров. Команда объявляется победительницей, если строка, столбец или диагональ состоят только из символов коров одной команды.

Помогите коровам определить, сколько одиночных коров или команд из двух коров могут одержать победу. Заметим, что один и тот же квадратик доски может быть использова в разных вариантах объявления победы.

The Bessie Shuffle (gold)

Беси практикуется в карточных фокусах. Она уже освоила Беси-тасование – тасование M (2 <= M <= 100,000) карт, так чтобы i-ая карта сверху становилась P[i]-ой картой сверху.
Теперь она переходит на бОльшие колоды. У неё есть колода из N (M <= N <= 1,000,000,000) карт, последовательно пронумерованных от 1 до N. Она тасует её следующим образом: берёт первые M карт, и выполняет их Беси-тасование, затем снова кладёт их наверх колоды. Далее она удаляет верхнюю карту из колоды и кладёт ее на стол значением вниз. Она повторяет этот процесс, выкладывая забираемые карты поверх друг друга, пока карты не кончатся. Когда у неё в исходной колоде остаётся меньше чем M карт, она прекращает выполнять Беси-тасование, но продолжает брать верхнюю карту и выкладывать её поверх ранее взятых.
Беси знает, что изначально колода находится в отсортированном порядке, Причём карта 1 наверху, карта 2 следующая и т.д. По заданному описанию Беси-тасования, вычислите какие карты окажутся на Q (1 <= Q <= N, Q <= 5,000) различных указанных позициях колоды.
В 50% тестов N<=100,000.
PROBLEM NAME: shufflegold
Формат входных данных
* Строка 1: Числа N, M и Q разделенные одиночными пробелами
* Строки 2..1+M: Строк i+1 указывает позицию сверху колоды, P[i], на которую переместиться i-ая карта после Беси-тасования (1 <= P[i] <= M).
* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число q_i описывающее i-ый запрос. Вы должны вычислить значение на карте, которая окажется в позиции q_i сверху (1 <= q_i <= N).
Формат выходных данных
* Строки 1..Q: На i-ой строке, выведите одно целое число, указывающее карту, которая окажется на позиции q_i сверху.
Примечание
Тасование происходило так
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выкладываем 2 значением вниз) [3, 1, 4, 5] -> [1, 4, 3, 5] (выкладываем 1 значением вниз) [4, 3, 5] -> [3, 5, 4] (выкладываем 3 значением вниз) [5, 4] (выкладываем 5 значением вниз) [4] (выкладываем 4 значением вниз)
Финальный расклад [4, 5, 3, 1, 2]

Математический калькулятор из строки

Дана строка с выражением.
1.    Преобразовать её в символьное выражение
2.    Упростить
3.    Вывести результат в символьном виде
 

ПИКСЕЛЬНАЯ МОЗАИКА В СТИЛЕ 8-БИТ

Создадим эффект старой 8-битной графики! Разделим фото на блоки k×k и каждый блок заменим на один пиксель со средней яркостью. Программа получает на вход размеры фото n и m (оба делятся на k нацело), затем n строк по m чисел - пиксели, затем размер блока k. Программа должна вывести "пикселизированное" изображение: (n/k) строк по (m/k) чисел. Каждое число - это среднее арифметическое блока k×k из исходного изображения, округлённое вниз.

Самый используемый признак

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

Формат входных данных
JSON с деревом решений.

Формат выходных данных
Одно число — индекс самого используемого признака.

Подсчёт узлов дерева

Дано дерево решений в формате JSON. Подсчитайте количество внутренних узлов (type = "decision") и листьев (type = "leaf").

Формат входных данных
JSON с полем "nodes" — список узлов.


Формат выходных данных
Два числа через пробел: количество внутренних узлов и количество листьев.

Анализ заказов в кафе

Кафе хранит данные о заказах за день в формате JSON. Каждый заказ содержит список позиций с ценами.
Вычисли общую выручку кафе за день (сумму всех цен всех позиций всех заказов).

Формат входных данных
JSON-объект с полем `"orders"` — массив заказов. Каждый заказ имеет:
- `"order_id"` — номер заказа
- `"items"` — массив позиций, каждая позиция имеет `"name"` и `"price"`

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

Поиск отличников

В школьной системе хранятся данные об учениках в формате JSON.
Найди и выведи имена всех отличников — учеников, у которых средний балл (average_score) больше или равен 90.

Формат входных данных
JSON-объект с полем `"students"` — массив учеников. Каждый ученик имеет поля:
- `"name"` — имя ученика
- `"class"` — класс
- `"average_score"` — средний балл (число от 0 до 100)

Формат выходных данных
Имена отличников, каждое на отдельной строке, в том порядке, в котором они встречаются во входных данных.
Если отличников нет — выведи Нет отличников.
 

Гирлянда

Часть 1

Напиши функцию lantern(size, c), которая рисует фонарик.

Параметры функции:

• size — диаметр круга (число)
• c — цвет фонарика (строка)

Порядок рисования

1. Подвес — коричневый ("brown") закрашенный прямоугольник:
   • ширина: 10
   • высота: 20
2. Круг — закрашенный круг под подвесом:
   • цвет: параметр c
   • диаметр: параметр size
   • круг рисуется так, чтобы он был по центру подвеса

Часть 2

красн жёлт  зелён красн жёлт  зелён
 40    35    45    35    40    35

Пример вызова

lantern(50, "red")    # красный фонарик диаметром 50
lantern(30, "yellow") # жёлтый фонарик диаметром 30

Подсказки

• Используй begin_fill() и end_fill() для заливки
• Для круга используй circle(-size/2) — минус нужен, чтобы круг рисовался справа от черепашки
• Не забудь поднимать и опускать перо (pu(), pd()) в нужных местах

Три дуги

Нарисуйте цветной рисунок из трёх дуг (каждая дуга это полуокружность - угол 180 градусов)

1. Начало в (0, 0).
2. Фиолетовая дуга радиусом 150 (рисуется вверх вправо).
3. Желтая дуга радиусом 100.
4. Зеленая дуга радиусом 50.
5. Жёлтая и зеленая дуги находятся внутри фиолетовой так как показано на рисунке

У каждой дуги цвет контура и цвет заливки одинаковый

Н

Нарисуйте букву "H" из трёх линий

• Начальная точка: (0, 0)

• Черепашка идёт вверх 100 (левая вертикаль), затем перемещается в (0, 50) без рисования,

• Рисует горизонтальную линию вправо 50 (перекладина),

• Перемещается в (50, 0) без рисования,

• Рисует вертикаль вверх 100 (правая).

Буква должна состоять ровно из трех линий!

Задача. Время-оценка

Создайте модель, которая предсказывает оценку на экзамене в зависимости от потраченных часов на подготовку.

Формат входных данных
В первой строке записано натуральное число n (n <= 1000). Вторая и третья строки содержат соответственно время подготовки (в часах) и количество баллов набранных на экзамене i-м студентом (1<=i<=n). Все числа положительные целые. В первой строке числа не превышают 10, во второй строке - не превышают 100.

Выполните следующие задания
1. Создайте DataFrame из входных данных
2. Обучите модель LinearRegression
3. Предскажите оценку для студента, который готовился 5.5 часов
4. Во второй строке выведите через пробел два числа: коэффиценты k и b линии регрессии
6. В третьей строке выведите время подготовки, необходимое для получения чтобы получить 75 баллов 

Все числа необходимо вывести с точностью до одного знака после запятой

Обои и дипломы

Родители Андрея решили поклеить на одну из стен в его комнате новые обои. Высота стены n сантиметров, а ширина m сантиметров. К сожалению, обои, выбранные родителями, Андрею не понравились, и он решил их чем-нибудь закрыть. Так как он участвовал в большом количестве олимпиад, у него накопилось много дипломов. Все дипломы у Андрея одинаковые это прямоугольники высотой a сантиметров и шириной b сантиметров. Помогите Андрею узнать, сколько квадратных сантиметров обоев он сможет завесить дипломами, если не будет их разрезать и переворачивать. Все дипломы должны целиком размещаться внутри стены и не накладываться друг на друга.
Формат входных данных
В первой строке входных данных находится целое число n (1 n ≤ 2 ·10⁹) высота стены.
Во второй строке находится целое число m (1 ≤ m ≤ 2 · 10⁹) ширина стены.
В третьей строке находится целое число a (1 ≤ a ≤ 2 ·10⁹) высота диплома.
В четвёртой строке находится целое число b (1 ≤ b ≤ 2 · 10⁹) ширина диплома.
Формат выходных данных
Выведите одно целое число площадь части стены, которая будет закрыта дипломами, если их не поворачивать, не обрезать и не накладывать друг на друга.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в С и С++, тип long в Java и С#).

Замечание
В примере из условия можно разместить 6 дипломов, суммарная площадь которых равна 12 квадратным сантиметрам. Большее число дипломов разместить нельзя, они будут вылезать за границы стены.