XX ОЛИМПИАДА ШКОЛЬНИКОВ КРАСНОЯРСКОГО КРАЯ ПО ИНФОРМАТИКЕ
2006-2007 УЧЕБНЫЙ ГОД
(II этап - районный)

ЗАДАЧИ

ЗАДАЧА 1

Максимальная оценка: 100 баллов

В декартовой системе координат на плоскости заданы координаты вершин треугольника и еще одной точки.
Требуется написать программу, определяющую, принадлежит ли эта точка треугольнику.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Максимальное время работы на одном тесте: 1 секунда
Формат входных данных
В четырех строках входного файла находятся пары целых чисел - координаты точек. Числа в первых трех строках - это координаты вершин треугольника (x1; y1), (x2; y2), (х3; у3), в четвертой строке - координаты тестируемой точки (x4; у4).
Ограничения на входные данные:
        1) -10 000 < хi, уi < 10 000 (i = 1, 2, 3, 4).
Формат выходных данных
В выходной файл выводится слово «In», если точка находится внутри треугольника, или «Out» - если снаружи.
Примеры входных и выходных файлов

Решение задачи №1

ЗАДАЧА 2

Максимальная оценка: 100 баллов

Даны два целых неотрицательных числа A и В.
Требуется написать программу, вычисляющую их сумму.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Максимальное время работы на одном тесте: 1 секунда
Формат входных данных
Во входном файле записаны целые неотрицательные числа А и В по одному в строке.
Ограничения на входные данные:
         1) A, B < 10¹⁰⁰.
Формат выходных данных
В выходной файл выведите единственное число без лидирующих нулей: А + В.
Примеры входных и выходных файлов

Решение задачи №2

ЗАДАЧА 3

Максимальная оценка: 100 баллов

Будем рассматривать слова из больших латинских букв и шаблоны, состоящие из больших латинских букв и символов «?» и «*». Говорят, что слово подходит под шаблон, если в шаблоне можно заменить каждый символ «?» на большую латинскую букву, а каждый символ «*» - на последовательность (возможно, пустую) больших латинских букв, так, чтобы получилось требуемое слово.
Требуется написать программу, определяющую, подходит ли слово под шаблон.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Максимальное время работы на одном тесте:3 секунды
Формат входных данных
В первых двух строках входного файла записаны шаблон и слово: в одной строке записан шаблон - последовательность больших латинских букв, «?» и «*», в другой - слово, состоящее только из больших латинских букв.
Ограничения на входные данные:
1) строки входного файла короче 256 символов.
Формат выходных данных
В выходной файл выводится слово «YES», если слово подходит под шаблон, или «NO» - если нет.

Решение задачи №3

ЗАДАЧА 4
(Задача XIX краевой олимпиады школьников Красноярского края по информатике)

Максимальная оценка: 100 баллов

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать...
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык - язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали «унарный минус»: вместо «-5» они писали «0-5»). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью «18=7 (5 3) 2», то возможна такая расстановка знаков: «18=7+(5-3)*2» (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью «5=3 3», то марсиане явно не имели в виду числового равенства, когда писали это...
Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.
Технические требования
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 32 мегабайта
Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 230, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 230. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).
Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа «-1». Выходная строка не должна содержать пробелов.
Примеры входных и выходных файлов

Решение задачи №4