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






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

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


Номер задачиНазвание задачиЗадача 
 
597Внеземные гостиНедавно на поле фермера Джона были обнаружены следы приземления летающих тарелок. Об этом даже писала газета Mew Yorc Courier.

Поле фермера Джона имеет форму круга радиусом r1. По сообщениям журналистов были обнаружены два следа от летающих тарелок, имевшие форму кругов. Один из них имел радиус r2, второй - радиус r3. Также сообщается, что они находились внутри поля фермера Джона и не пересекались, ни один из них не лежал внутри другого. При этом, они, возможно, касались друг друга и/или границы поля.

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

Входные данные
Входной файл INPUT.TXT содержит три целых положительных числа - r1, r2, r3 (1 ≤ r1, r2, r3 ≤ 109).

Выходные данные
В выходной файл OUTPUT.TXT выведите слово YES, если информация, опубликованная в газете, может соответствовать правде, и слово NO - иначе.
529Длина отрезкаОтрезок задан координатами своих концевых точек. Требуется вычислить длину этого отрезка.

Входные данные
Входной файл INPUT.TXT содержит координаты концов отрезка в формате X1 Y1 X2 Y2 . Все координаты – целые числа, не превышающие 1000 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите длину отрезка с точностью 10-5.
106МонеткиНа столе лежат n монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно перевернуть, чтобы все монетки были повернуты вверх одной и той же стороной.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество монет, которые нужно перевернуть.
81АрбузыИван Васильевич пришел на рынок и решил купить два арбуза: один для себя, а другой для тещи. Понятно, что для себя нужно выбрать арбуз потяжелей, а для тещи полегче. Но вот незадача: арбузов слишком много и он не знает как же выбрать самый легкий и самый тяжелый арбуз? Помогите ему!

Входные данные
В первой строке входного файла INPUT.TXT задано одно число N – количество арбузов. Вторая строка содержит N чисел, записанных через пробел. Здесь каждое число – это масса соответствующего арбуза. Все числа натуральные и не превышают 30000.

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести два числа через пробел: массу арбуза, который Иван Васильевич купит теще и массу арбуза, который он купит себе.
35Конечные автоматыОднажды известный профессор обнаружил описания k конечных автоматов. По его мнению, нетривиальность конечного автомата, имеющего n состояний и m переходов, можно описать целым числом d = 19m + (n + 239)*(n + 366) / 2 . Чем больше d, тем больший интерес для науки представляет изучение его свойств.

Помогите профессору вычислить нетривиальность имеющихся у него автоматов.

Входные данные
Первая строка входного файла INPUT.TXT содержит целое число k (1 ≤ k ≤ 10000) – количество конечных автоматов. Следующие k строк содержат по два целых числа ni (0 ≤ ni ≤ 1000) и mi (0 ≤ mi ≤ 26ni2) – число состояний и переходов i-го автомата.

Выходные данные
Выходной файл OUTPUT.TXT должен состоять из k строк. На i-й строке выходного файла выведите одно число – нетривиальность i-го автомата.
233Автобусная экскурсияОргкомитет Московской городской олимпиады решил организовать обзорную экскурсию по Москве для участников олимпиады. Для этого был заказан двухэтажный автобус (участников олимпиады достаточно много и в обычный они не умещаются) высотой 437 сантиметров. На экскурсионном маршруте встречаются N мостов. Жюри и оргкомитет олимпиады очень обеспокоены тем, что высокий двухэтажный автобус может не проехать под одним из них. Им удалось выяснить точную высоту каждого из мостов. Автобус может проехать под мостом тогда и только тогда, когда высота моста превосходит высоту автобуса.

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

Входные данные
Во входном файле INPUT.TXT сначала содержится число N (1 ≤ N ≤ 1000). Далее идут N натуральных чисел, не превосходящих 10000 - высоты мостов в сантиметрах в том порядке, в котором они встречаются на пути автобуса.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести фразу "No crash", если экскурсия закончится благополучно. Если же произойдет авария, то нужно вывести сообщение "Crash k", где k - номер моста, где произойдет авария. Фразы выводить без кавычек ровно с одним пробелом внутри.
131ПереписьВ доме живет N жильцов. Однажды решили провести перепись всех жильцов данного дома и составили список, в котором указали возраст и пол каждого жильца. Требуется найти номер самого старшего жителя мужского пола.

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

Выходные данные
Выходной файл OUTPUT.TXT должен содержать номер самого старшего мужчины в списке. Если таких жильцов несколько, то следует вывести наименьший номер. Если жильцов мужского пола нет, то выведите -1.
63ЗагадкаПетя и Катя – брат и сестра. Петя – студент, а Катя – школьница. Петя помогает Кате по математике. Он задумывает два натуральных числа X и Y (X,Y≤1000), а Катя должна их отгадать. Для этого Петя делает две подсказки. Он называет сумму этих чисел S и их произведение P. Помогите Кате отгадать задуманные Петей числа.

Входные данные
Входной файл INPUT.TXT содержит два натуральных числа S и P, разделенных пробелом.

Выходные данные
В выходной файл OUTPUT.TXT выведите два числа Х и Y, загаданные Петей. Числа следует вывести в порядке неубывания своих значений, разделенные пробелом.
15ДорогиВ галактике «Milky Way» на планете «Snowflake» есть N городов, некоторые из которых соединены дорогами. Император галактики «Milky Way» решил провести инвентаризацию дорог на планете «Snowflake». Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог. Требуется написать программу, помогающую императору сосчитать количество дорог на планете «Snowflake».

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

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести число, определяющее количество дорог на планете «Snowflake».
2СуммаТребуется посчитать сумму целых чисел, расположенных между числами 1 и N включительно.

