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

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

В 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) — длины имеющихся кусков каната.

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

Ввод	Вывод
2 10 25 50	55
5 2 4 5 6 7 8	14

Алгоритмы сортировки Задача на реализацию

✓ 2✗ 16—Войти и решать

Вращающаяся пластина#30715

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

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

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 10⁶ по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа α_i и β_i , где α_i — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а β_i— максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите α_i = β_i = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10⁻⁶ .

Ввод	Вывод
4 0 0 -3 -3 0 -6 3 -3 3 -8 0 -2 0 2 -1	360.000000000000 360.000000000000 45.000000000000 225.000000000000 251.565051177078 18.434948822922

Пояснение

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

Вычислительная геометрия Задача на реализацию

✓ 0✗ 4—Войти и решать

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

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

Будем считать, что любой телефонный номер состоит из 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».

Ввод	Вывод
2 7 3 981 3517 812 351 3 34712 1234 963 8 79818266456 35196328463 78122472557 01234567890 73517960326 35134712239 35112342013 78120203040	+7(981)826-64-56 +351(963)284-63 +7(812)247-25-57 Incorrect +7(3517)96-03-26 +351(34712)239 +351(1234)20-13 Incorrect

Задача на реализацию Разбор случаев Строки

✓ 0✗ 2—Войти и решать

Очередная задача про запросы в массиве#29654

Вам дается массив a размера n и q запросов к нему. Есть запросы двух типов:

1 l_i r_i — осуществить циклический сдвиг отрезка [l_i, r_i] вправо. То есть, для каждого такого x, что l_i ≤ x < r_i, a_x_+ 1 становится равным прежнему значению a_x, а a_li становится равным прежнему значению a_ri;
2 l_i r_i — перевернуть отрезок [l_i, r_i].

Необходимо вывести массив после обработки всех запросов.

Входные данные
В первой строке записаны два целых числа n и q (1 ≤ n, q ≤ 2·10⁵).
Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
Дальше идут q строк. В i-й из них записаны три целых числа t_i, l_i, r_i, где t_i — тип i-го запроса, [l_i, r_i] — отрезок, на котором запрос выполняется (1 ≤ t_i ≤ 2, 1 ≤ l_i ≤ r_i ≤ n).

Выходные данные
Выведите m чисел, i-е из которых равно числу на позиции b_i после обработки всех запросов.

Ввод	Вывод
6 3 1 2 3 4 5 6 2 1 3 2 3 6 1 1 6	1 3 2 6 5 4

Задача на реализацию Структуры данных

✓ 3✗ 01 000средняяВойти и решать

Circular Barn#29547

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.

