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






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

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


Номер задачиНазвание задачиЗадача 
 
119Сортировка времениТребуется выполнить сортировку временных моментов, заданных в часах, минутах и секундах.

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

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

Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.

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

Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь по три сторонника в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.

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

Входные данные
Входной файл INPUT.TXT состоит из двух строк. В первой строке записано натуральное число K < 1001 - количество групп избирателей. Во второй строке через пробел записаны K натуральных чисел, которые задают количество избирателей в группах. Население острова не превосходит 30000 человек.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
174СвадьбаОдна предприимчивая и очень симпатичная дамочка с прелестнейшим именем Горгона решила заработать себе денег на роскошную жизнь. N молодых людей так влюблены в нее, что предложили руку и сердце. К несчастью для них, Горгона видит в них только мешок с деньгами. Она планирует выйти замуж и почти сразу же развестись с некоторыми из молодых людей ради денежной выгоды. Все, что ей нужно, это подзаработать как можно больше денег (и уж, конечно, остаться незамужней). По законам этой прекрасной страны при разводе каждый из супругов получает половину всего имущества.

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

Входные данные
В первой строке входного файла INPUT.TXT записано целое число N — количество молодых людей, без памяти влюбленных в Горгону (1 < N ≤ 40). Далее следует N чисел — сумма денег на счету каждого молодого человека. В последней строке записано целое число А — сумма денег на счету Горгоны. Суммы денег на счету — целые неотрицательные числа, не превосходящие 109.

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число — максимальную сумму денег, которой сможет обладать Горгона после своей махинации. Ответ выводите в формате с фиксированной точкой с ровно шестью знаками после десятичной точки.
41Сортировка подсчетомНа планете «Аурон» атмосфера практически отсутствует, поэтому она известна своими перепадами температур в различных точках. Известно, что эти перепады колеблются от -100 до 100 градусов. Нашим специалистам удалось выяснить значения температур в N точках этой планеты. К сожалению, эти значения вычислены с большими погрешностями, поэтому их решили округлить до целых чисел. Хотелось бы наглядно видеть участки с повышенной и пониженной температурой. Вам требуется помочь. Вы должны упорядочить температуры участков по неубыванию.

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

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести разделенные пробелом значения температур всех известных участков, которые должны следовать друг за другом в порядке неубывания.
475Арифметическая прогрессия - 2Задана последовательность натуральных чисел из диапазона [1, 2147483647]. Необходимо определить: можно ли выстроить эти числа в отрезок арифметической прогрессии. При необходимости порядок чисел в последовательности можно изменять.

Требуется написать программу для решения этой задачи.

Входные данные
Входной файл INPUT.TXT содержит последовательность натуральных чисел. Количество чисел в последовательности может быть от 2 до 100 000. Числа в файле разделены пробелами или символами перехода на новую строку.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать либо «Yes» в случае положительного ответа, либо «No» в противоположном случае.
344Ближайшие точкиАнтон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: «На числовой прямой задано n точек. Необходимо найти среди них две ближайшие». Расстояние между двумя точками числовой прямой x и y равно |x - y|.

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

Входные данные
Первая строка входного файла INPUT.TXT содержит количество точек n (2 ≤ n ≤ 105). Вторая строка содержит n различных целых чисел xi – координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значения всех координат xi не превосходят 109 по абсолютной величине.

