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

Раскраска#21884

Рисунок задан в виде матрицы A, в которой элемент A[y][x] определяет цвет пикселя на пересечении строки y и столбца x. Перекрасить в цвет 2 одноцветную область, начиная с пикселя (x0,y0).

Входные данные
В первой строке задается размер квадратной матрицы n (\(0<n<10\)). Во второй строке заданы координаты точки (x0, y0) - два числа через пробел (0 <= x0, y0 < n) . Далее идут n строк по n неотрицательных чисел в каждой через пробел (каждое число не больше 10).

Выходные данные
Вывести получившуюся после перекраски матрицу.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 0 1 0 1 1 1 1 1 2 2 0 1 0 2 2 3 3 1 2 2 0 1 1 0 0	0 2 0 1 1 2 2 2 2 2 0 2 0 2 2 3 3 1 2 2 0 1 1 0 0

Источник: К.Ю. Поляков. Учебник. Информатика.

Очередь

✓ 704✗ 1 263600лёгкаяВойти и решать

Инфиксная в постфиксную#21881

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

Входные данные
На вход подается строка, представляющая из себя инфиксную форму записи выражения (в строке отсутствуют пробелы).

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

Примеры

№	Входные данные	Выходные данные
1	(5+3)(7+24)	5 3 + 7 2 4 * + *

Стек

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

Математическое выражение#21878

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

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

Выходные данные
Если скобки расставлены верно, то вывести на экран слово Yes, в противном случае - No и количество неправильно расставленных скобок (скобка считается неправильно расставленной, если у нее нет пары).

Примеры

