Решения задач с «ACMP - Школа программиста»






На нашем сайте представлены решения задач по программированию с сайта acmp.ru на языке C++, по таким темам как:

  • Условные операторы и операторы цикла
  • Строковые типы данных, строки
  • Одномерные и двумерные массивы
  • Функции
  • Сортировки
  • Рекурсия
  • Целочисленная арифметика, длинная арифметика
  • Теория графов
  • Структуры данных


Номер задачиНазвание задачиЗадача 
 
293НалогиВ некотором государстве действует N фирм, конкурирующих между собой. У каждой фирмы есть некоторая прибыль в год, равная V[i] американских рублей. У царя есть любимые фирмы, а есть нелюбимые. Соответственно, налог для всех фирм разный и назначается царем в индивидуальном порядке. Налог на i-ую фирму равен p[i] процентов.

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

Помогите им в этой нелегкой задаче.

Входные данные
Во входном файле INPUT.TXT сначала записано число N - число фирм (0 < N ≤ 100). Далее идет N целых неотрицательных чисел, не превышающих 154 - доходы фирм, а затем еще N целых чисел от 0 до 100 - налоги фирм в процентах.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - номер фирмы, от которой государство получает наибольший налог. Если таких фирм несколько, выведите фирму с наименьшим номером.
149РазворотДано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.

Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число N (N ≤ 103). Во второй строке через пробел идут N целых чисел, по модулю не превосходящих 103 - элементы последовательности.

Выходные данные
В выходной файл OUTPUT.TXT выведите заданную последовательность в обратном порядке.
284Подмассив массиваПусть задан массив целых чисел а1, а2, ..., аn. Назовем его подмассивом f(i,j) массив, составленный из чисел массива аi, ai+1,..., aj-1, aj. Напишите программу, которая будет выводить подмассивы массива a.

Входные данные
Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 1000) - количество элементов в массиве а. Во второй строке содержатся числа a1, a2, … , аn разделенные пробелом. Все аi находятся в диапазоне от -231 до 231 - 1. В третьей строке находится m (1 ≤ m ≤ 100) — количество подмассивов, которые необходимо вывести. Следующие m строк содержат пары чисел ik, jk (1 ≤ ik ≤ jk ≤ n).

Выходные данные
В выходной файл OUTPUT.TXT для каждой пары (ik,jk) в отдельной строке выведите подмассив f(ik,jk).
1218ШеренгаПетя впервые пришел на урок физкультуры в новой школе. Перед началом урока ученики выстраиваются по росту, в порядке невозрастания. Напишите программу, которая определит на какое место в шеренге Пете нужно встать, чтобы не нарушить традицию, если заранее известен рост каждого ученика и эти данные уже расположены по невозрастанию (то есть каждое следующее число не больше предыдущего). Если в классе есть несколько учеников с таким же ростом, как у Пети, то программа должна расположить его после них.

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N (N ≤ 100) – количество учеников (не считая Петю). Во второй строке записаны N натуральных чисел Ai (Ai ≤ 200) – рост учеников в сантиметрах в порядке невозрастания. Третья строка содержит единственное натуральное число X (X ≤ 200) – рост Пети.

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – номер Пети в шеренге учеников.
1219Двойной переворотДана последовательность натуральных чисел 1, 2, 3, ..., N. Необходимо сначала расположить в обратном порядке часть этой последовательности от элемента с номером A до элемента с номером B, а затем от C до D.

Входные данные
Входной файл INPUT.TXT содержит 5 натуральных чисел N, A, B, C и D (A ≤ B; C ≤ D; 1 ≤ A, B, C, D ≤ N ≤ 1000).

Выходные данные
В выходной файл OUTPUT.TXT выведите полученную последовательность, полученную в результате двойного переворота.
392Сдвиг перестановкиПерестановкой порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ... , pn, где каждое 1 ≤ pi ≤ n. Будем говорить, что перестановка q1, q2, ... , qn лексикографически меньше перестановки p1, p2, . . . , pn, если существует такое i, что qi < pi, а для любого j < i pj = qj .

Циклическим сдвигом на k перестановки p1, p2, ... , pn называется последовательность, pk+1, pk+2, ... , pn, p1, ... , pk. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

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

Входные данные
Первая строка входного файла INPUT.TXT содержит порядок n (1 ≤ n ≤ 105) заданной перестановки. Вторая строка содержит числа p1, p2, ... , pn, отделенные друг от друга пробелами.

