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






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

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


Номер задачиНазвание задачиЗадача 
 
143A-BТребуется найти разность между неотрицательными числами А и В.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите значение A-B.
402^NНеобходимо вычислить значение 2n.

Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число n (0 < n < 1000).

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести значение 2n.
144A*BДаны два целых неотрицательных числа A и B. Требуется найти их произведение.

Входные данные
Во входном файле INPUT.TXT записаны целые неотрицательные числа A и B по одному в строке (A < 10100, B ≤ 10000).

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число без лидирующих нулей: A*B.
172Деление с остаткомЗаданы два числа: N и K. Необходимо найти остаток от деления N на K.

Входные данные
Входной файл INPUT.TXT содержит два целых числа: N и K (1 ≤ N ≤ 10100, 1 ≤ K ≤ 109).

Выходные данные
В выходной файл OUTPUT.TXT выведите остаток от деления N на K.
145A div BДаны два целых числа A и B. Требуется найти их целую часть от их частного.

Входные данные
Во входном файле INPUT.TXT записаны целые числа A и B по одному в строке (0 ≤ A ≤ 10100, 0 < B ≤ 10000).

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число без лидирующих нулей: A div B.
946ПолкаУ Андрея есть младший брат Ванечка, который очень любит смотреть мультики. Ванечка вечно разбрасывал по дому и терял свои DVD с мультиками. Поэтому на день рождения Андрей подарил брату длинную полку для того, чтобы Ванечка ставил на нее свои диски. Чтобы на полке был порядок, Андрей просил Ванечку соблюдать простой порядок:

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

Входные данные
В первой строке входного файла INPUT.TXT указано целое число N (1 ≤ N ≤ 10000) - количество операций, которые выполнил Ванечка. Далее в N строках находится информация об операциях. Каждая операция постановки диска на полку описывается парой чисел. Первое из них (1 или 2) показывает, что диск ставится с левого края или с правого края соответственно. Второе целое число (от 0 до 10000) обозначает номер диска. Операции снятия диска с полки описывается одним числом 3 или 4, обозначающим с левого и правого края полки соответственно снимается диск.

В начальный момент полка пуста. Гарантируется, что последовательность операций корректна, нет команд снятия диска с пустой полки.

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

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

Входные данные
Входной файл INPUT.TXT содержит не менее 1 и не более 10 строк. В каждой строке записана одна последовательность скобок. Длина последовательности от 1 до 255 символов.

Выходные данные
В выходной файл OUTPUT.TXT выведите слитно символы 0 или 1. Их общее количество равно количеству введенных строк. Для каждой строки выводится 0, если из нее может получиться правильное скобочное выражение, и 1 иначе.
50СтрокиЦиклическим сдвигом строки s называется строка sksk+1sk+2…s|s|s1s2…sk-1 для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка sisi+1…sj-1sj для некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b.

Входные данные
Первая строка входного файла INPUT.TXT содержит строку a (1 ≤ |a| ≤ 1000). Во второй строке входного файла записана строка b (1 ≤ |b| ≤ min(100,|a|)). Обе строки состоят только из символов английского алфавита и цифр.

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
1160Префикс-функцияДана непустая строка S длиной N символов. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой i-й позиции строки S определим подстроку, заканчивающуюся в этой позиции, которая совпадает с некоторым началом всей строки S и имеет длину, меньшую, чем i (т.е. не равна i-му префиксу исходной строки). Значением префикс-функции P(i) будем считать длину этой подстроки.

Требуется для всех i от 1 до N вычислить значение P(i).

Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.

Выходные данные
В выходной файл OUTPUT.TXT выведите все значения префикс-функции.
1161Z-функцияДана непустая строка S длиной N символов. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой i-й позиции строки S определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки S. Значением Z-функции Z(i) будем считать длину этого Z-блока. При i=1 будем считать, что Z(1)=0, несмотря на то, что в начале строки строка совпадает сама с собой.

Требуется для всех i от 1 до N вычислить значение Z(i).

Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.

Выходные данные
В выходной файл OUTPUT.TXT выведите все значения Z-функции.
202Поиск подстрокиНайти все вхождения строки T в строке S.

