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

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

Недавно в солнечный весенний день директору Летней Флатландской Компьютерной Школы (ЛФКШ) Сергею Александровичу пришла в голову идея организовать первую флатландскую конференцию для школьников по программированию. Теперь перед ним стоит задача выбрать место проведения.

Флатландия представляет собой прямоугольник из m строк и n столбцов, в каждой из клеток которого расположен один город? Сергей Александрович уже посчитал для каждого города количество желающих принять участие в конференции. Известно, что флатландцы не любят далеко ездить, так что в каком бы городе она проводилась, в конференции смогут принять участие только школьники из самого города и соседних с ним по стороне городов. Формально говоря, если конференция проводится в городе, находящемся в i-ой строке и j-ом столбце, то в этой конференции будут участвовать школьники из городов (i, j), (i − 1, j) ( при условии, что i > 1) , (i + 1, j) (при условии, что i < m), (i, j − 1) (при условии, что j > 1) , и (i, j + 1) , (при условии, что j < n).

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

Обратите внимание на то, что школьникам, живущим в том же городе, в котором проводится конференция, поселение не нужно.

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

В первой строке записаны два числа m и n (1 <= m, n <= 350) - размеры Флатландии. В каждой из последующих m строк содержатся по n чисел.
В i-ой стоке и j-ом столбце содержится число a_i,j ( 0<= a_i,j<=10000) - количество школьников из города (i, j), желающих принять участие в конференции.

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

Выведите m строк по n чисел в каждой. Число в строке с номером i и стобце с номером j должно равняться количеству приезжих участников конференции, если местом проведения будет

выбран город, с координатами (i, j).

Ввод	Вывод
3 4 1 0 3 2 5 6 1 2 1 1 0 11	5 10 3 5 8 7 11 14 6 7 13 2
1 1 5	0

Двумерные массивы Задача на реализацию

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

Совсем другие штурмовики#23366

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t, здоровье — h единиц.

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

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

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵), d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

Бинарный поиск Бинарный поиск по ответу

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

Коды Грея#23365

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

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

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

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

Ввод	Вывод
2 0? 0? 1? 1?	YES 00 01 11 10
3 ?00 0?1 01? 0?0 ?10 1?1 10? 1?1	NO

Система оценки

Номер подзадачи	Баллы	Ограничения	Комментарии
1	37	1<=n<=4	Баллы начисляются, если все тесты пройдены.
2	63	1<=n<=12	Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

Конструктив Рекурсия

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

Билеты в театр#23364

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

Оказалось, что у каждой девочки есть ровно одна банкнота номиналом 100 рублей, а у каждого мальчика — номиналом 1000 рублей. До ребят еще никто не успел купить билет, поэтому касса пуста. Это значит, что кассир выдает сдачу только теми банкнотами, которые получил от других ребят, стоявших раньше в очереди. Кассир обслуживает всех по очереди и не начинает обслуживать следующего человека, если еще не продал билет или не выдал требуемую сдачу предыдущему.

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

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

Формат входных данных
В первой строке задано два целых неотрицательных числа n и m, где n — количество девочек, m — количество мальчиков (1<= n + m < 10⁴).

Формат выходных данных
Выведите остаток от деления числа способов расставить студентов в очередь, чтобы все смогли купить билет, на 10⁹ + 7.

Ввод	Вывод
18 2	10
8 1	0
12 1	4

Динамическое программирование Динамическое программирование: два параметра

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

Сенсор#23362

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

Сенсор выдает число s равное суммарному числу точек на нижних гранях игральных костей.

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

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

В первой строке входного файла задано число s сумма на нижних гранях костей (s <= 10⁵).

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

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

Ввод	Вывод
2	2
4	4

Пояснение к примеру

В первом примере на нижних гранях могло выпасть 1 + 1 или 2, суммы на верхних гранях 12 и

5, соответственно.

Комбинаторика Перебор

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