ФД хочет разместить ровно ri коров в комнате i (1≤r_i≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.

ФОРМАТ ВВОДА:

Первая строка ввода содержит n и k. Последующие n строк содержат r₁…r_n.

ФОРМАТ ВВОДА:

Выведите минимальное суммарное расстояние пройденное коровами.

Ввод	Вывод
6 2 2 5 4 2 6 2	14

ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.

Динамическое программирование Динамическое программирование: два параметра Задача на реализацию Рекурсия

✓ 1✗ 1—Войти и решать

The Lost Cow#27223

Фермер Джон потерял свою корову Беси и хочет её найти.

К счастью через ферму ведёт только одна длинная дорога и и ФД знает, что Беси находится в некоторой точке на этой дороге. Если мы рассмотрим эту дорогу как числовую прямую, ФД сейчас находится в точке x, а Беси сейчас находится в точке y (неизвестной ФД). Если бы ФД знал, где Беси, то бы мог идти прямо к ней, пройдя расстояние |x−y|. К несчастью, сейчас темно, и ФД ничего не видит. Единственный способ, которым он может найти Беси - ходить вперёд и назад, пока не наткнётся на Беси.

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

Рекомендуемая стратегия такова: двинуться в позицию x+1, затем изменить направление движения на противоположное и перейти в позицию x−2, затем в позицию x+4 и т.д., двигаясь "большим зигзагом", каждый раз двигаясь в два раза дальше от своей первоначальной позиции, чем в прошлый раз. Такой подход гарантирует, что он пройдёт в худшем случае 9 раз прямое расстояние от себя до Беси |x−y|. И это - наименьшее число, гарантируемое в худшем случае.

ФД хочет проверить это утверждение. Вам даны x и y, вычислите общее расстояние пройденное в поиске по описанному выше алгоритму "большой зиг-заг", пройденное до момента находки Беси.

ФОРМАТ ВВОДА :

Единственная строка ввода содержит два различных разделённых одним пробелом целых числа x и y. Оба числа в интервале 0…1,000.

ФОРМАТ ВЫВОДА:

Выведите одну строку, содержащую расстояние пройденное ФД до достижения Беси.

Ввод	Вывод
3 6	9

Вычисление по заданной формуле Задача на реализацию

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

Where's Bessie?#27222

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

Картинка, получаемая камерой, может быть описана решёткой из N×N символов, каждый в интервале A…Z, представляющих один из 26 возможных различных цветов. ФД считает наилучшим такой алгоритм распознавания коров: PCL (возможное размещение коровы) - это прямоугольник на решётке (возможно вся решётка) со сторонами параллельными сторонам решётки, не содержащий внутри других PCL и обладающий следующим свойством: внутри этого прямоугольника должны присутствовать ровно два цвета, один формирует непрерывный регион, а другой формирует два или более непрерывных регионов.

Например, такой образ

AAAAA

ABABA

AAABB

есть PCL, поскольку символы A формируют непрерывный регион, символы B форрмируют более одного непрерывного региона. Интерпретация - это корова с цветом A и с пятнами цвета B.

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

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

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер решётки (1≤N≤20). Следующие N строк описывают образ, каждая состоит из N символов.

ФОРМАТ ВЫВОДА:

Количество PCL в образе.

Ввод	Вывод
4 ABBC BBBC AABB ABBC	2

Задача на реализацию Обход в глубину Перебор

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

COWBASIC#27217

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

COWBASIC - это простой, элегантный язык. У него две основные черты: сложение и циклы. Для решения проблемы переполнения, Беси выполняет все операции сложения по модулю 10⁹+7. MOO-цикл исполняет блок кода фиксированное количество раз. Циклы и сложения могут быть вложенными.

Вам дана COWBASIC-программа, определите результат её выполнения - число, которое она вернёт.

ФОРМАТ ВВОДА:

Вам дана COWBASIC-программа длиной не более 100 строк, каждая строка длиной не более 350 символов. COWBASIC-программа это список операторов.

Имеется три типа операторов:

<переменная> = <выражение>

<литерал> MOO {

<список операторов>

}

RETURN <переменная>

Имеется три типа выражений:

<литерал>

<перменная>

( <выражение> ) + ( <выражение> )

Литерал - это положительное целое число не более 100,000.

Переменная - это строка не более 10 маленьких латинских букв.

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

ФОРМАТ ВЫВОДА:

Выведите одно положительное целое число - значение переменной, возвращённой оператором RETURN.

ОЦЕНИВАНИЕ

в 20% тестов MOO-циклы не вложены.

В других 20% всех тестов программу будет иметь только одну переменную. MOO-циклы могут быть вложенными

В остальных тестах нет никаких ограничений.

Ввод	Вывод	Примечание
x = 1 10 MOO { x = ( x ) + ( x ) } RETURN x	1024	Эта COWBASIC-программа вычисляет 2¹⁰
n = 1 nsq = 1 100000 MOO { 100000 MOO { nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) ) n = ( n ) + ( 1 ) } } RETURN nsq	4761	Эта программа вычисляет (10⁵∗10⁵+1)² (по модулю 10⁹+7).

"Длинная" арифметика Задача на реализацию

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

Вычислитель#27121

Дана блок-схема алгоритма. Какое целое положительное число w необходимо подать на вход, чтобы после завершения алгоритма получилось значение s ? В ответе укажите целое число. Примечание. Операция mod вычисляет остаток от деления первого аргумента на второй. Операция div вычисляет частное от целочисленного деления первого аргумента на второй.

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

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