Входные данные
В первой строке входного файла INPUT.TXT записана строка S, во второй строке записана строка T. Обе строки состоят только из английских букв. Длины строк могут быть в диапазоне от 1 до 50 000 включительно.

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести все вхождения строки T в строку S в порядке возрастания. Нумерация позиций строк начинается с нуля.
391Взлом хеш-функцииВ некоторых задачах защиты информации используются так называемые хеш-функции. Одним из важнейших классов хеш-функций являются так называемые полиномиальные хеш-функции.

Пусть дана строка S = s1s2 ... sl, состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функции p(S, x, m) вычисляется следующим образом:

Хеш-функция

(a mod b обозначает остаток от деления числа a на число b). Например, пусть S = 0123, тогда p(S, 2, 5) = (0 ∙ 1 + 1 ∙ 2 + 2 ∙ 4 + 3 ∙ 8) mod 5 = 4.

Одним из способов применения хеш-функций является хранение паролей. Часто бывает так, что пароли приходится хранить в незащищенной таблице базы данных, поэтому вместо них хранят хеш-функции от них. При проверке пароля вычисляется хеш-функция от введенной строки и сравнивается со значением, хранящимся в таблице.

Ваша задача состоит в том, чтобы по заданным числам x, m, L и v найти строку S из цифр от 0 до 9 длины L, значение полиномиальной хеш-функции p(S, x, m) равно v.

Входные данные
Входной файл INPUT.TXT содержит четыре целых числа: x (x – простое число, 5 ≤ x ≤ 100), m (m является степенью двойки, 1 ≤ m ≤ 256), L (10 ≤ L ≤ 100) и v (0 ≤ v ≤ m-1).

Выходные данные
В выходной файл OUTPUT.TXT выведите искомую строку или NO SOLUTION, если такой строки не существует. Если решений несколько, выведите любое.
1180Максимумы на отрезкахЗадан числовой массив A[1..N]. Необходимо выполнить M операций вычисления максимального элемента на отрезке [L, R].

Входные данные
Первая строка входного файла INPUT.TXT содержит число N – размер массива (N ≤ 105). Во второй строке записаны N чисел – элементы массива, целые числа от 1 до 105. Третья строка содержит натуральное число M – количество запросов максимума (M ≤ 30 000). Следующие M строк содержат пары чисел L и R (1 ≤ L ≤ R ≤ N), описывающие отрезки.

Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса выведите значение максимума на отрезке через пробел.
1181Число нулей на отрезкеЗадан числовой массив A[1..N]. Необходимо выполнить M операций вычисления количества нулевых элементов на отрезке [L, R].

Входные данные
Первая строка входного файла INPUT.TXT содержит число N – размер массива (N ≤ 105). Во второй строке записаны N чисел – элементы массива, целые числа от 0 до 105. Третья строка содержит натуральное число M – количество запросов (M ≤ 30 000). Следующие M строк содержат пары чисел L и R (1 ≤ L ≤ R ≤ N), описывающие отрезки.

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.
185СкачкиИван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил проверить, сможет ли она выиграть у всех остальных лошадей. Иван Иванович раздобыл информацию, в которой для некоторых пар лошадей сообщается, какая из этих лошадей быстрее. Также он узнал, что у всех лошадей разные скорости.

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

Входные данные
Входной файл INPUT.TXT содержит в первой строке два целых числа N (1 ≤ N ≤ 100) и K (1 ≤ K ≤ N), где N – количество лошадей, принимающих участие в скачках, K – номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 ≤ X, Y ≤ N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо.

Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна.

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
128Один коньНа шахматной доске N×N в клетке (x1,y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2,y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Входные данные
Входной файл INPUT.TXT содержит пять чисел: N, x1, y1, x2, y2 (5 ≤ N ≤ 20, 1 ≤ x1, y1, x2, y2 ≤ N). Левая верхняя клетка доски имеет координаты (1,1), правая нижняя - (N,N).

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

Входные данные
В первой строке входного файла INPUT.TXT находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, английской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, английской заглавной X - конечное положение шарика. (2 ≤ N ≤ 250)

Выходные данные
В выходной файл OUTPUT.TXT выведите в первой строке «Y», если движение возможно, или «N», если нет. Если движение возможно, то далее следует вывести N строк по N символов - как и на вводе, но буква X, а также все точки по пути следует заменить плюсами. Если решений несколько, выведите любое.
135Алгоритм ФлойдаПолный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.