Примеры. Примечание. Пример не содержит цифры ноль, потому что она выглядит практически так же, как символ химического элемента кислорода

⇐ ПредыдущаяСтр 6 из 13Следующая ⇒

Ввод 1 C2H5OH+3O2+3(SiO2)72CO2+3H2O+3SiO22C+6H+13O+3Si99C2H5OH+3SiO23SiO4+C2H5OHC2H5OH+3O2+3(SiO2)+Ge3(Si(O)2)+2CO+3H2O+O22CO+3H2O+3O2+3Si Вывод 1 C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2C2H5OH+3O2+3(SiO2)==2C+6H+13O+3SiC2H5OH+3O2+3(SiO2)! =99C2H5OH+3SiO2C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OHC2H5OH+3O2+3(SiO2)! =C2H5OH+3O2+3(SiO2)+GeC2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2C2H5OH+3O2+3(SiO2)! =2CO+3H2O+3O2+3Si

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

Задача 25. Последовательность

В последовательности чисел a ₁, a ₂, a ₃,... задан первый член, а остальные вычисляются по формуле a_i = (a_i _{- 1})² mod 10 000. Найти N -й член последовательности.
Ограничения: 0 < = a ₁ < 10 000, 1 < = N < = 2 000 000 000, время 1 с.
Ввод из файла seq.in. В первой строке находятся числа a ₁ и N, разделённые пробелом.
Вывод в файл seq.out. Вывести одно число - a_N.
Примеры

Ввод 1 Ввод 2 4 3 0 2000000000 Вывод 1 Вывод 2 256 0

Задача 26. Провода

Дано N отрезков провода длиной L ₁, L ₂,..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
Ограничения: 1 < = N < = 10 000, 1 < = K < = 10 000, 100 < = L_i < = 10 000 000, все числа целые, время 1 с.
Ввод из файла cable.in. В первой строке находятся числа N и К. В следующих N строках - L ₁, L ₂,..., L_N, по одному числу в строке.
Вывод в файл cable.out. Вывести одно число - полученную длину отрезков.
Примеры

Ввод 1 4 11802743457539 Вывод 1 200

Задача 27. Палиндромы

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.
Ограничения: 1 < = N < = 60, время 1 с.
Ввод из файла palindr.in. В первой строке записано слово S.
Вывод в файл palindr.out. Вывести одно целое число - количество способов вычёркивания.
Примеры

Ввод 1 BAOBAB Вывод 1 22

Задача 28. Круговая площадь

Два круга заданы координатами центров в прямоугольной декартовой системе координат и радиусами. Найти площадь их пересечения.

Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000, время 1 с. Ввод из файла circarea.in. В первой строке находятся шесть вещественных чисел через пробел - координаты центров и радиусы двух кругов: x1, y1, r1, x2, y2, r2. Вывод в файл circarea.out. Вывести одно вещественное число с двумя знаками после запятой - площадь пересечения кругов. Примеры

Ввод 1 20.0 30.0 15.0 40.0 30.0 30.0 Вывод 1 608.37

Задача 29. Гомер Симпсон

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения: 1 < = M, N, T < = 1 000 000, все числа целые, время 2 с.
Ввод из файла 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

Задача 30. Дробная арифметика

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

