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






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

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


Номер задачиНазвание задачиЗадача 
 
1149Количество нулейДано натуральное число N. Требуется определить количество нулей среди цифр данного числа.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите число нулей в числе N.
1150Удаление цифрДана строка, состоящая из английских букв, специальных символов и цифр. Необходимо удалить в ней все цифры 4 и 7.

Входные данные
Входной файл INPUT.TXT содержит строку S, состоящую из символов с ASCII-кодами от 33 до 127. Длина строки не превосходит 100.

Выходные данные
В выходной файл OUTPUT.TXT выведите исходную строку без цифр 4 и 7.
1152Вставка символовДана строка. Требуется между ее символами вставить символ «#» (ASCII 35).

Входные данные
Входной файл INPUT.TXT содержит строку, состоящую только из английских букв. Строка содержит от 1 до 100 букв.

Выходные данные
В выходной файл OUTPUT.TXT выведите строку, полученную из исходной, путем вставки символа «#» между всеми ее буквами.
297КругляшиОднажды в просторах рунета появился следующий ребус:

157892 = 3
203516 = 2
409578 = 4
236271 = ?
Никто так и не смог его разгадать. Позже оказалось, что число в правом столбце равно сумме "кругляшей", которые есть в цифрах числа, расположенного слева. Ваша задача написать программу, которая определяет, сколько кругляшей в числе.

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

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

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

Входные данные
Входной файл INPUT.TXT содержит строку, состоящую только из английских букв и цифр. Длина строки не превосходит 100.

Выходные данные
В выходной файл OUTPUT.TXT выведите «Yes», если пароль является криптостойким и «No» – в противном случае.
43НулиТребуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.

Входные данные
В единственной строке входного файла INPUT.TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр от 1 до 100.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести искомую длину цепочки нулей.
504ЦветочкиВ рождественский вечер на окошке стояло три цветочка, слева на право: герань, крокус и фиалка. Каждое утро Маша вытирала окошко и меняла местами стоящий справа цветок с центральным цветком. А Таня каждый вечер поливала цветочки и меняла местами левый и центральный цветок. Требуется определить порядок цветов ночью по прошествии K дней.

Входные данные
Во входном файле INPUT.TXT содержится натуральное число K – число дней (K ≤ 1000).

Выходные данные
В выходной файл OUTPUT.TXT требуется вывести три английских буквы: «G», «C» и «V» (заглавные буквы без пробелов), описывающие порядок цветов на окошке по истечении K дней (слева направо). Обозначения: G – герань, C – крокус, V – фиалка.
6ШахматыСовсем недавно Вася занялся программированием и решил реализовать собственную программу для игры в шахматы. Но у него возникла проблема определения правильности хода конем, который делает пользователь. Т.е. если пользователь вводит значение «C7-D5», то программа должна определить это как правильный ход, если же введено «E2-E4», то ход неверный. Так же нужно проверить корректность записи ввода: если например, введено «D9-N5», то программа должна определить данную запись как ошибочную. Помогите ему осуществить эту проверку!

Входные данные
В единственной строке входного файла INPUT.TXT записан текст хода (непустая строка), который указал пользователь. Пользователь не может ввести строку, длиннее 5 символов.

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести «YES», если указанный ход конем верный, если же запись корректна (в смысле правильности записи координат), но ход невозможен, то нужно вывести «NO». Если же координаты не определены или заданы некорректно, то вывести сообщение «ERROR».
44СтрелкиЗадана последовательность, состоящая только из символов ‘>’, ‘<’ и ‘-‘. Требуется найти количество стрел, которые спрятаны в этой последовательности. Стрелы – это подстроки вида ‘>>-->’ и ‘<--<<’.

Входные данные
В первой строке входного файла INPUT.TXT записана строка, состоящая из символов ‘>’, ‘<’ и ‘-‘ (без пробелов). Строка состоит не более, чем из 250 символов.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести искомое количество стрелок.
1200Измени порядокНа одном из предприятий установлена пропускная система, которая ежедневно фиксирует порядок прихода сотрудников, используя персональные магнитные карты.

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

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

