Региональная олимпиада по информатике для школьников
БГТУ 2008 г.
Все входные данные всегда располагаются в файле INPUT. TXT, выходные в OUTPUT. TXT. Ограничение по времени – 10с на тест, если специально не указано другое. В скобках после названия задачи указано максимальное количество баллов за нее.
Задача 1. Число (6)
По заданным числам a, b, c и d, найдите наименьшее натуральное число n, большее ac, которое нельзя представить в виде произведения двух натуральных чисел u и v, таких что a ≤ u ≤ b и c ≤ v ≤ d.
Входной файл содержит одну строку, состоящую из натуральных чисел a, b, c, d (1 ≤ a ≤ b ≤ 106, 1 ≤ c ≤ d ≤ 106).
Выведите в выходной файл искомое число n.
Пример входного файла | Пример выходного файла | Пример входного файла | Пример выходного файла |
3 | 7 |
Задача 2. Зоопарк (6)
В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов. Нужно определить сколькими способами можно выбрать трех животных для участия в выставке.
Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных: первый медведь, тигр и лев; первый медведь, тигр и пингвин;первый медведь, лев и пингвин;второй медведь, тигр и лев; второй медведь, тигр и пингвин; второй медведь, лев и пингвин;тигр, лев и пингвин.
В первой строке входного файла содержится натуральное число n - количество видов животных в городском зоопарке (1 ≤ n ≤ 105). В каждой из следующих n строк содержится одно натуральное число - количество животных соответствующего вида. Общее число животных в зоопарке не превышает 105.
В выходной файл выведите количество способов выбрать трех животных для международной выставки.
Пример входного файла | Пример выходного файла | Пример входного файла | Пример выходного файла |
4 2 1 1 1 | 7 | 3 30000 30000 30000 |
Задача 3. Белоснежка и гномы (8)
У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно ai минут, и после этого он будет спать ровно bi минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Первая строка входного файла содержит число n (1 ≤ n ≤ 105), вторая строка содержит числа a1, a2, ..., an, третья - числа b1, b2, ..., bn (1 ≤ ai, bi ≤ 109).
Выведите в выходной файл n чисел - порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.
Пример входного файла | Пример выходного файла | Пример входного файла | Пример выходного файла |
2 1 10 10 20 | 2 1 | 2 10 10 10 10 | -1 |
Задача 4. Выражение (8)
В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков «+» или «ˣ» таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.
Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 ˣ 3 ˣ 1 ˣ 2 ˣ 3. Значение выражения в этом случае равно 37.
Первая строка входного файла содержит число n (2 ≤ n ≤ 200000).
Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 109.
Выведите в выходной файл оптимальное выражение. В качестве знака «ˣ» выводите символ «*» (звездочку). Если оптимальных решений несколько, выведите любое из них.
Пример входного файла | Пример выходного файла |
6 | 1+2*3*1*2*3 |
Задача 5. Куча камней (4)
Имеется N (1 £ N £ 20) камней с весами W1…Wn (1 £ Wi £ 100000). Написать программу, которая разложит их по двум кучам, так что разница между их весом будет минимальна.
Во входном файле содержится число N и далее следуют веса камней. Выходной файл должен содержать минимальную разницу в весе куч камней.
Пример входного файла | Пример выходного файла |
5 5 8 13 27 14 | 3 |
