Задача «Шаблоны»
Шаблоном называется строка, состоящая из английских букв (a..z, A..Z) и символов? и *. Каждый из символов? разрешается заменить на одну произвольную букву, а каждый из символов * - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
Имеются 2 шаблона. Требуется найти длину строки минимальной длины, которая удовлетворяет обоим шаблонам. Если такой строки не существует, то вывести 0 (ноль).
Формат входного файла input.txt:
Заданные шаблоны записаны в первых двух строках, длина каждого шаблона не превышает 45 символов.
Формат выходного файла output.txt:
В выходной файл следует вывести длину строки минимальной длины, удовлетворяющей обоим шаблонам, либо "0"
Пример: Входной файл Выходной файл
A* 2
*B
Задача «Число»
Необходимо определить, является ли заданное натуральное число N, представленное в шестнадцатеричной системе счисления, числом вида 2^p - 1, где p - простое число (в десятичной системе счисления).
|
|
Формат входного файла input.txt:
Содержит одну непустую строку длиной не более 80 символов. В строке могут встречаться только цифры (0..9) и заглавные буквы английского алфавита (A..Z). Первым символом в строке не может быть цифра 0 (ноль).
Формат выходного файла output.txt:
Результат работы программы может принимать одно из следующих значений: «YES - простое число p» в десятичной системе счисления, если заданное шестнадцатеричное число является числом вида 2^p – 1 и «NO» в остальных случаях.
Пример: Входной файл Выходной файл
1 1F YES-5
2 5AM2 NO
3 3E NO
Задача «Сумма делителей»
Дано число N. Найти число из диапазона от 1 до N с максимальной суммой делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите любое из них.
Пример: Входной файл input.txt Выходной файл output.txt
5 4
Задача «Перестановка»
Целочисленный массив A[1..N] состоит из N элементов (1<=N<=20000). Элементы массива – числа от 1 до N, все числа - различные. Массив B[1..N] строится из массива A по следующему правилу:
B[A[A[i]]]=i, для каждого i от 1 до N
По введенному массиву B найти, если это возможно, массив A. Если имеется несколько вариантов решения, то привести любой из них.
|
|
Формат входного файла input.txt:
В первой строке находится целое число N – количество элементов в массиве B. В N последующих строках записаны целые числа B[1], …, B[N] по одному в строке.
Формат выходного файла output.txt:
Первая строка выходного файла содержит число N – количество элементов в массиве A, или число 0, если такого массива A не существует. В случае N>0 в N последующих строках записаны целые числа A[1], …, A[N] по одному в строке.
Пример: Входной файл Выходной файл
4 4
3 2
4 3
1 4
2 1
Задача «Оптимальная покупка»
На юбилейный вечер встречи выпускников собралась группа бывших одноклассников численностью N (1<N<40). Предварительно они договорились, что каждый выпишет чек на сумму, соответствующую части своего заработка (в условных единицах), и затем эти чеки они подарят школе. Но, собравшись у школы, они передумали и решили, что лучше будет, если они купят общий подарок. В ближайшем магазине продавец готов взять чеки только в том случае, если бывшие одноклассники составят из них сумму равную цене выбранного товара (подарка). Участники встречи первоначально выбрали K (0<K<20) товаров, из которых надо окончательно выбрать один. Товар считается выбранным оптимально, если выполняются 2 условия: 1-существует хотя бы один вариант составления суммы (из чеков участников встречи) равной цене выбранного товара; 2-количество чеков, взятых для покупки данного товара, максимально (больше чем для покупки других товаров). Составьте программу, которая решает проблему оптимальным образом. Гарантируется, что из первоначально выбранных товаров, в конечном итоге, всегда можно выбрать один. Если 2 или более товаров можно купить за одинаковое максимальное количество чеков, то выбирается товар с максимальной ценой. Если при этом товары имеют одинаковую цену, то выбирается тот, который имеет больший номер в заданной последовательности цен первоначально выбранных товаров.
Формат входного файла input.txt:
1-я строка: < N > < K > {2 целых числа через пробел}
2-я строка: <S1> <S2> … <Si> … <SN> {N целых чисел через пробел, где Si является суммой чека i-го участника встречи и может принимать значение любого целого числа из диапазона 1..100}.
3-я строка: <C1> <C2> … <Ci> … <CK> {K целых чисел через пробел, где Ci является ценой i-го товара и может принимать значение любого целого числа из диапазона 1..10000}.
Формат выходного файла output.txt:
1-я строка: <максимальное количество чеков взятых для покупки> {1 целое число}
2-я строка: <номер выбранного товара> < цена этого товара> {2 целых числа через пробел}
Пример: Входной файл Выходной файл
1 5 3 3
3 2 5 7 5 1 12
12 2 26
2 5 3 5
3 2 5 7 5 3 22
2 12 22
Задача «Долины и горы»
Задана числовая последовательность a1, a2,... aN.
Назовём отрезок aS, aS+1,... aF-1, aF из нескольких подряд идущих элементов заданной последовательности горой, если последовательность сначала возрастает на этом отрезке, а затем убывает, или, более строго: если существует такой номер H (S<H<F), что
|
|
aK<aK+1 для всех K от S до H-1, и
aK>aK+1 для всех K от H до F-1.
Высотой горы назовём величину min (H-S, F-H).
Аналогично, назовём отрезок aS, aS+1,... aF-1, aF из нескольких подряд идущих элементов заданной последовательности долиной, если последовательность сначала убывает на этом отрезке, а затем возрастает, или, более строго: если существует такой номер H (S<H<F), что
aK>aK+1 для всех K от S до H-1, и
aK<aK+1 для всех K от H до F-1.
Глубиной долины назовём величину min (H-S, F-H).
Задача состоит в том, чтобы найти высоту самой высокой горы и глубину самой высокой долины.
Формат входного файла input.txt:
Первая строка входного файла содержит единственное натуральное число N (N<=100000) – количество чисел в заданной последовательности. Вторая строка содержит N целых чисел – элементы заданной последовательности. Соседние числа в строке разделены одним пробелом. Все элементы последовательности не превосходят по абсолютной величине 1000000.
Формат выходного файла output.txt:
В единственной строке выходного файла должны находиться два целых числа, разделённых пробелом – высота самой высокой горы и глубина самой глубокой долины. Если в заданной последовательности нет гор или долин, то на соответствующем месте следует выводить 0.
Пример: Входной файл Выходной файл
1 10 1 3
4 4 1 6 3 2 1 2 5 7
2 10 1 0
2 3 4 5 6 7 8 9 10 9