Выходные данные
В первой строке выходного файла OUTPUT.TXT необходимо вывести минимальное расстояние между двумя точками, заданными во входном файле. Во второй строке выходного файла необходимо вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от 1 до n в том порядке, в котором они заданы во входном файле. Если ответов несколько, выведите тот из них, в котором точки расположены левее других на числовой прямой. Первым выводится номер левой точки, далее через пробел – номер правой точки.
1168ЭкзаменыВступительные испытания в вуз состоят из трех экзаменов – математики, информатики и русского языка. На каждом из них абитуриент может набрать от одного до ста баллов. По результатам сдачи экзаменов составляется экзаменационная ведомость, где для каждого студента указывается фамилия и баллы за каждый экзамен. Для определения лучших абитуриентов, данная ведомость сортируется по сумме набранных баллов за все экзамены, а если сумма баллов совпадает – по фамилии (в алфавитном порядке, по убыванию). После чего первые M абитуриентов из списка зачисляются на первый курс и становятся студентами!

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

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

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

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество учеников (N ≤ 100). Далее, для каждого ученика определены 4 строки, содержащие фамилию, имя, класс и дату рождения соответственно. Фамилия и имя – строки, не превышающие 20 символов английского алфавита: первая буква заглавная, остальные – строчные. Класс – строка, состоящая из числа (от 1 до 11) и заглавной английской буквы (от «A» до «Z»). Дата рождения – строка в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

Выходные данные
В выходной файл OUTPUT.TXT выведите список учеников, отсортированный сначала по классам (классы сравниваются по номеру, а потом по букве), а потом по фамилии. Данные об ученике выводятся в отдельной строке: класс, фамилия, имя и дата рождения через пробел.
1232Двумерный массивЗадан целочисленный двумерный массив, состоящий из N строк и M столбцов. Требуется вычислить сумму элементов в каждой строке и в каждом столбце.

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

Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите N чисел – суммы элементов массива для каждой строки в отдельности. Во второй строке в аналогичном формате выведите M чисел – суммы элементов для каждого столбца. Третья строка должна быть пустой, а далее должны следовать N строк по M чисел – исходный массив, определенный во входных данных.
1233Транспонирование - 1Задана целочисленная квадратная матрица размером N x N. Требуется транспонировать ее относительно главной диагонали.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, полученную транспонированием исходной матрицы относительно главной диагонали.
1234Транспонирование - 2Задана целочисленная квадратная матрица размером N x N. Требуется транспонировать ее относительно побочной диагонали.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, полученную транспонированием исходной матрицы относительно побочной диагонали.
1235Транспонирование - 3Задана целочисленная матрица, состоящая из N строк и M столбцов. Требуется транспонировать ее относительно вертикали.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, полученную транспонированием исходной матрицы относительно вертикали.
1237Сумма матрицЗаданы две целочисленные матрицы, каждая из которых состоит из N строк и M столбцов. Требуется вычислить их сумму.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и столбцов каждой матрицы. Далее следует описание двух матриц. Каждая матрица состоит из N строк по M целых чисел. Матрицы отделены друг от друга пустой строкой. Все числа во входных данных не превышают 100 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, полученную в результате суммы заданных матриц.
1238Произведение матрицЗаданы две целочисленные матрицы A и B. Матрица A состоит из N строк и M столбцов, Матрица B состоит из M строк и P столбцов. Требуется вычислить произведение данных матриц A*B.

Входные данные
Первая строка входного файла INPUT.TXT содержит три натуральных числа N, M и P. Далее следует описание матриц A и B. Матрица A состоит из N строк по M целых чисел. Матрица B состоит из M строк по P чисел. Матрицы отделены друг от друга пустой строкой. Все числа во входных данных не превышают 100 по абсолютной величине.

Выходные данные
В выходной файл OUTPUT.TXT выведите матрицу, полученную в результате произведения A*B.
924Симпатичный узорНа днях Иван у себя в прихожей выложил кафель, состоящий из квадратных черных и белых плиток. Прихожая Ивана имеет квадратную форму 4х4, вмещающую 16 плиток. Теперь Иван переживает, что узор из плиток, который у него получился, может быть не симпатичным. С точки зрения дизайна симпатичным узором считается тот, который не содержит в себе квадрата 2х2, состоящего из плиток одного цвета.

Примеры возможных узоров:

Симпатичный узор
По заданному расположению плиток в прихожей Ивана требуется определить: является ли выполненный узор симпатичным.

Входные данные
Входной файл INPUT.TXT содержит 4 строки по 4 символа «W» или «B» в каждой, описывающие узор из плиток. Символ «W» обозначает плитку белого цвета, а «B» - черного.