Kotlin Island#27119

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.

Input	Output
3 5 4	..#.. ##### ..#..
2 1 1	# .
5 3 10	Impossible

Задача на реализацию Разбор случаев

✓ 0✗ 21 300средняяВойти и решать

СКОБКИ#27114

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

Приоритет	Операции
1 (наибольший)	*, /
2	+, -
3	&
4	^
5 (наименьший)	\|

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

Ввод	Вывод	Замечания
a+(b*c)	a+b*c	(у ‘*’ приоритет выше, чем у ‘+’, поэтому она и так выполняется первой,- скобки лишние);
((a+b)+(c+d))	a+b+(c+d)	(Скобки вокруг всего выражения допустимы, но никогда не влияют на порядок вычисления внутри. Поскольку ассоциативность всех операций слева направо, первые внутренние скобки лишние, а вторые – нет, без них выражение было бы эквивалентно (((a+b)+c)+d));
((a)+b)&c^d	a+b&c^d	(скобки вокруг переменной всегда лишние).
(((a)&b^c\|((d))))	a&b^c\|d
a	a

Формат входного файла:
Одна строка, содержащая исходное математическое выражение не длиннее 100 символов.
Формат выходного файла:
Одна строка с математическим выражением без лишних скобок.

Задача на реализацию Строки

✓ 2✗ 61 100средняяВойти и решать

Шифрование#27098

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

Сообщение	Шифртекст	Сообщение	Шифртекст	Сообщение	Шифртекст
А	Г	К	Т	Х	З
Б	Ш	Л	Х	Ц	Ж
В	Ы	М	Я	Ч	Л
Г	О	Н	Ь	Ш	Ё
Д	Э	О	Ф	Щ	Н
Е	Ц	П	У	Ъ	Д
Ё	М	Р	К	Ы	Е
Ж	Ъ	С	Ю	Ь	Б
З	Щ	Т	Р	Э	Ч
И	А	У	П	Ю	И
Й	В	Ф	С	Я	Й

Если применить замену, заданную такой таблицей, к слову «ДОМ», получится зашифрованный текст «ЭФЯ». Если применить замену к полученному результату, из «ЭФЯ» получится «ЧСЙ», а из «ЧСЙ» таким способом можно получить текст «ЛЮВ». Известно, что через некоторое количество применений замены полученный результат совпадет с исходным словом «ДОМ», после чего результаты замены начнут повторяться. Определите, сколько различных шифртекстов (включая совпадающий с исходным словом) можно получить из произвольного заданного слова по произвольно заданной таблице замены таким способом.

Рекомендации.
До начала работы над программной реализацией постарайтесь найти ответы на следующие вопросы:
1. Сколько различных зашифрованных текстов (включая и совпадающий с открытым текстом) можно получить одной операцией замены из открытого текста с n различными буквами, используя все возможные таблицы замены.
2.Можно ли получить все возможные зашифрованные тексты (число которых установлено в пункте 1), применяя к результату зашифрования операцию замены символов по одной и той же таблице неограниченное число раз.

Формат ввода:
В первой строке задана строка с алфавитом используемых символов. Во второй строке задана последовательность заглавных букв, заменяющих буквы, стоящие в алфавитном порядке (таблица замены). Например, приведенной выше таблице соответствует строка «ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ». В следующей строке задано слово, являющееся открытым текстом – в верхнем регистре (заглавными буквами) без пробелов. Например, слово «КРИПТОАНАЛИЗ».
Каждая из этих строк заканчивается либо символами с кодами 13, 10 (окончание строк DOS – для Pascal ABC .NET), либо символом с кодом 10 (окончание строк Unix) в зависимости от выбранного при сдаче программы типа конца строк. Никаких других символов в двух входных строка не встречается.
Русский текст задан в кодировке Windows-1251 (cp1251). В ней заглавные русские буквы от "А" до "Я" кроме буквы "Ё" имеют коды от 192 (шестнадцатеричное C0) до 223 (шестнадцатеричное DF). Буква "Ё" имеет код 168 (шестнадцатеричное A8). Русские буквы (кроме "Ё") упорядочены по алфавиту.

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

