Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Городки Седрика#23456

Волшебник Седрик пригласил принцессу Софию и ее друзей поиграть в свою версию старинной игры "Городки".  Седрик расставил несколько столбиков в ряд, которые необходимо сбить битой по порядку. Седрик сбивал столбики один за другим, начиная с самого левого, София — с самого правого. В какой-то момент они сбили последний столбик вместе.

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


Формат входных данных
На вход подается два числа - количество столбиков, которые сбил Седрик и София соответственно (каждое не больше 100). Каждое число записано в отдельной строке.

Формат выходных данных
Выведите количество столбиков, которые были установлены в начале игры.
Линейные алгоритмы
✓ 8 295✗ 6 612200лёгкаяВойти и решать
Площадь невырожденного треугольника - 2#23454

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

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


Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты очередной точки.
 
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «NO».
 

 

Примеры
№ Входные данные Выходные данные
1
3
6 6
-8 8
9 7
 48
ЕГЭ - вычислительные задачи
✓ 263✗ 619600лёгкаяВойти и решать
Спутник "Восход"#23419

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. 

Необходимо найти в заданной серии показаний прибора максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 9 минут. Если получить такое произведение не удаётся, ответ считается равным –1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Задача А (2 балла). 

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

Задача Б (4 балла). 

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

Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N > 9\). В каждой из следующих N строк задаётся одно неотрицательное целое число – очередное показание прибора.
 

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



Примеры
№ Входные данные Выходные данные
1
11
12
45
5
3
17
23
21
20
19
12
26
 1170

 

ЕГЭ - вычислительные задачи
✓ 381✗ 711600лёгкаяВойти и решать
Покупка билетов#23414
За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. 
Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех. 
 
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
 
Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов - Bi секунд, трех билетов - Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
 
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
 
Входные данные: 
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.
 
Выходные данные: выведите одно число - минимальное время в секундах, за которое могли быть обслужены все покупатели.
 
 
Примеры
№ Входные данные Выходные данные
1
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
 12
2
2
3 4 5
1 1 1
 4
Динамическое программирование: один параметр
✓ 439✗ 511700средняяВойти и решать
Ход конем#23411
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
 
Клавиатура телефона выглядит так:
7 8 9
4 5 6
1 2 3
  0  
 
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.
 
Входные данные: на вход подается целое число N (\(1<=N<=50\)).
 
Выходные данные: выведите файл искомое количество телефонных номеров.
 

Примеры
№ Входные данные Выходные данные
1 2 16
Динамическое программирование: один параметр
✓ 233✗ 509700средняяВойти и решать
Подпоследовательности#23409
Дана последовательность, требуется найти длину наибольшей возрастающей 
подпоследовательности.
 
Входные данные
В первой строке входного файла записано число N - длина последовательности  (1 <= N <= 1000). Во второй строке записана сама последовательность  (через пробел). Числа последовательности - целые числа,  не превосходящие 10000 по модулю.
 
Выходные данные
В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.
 
Примеры
№ Входные данные Выходные данные
1
6
3 29 5 5 28 6
 3
 
 
 
Динамическое программирование: последовательности
✓ 509✗ 950300лёгкаяВойти и решать
Гвоздики#23408
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
 
Входные данные: 
- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
 
Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.
Динамическое программирование: один параметр
✓ 649✗ 1 357600лёгкаяВойти и решать
Минимальный путь в таблице#23407
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
 
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
 
Входные данные
В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).
 
Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
 
 
Примеры
№ Входные данные Выходные данные
1
3 4
1 1 1 1
5 2 2 100
9 4 2 1
 8
Динамическое программирование: два параметра
✓ 722✗ 745400лёгкаяВойти и решать
Распаковка строчки#23406
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки. 
 
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
 
Выходные данные
Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n - количество повторений символа (целое число от 2 до 99), а A - заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.
 
Выходные данные
В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
 
Примеры
 
Ввод Вывод
3A4B7D                      AAABBBBDDDDDDD
22D7AC18FGD
DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF
FFFFFFFFGD
95AB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAB
40AB39A
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 
Алгоритмы на строках
✓ 70✗ 211700средняяВойти и решать
Поиск подстроки#23403
Сколько раз встречается?
 
Входные данные
Вам дается две строки. Длина каждой из строк не превышает 255 символов.

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

 

Примеры
№ Входные данные Выходные данные
1
abab
abababcab
 2

Пояснение: подстрока abab встречается во второй строке дважды, начиная с 1-го и 3-го символа.

Поиск подстроки в строке
✓ 106✗ 124400лёгкаяВойти и решать
Арифметическое выражение#23402

В первой строке входных данных записано арифметическое выражение в виде:

<число> <операция> <число> =

<Число> - это натуральное число, не превышающее 10000.

<Операция> - один из знаков +, -, *.

В начале строки, в конце строки, а также между числами и знаком операции, числом и символом =, может быть любое число пробелов (а может пробелов и не быть).

Гарантируется, что длина строки не превышает 200 символов.

 Выведите результат вычисления выражения.

 