Входные данные
В единственной строке входного файла INPUT.TXT записано единственное целое число N, не превышающее по абсолютной величине 104.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — сумму чисел, расположенных между 1 и N включительно.
10УравнениеВася в школе изучил квадратные уравнения и понял, как они легко решаются путем вычисления дискриминанта. Но Петя поведал ему о методе решения кубических уравнений вида A*X3 + B*X2 + C*X + D = 0. На факультативе по математике Васе задали решить около ста уравнений как раз такого вида. Но, к сожалению, Вася забыл формулы, о которых рассказывал ему Петя. Но Васе было известно, что все корни уравнений – целые числа и находятся на отрезке [-100, 100]. Поэтому у Васи есть шанс найти их методом перебора, но для этого ему придется затратить уйму времени, т.к. возможно необходимо будет осуществить перебор нескольких тысяч значений. Помогите Васе написать программу, которая поможет ему найти корни кубических уравнений!

Входные данные
В единственной строке входного файла INPUT.TXT записаны 4 числа: A, B, C и D – целые коэффициенты кубического уравнения. Каждый коэффициент по модулю меньше 32768.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести через пробел в порядке возрастания все корни заданного кубического уравнения. Кратные корни следует выводить только один раз.
264ОттепельУставшие от необычно теплой зимы, жители решили узнать, действительно ли это самая длинная оттепель за всю историю наблюдений за погодой. Они обратились к синоптикам, а те, в свою очередь, занялись исследованиями статистики за прошлые годы. Их интересует, сколько дней длилась самая длинная оттепель.

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

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

Выходные данные
В выходной файл OUTPUT.TXT требуется вывести одно число – длину самой продолжительной оттепели, то есть наибольшее количество последовательных дней, на протяжении которых среднесуточная температура превышала 0 градусов. Если температура в каждый из дней была неположительной, выведите 0.
1125Список квадратовТребуется вывести квадраты натуральных чисел, не превосходящие числа N.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите все квадраты натуральных чисел, не превосходящие N, в порядке возрастания.
1126Минимальный делительТребуется найти наименьший натуральный делитель целого числа N, отличный от 1.

Входные данные
Входной файл INPUT.TXT содержит целое число N (1 < N ≤ 106).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
1127Список степеней двойкиТребуется вывести все целые степени двойки (т.е. числа вида 2k), не превосходящие числа N.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите в порядке возрастания все степени двойки, не превосходящие N.
692Бинарные числаГоворят, что плохой программист – это тот, кто считает, что в одном килобайте 1000 байт, а хороший программист – это тот, кто полагает, что в одном километре 1024 метра.

Многим эта шутка понятна, так как все знают, что в процессах, связанных с информатикой и компьютерной техникой, фигурирует множество значений, выражаемых степенью двойки, то есть чисел вида 2K, где K – некоторое неотрицательное целое число. Назовем такие числа бинарными. Это такие числа как 2, 4, 8, 16, 32 и т.д. Действительно, когда речь идет о размере памяти или о разрешении экрана монитора, то мы часто наталкиваемся на бинарные числа. Все это связано с принципом хранения информации в памяти ЭВМ.

Задано целое число N. Требуется определить, является ли оно бинарным.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите YES, если заданное число является бинарным, и NO в противном случае.
147Числа ФибоначчиПоследовательностью Фибоначчи называется последовательность чисел a0, a1, ..., an, ..., где
a0 = 0, a1 = 1, ak = ak-1 + ak-2 (k > 1).

Требуется найти N-е число Фибоначчи.

Входные данные
Во входном файле INPUT.TXT записано целое число N (0 ≤ N ≤ 30).

Выходные данные
В выходной файл OUTPUT.TXT выведите N-е число Фибоначчи.
271Числа Фибоначчи - 2Числа Фибоначчи строятся следующим образом: 1, 1, 2, 3, 5, …. В этой последовательности, начиная с третьего числа, каждый следующий член равен сумме двух предыдущих. Получаем, что, например, шестое число равно 8, а десятое - 55.

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

Входные данные
Входной текстовый файл INPUT.TXT содержит одно натуральное число в диапазоне от 2 до 1200000000.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать в первой строке 1, если заданное число является числом Фибоначчи, и 0, иначе. В первом случае во вторую строку требуется вывести его порядковый номер.
1129Банковские процентыВклад в банке составляет X рублей. Ежегодно он увеличивается на P процентов, после чего дробная часть копеек отбрасывается.

Требуется определить: через сколько лет вклад составит не менее Y рублей.

Входные данные
Входной файл INPUT.TXT содержит три натуральных числа: X, P и Y (X,Y ≤ 1000, P ≤ 100).

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
272Сумма максимума и минимумаЗадана последовательность целых чисел. Числа нумеруются по порядку следования, начиная с единицы.

Требуется написать программу, которая найдет сумму максимума из чисел с четными номерами и минимума из чисел с нечетными номерами – max{a2, a4, …}+min{a1, a3, …}.

Входные данные
Входной текстовый файл INPUT.TXT содержит в единственной строке последовательность от 2 до 2×105 целых чисел, которые по модулю не превышают 10000.

Выходные данные
Выходной текстовый файл OUTPUT.TXT должен содержать одно целое число - сумму максимума из чисел с четными номерами и минимума из чисел с нечетными номерами.