Задача 1. Коза
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда |
Ограничение по памяти: | 64 мегабайта |
На лугу пасется коза. Пете надо загнать её во двор. Как-то раз, Петя обратил внимание, что когда коза пасётся на лугу, она всегда ходит по периметру треугольника: от первой точки ко второй, от второй к третьей, от третьей к первой и т. д. Причём территорию внутри этого треугольника она считает “своей”, и очень пугается, когда туда кто-нибудь заходит.
Петя заметил, что когда коза ходит по периметру треугольника, то один её бок всегда находится на внутренней стороне треугольника, и к козе нельзя подходить с этой стороны. Зато другой бок всегда повернут к внешней стороне. Помогите Пете узнать, с какой стороны ему лучше подойти к козе.
Входные данные
В первой строке входного файла даны координаты первой точки треугольника, а во второй и в третьей строке, соответственно, координаты второй и третьей точек. Координаты каждой точки представлены парой целых чисел X, Y, разделённых пробелом (–10000 £ X, Y £ 10000) . Известно, что заданные точки не лежат на одной прямой.
Выходные данные
В выходной файл необходимо вывести всего одну букву: “R” или “L”, обозначающую правую или левую сторону, соответственно.
Пример
input.txt | output.txt |
1 1 3 1 1 3 | R |
Задача 2. Минимумы
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
Дана прямоугольная таблица, содержащая целые числа из диапазона –109..109. Вместо нее нужно построить новую таблицу, состоящую из чисел, полученных следующим образом: на [i, j]-ом месте (на рисунке этот элемент заштрихован крестиком) должен стоять минимум среди всех чисел из области, ограниченной сверху и слева краями таблицы, снизу — строкой с номером i, а справа – линией, параллельной побочной диагонали, и проходящей через клетку [i, j].
j | ||||||||
i | ||||||||
Входные данные
Во входном файле содержится следующая информация:
в первой строке два целых числа M и N — количество строк и столбцов в исходной таблице (1 £ M, N £ 10000); далее в М строках по N целых чисел, разделенных пробелами — запись таблицы.
Выходные данные
В выходной файл нужно вывести М строк по N целых чисел, разделенных пробелами — запись полученной таблицы минимумов.
Пример
input.txt | output.txt |
4 6 1 30 -0 | 1 -1 -1 -3000 |
Задача 3. Вид четырехугольника
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
На плоскости задано четыре точки A, B, C и D. Для замкнутой ломаной ABCDA определить, к какому классу четырехугольников относится получившаяся фигура:
вырожденным (все четыре точки лежат на одной прямой), частично-вырожденным (три точки из четырёх лежат на одной прямой), имеющим самопересечения, невыпуклым, выпуклым.Если четырёхугольник относится одновременно к двум классам, то программа должна выдать тот класс, чей номер меньше.
Входные данные
В единственную строку входного файла записано через пробел 8 чисел: XA, YA, XB, YB, XC, YC, XD, YD — соответствующие координаты точек A, B, C, D. Все числа целые и по своему абсолютному значению не превышают 1000.
Выходные данные
Для заданной замкнутой ломаной, вывести в выходной файл одно число — номер класса, к которому относится получившаяся фигура.
Примеры
input.txt | output.txt |
2 | |
5 | |
3 | |
1 |
Задача 4. Лабиринт
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
Как известно, из любого лабиринта можно заведомо найти выход, если начать его «инспекцию» от входа, а затем двигаться, все время касаясь левой (или правой – на выбор) стены рукой.
Однако со времен фараоновых гробниц лабиринты строили весьма умные люди, это правило было им известно, и они старались сделать так, чтобы при подобном обходе лабиринта «посетитель» заведомо не попал в самые интересные места, — скажем, в те комнаты, где хранятся главные сокровища.
e | ||
Например, в лабиринте, схематично изображенном на рисунке, найти выход очень просто, а вот клад — попросту невозможно.
Итак, по имеющемуся плану лабиринта нужно определить, есть ли в нем недоступные области. Причем, обходить лабиринт можно любым способом.
Входные данные
В первой строке входного файла задано одно целое число N — размер лабиринта (лабиринт у нас квадратный, 3 ≤ N ≤ 1000). Далее N строк содержат по N символов, описывающих сам лабиринт: стенки изображаются звездочками, пустоты — пробелами. Считается, что вход в лабиринт располагается в самой первой строке (мы ведь всегда можем развернуть карту так, как нам удобнее).
Выходные данные
В выходной файл нужно вывести одно число — количество недоступных областей лабиринта. Недоступные области считаются различными, если из одной нельзя попасть в другую (проходы «по диагонали» не учитываются).
Пример
input.txt | output.txt |
7 *** *** * * * *** * * * * * * *** * * * ******* | 1 |
Задача 5. Считалка
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
Вы попали на некоторый остров (название которого мы не назовем, чтобы избежать нападения). На нем живет племя, имя которого “Eeny Meenys”. Они получили его благодаря способу, посредством которого они ежегодно избирали главу племени.
Как оказалось, корреспондент одной газеты тоже когда-то побывал в этом племени. Он четко изложил им основные идеи цивилизации, но, по-видимому, весьма неудачно закончил там свою работу.
Итак, племя никогда не имеет постоянного вождя, срок его правления ровно год. В конце этого срока они его просто съедают и выбирают следующего правителя. Их метод выбора основан на считалке “Eeny meeny miny mo!”. Все имеющие право быть избранными члены племени (женщины тоже могут быть избраны — это благо цивилизации в племени прижилось) вставали в круг, выбиралось начало отсчета, и главный лекарь племени (он не выбирался на роль вождя) шел по кругу и считал: `E', `e', `n', `y', `M', `e', `e', `n', `y', `M',`i', `n', `y', `M', `o!', `E', `e', `n', `y', `M', `e', `e', `n', `y', `M', `i', `n', `y', `M', `o!', ... На каждое `o!', человек, на которого он указывал, выходил из круга, а круг смыкался, и счет начинался со следующего за удаленным человека. Этот процесс продолжался, пока в круге не оставался только один человек — новый вождь.
В то время как возможность пожить целый год в лучах славы делает работу вождя весьма привлекательной для его соплеменников, вас не может соблазнить краткость этой славы. Вам удалось узнать, что счет в этом году будет начинаться с человека по имени Миксгобвоуку (очень высокий мужчина), поэтому вам хотелось бы знать, куда не нужно становиться. Вы не знаете ни направления счета, ни количества людей, которые могут быть избраны, но вы можете оценить их число.
Напишите программу, которая определит первую (самую близкую к Миксгобвоуку) безопасную позицию в круге, куда нужно встать, независимо от реального количества людей и от направления счета (по часовой стрелке или против).
Входные данные
Входной файл содержит два целых числа M и N, записанных через пробел — минимальное и максимальное количество людей, участвующих в выборах (1 < M £ N < 500).
Выходные данные
В выходной файл нужно вывести единственное целое число — номер ближайшей позиции к Миксгобвоуку, на которой человек не будет избран вождем для любого числа людей из заданного диапазона и независимо от направления счета. Если ни одной безопасной позиции не окажется, то нужно вывести слово NO.
Примеры
input.txt | output. txt |
80 150 | 1 |
40 150 | NO |
Задача 6. Вычислитель
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
Язык вычислений CL (Calculator Language) поддерживает операцию присваивания, положительные и отрицательные целые, а также простую арифметику. В язык CL включены следующие допустимые символы:
A .. Z | имена переменных | / | операция целочисленного деления |
0 .. 9 | цифры | = | операция присваивания |
+ | операция сложения | ( ) | скобки |
– | операция вычитания | _ | знак отрицания для чисел (подчерк) |
* | операция умножения |
Все операции имеют одинаковый приоритет и применяются справа налево. Например, выражение 15 – 8 – 3 вычисляется так же, как выражение 15 – (8 – 3), и его значение равно 10. Выражение, заключенное в скобки, как всегда, выполняется первым. Скобки могут быть много раз вложены друг в друга. В выражении никогда не встречаются два знака операции, идущие один за другим (даже если они отделены скобкой), перед операцией присваивания всегда стоит переменная, кроме того, самая левая операция в выражении — это операция присваивания. Для удобочитаемости пробелы можно вставлять в любое место выражения, за исключением промежутка между знаком отрицания и цифрой. Знак отрицания не может появиться перед переменной. Все переменные в начальный момент инициализируются нулем (0) и сохраняют свои значения до тех пор, пока они не изменятся явно.
Напишите программу, которая получает на вход и вычисляет выражение, написанное на этом языке. Каждое выражение занимает одну строку и содержит, по крайней мере, одну операцию присваивания, но их может быть и больше. Гарантируется, что результат вычислений нигде не превзойдет по модулю
Входные данные
Входной файл содержит последовательность строк, в каждую из которых записано правильное выражение на языке CL. Длина любой строки не превышает 100 символов. Последняя в файле строка содержит единственный символ ‘#’.
Выходные данные
В выходной файл нужно вывести последовательность строк, соответствующих строкам входного файла, каждая из которых должна содержать список заключительных значений всех переменных, чьи значения изменились в результате вычисления заданного выражения. Если более одной переменной изменило значения, то они должны быть выданы через запятую в алфавитном порядке. Если переменная изменила значение более одного раза в выражении, то нужно вывести только последнее значение. Считается, что переменная изменила свое значение, если после вычисления выражения ее значение отличается от того, которое было перед началом вычисления выражения. Если ни одна переменная не изменит значение, то нужно выдать строку “No Change”. Строго придерживайтесь формата выдачи результата, который показан в примере.
Пример
input.txt | output. txt |
A = B = 4 C = (D = 2)*_2 C = D = 2 * _2 F = C – D E = D * _10 Z = 10 / 3 # | A = 4, B = 4 C = -4, D = 2 D = -4 No Change E = 40 Z = 3 |
Задача 7. Лягушка возвращается
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
С левого берега реки на правый пытается перебраться лягушка. Поперек реки по прямой лежат камни, по которым она может прыгать. Длина прыжка лягушки, так же как ширина реки и расстояния между камнями выражаются целыми числами. Лягушка может менять длину прыжка. Каждый следующий прыжок может быть сделан на единицу больше или меньше предыдущего. Первый прыжок с берега лягушка совершает длиной в 1. Лягушка может приземляться только на камни или на края берегов. Максимальная длина прыжка лягушки равна 50. Считается, что лягушка завершила путешествие, если она совершила прыжок на правый берег единичной длины. Число камней находится в интервале [0..255]. Максимальное расстояние между берегами реки 256, минимальное 1.
Требуется написать программу, определяющую минимальное количество прыжков, которые потребуются лягушке, чтобы пересечь реку, если такое возможно.
Входные данные
Входной файл содержит последовательность натуральных чисел. Первое число — расстояние между левым берегом и первым камнем. Следующие числа — расстояния между рядом стоящими камнями по порядку. Последнее число — расстояние между последним камнем и правым берегом. Числа в файле разделены пробелами или символами перехода на новую строку.
Выходные данные
В выходной файл нужно вывести одно целое число – минимальное количество прыжков. Если реку по заданным правилам перепрыгнуть невозможно, то вывести слово no.
Пример
input. txt | output. txt |
|
1 1 2 1 | 9 |
Задача 8. Лазерные линии
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды |
Ограничение по памяти: | 64 мегабайта |
Изготовитель компьютерных чипов изобрел новый способ комбинирования оптоэлектроники и обычной электроники: смонтировать на поверхности чипа свето-испускающие и свето-принимающие узлы, которые могут передавать друг другу сигналы по прямым лучам. За счет увеличенной плотности передачи информации быстродействие чипа значительно возрастет. Единственная сложность состоит в том, что все узлы должны быть в состоянии обмениваться сигналами друг с другом; никакой узел не должен перекрывать линию видимости между двумя другими узлами. При существующем способе производства все рабочие узлы помещаются точно в узлах решетки, покрывающей поверхность чипа, поэтому их координаты задаются целыми числами от 0 до 9999 включительно (кроме узла с координатами (0,0), в котором по техническим причинам рабочий узел не может быть помещен).
Напишите программу, которая прочитает наборы координат рабочих узлов и определит, имеются ли среди них группы узлов (3 и более), лежащих на одной линии. Поскольку используется метод планировки, то заранее можно сказать, что может быть несколько троек узлов, лежащих на одной линии, но более «длинные» наборы встречаются редко. В любом случае, более 10-ти узлов не могут выстроиться в одну линию.
Входные данные
Входной файл содержит координаты от 3 до 300 (включительно) узлов. Набор координат заканчивается парой нулейКоординатами узлов служат пары чисел из диапазона [0..9999], разделенные одним или несколькими пробелами или концами строк, при этом гарантируется, что концы строк не разрывают координатные пары.
Выходные данные
В выходной файл нужно занести либо строку «No lines were found», либо сообщение «The following lines were found:», а затем вывести группы узлов, лежащих на одной линии — упорядоченных по возрастанию координаты х, а среди узлов с одинаковой координатой х — по координате у. Все координаты должны быть записаны в поля длины 4 и разделены запятыми, узлы обозначаются круглыми скобками, без дополнительных пробелов. Информация о линиях должна быть упорядочена по тому же правилу: по координатам узлов, являющихся началом линий. Если несколько линий начинаются в одном узле, то по координатам вторых узлов.
Примеры
input.txt | output. txt |
8 20 15 1 | The following lines were found: ( 4, 8)( 8, 7)( 12, 6) ( 5, 5)( 8, 7)( 14, 11)( 20, 15) ( 12, 6)( 14, 11)( 18, 21) |
0 | No lines were found |
100 0 | The following lines were found: ( 5, 5)( 10, 11)( 20, 23) ( 5, 5)( 15, 11)( 20, 14)( 25, 17) |