знак числа (пишется только в случае, когда его отсутствие изменяет число);
целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
пробел (не пишется, если отсутствует целая или дробная часть);
числитель (если он не равен нулю);
знак / (если есть числитель);
знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.
Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю, время 1 с.
Ввод из файла frac-ar.in. В первой строке вводится дробь (первый операнд), во второй - знак операции (" +" - сложение, " -" - вычитание, " *" - умножение, " /" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.
Вывод в файл frac-ar.out. В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.
Примеры

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

Задача 31. Анти-QuickSort

Для сортировки последовательности чисел широко используется быстрая сортировка - QuickSort. Далее приведена программа, которая сортирует массив a, используя этот алгоритм.

var a: array [1..N] of integer; procedure QSort(left, right: integer); var i, j: integer; key: integer; buf: integer; begin key: = a[(left + right) div 2]; i: = left; j: = right; repeat while a[i] < key do {первый while} inc(i); while key < a[j] do {второй while} dec(j); if i < = j then begin buf: = a[i]; a[i]: = a[j]; a[j]: = buf; inc(i); dec(j); end; until i > j; if left < j then QSort(left, j); if i < right then QSort(i, right); end; begin... QSort(1, N); end.

Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
Ввод из файла antiqs.in. В первой строке находится единственное число N.
Ограничения: 1 < = N < = 70 000, время 1 с.
Вывод в файл antiqs.out. Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
Примеры

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

Задача 32. Строки Фибоначчи

Строку Фибоначчи F (K) для натуральных чисел K определим так: F (1) = 'A', F (2) = 'B', F (K) = F (K - 1) + F (K - 2) при K > 2, где " +" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F (N).
Ограничения: длина S от 1 до 25, 1 < = N < = 45, время 1 с.
Примечание. Длина F (45) равна 1 134 903 170.
Ввод из файла fibostr.in. В первой строке содержится число N, во второй - строка S.
Вывод в файл fibostr.out. Выводится одно число - количество вхождений строки S в строку Фибоначчи F (N).
Примеры

Ввод 1 Ввод 2 Ввод 3 Ввод 4 1 2 8 35A ABA BBABAB BBABAB Вывод 1 Вывод 2 Вывод 3 Вывод 4 1 0 3 1346268

Задача 33. Игра в зачёркивание

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.
Ограничения: 1 < = K < = N < = 40, время 10 с.
Ввод из файла crossgam.in. В первой строке содержатся числа N и K, во второй строке N символов: латинская заглавная O - пустая клетка, латинская заглавная X - зачёркнутая клетка.
Вывод в файл crossgam.out. Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.
Примеры

Ввод 1 Ввод 2 Ввод 3 4 2 5 2 7 2OOOO OOOOO OXXOXXO Вывод 1 Вывод 2 Вывод 3 1 2 0

Задача 34. Граница многоугольника

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 < = N < = 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000, время 2 с.
Ввод из файла border.in. В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод в файл border.out. Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.
Примеры

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

Задача 35. Путь спелеолога

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N ³ кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.
Ограничения: 1 < = N < = 30, время 1 с.
Ввод из файла speleo.in. В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # - обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.
Вывод в файл speleo.out. Вывести одно число - длину пути до поверхности.
Примеры

Ввод 1 3 ######.##.#..#S.#. ###...### Вывод 1 6 Комментарий 1 Нужно спуститься на уровень вниз, сделать два движения на запад, подняться на уровень вверх, сделать движение на юг, подняться на уровень вверх.

Задача 36. Дырявая ткань

На столе лежат несколько кусков ткани, не перекрывая друг друга. Эти куски могут иметь дыры, в том числе и настолько большие, что в них может поместиться целый кусок ткани. Был получен чёрно-белый образ поверхности стола, на котором области, покрытые тканью, представлены символами *, а свободные площади - точками. Один кусок ткани, таким образом, представлен 4-связной областью символов *, то есть группой *, соседствующих друг с другом горизонтально или вертикально, но не по диагонали.

.***..***.*.*.**.*.***.*.***...**.*.

На схеме три куска - один без дыр, а два - с одной дырой каждый: первый площадью 8, второй - площадью 12.

Ваша цель - найти кусок с наибольшим количеством дыр в нём. Дыра - это 4-связная область точек, полностью окружённых символами *. Если несколько кусков имеют одинаковое количество дыр, нужно выбрать кусок минимальной площади.

Ввод из файла holey.in. В первой строке содержатся два числа W и H, разделённые пробелами. Следующие H строк содержат по W символов каждая. Символы в этих строках - или * (ASCII 42), или точка (ASCII 46).

Ограничения: 1 < = W, H < = 100, время 1 с.

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

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал