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

Сумма ряда - 2#27004

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {{1\over 2^n} + {1 \over 3^n}}\)

Выведите на экран сумму такого ряда.

Циклы

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

Сумма ряда - 1#27003

\(a_n = {(-1)^{n-1} \over{n^n}}\)

Выведите на экран сумму такого ряда.

Циклы

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

Крепкий дом#27001

Джон Доу хочет построить крепкое здание, чтобы никто и никогда не нашел его. У него есть кирпичи 1х2, 1х3 и "уголки", то есть квадратики 2х2, у которых отсутствует одна клетка. Для уточнения смотрите на рисунки.

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

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

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

Вводятся числа N и M (1 <=N, M <= 100) высота и ширина требуемой стены.

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

Выведите N строк, содержащих по M символов от «A» до «Z», описывающие стену. Каждый кирпич должен описываться одинаковыми символами (кирпичи, имеющие общую сторону должны описываться различными символами). Не должно существовать прямой, по обе стороны которой были бы кирпичи и она не пересекала бы ни один из кирпичей. Если стену с заданными ограничениями построить невозможно, выведите «impossible».

Частичные решения, работающие при N, M <=6 получат не менее 40 баллов.

Двумерные массивы

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

Школьные наборы#27000

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

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

В первой строке входного файла записано натуральное число N> (1<=N<<=100).

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

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

Ввод	Вывод
2	3

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

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

Палиндромы#26998

Вам дана строка символов, состоящая из заглавных букв латинского алфавита. Подсчитайте сколько различных палиндромов можно составить, меняя местами буквы этой строки. Палиндромом называется строка, которая одинаково читается как справа налево, так и слева направо. Например, “ABCBA” - палиндром, а “ABCDA” - нет.

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

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

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

Вывести целое число - искомое количество различных палиндромов. Палиндромы считаются различными, если у них есть отличие хотя бы в одном символе.

Ввод	Вывод
ABCBA	2

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

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

Простые вычисления#26997

Вам даны числа X и N. Посчитайте значение выражения:

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

В первой строке через пробел записаны действительное число X и натуральное число N (-1000 <= X<=1000, 1<=N <=10¹²). Число X содержит в своей записи не более 8 знаков после десятичной точки.

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

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

Частичные решения, работающие при N<=10⁷ получат не менее 40 баллов.

Ввод	Вывод
1.24 5	-0.04

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

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

Одуванчики#26996

У Ани есть поле размером N×M клеток. На этом поле Аня разводит одуванчики. Аня заметила, что если в некоторой клетке поля растёт одуванчик, то на следующий день в четырёх клетках рядом с ним (севернее, восточнее, южнее и западнее) вырастает по одуванчику. Однако за пределами поля одуванчики не вырастают.

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

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

На первой строке находятся числа N и M (1<=N, M <= 100) размеры поля. Далее идут N строк, каждая из которых по M элементов. Эти строки обозначают поле. Символ «.» в строке означает, что данная клетка поля пуста, а символ «*» что в клетке находится одуванчик. Других символов в строках быть не может.

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

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

Частичные решения, работающие при случаях, когда N = 1 или M = 1, получат не менее 30 баллов.

Ввод	Вывод
3 3 ... .*. ...	2
4 3 ... ... ... *..	5

Обход в ширину

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

Массив#26995

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

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

В первой строке входного файла находится число N> (3<=N <= 100000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 10000.

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

Нужно вывести три числа x, y и z в порядке возрастания. Если вариантов такой тройки несколько, вывести любой.

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

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

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

Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

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

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

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

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

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

Разбиение на пары#26982

Мария Ивановна написала на доске четыре числа: a, b, c и d. После чего предложила своему классу разбить эти числа на две пары так, чтобы сумма произведений чисел в парах была максимальна.

Например, если на доске написаны числа 5, 6, 7 и 8, то оптимально разбить их на пары (5, 6) и (7, 8), в этом случае искомая сумма равна 5 × 6 + 7 × 8 = 86.

Формат ввода

На вход подаются четыре целых числа: a, b, c и d. Все числа по модулю не превышают 1000.

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

Выведите искомую максимальную сумму.

Пример

Ввод	Вывод
5 6 7 8	86

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

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

2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.

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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0	4
2	2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0	8
3	2 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0	4
4	2 2 4 0 0 2 2 2 0 2 4 0 2 4 4 0	16

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

Двумерные массивы

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

Бумага для олимпиады#26980

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи A одинаковых товаров и получи еще один товар бесплатно», а также «купи B товаров по цене B-1 товара».

Лёлик узнал, что одна пачка бумаги в этом магазине стоит n рублей. Теперь он хочет определить сколько упаковок бумаги он сможет купить на p рублей. Помогите ему.

Формат ввода

На вход подаются четыре натуральных числа, разделенных пробелом: A, B, p и n (1 ≤ A ≤ 100, 2 ≤ B ≤ 100, 1 ≤ p, n ≤ 10000).

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

Выведите единственное целое число — максимальное количество упаковок бумаги, которое сможет купить Лёлик.

Пример

Ввод	Вывод
4 4 13 2	8
3 4 8 3	2
3 4 7 1	9

Примечания

В первом примере, дважды используя вторую акцию, можно купить 8 упаковок бумаги, заплатив за 6.

Во втором примере акциями воспользоваться нельзя.

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

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

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

Логические выводы#26979

Болик решает логическую задачу. Для ее решения, он сначала сделал N базовых предположений. После этого происходит следующий процесс: Холмс разбивает все предположения на пары, из каждой пары отбрасывает наименее вероятное предположение (предположения таковы, что всегда есть наименее вероятное). Если получилось так, что какому-то предположению, пары не хватило, то Болик оставляет его для рассмотрения. Алгоритм повторяется пока у Болика не останется последнее предположение.

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

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

Формат ввода

На вход подается натуральное число N (1 ≤ N ≤ 10²¹⁸) — количество базовых предположений.

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

Выведите единственное целое число — количество логических выводов.

Пример

Ввод	Вывод
3	3

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

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

Максимальная сумма, не делящаяся на 4#25980

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

В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

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

Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму.

Примеры

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

ЕГЭ - вычислительные задачи

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

Выборка чисел для максимальной суммы, кратной 4#25979

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

Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

Примеры

№	Входные данные	Выходные данные
1	6 8 3 4 4 8 12 9 5 6 2 8 3 12 3 5 1 4 12	88

ЕГЭ - вычислительные задачи

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

Задача#25974

Для чего производится описание массивов?

1) чтобы самому запомнить сколько ячеек в массиве
2) чтобы компьютер запомнил имя массива
3) чтобы компьютер зарезервировал память для хранения элементов массива
4) чтобы компьютер зарезервировал количество энергии для обработки массива

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

300лёгкаяВойти и решать

Одномерные массивы. Введение#25971

В программе измените объявление массива таким образом, чтобы массив состоял из 30 элементов.

Линейные структуры

✓ 3 390✗ 1 568100лёгкаяВойти и решать

По мотивам ЕГЭ 2017#25970

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых \(1 <= i < j <= N\) и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи.

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

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

Примеры

№	Входные данные	Выходные данные
1	5 14 7 7 2 19	6

ЕГЭ - вычислительные задачи

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

3-ий минимум#25969

От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 100 10 100 10 100	#

ЕГЭ - вычислительные задачи

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

Дипломы#25961

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).

Выходные данные: необходимо вывести ответ на поставленную задачу.

Примеры

№	Входные данные	Выходные данные
1	2 3 10	9
2	1 1 1	1

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

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