Выходные данные
В выходной файл OUTPUT.TXT выведите «Yes», если узор является симпатичным и «No» в противном случае.
715Миша и негативМиша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив бинарного черно-белого изображения.

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

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

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

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

Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n, m ≤ 100) – высоту и ширину исходного изображения (в пикселях). Последующие n строк содержат описание исходного изображения. Каждая строка состоит из m символов «B» и «W». Символ «B» соответствует черному пикселю, а символ «W» – белому. Далее следует пустая строка, а после нее – описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.
234СаперМальчику Васе очень нравится известная игра "Сапер" ("Minesweeper").

В "Сапер" играет один человек. Игра идет на клетчатом поле (далее будем называть его картой) N×M (N строк, M столбцов). В K клетках поля стоят мины, в остальных клетках записано либо число от 1 до 8 — количество мин в соседних клетках, либо ничего не написано, если в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую точку, в одной клетке не может стоять более одной мины. Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. Если в открытой им клетке оказывается мина — он проигрывает, иначе игроку показывается число, которое стоит в этой клетке, и игра продолжается. Цель игры — открыть все клетки, в которых нет мин.

У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. Однако фантазия у него богатая, а времени мало, и он хочет успеть нарисовать как можно больше карт. Поэтому он просто выбирает N, M и K и расставляет мины на поле, после чего все остальные клетки могут быть однозначно определены. Однако на определение остальных клеток он не хочет тратить свое драгоценное время. Помогите ему!

По заданным N, M, K и координатам мин восстановите полную карту.

Входные данные
В первой строке входного файла INPUT.TXT содержатся числа N, M и K (1 ≤ N ≤ 200, 1 ≤ M ≤ 200, 0 ≤ K ≤ N×M). Далее идут K строк, в каждой из которых содержится по два числа, задающих координаты мин. Первое число в каждой строке задает номер строки клетки, где находится мина, второе число — номер столбца. Левая верхняя клетка поля имеет координаты (1,1), правая нижняя — координаты (N,M).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать N строк по M символов — соответствующие строки карты. j-й символ i-й строки должен содержать символ ‘*‘ (звездочка) если в клетке (i,j) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо ‘.‘ (точка), если клетка (i,j) пустая.
27ХудожникИзвестный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом: сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников со сторонами, параллельными сторонам холста и вершинами, расположенными в целочисленных координатах. Помогите художнику определить площадь незакрашенной части холста.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа w и h (1 ≤ w, h ≤ 100). Во второй строке записано целое число n (0 ≤ n ≤ 5000) – количество прямоугольников. Следующие n строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2 , где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно.

Выходные данные
Выведите в выходной файл OUTPUT.TXT одно целое число – площадь незакрашенной части холста.
58Проверка на симпатичностьРассмотрим таблицу, содержащую n строк и m столбцов, в каждой клетке которой расположен ноль или единица. Назовем такую таблицу симпатичной, если в ней нет ни одного квадрата 2 на 2, заполненного целиком нулями или целиком единицами.

Так, например, таблица 4 на 4, расположенная слева, является симпатичной, а расположенная справа таблица 3 на 3 - не является.


Задано несколько таблиц. Необходимо для каждой из них выяснить, является ли она симпатичной.

Входные данные
Первая строка входного файла INPUT.TXT содержит количество t (1 ≤ t ≤ 10) наборов входных данных. Далее следуют описания этих наборов. Описание каждого набора состоит из строки, содержащей числа n и m (1 ≤ n,m ≤ 100), и n строк, каждая из которых содержит по m чисел, разделенных пробелами. j-ое число в i+1-ой строке описания набора входных данных - элемент aij соответствующей таблицы. Гарантируется, что все aij равны либо нулю, либо единице.

Выходные данные
Для каждого набора входных данных выведите в файл OUTPUT.TXT единственную строку, содержащую слово «YES», если соответствующая таблица является симпатичной, и слово «NO» - в противном случае.
103Снова A+BТребуется сложить два целых числа А и В.

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

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