Задача «Долины и горы»

Задача «Шаблоны»

Шаблоном называется строка, состоящая из английских букв (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