Успехов в реализации данной программы!

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число K (K ≤ 10) – число дней. Далее идут K строк, в каждой из которых задана последовательность фамилий сотрудников, разделенных ровно одним пробелом, в порядке их прихода на работу в один из K дней. Общее число сотрудников на предприятии не превышает 100, гарантируется, что каждый день на работу приходит хотя бы один сотрудник. Фамилия сотрудника – последовательность символов английского алфавита, длиной от 1 до 100 символов.

Выходные данные
В выходной файл OUTPUT.TXT выведите ровно K строк в формате, удобном для отслеживания опаздывающих сотрудников.
7Золото племени АББАГлавный вождь племени Абба не умеет считать. В обмен на одну из его земель вождь другого племени предложил ему выбрать одну из трех куч с золотыми монетами. Но вождю племени Абба хочется получить наибольшее количество золотых монет. Помогите вождю сделать правильный выбор!

Входные данные
В первой строке входного файла INPUT.TXT записаны три натуральных числа через пробел. Каждое из чисел не превышает 10100. Числа записаны без ведущих нулей.

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

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

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — количество двоичных единиц в записи числа n.
59Несложное вычислениеЗадано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.

Например, пусть n = 239, k = 8. Тогда представление числа n в восьмеричной системе счисления — 357, а ответ на задачу равен 3 × 5 × 7 − (3 + 5 + 7) = 90.

Входные данные
Входной файл INPUT.TXT содержит два натуральных числа: n и k (1 ≤ n ≤ 109, 2 ≤ k ≤ 10). Оба этих числа заданы в десятичной системе счисления.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу (в десятичной системе счисления).
941UnixНаш любимый сисадмин Алексей установил новую ОС семейства Unix. Основные её особенности - это стабильность, надежность, гибкость и масштабируемость и огромное количество идущего в стандартной поставке программного обеспечения. Одна из таких встроенных программ предназначена для сложения чисел, представленных в троичной системе счисления. Вы понимаете то, что Костя - известный тестер, и делом чести для него является найти ошибку в реализации столь сложной задачи. Помогите ему - напишите свою, абсолютно безошибочную версию «троичного калькулятора».

Входные данные
Входной файл INPUT.TXT содержит два, разделенных пробелом, числа N и M (0 ≤ N, M ≤ 231-1) в троичной системе счисления.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ – сумму N и M в десятичной системе счисления.
542Бит-реверсЦелое положительное число m записывается в двоичной системе счисления, разряды (в этой записи) переставляются в обратном порядке и число переводится в десятичную систему счисления. Получившееся число принимается за значение функции B(m).

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите значение B(m).
1214Линейный поискТребуется вычислить, сколько раз встречается некоторое число X в массиве A[1..N].

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

Выходные данные
В выходной файл OUTPUT.TXT выведите количество вхождений числа X в массив A.
1216Максимальный элементВ целочисленном массиве A[1..N] на отрезке [L,R] необходимо найти максимальный элемент и его номер.

Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество элементов в массиве. Во второй строке записаны N целых чисел Ai, разделенные пробелом. Третья строка содержит два натуральных числа L и R, которые задают отрезок поиска [L,R] (-1000 ≤ Ai ≤ 1000, 1 ≤ L ≤ R ≤ N ≤ 1000).

Выходные данные
В выходной файл OUTPUT.TXT выведите значение максимального элемента массива на отрезке [L,R] и его индекс. В случае неоднозначности определения индекса следует вывести наименьший из них.
1217КонтроперацияХакер Василий получил доступ к классному журналу и хочет заменить все свои минимальные оценки на максимальные. Напишите программу, которая заменяет оценки Василия, но наоборот: все максимальные – на минимальные.

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

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

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

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

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
1215Ближайшее числоТребуется найти в массиве A[1..N] самый близкий по величине элемент к заданному числу X.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите значение элемента массива, ближайшее к X. Если таких значений несколько, следует вывести наименьшее среди них.