Ввод 1 Ввод 2 Ввод 3

Пример

Ввод 1 Ввод 2 AB IOX Вывод 1 Вывод 2 AB XOIBA OIX IXO XIO OXI IOX

2. «Электронная таблица» (15 баллов)

Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от A до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например, B1, S8.

Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки, бинарные операторы +, -, *, / (целочисленное деление). Так, 567, E8/2, (3+B3)*(C4-1) являются правильными выражениями. Все операторы целочисленные. Деление на ноль дает в результате ноль.

Если значение ячейки, на которую ссылается некоторое выражение, не определено, оно считается равным нулю. Ситуация, когда две или более ячейки зависят друг от друга, является отдельным случаем – циклической ссылкой.

Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000.

Ввод из файла sprsheet.in. Первая строка содержит число выражений N. Следующие N строк имеет формат <имя клетки>=<выражение>. Все выражения корректные каждая ячейка определена не более чем одним выражением.

Вывод в файл sprsheet.out. В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.

Пример

Ввод

A1=B1+C5

B1=20

C5=B1 /D7-E1*E1

E1=(3+1)*2

Вывод

-44

3. «Упаковка символов» (15 баллов)

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD – это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

· Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности дает ту же последовательность из одного символа.

· Если S и Q – упакованные последовательности, то SQ – также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.

· Если S – упакованная последовательность, то X (S) – также упакованная последовательность, где X – десятичное представление целого числа, большего 1. Если S распаковывается в S', то X (S) распаковывается в S', повторенную X раз.

Следуя этим правилам, легка распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.

Ограничения: длина исходной последовательности от 1 до 100.

Ввод из файла folding.in. В первой строке находится последовательность символов от A до Z.

Вывод в файл folding.out. В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.

Пример

Ввод 1 Ввод 2 AAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES Вывод 1 Вывод 2 9(A)3(AB)CCD 2(NEERC3(YES))

4. «Двойная решетка» (10 баллов)

Две бесконечные равномерные прямоугольные решетки заданы размерами ячеек x ₁ ´ y ₁ и x ₂ ´ y ₂. Решетки расположены на плоскости параллельно друг другу и координатным осям так. Что смещение одного из узлов второй решетки относительно узла первой составляет D_x по горизонтали и D_y по вертикали. В результате наложения образуется новая, «составная» решетка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решетки.

Ограничения: 1 ≤ x ₁, y ₁, x ₂, y ₂ ≤ 100, 0 ≤ D_x < x ₁, 0 ≤ D_y < y ₁, все числа целые.

Ввод из файла dlattice.in. В первой строке находятся числа x ₁, y ₁, x ₂, y ₂, D_x, D_y, разделенные прбелами.

Вывод в файл dlattice.out. В первой строке вывести N – количество получившихся площадей, а в следующих N строках – сами площади.

Пример

Ввод 20 20 12 10 2 0 Вывод 42060100120

1. «Совершенные числа» (5 баллов)

Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Найти все совершенные числа от M до N. Если в указанном интервале совершенных чисел нет, сообщить об этом.

Ограничения: M и N – целые, ,

Вход: из файла perfect.in. В первой строке находятся разделенные пробелом числа M и N.

Вывод: в файл perfect.out. В каждой строке вывести по одному числу в порядке возрастания. Если совершенных чисел в промежутке нет, вывести Absent.

Примеры:

Ввод 1 Ввод 2 6 6 4 5 Вывод 1 Вывод 2 6 Absent

2. «Умножение многочленов» (10 баллов)

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

Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 10⁴.

Ввод из файла polymul.in. В двух строках находятся многочлены.

Вывод в файл polymul.out. В единственной строке выводится многочлен.

Пример

Ввод 1 Ввод 2 Ввод 3 0 x+1 -50 x-1 x^2+x+x-2x^3 Вывод 1 Вывод 2 Вывод 3 0 x^2-1 10x^3-5x^2-10x

3. «Электронная таблица» (15 баллов)

см. 2008 год

4. «Упаковка символов» (20 баллов)

см. 2008 год

1. «Граница многоугольника» (10 баллов)

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних — в вершинах) и не пересекаются.