Задача на реализацию Множества Структуры данных

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

КОЛОНИЗАЦИЯ МАРСА#27072

Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки. Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.

Формат входных данных
Задается одно число N ( 1<= N <= 10⁹ ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.

Ввод	Вывод
2	3

Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

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

Задача на реализацию

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

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

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

Тяжелая, вариант-2#27065

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

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

Гарантируется, что машины не пересекаются между собой, а также со стенами, но возможно соприкасаются.

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

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

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

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

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

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

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

Формальное исполнение алгоритма, заданного на естественном языке или для конкретного исполнителя с заданным набором команд#27036

Цепочки цифр (строки) создаются по следующему правилу:

Первая строка состоит из двух цифр «1».

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

Эта цифра вставляется в начало, в конец и между всеми цифрами предыдущей строки.

Вот первые 4 строки, созданные по этому правилу:

(1) 11

(2) 21212

(3) 32313231323

(4) 43424341434243414342434

Таким образом, было построено еще 5 строк и в результате получена строка, содержащая цифры от 1 до 9 и состоящая из 767 цифр.

Напишите через пробел сначала цифру, стоящую на a позиции от начала, а затем на b позиции от начала. a и b считываются с клавиатуры (записаны в одной строке через пробел, номер позиции от начала отсчитывается с 1).

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

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

Алгоритмизация и программирование#27033

Дан фрагмент программы:

Операции MOD, mod и функция ост_дел вычисляют остаток от деления первого аргумента на второй. Операции \, div и функция цел_дел осуществляют целочисленное деление. Какое минимальное значение целочисленной переменной X должно было быть перед началом выполнения этого фрагмента, если после его выполнения получилось значение R=A?, где А - вводится с клавиатуры.
В ответе укажите целое число.

Задача на реализацию

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

Алгоритмизация и программирование#27032

Дана исходная последовательность цифр: 1234
Задан алгоритм преобразования последовательности, на каждом шаге которого выполняются следующие операции:
1. В конец последовательности, имеющейся перед выполнением шага, дописывается ее копия, но развернутая зеркально (цифры записываются в обратном порядке).
2. В конце получившейся последовательности удаляется количество цифр, равное номеру шага выполнения алгоритма.

Ниже приведены результаты выполнения первых двух шагов алгоритма:
1: 1234432
2: 123443223443

Определите, какие цифры будут на A-ой, B-ой и C-той позиции от начала последовательности, которая получилась после выполнения 8-ого шага алгоритма. В ответе укажите через пробел три цифры: сначала цифру, которая стоит на А-ой позиции, затем цифру, которая стоит на В-ой позиции и затем цифру, которая стоит на С-той позиции. A, B и C задаются с клавиатуры.

Задача на реализацию Задачи на моделирование Строки

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

27031#27031

Сколько существует таких натуральных чисел в диапозоне от a до b, что их запись в шестнадцатеричной системе счисления будет иметь ровно две значащих цифры, а в восьмеричной системе счисления – ровно три значащих цифры?

Задача на реализацию Разные системы счисления

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

На связи#26983

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

Владимир, как истинный программист, решил заменить все цифры в своем сообщении на их названия на английском языке:

0 - zero
1 - one
2 - two
3 - three
4 - four
5 - five
6 - six
7 - seven
8 - eight
9 - nine

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

Формат ввода

В единственной строке введена строка s — сообщение Владимира для Даши. Строка может содержать любые символы с ASCII-кодами от 32 до 126. Длина строки не превосходит 4 × 10⁶.

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

Выведите измененное сообщение Владимира, в котором каждая цифра заменена на её название на английском языке.

Пример

Ввод	Вывод
Dashka, I love you!!! <3	Dashka, I love you!!! <three

Задача на реализацию Строки

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