Примеры
№ Входные данные Выходные данные
1 154    +3   = 157
 
Строки
✓ 349✗ 452600лёгкаяВойти и решать
Найти 1543#23401
Найдите в тексте 1543.

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

Выходные данные
Если в нем встречается число 1543, выведите слово URA, если же 1543 в файле не встречается, выведите NO.
 
Примеры
№ Входные данные Выходные данные
1 hgdfjgkdghkdjgkgkd1543gjdlgkdjlg URA
2 1=5 4=3 NO
Поиск подстроки в строке
✓ 145✗ 567700средняяВойти и решать
Под побочной диаганалью#23390
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных под побочной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.
 

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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888
 57 75 888
Двумерные массивы
✓ 79✗ 119600лёгкаяВойти и решать
Под главной диагональю#23389
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных под главной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.
 

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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888 
 92 73 75
Двумерные массивы
✓ 79✗ 87500лёгкаяВойти и решать
Над побочной диагональю#23388
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных над побочной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.


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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888 
 888 29 92
Двумерные массивы
✓ 119✗ 100500лёгкаяВойти и решать
Над главной диагональю#23387
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных над главной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.


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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888  
 29 37 57
Двумерные массивы
✓ 151✗ 186400лёгкаяВойти и решать
Увеличение чисел - 1#23385

В первой строке входных данных записано число N (от 1 до 100).

В каждой из последующих N строк записано сначала некоторое целое число (из диапазона от 0 до 10000), затем пробел, и затем некоторый текст (не более 20 символов).

Требуется вывести информацию в том же формате, увеличив число в каждой строке (кроме первой, где записано число N) на 1.

 
Примеры
№ Входные данные Выходные данные
1
2
14 Start
42 Stop
2
15 Start
43 Stop
 
Строки
✓ 1 557✗ 3 593400лёгкаяВойти и решать
Наименьшее число#23378
Дана последовательность чисел. Найти в ней наименьшее число.
 
Входные данные.
Задано сначала число N (количество чисел в последовательности), а затем
N чисел. Все числа - из диапазона Integer. N<=100
 
Выходные данные.
Выведите наименьшее число.
 
 
Линейный поиск
✓ 432✗ 305300лёгкаяВойти и решать
Монотонность#23363
Университет Иннополис готовится к проведению Летней школы олимпиадного программирования. Сейчас им нужно выбрать даты проведения.

Организаторы заметили, что школа проходит лучше, если настроение детей с каждым днем школы улучшается, также они заметили, что настро- ение школьников сильно зависит от погоды: в ясную погоду школьники веселее, чем в пасмурную. Организаторы запросили прогноз погоды на n дней, в которые можно провести школу. Для каждого дня они посчитали число ai — солнечность i-го дня. Теперь они хотят выбрать для про- ведения школы некоторый непрерывный отрезок дней, такой, что каждый следующий день школы солнечность строго больше, чем в предыдущий.

Помогите организаторам школы найти максимальное число дней, которые может идти школа.

Формат входных данных
В первой строке входного файла задано число n — число дней, в которые можно провести школу. Во второй строке заданы n ( 1<=n<=105) чисел ai — солнечности дней (0 <= ai <= 109 ).
Формат выходных данных
Выведите одно число: максимальное число дней, которое может идти школа так, чтобы каждый следующий день школы был солнечнее, чем предыдущий.
 
Вывод Ввод
6
2 0 3 7 4 5		 3
3
1 2 3		 3
4
1 1 1 1		 1
Линейный поиск
✓ 104✗ 239400лёгкаяВойти и решать
Касса (D, C')#23333
Оля решила стать предпринимателем, и недавно открыла свой магазин "Н-аудио". Магазин работает уже в течение целых n дней, и в конце каждого дня Оля приходит, и записывает на листочек количество денег в кассе магазина. При этом, в конце дня деньги из кассы не изымаются,  то есть, после первого дня в кассе хранится выручка за первый день, после второго дня выручка за первый и второй дни и так далее. Оле стало интересно, в какой из n дней выручка магазина была максимальна. Если таких дней несколько, то Олю интересует первый такой день.
 
Формат входных данных  
в  первой строке входного файла находится целое число n - количество дне, в течение которых
работал магазин 1 <= n <= 105 . В i-ой из следующих n строчек содержится целое число ai -
описание баланса рублей в кассе магазина после i-ого дня 0 <= ai <=109
гарантируется, что деньги из кассы никогда не забирали, то есть ai > ai?1 -  для любого i от 2 до n.
 
Формат выходных данных
В единственной строке выходного файла выведите два целых числа - номер дня, в котором
выручка магазина была максимальна, и величину этой выручки. Если таких дней несколько, то
выведите самый ранний из них. Дни в магазине нумеруются с единицы?
 
Ввод Вывод
3
4
5
17		 3 12
5
1
1
3
5
5		 3 2
Линейный поиск
✓ 113✗ 311600лёгкаяВойти и решать
Поделиться
Класснуть