№	Входные данные	Выходные данные
1	7-((X*((X+Y)/(J-3))+Y)/(4-2.5))	Yes
2	(a-c/(d)	No. Incorrect brackets = 1

реализация Стек

✓ 595✗ 1 569600лёгкаяВойти и решать

Сумма квадратов цифр#21876

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

Входные данные
На вход программы подается натуральное пятизначное число.

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

Примеры

№	Входные данные	Выходные данные
1	12345	55

Целые числа

✓ 12 604✗ 19 900200лёгкаяВойти и решать

Цифры числа#21875

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

Входные данные
С клавиатуры вводится трехзначное число.

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

Примеры

№	Входные данные	Выходные данные
1	365	14 356

Целые числа

✓ 2 762✗ 6 637200лёгкаяВойти и решать

Запись арифметических операций#21874

Напишите программу, которая вычисляет значение выражения по заданной формуле:

\({x + y\over {x +1}}-{x\cdot y-12 \over 34 + x}\)

Входные данные
С клавиатуры вводятся x и y - переменные целого типа.

Выходные данные
Программа должна вывести одно число - результат вычисления выражения.

Примеры

№	Входные данные	Выходные данные
1	1 2	1.786

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

Информатика

✓ 3 966✗ 14 554200лёгкаяВойти и решать

Встроенные функции#21872

Напишите программу, которая определяет расстояние между двумя точками с заданными координатами x1 и x2 на числовой оси. Расстояние между двумя точками вычисляется по формуле \(|x2 - х1|\).

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

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

Примеры

№	Входные данные	Выходные данные
1	100000 0	100000.000000

Информатика

✓ 4 508✗ 13 179200лёгкаяВойти и решать

Арифметические выражения#21871

Напишите программу, которая вычисляет значение переменной y по формуле:
y=(1-x²+2,5x³+x⁴)²

Значение переменной x задается с клавиатуры. Типы переменных x и y определите самостоятельно.
Выведите значение переменной y на экран.

Язык программирования

✓ 4 864✗ 33 823200лёгкаяВойти и решать

21869#21869

Управление с обратной связью может описываться:

1. только линейными алгоритмами
2. линейными и цикличекими алгоритмами
3. линейными, ветвящимися и циклическими алгоритмами
4. любыми алгоритмами

Линейные алгоритмы

—Войти и решать

21868#21868

Управление с прямой связью может описываться:

1. только линейными алгоритмами
2. линейными и цикличекими алгоритмами
3. линейными, ветвящимися и циклическими алгоритмами
4. любыми алгоритмами

Линейные алгоритмы

—Войти и решать

21867#21867

Поисковыми системами являются:

1. Google, Yandex, Rambler
2. Google, Rambler, Search
3. Google, Yandex, Viber
4. Yandex, Firefox, Google

Экзамены и диагностики

—Войти и решать

Удаление#21845

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

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

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

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

В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹.

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

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

Примеры тестов

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

4
1 2 3 4

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

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

5
1 2 3 4 5

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

-4

Примечание

Тесты разделены на группы, но оцениваются отдельно

n ≤ 81 — 20 баллов
n ≤ 300 — 10 баллов
n ≤ 5000 — 20 баллов
Без дополнительных ограничений — 50 баллов

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

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

Отсутствующее число#21844

Вам даны n чисел a1, a2, ..., an. Найдите наименьшее целое положительное число x, не содержащееся в множестве {a1, ..., an}, то есть, такое, что не существует i, для которого верно ai = x.

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество чисел. Во второй строке через пробел записаны n чисел: a1, ..., an (1 ≤ ai ≤ 10⁹).

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

Выведите наименьшее целое положительное x не содержащееся в множестве {a1, ..., an}.

Примеры тестов

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

5
1 2 3 4 5

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

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

5
1 3 4 5 6

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

Примечание

Тесты разделены на группы, но оцениваются отдельно

n = 1 — 10 баллов
n ≤ 100 — 20 баллов
ai ≤ 10⁶ — 30 баллов
Без дополнительных ограничений.

Так, если вы решили задачу для n ≤ 100, то вы получите 30 баллов за первую и вторую группы, если вы решили задачу для a_i ≤ 10⁶, то вы получите 30 баллов за третью группу. Если ваша программа будет работать в обоих случаях, то вы получите 60 баллов. За полное решение вы получите 100 баллов.

Одномерные массивы

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

Три числа#21843

Вам дано три числа a, b и c. Вы должны в таком порядке приписать эти числа друг к другу, чтобы в результате получилось минимальное число. Например, если a = 12, b = 5, c = 3, приписыванием можно получить числа 1253, 1235, 3125, 3512, 5123, 5312. Минимальным, среди этих чисел является 1235.

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

В первой строке через пробел записаны три целых числа a, b и c (1 ≤ a, b, c ≤ 100).

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

Выведите минимальное число, которое можно получить, приписав a, b и c друг к другу в каком-нибудь порядке.

Примеры тестов

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

12 3 5

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

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

2 21 3

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

Перестановки реализация

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

Пифагоровы тройки#21840

У Фёдора есть массив различных натуральных чисел. Известно, что чисел N. Фёдор хочет найти в массиве количество троек x, y и z (x < y < z), таких, что x² + y² = z². Помогите ему в этом.

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

В первой строке находится число N (3 ≤ N ≤ 3000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 3000.

Решения, корректно работающие при N ≤ 100, получат не менее 50 баллов.

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

В единственной строке нужно вывести одно число — ответ на задачу.

Ввод:

5 12 13 9 15

Вывод:
2

Вывод формулы

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

Числа#21838

У Артура есть два натуральных числа — x и y (x < y). Помогите ему найти натуральное число z такое, что:

z > x;
z > y;
z не делится на x;
z не делится на y;
z делится на y - x;
z минимально.

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

В первой строке находятся числа x и y (x, y ≤ 10⁶)

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

Выведите число z или '0', если его не существует.

Ввод:
1 2

Вывод:
0

Разбор случаев реализация

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

Друзья#21825

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

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

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

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

В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:

3 1

0 1 0

1 0 1

0 1 0

Вывод
2

графы Поиск компонент связности

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

Z-функция#21824

Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

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

Вывести k строк с ответами на запросы.

Примеры

№	Входные данные	Выходные данные
1	2 ali balimali 3 0	2 8

Z-функция. Префикс-функция

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

Pref-функция#21823

Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S.

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

В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).

Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

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

В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.

Примеры

№	Входные данные	Выходные данные
1	abacaba 2 3 7	4

Z-функция. Префикс-функция

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

HASH#21822

Программисту Васе не повезло - вместо отпуска его послали в командировку на научную конференцию. "Надо повышать уровень знаний", - сказал начальник, "Важная конференция по криптографии, проводится во Франции - а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета."

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

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

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

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

На входе дана непустая строка, полученная Васей. Строка состоит только из строчных латинских символов. Ее длина не превосходит 2000 символов.

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

Выведите количество различных подстрок этой строки.

Примеры

№	Входные данные	Выходные данные
1	aaba	8

Хеш

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