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

Последовательность#33303

Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.

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

Дано натурально число число N (1 ≤ N ≤ 10¹⁸).

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

Выведите число, которое стоит на k-ом месте в последовательности.

Ввод	Вывод
1	0
10	2

Арифметические алгоритмы (Теория чисел)Рекурсия Целые числа

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

Декодирование сообщения#33255

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

секретное сообщение скруллов — строку s. Однако, в закодированном виде никакой полезной информации оно из себя не представляет, поэтому его непременно нужно раскодировать.

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

• Перед кодированием сообщения выбирается цифра d (0 <= d <= 9)

• Символы сообщения рассматриваются слева направо

• У каждого символа сообщения вычисляется его ASCII-код (например, у «a» он равен 97, у

«b» — 98, у «z» — 122)

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

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

дописывается к текущей закодированной строке (например, если d = 3, а текущая буква —

«a», к текущей закодированной строке могут дописатсья числа 397, 937 или 973)

• После обработки всех букв, результатом считается полученная закодированная строка

Число d обычно передается вместе с сообщением, но Капитану Марвел не удалось его найти. Однако, она точно знает, что исходное сообщение состояло только из строчных и заглавных латинских

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

и заглавных латинских букв, таких, что, закодировав их, получится строка s. Так как наша героиня

не может быть полностью уверена, что сообщение было перехвачено полностью, вполне возможно,

что его невозможно декодировать ни одним способом.

Помогите нашей героине — найдите количество этих строк по модулю 10⁹ + 7.

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

В единственной строке содержится закодированная строка s, выкраденная Капитаном Марвел

(3 <= |s| <= 10⁵). Гарантируется, что строка s состоит только из цифр, а также что ее длина кратна 3.

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

В единственной строке выведите одно число — количество различных строк, состоящих из строчных и заглавных латинских букв, которые кодируются в строку s, по модулю 10⁹ + 7.

Ввод	Вывод
988	2
100905	1
600	0

Замечание

В первом примере закодированную строку можно получить из «b», если d = 8, а также из «X», если d = 9.

Во втором примере закодированную строку можно получить только из «dZ» при d = 5.

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

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

Старая книга#33126

Группа юных археологов работает на раскопках здания древней библиотеки. Летом

они обнаружили остатки старой книги и, изучив их, сделали следующие выводы.

Книга содержит несколько страниц, каждая страница содержит либо текст, либо

иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги

пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма

номеров страниц с текстом равна s.

К сожалению, ни общее количество страниц в книге, ни количество иллюстраций

установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое

минимальное количество иллюстраций могло быть в книге.

Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание

(буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая

иллюстрацию):

- И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;

- И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;

- И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.

Минимальное количество иллюстраций равно 3.

Требуется написать программу, которая по заданным целым числам k и s определяет

минимальное количество иллюстраций, которое могло быть в книге.

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

Первая строка входных данных содержит целое число k (0 ≤ k ≤ 10⁹).

Вторая строка входных данных содержит целое число s (k + 1 ≤ s ≤ 10¹²).

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

Требуется вывести одно целое число — минимальное количество иллюстраций в

книге.

Ввод	Вывод
1 8	3

"Два указателя"Бинарный поиск Вывод формулы

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

Удаление чисел#33125

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На

очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

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

Например, пусть n = 13, k = 2.

- На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.

- На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.

- На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.

- На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

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

Первая строка входных данных содержит целое число n (3 ≤ n ≤ 10¹⁸).

Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n).

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

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Ввод	Вывод
13 2	3

Задачи на моделирование Идеи Целые числа

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

Квадраты и кубы#33122

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

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

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных

чисел от a до b, включительно. Будем называть k-плотностью этого множества количество

пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x²– y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как

подходят следующие пары:

x = 1, y = 1, |x²– y³| = |1 – 1| = 0;

x = 3, y = 2, |x²– y³| = |9 – 8| = 1;