Динамика - 03#23262

Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 26 и при этом траектория вычислений содержит число 8?

ЕГЭ_информатика ЕГЭ-13. Динамическое программирование

900средняяВойти и решать

Динамика - 02#23261

Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 15 и при этом траектория вычислений содержит число 11?

ЕГЭ_информатика ЕГЭ-13. Динамическое программирование

1 000средняяВойти и решать

Динамика - 01#23260

Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
3. Прибавить 5
Программа для исполнителя Громозека – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 7?

ЕГЭ_информатика ЕГЭ-13. Динамическое программирование

900средняяВойти и решать

Первые одинаковые#23095

Дано предложение. Определить порядковые номера первой пары одинаковых соседних символов. Если таких символов нет, то вывести на экран слово NO.

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

Входные данные
В первой строке задается предложение длиной не более 255 символов (в начале и конце предложения нет пробелов).

Выходные данные
Необходимо вывести через пробел порядковые номера первой пары одинаковых соседних символов, или слово "NO" - если такой пары соседних символов нет (первый символ в предложении имеет порядковый номер 1).

Примеры

№	Входные данные	Выходные данные
1	foresete	NO
2	haah	2 3

Символы Строки

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

Сколько "n" перед запятой#23094

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

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

Входные данные: в первой строке задается исходное предложение.

Выходные данные: выведите одно число - ответ на задачу

Примеры

№ теста	Входные данные	Выходные данные
1	fore, sete.	0
2	hanah.	1

Символы Строки

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

Сколько "o"#23093

Дано предложение, в котором нет символа "-". Определить количество букв "o" (англ.) в первом слове. В начале предложения могут быть пробелы.

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

Входные данные: в единственной строке задается исходное предложение.

Выходные данные: необходимо вывести количество букв "о" (англ.) в первом слове.

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

№ теста	Входные данные	Выходные данные
1	fore sete.	1
2	hal ah.	0

Символы Строки

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

Префикс#23092

Дано два слово. Определить, сколько начальных букв первого слова совпадает с начальными буквами второго слова

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

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

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

№ теста	Входные данные	Выходные данные
1	fore forest	4
2	forest torest	0

Символы Строки

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

Одинаковые в начале#23091

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

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

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

Выходные данные: необходимо вывести количество одинаковых симвлов в начале строки.

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

№ теста	Входные данные	Выходные данные
1	foresete	0
2	ааав	3

Символы Строки

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

Сколько "i"#23090

Дана строка, разбитая на предложения. Все предложения заканчиваются знаком точка. Определить количество букв 'i' в первом предложении.

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

Входные данные: программа получает на вход строку.

Выходные данные: необходимо вывести количество букв 'i' в первом предложении.

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

№ теста	Входные данные	Выходные данные
1	foresete. forest.	0
2	firist. forist	2

Символы Строки

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

Перевертыш#23089

Дано слово. Проверить, является ли оно "перевертышем", (то есть читается одинаково как сначала, так и с конца).

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

Входные данные: в первой строке задается слово.

Выходные данные: необходимо вывести слово "YES", если слово является перевертышем, и слово "NO" - в противном случае

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

№ теста	Входные данные	Выходные данные
1	foresete	NO
2	halah	YES

Символы Строки

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

Найди "a"#23088

Дано предложение. Определить, есть ли в нем буква "a" (англ.). В случае положительного ответа вывести порядковый номер первой из них. В случае отрицательного - вывести слово NO.

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

Входные данные: в первой строке задается исходное предложение.

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

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

№ теста	Входные данные	Выходные данные
1	foresete	NO
2	forast	4

Символы Строки

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

Первая "e"#23087

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

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

Входные данные: в первой строке задается исходное предложение.

Выходные данные: необходимо вывести номе первой буквы "е" (англ) в предложении

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

№ теста	Входные данные	Выходные данные
1	foresete	4

Символы Строки

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

Символы перед запятой#23086

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

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