Выходные данные
В выходной файл OUTPUT.TXT выведите перестановку, являющуюся наименьшим лексикографически циклическим сдвигом перестановки, заданной во входном файле.
1220СуперсдвигДана последовательность из N целых чисел и число K. Необходимо сдвинуть всю последовательность (сдвиг - циклический) на |K| элементов вправо, если K – положительное и влево, если отрицательное.

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N, во второй строке записаны N целых чисел Ai, а в последней – целое число K. (1 ≤ N ≤ 105, |K| ≤ 105, |Ai| ≤ 100).

Выходные данные
В выходной файл OUTPUT.TXT выведите полученную последовательность.
5СтатистикаВася не любит английский язык, но каждый раз старается получить хотя бы четверку за четверть, чтобы оставаться ударником. В текущей четверти Вася заметил следующую закономерность: по нечетным дням месяца он получал тройки, а по четным – четверки. Так же он помнит, в какие дни он получал эти оценки. Поэтому он выписал на бумажке все эти дни для того, чтобы оценить, сколько у него троек и сколько четверок. Помогите Васе это сделать, расположив четные и нечетные числа в разных строчках. Вася может рассчитывать на оценку 4, если четверок не меньше, чем троек.

Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов целочисленного массива (1 ≤ N ≤ 100). Вторая строка содержит N чисел, представляющих заданный массив. Каждый элемент массива – натуральное число от 1 до 31. Все элементы массива разделены пробелом.

Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести числа, которые соответствуют дням месяцев, в которые Вася получил тройки, а во второй строке соответственно расположить числа месяца, в которые Вася получил четверки. В третьей строке нужно вывести «YES», если Вася может рассчитывать на четверку и «NO» в противном случае. В каждой строчке числа следует выводить в том же порядке, в котором они идут во входных данных. При выводе, числа отделяются пробелом.
1222Телефонный справочникУ Вас в наличии есть телефонный справочник с информацией о номерах телефонов и адресов абонентов.

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

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M (N,M ≤ 30 000) – количество абонентов и количество запросов по номеру телефона соответственно.

Далее в 3∙N строках следует содержание телефонного справочника, где информация о каждом из абонентов занимает 3 строки и имеет вид:

<номер телефона>

<фамилия> <имя> <отчество>

<улица> <дом>-<квартира>

Где «номер телефона» – целое число, состоящее из 6 цифр. Здесь «дом» и «квартира» – натуральные числа, не превосходящие 100. Все строки во входных данных состоят не более, чем из 50 символов.

Далее следует M строк с информацией о номерах телефонов абонентов, информацию о которых необходимо получить. Гарантируется, что все номера телефонов присутствуют в телефонном справочнике.

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

<фамилия> <имя> <отчество> (<улица> <дом>-<квартира>)
1223Точки на плоскостиНа плоскости заданы N точек с целочисленными координатами. Требуется найти среди них пару самых ближних и пару самых дальних друг от друга точек.

Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (2 ≤ N ≤ 1000) – количество точек. Далее следует N строк пар целых чисел (Xi,Yi), описывающих координаты первой, второй и т.д. точек соответственно (-109 ≤ Xi,Yi ≤ 109).

Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите через пробел номера пары ближних друг к другу точек. Во второй строке выведите номера пары дальних друг от друга точек. В случае неоднозначности определения ответа выведите любой.
1225Количество цифрДано три символа. Требуется определить, сколько из них являются цифрами.

При решении данной задачи необходимо реализовать функцию IsDigit(C), которая возвращает 1, если символ C – цифра, и 0 – иначе.

Входные данные
Входной файл INPUT.TXT содержит три символа, разделенные пробелом. Гарантируется, что ASCII-коды символов превышают 32.

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

При решении данной задачи необходимо реализовать функцию IsLetter(C), которая возвращает 1, если символ C – английская буква, и 0 – иначе.

Входные данные
Входной файл INPUT.TXT содержит три символа, разделенные пробелом. Гарантируется, что ASCII-коды символов превышают 32.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
1227Число сочетанийФакториал числа n – произведение всех натуральных чисел от 1 до n:


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

Число возможных сочетаний из n по k вычисляется по следующей формуле:


По заданным целым числам n и k требуется вычислить число сочетаний.

При решении данной задачи необходимо реализовать функцию F(n), вычисляющую факториал числа.

Входные данные
Входной файл INPUT.TXT содержит целые числа n и k (0 ≤ k ≤ n ≤ 20).

Выходные данные
В выходной файл OUTPUT.TXT выведите число сочетаний из n по k.
1228Сумма простых чиселПростым числом называют натуральное число, у которого ровно два различных натуральных делителя. Другими словами, число является простым, если оно больше единицы и делится нацело только на себя и на единицу.

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