x = 5, y = 3, |x²– y³| = |25 – 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а

также целому неотрицательному числу k, определяет k-плотность множества натуральных

чисел от a до b, включительно.

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

Входные данные содержат три строки. Первая строка содержит натуральное число a,

вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное

число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

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

Выходные данные должны содержать одно целое число: искомую k-плотность

множества натуральных чисел от a до b, включительно.

Ввод	Вывод
1 30 2	3

Арифметические алгоритмы (Теория чисел)Вещественные числа Линейный поиск

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

Улучшение успеваемости#33121

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.

Примеры округления оценок приведены в таблице.

Оценки на уроках	Среднее арифметическое	Итоговая оценка
2, 3, 5	\({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\)	3
3, 3, 4, 4	\({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\)	4
5, 5, 5, 3, 5	\({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\)	5

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

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

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

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 10¹⁵, a + b + c ≥ 1).

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

Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Ввод	Вывод
2 0 0	2

Бинарный поиск Вывод формулы Целые числа

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

Инопланетный геном#32979

Геном жителей системы Тау Кита содержит 26 видов оснований, для обозначения которых будем использовать буквы латинского алфавита от A до Z, а сам геном записывается

строкой из латинских букв. Важную роль в геноме играют пары соседних оснований, например, в геноме «ABBACAB» можно выделить следующие пары оснований: AB, BB, BA,

AC, CA, AB.

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

Вам даны два генома, определите степень близости первого генома второму геному.

Программа получает на вход две строки, состоящие из заглавных латинских букв. Каждая строка непустая, и её длина не превосходит 10⁵.

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

Ввод	Вывод	Примечание
ABBACAB BCABB	4	Следующие пары оснований первого генома встречаются во втором геноме: AB, BB, CA, AB. Обратите внимание на то, что пара AB в первом геноме встречается два раза, поэтому и подсчитана в ответе два раза.

Алгоритмы обработки Строки Хеш

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

RSA. Зашифровать небольшое сообщение.#31917

Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод	Вывод
3 7 3 1 2 3	1 11 12

Быстрое возведение в степень МЦКО-10. RSA Остатки

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

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средняяВойти и решать

Modern Art 2#27219

Picowso решила переключиться на 1-мерный стиль.

Теперь её картины могут описываться 1-мерным массивом цветов длины NN (1≤N≤100,000). А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1…N ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.

Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.

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

Первая строка ввода содержит N, и следующие N строк содержат целое число в интервале 0…N, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

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

Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).

Ввод	Вывод
7 0 1 4 5 1 3 3	2

Примечание
В данном примере интервал цвета 1 должен быть закрашен в более раннем раунде, чем интервалы цветов 4 и 5, поэтому необходимо как минимум два раунда.

Конструктив Линейные структуры Стек

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

Bovine Genomics#27218

У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.

За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:

Позиция : 1 2 3 4 5 6 7 8

Пятнистая корова 1: A A T C C C A T

Пятнистая корова 2: A C T T G C A A

Пятнистая корова 3: G G T C G C A A

Корова без пятен 1: A C T C C C A G

Корова без пятен 2: A C T C G C A T

Корова без пятен 3: A C T T C C A T

Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.

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

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

Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.

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

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

Ввод	Вывод
3 8 AATCCCAT ACTTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	4

Множества Строки Хеш

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

Boolean Satisfiability#27116

Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this problem you are given a Boolean formula, and you need to find out if the variables of a given formula can be consistently replaced by the values true or false in such a way that the formula evaluates to true. SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of 3-CNF formula (3-SAT). However, for example, SAT problem for 2-CNF formulae (2-SAT) is in P.

#SAT is the extension of SAT problem. In this problem you need to check if it is possible, and count the number of ways to assign values to variables. This problem is known to be #P-complete even for 2-CNF formulae. We ask you to solve #1-DNF-SAT, which is #SAT problem for 1-DNF formulae.
You are given a Boolean formula in 1-DNF form. It means that it is a disjunction (logical or) of one or more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not). Formally:

Your task is to find the number of ways to replace all variables with values true and false (all occurrences of the same variable should be replaced with same value), such that the formula evaluates to true.

Input
The only line of the input file contains a logical formula in 1-DNF form (not longer than 1000 symbols). Logical operations are represented by ‘|’ (disjunction) and ‘~’ (negation). The variables are ‘A’ . . . ‘Z’ and ‘a’ . . . ‘z’ (uppercase and lowercase letters are different variables). The formula contains neither spaces nor other characters not mentioned in the grammar.

Output
Output a single integer — the answer for #SAT problem for the given formula

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7

Алгоритмы на графах Комбинаторика Конструктив

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

Алгоритм#27014

Реализуйте на одном из языков программирования алгоритм, представленный на схеме. Выражение S mod K означает вычисление остатка от деления S на K.

В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует N строк, содержащих по одному целому числу в диапазоне от 1 до 1000.

Вывести сообщение Yes или No как указано в алгоритме.

Ввод	Вывод
3 2 1 3	Yes
3 1 2 3	No

Линейные алгоритмы Условный оператор Цикл for

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

Дело в шляпах#25919

Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы!

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

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

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

Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?

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

В первой строке содержится число N (1 <= N <= 10⁵) количество людей, которые придут к парикмахеру.

Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 10⁹), момент времени прихода s (1 <= s <= 10⁹), и время на стрижку t (1 <= t <= 10⁹). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 10⁹, даже если бы из очереди никто не уходил.

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

В единственной строке выведите через пробел номера людей в очереди в порядке возрастания, которых парикмахер всё-таки пострижёт. Люди нумеруются в порядке прихода в очередь, начиная с 1.

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

Задачи на моделирование Очередь Разбор случаев

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

Orders#24733

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

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

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

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

Бор Обход в глубину Перебор

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

Таймер#23405

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

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

В первой строке записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.

Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0.

А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.

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

В ответе выведите в формате ЧЧ:ММ:СС время, когда прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days.

Примеры

№	Входные данные	Выходные данные
1	01:01:01 48:0:0	01:01:01+2 days
2	01:01:01 58:119	02:01:00
3	23:59:59 1	00:00:00+1 days

Дата и время Строки Условный оператор

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

Мишина машина (В', В)#23371

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

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

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

Помогите Мише найти самый выгодный маршрут.

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

В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 10⁵, 0<= m <= 10⁵)

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

Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.

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

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

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

Замечание

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

Кратчайшие пути в графе Обход в ширину Способы задания графа

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

Число способов#22015

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

Посчитайте, сколько есть способов у игрока попасть в правую

нижнюю клетку.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,

1<=M<=10).

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

В выходной файл запишите искомое число способов.

Примечание

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

Пример входного файла

2 3

Пример выходного файла

Пояснение

Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие

способы попасть из левого верхнего угла в правый нижний:

1) вниз, вправо, вправо

2) вправо, вниз, вправо

3) вправо, вправо, вниз

Еще один пример входного файла

3 3

Пример выходного файла

Динамическое программирование на таблицах Динамическое программирование: один параметр Комбинаторика

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

Кладовка из Простоквашино#21996

Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_iминут.

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

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

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

Ввод	Вывод
1 2 5 6 3 5	12
3 1 15 10 1 3 4 5 30 35	105

Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку

Динамическое программирование Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

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

ЕГЭ-2026. 23 ДВ#95460

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены номерами:

1. Прибавь 2
2. Замени 1 на 3

Первая из этих команд увеличивает число на экране на 2. Вторая команда может применяться только к числу, в десятичной записи которого содержится хотя бы одна цифра «1», и действует, заменяя все цифры «1» в записи числа на цифры «3» (например, число 11 превратится в 33, а 21 - в 23).

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 10 результатом является число 44?

ЕГЭ - 2026 год ЕГЭ_информатика

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

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7