Входные данные: в первой строке задается исходное предложение.

Выходные данные: необходимо вывести все символы предложения, которые предшествуют первой запятой, если запятых нет - вывести все предложение

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

№ теста	Входные данные	Выходные данные
1	fore, s t.	fore
2	fore s t.	fore s t.

Символы Строки

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

Кодовый замок#23041

Весь год Гошан был прилежным мальчиком и делал добрые дела: переводил бабушку через дорогу, еженедельно оставался в школе на контесты, давал одноклассникам списать химию и т.д. За это Дедушка Мороз позволил Гошану выбрать абсолютно любой подарок на новый год. Гошан воспользовался возможностью и попросил долгожданную для него книгу “History of Hip-Hop”, ведь он был истинным поклонником хип-хопа! За кем же еще может стоять андерграунд?

Но Дед Мороз решил устроить испытание для мальчика. Он поставил на коробку с книгой кодовый замок.
Кодовый замок устроен следующим образом. На электронном экране замка появляются три числа – a , b и c. Чтобы открыть замок необходимо перевести числа a и b в двоичную систему счисления и поразрядно выполнить для них операцию c.
Описание операций:

1	Конъюнкция
2	Дизъюнкция
3	Исключающее или
4	Импликация
5	Эквивалентность

Результат операции необходимо представить в виде числа в двоичной системе счисления, а затем перевести в десятичное число .
Это число и будет являться ключом числа.
Помогите Гошану открыть замок, ведь с логикой у него плохи дела, а ему очень хочется поскорее почитать “History of Hip-Hop”.
P.S. Если в одном из чисел a и b разрядов будет больше, чем в другом, то в наименьшее необходимо добавить ведущие нули.
Входные данные
Входной файл содержит в себе три числа – a,b(1<=a,b<=1000) и с(1<=c<=5).
Выходные данные
Необходимо вывести одно число – ответ на задачу.
Пример
Ввод:
12 10 5
Вывод:
9
Пояснение
12=1100
10=1010

1100

1010

1001

1001=9

(с) Курбатов Егор 9и

Битовые операции Двоичная система счисления

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

Узник нейропривода#23040

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

И как вы думаете, что попросил Павлик у Дедушки Мороза на новый год? Конечно же нейропривод а так же только что вышедшую под него “Borderlands 5 online”.

Первого января, после получения своего подарка, Павлик начал играть. Паша был лютым геймером, поэтому прокачивался с космической скоростью. Это позволило ему в первый же день игры развести 5 новичков на деньги и шмот. Конечно Дедушке Морозу это не понравилось, и он решил проучить Павлика. Он заблокировал Павлику доступ вернуться в реальность и послал ему в игре злого босса по имени Даня Зевс, элитного игрока команды NA’VI по CS GO в прошлом. Чтобы выбраться в реальность Павлику необходимо победить босса.

У Дани Зевса n здоровья. У Павлика же есть Дробовик с a1 патронами и наносящий а2 урона, пистолет с b1 патронами и наносящий b2 урона и снайперская винтовка с с1 патронами и наносящая с2 урона.

Какое минимальное количество выстрелов необходимо сделать Павлику, чтобы убить босса, если это вообще возможно.

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

В первой строке записано число n – количество здоровья у Данечки Зевса.

Во второй строке записаны числа а1 и а2 – количество патрон и урон дробовика.

В третей строке записаны числа b1 и b2 – количество патрон и урон пистолета.
В четвертой строке записаны числа с1 и с2 – количество патрон и урон снайперской винтовки.

0<=n,a1,a2,b1,b2,c1,c2<=2*10^9

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

Вам необходимо вывести минимальное количество выстрелов, которое необходимо сделать Павлику или -1, если Павлик не сможет убить босса

Пример

Ввод

7 1

3 5

10 2

Вывод

(с) Курбатов Егор 9и

Жадный алгоритм Разбор случаев

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