Ограничения: , координаты вершин целые и по модулю не превосходят 1 000 000 000.

Вход: из файла border.in. В первой строке содержится число N, в следующих N строках — пары чисел — координаты точек. Если соединить точки в заданном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Вывод: в файл border.out. Вывести одно число — количество точек с целочисленными координатами на границе многоугольника.

Пример:

Ввод 310 00 100 0 Вывод 30

2. «Гомер Симпсон» (5 баллов)

Обеденный перерыв Гомера Симпсона составляет T мс. Один гамбургер Гомер съедает за N мс, один чизбергер — за M мс. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть с течение обеденного перерыва.

Ограничения: , все числа целые.

Ввод из файла homer.in. В первой строке находятся три числа — M, N, T, разделенные пробелами.

Вывод в файл homer.out. Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остается какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остается как можно меньше.

Пример

Ввод 1 Ввод 2 Ввод 3 3 5 54 3 5 55 4 4 6 Вывод 1 Вывод 2 Вывод 3 18 17 1 2

3. «Головоломка умножения» (20 баллов)

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от нее. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остается только две карты.

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, и подсчитать очки по следующей формуле:

/

Если бы он взял карты в обратном порядке, т. е. 50, затем 20, затем 1, количество очков было бы таким:

.

Ввод из файла mpuzzle.in. В первой строке находится число карт N, во второй – разделенные пробелами N чисел на картах.

Ограничения: , числа на картах целые от 1 до 100.

Вывод в файл mpuzzle.out. Вывести одно целое число – минимально возможное число очков.

Пример

Ввод

10 1 50 50 20 5

Вывод

4. «Дробная арифметика» (15 баллов)

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

· знак числа (пишется только в случае, когда его отсутствие изменяет число);

· целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);

· пробел (не пишется, если отсутствует целая или дробная часть);

· числитель (если он не равен нулю);

· знак / (если есть числитель);

· знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0…30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Ввод из файла frac-ar.in. В первой строке вводится дробь (первый операнд), во второй – знак операции («+» – сложение, «-» – вычитание, «*» – умножение, «/» – деление), в третьей строке – дробь (второй операнд). Обе дроби могут быть сократимы.

Вывод в файл frac-ar.out. В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.

Пример

Ввод -3 1/6+2/4 Вывод -2 2/3

Вуз

1. «выражение» (10 баллов)

Даны N целых чисел X ₁, X ₂, …, X_n. Расставить между ними знаки «+» или «–» так, чтобы значение получившегося выражения было равно заданному целому S.

Ограничения: .

Вход: из файла expr.in. В первой строке находятся числа N и S. В следующей строке — N чисел через пробел.

Вывод: в файл expr.out. Если получить требуемый результат невозможно, вывести «No solution», если можно — то вывести равенство. Если решение не единственное, то вывести любое.

Пример:

Ввод 1 Ввод 2 3 10 2 10015 25 30 10 10 Вывод 1 Вывод 2 15+25-30=10 No solution

2. «Возрастающая подпоследовательность» (15 баллов)

Даны N целых чисел X ₁, X ₂, …, X_n. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Ограничения: .

Ввод из файла incseq.in. В первой строке находится число N. В следующей строке — N чисел через пробел.

Вывод в файл incseq.out. В первой строке выводится количество невычеркнутых чисел, во второй — сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько — вывести любой.

Пример

Ввод 62 5 3 4 6 1 Вывод 42 3 4 6

3. «Игра "Даты"», «2012» (15 баллов)

Играют двое. Задается какая-то дата 2012 года (2004 года). Каждый игрок на своем ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты, вывести, кто выиграет.

Ограничения: месяц от 1 до 12, день от 1 до числа дней в месяце, даты «31 декабря» во входных данных нет.

Ввод из файла dategame.in. В первой строке находятся разделенные пробелом числа, обозначающие день и месяц.

Вывод в файл dategame.out. Вывести 1, если выигрывает первый (начинающий) игрок, или 2 — в противном случае.

Пример

Ввод 1 Ввод 2 Ввод 3

30 12 29 12 29 11

Дата добавления: 2015-11-16