При решении данной задачи необходимо реализовать функцию IsPrime(N), которая возвращает N, если N – простое число, и 0 – иначе.

Входные данные
Входной файл INPUT.TXT содержит три целых числа, не превосходящие 1000 по абсолютной величине.

Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите сумму, составленную из простых чисел во входных данных. Если таковых чисел нет, выведите 0. Во второй строке выведите «Yes», если полученная сумма – простое число, и «No» – в противном случае.
1229Прямоугольный треугольникЗаданы целочисленные координаты вершин треугольника на плоскости. Необходимо определить, является ли данный треугольник прямоугольным.

Требуется решить данную задачу с использованием теоремы Пифагора, вычислив квадраты длин сторон треугольника и проверив условие: a2+b2=c2. При этом следует описать структуру Point для хранения координат точки на плоскости, а также функцию Side(a,b), вычисляющую квадрат длины отрезка между парой точек.

Входные данные
Во входном файле INPUT.TXT записаны через пробел координаты вершин треугольника в формате x1 y1 x2 y2 x3 y3. Все числа целые, не превосходящие 1000 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите «Yes», если треугольник является прямоугольным и «No» в противном случае.
822Площадь треугольникаПо целочисленным координатам вершин треугольника (x1,y1), (x2,y2) и (x3,y3) требуется вычислить его площадь.

Входные данные
Входной файл INPUT.TXT содержит 6 целых чисел x1,y1,x2,y2,x3,y3 – координаты вершин треугольника. Все числа не превышают 106 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите точное значение площади заданного треугольника.
323Гипотеза Гольдбаха Известно, что любое чётное число, большее 2, представимо в виде суммы 2 простых чисел, причём таких разложений может быть несколько. Впервые гипотезу о существовании данного разложения сформулировал математик Х. Гольдбах.

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

Входные данные
Входной файл INPUT.TXT содержит чётное число N (4 ≤ N ≤ 998).

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести два простых числа, сумма которых равна числу N. Первым выводится наименьшее число.
1230Сортировка выборомЗадан целочисленный массив, состоящий из N элементов. Требуется упорядочить в нем элементы по неубыванию, используя сортировку выбором (SelectSort).

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество элементов в массиве (N ≤ 1000). Во второй строке содержатся N целых чисел, не превосходящих 109 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел – элементы массива, упорядоченные по неубыванию.
1231Сортировка пузырькомЗадан целочисленный массив, состоящий из N элементов. Требуется посчитать число инверсий (обмена значений соседних элементов массива) в процессе сортировки элементов массива по неубыванию при использовании алгоритма сортировки «пузырьком» (BubbleSort).

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество элементов в массиве (N ≤ 1000). Во второй строке содержатся N целых чисел, не превосходящих 109 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество инверсий в процессе сортировки методом «пузырька».
648Азартный ШрэкКак-то раз Шрек решил посетить казино. Не будучи заядлым любителем азартных игр, Шрек обнаружил, что он не знает правил ни одной из игр, доступных в казино. Недолго думая, Шрек решил все-таки поиграть. Его взор привлекла игра с довольно незамысловатыми правилами.

На игровом столе лежат N карточек. На каждой карточке написано целое положительное число. Игра проходит между игроком и крупье. Карточки лежат на столе числами вниз. Игра заключается в том, что игрок открывает ровно N/2 карточек. Сумма всех чисел, написанных на карточках открытых игроком, называется “суммой игрока”. Следующим ходом крупье открывает оставшиеся N/2 карточек. Сумма всех чисел, написанных на карточках открытых крупье, называется “суммой крупье”. Выигрыш игрока определяется разностью чисел между “суммой игрока” и “суммой крупье”. Очевидно, что полученная разность может быть отрицательным числом. Это свидетельствует о том, что игрок проиграл и должен казино соответствующую сумму.

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

Входные данные
Первая строка входного файла INPUT.TXT содержит одно четное натуральное число N (2 ≤ N ≤ 100). Вторая строка входного файла содержит ровно N чисел Ai(1 ≤ Ai ≤ 106) – числа, написанные на игральных карточках. Все числа в строке разделяются одиночными пробелами, Ai – число, написанное на i-й карточке. Карточки нумеруются последовательно, начиная с единицы.

Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать ровно одно целое число – максимальный выигрыш, который может получить Шрек с учетом своей уникальной способности видеть числа, написанные на карточках.