[Показать меню]

Контрольная работа

Оценка за контрольную складывается из количества решенных задач и языка, на котором задача решена. Решение задачи на Lua даёт 1 балл к оценке, а на C - 2 балла к оценке. По каждой задаче можно набрать не более двух баллов суммарно. Студенты, сделавшие хотя бы одну домашнюю работу по Lua и хотя бы одну по С, получают +1 к оценке (результат выполнения проверяется по github и по kodomoquiz.tk). Для успешной сдачи контрольной необходимо набрать хотя бы 3 балла.

Код решения записывайте в файл с именем <Фамилия>_cw_<мнемоника-задачи>.lua или <Фамилия>_cw_<мнемоника-задачи>.c при решении на Lua и C соответственно. Пример: Ivanov_cw_max.lua.

Файл с решением загружайте на сайт http://hometask.kodomoquiz.tk/ и зовите преподавателя в случае успешного решения. Успешное решение - это решение, на которое проверяющий сайт выдаёт оценку хотя бы 3 балла. Если решение не проходит, сайт скажет, что не так, и приведёт пример входных данных, на которых вылезает ошибка.

Во время контрольной запрещается использовать чужие решения!

Подсказки даются после условий задач, в которых требуется придумать алгоритм, а не просто "закодить" готовый алгоритм. Если хотите сами поразмыслить над алгоритмом, пропускайте эти подсказки.

Если задача не идёт, не застревайте на ней и переходите к следующей. Задачи расположены в произвольном порядке, а не по возрастанию сложности.

Все задачи были взяты из разных источников, которым выражается благодарность за их существование!

Задача 1 "Максимум из двух чисел". Мнемоника max

Условие задачи взято отсюда.

Входные данные

Даны два целых числа, каждое число записано в отдельной строке.

Выходные данные

Выведите наибольшее из данных чисел.

Примеры

Входные данные

1
2

Выходные данные

2

Задача 2 "Экзамен". Мнемоника exam

Условие задачи взято отсюда.

Экзамен для n студентов будет проходить в длинной и узкой аудитории, таким образом, студенты будут сидеть в ряд в некотором порядке. Преподаватель подозревает, что студенты с соседними номерами (i и i + 1) в течение обучения всегда сидели рядом и подружились, и если их посадить рядом на экзамене, то они наверняка будут помогать друг другу.

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

Входные данные

В единственной строке задано целое число n (1 ≤ n ≤ 5000) — количество студентов на экзамене.

Выходные данные

В первую строку выведите целое число k — максимальное количество студентов, которых можно рассадить так, что никакие два студента с соседними номерами не сидят рядом.

Во вторую строку выведите k целых различных чисел a1, a2, ..., ak (1 ≤ ai ≤ n), где ai — номер студента на i-й позиции. Студенты на соседних позициях не должны иметь соседние номера. Формально, |ai - a_i + 1| ≠ 1 для всех i от 1 до k - 1.

Если возможных ответов несколько, выведите любой.

Примеры тестов

Входные данные

6

Выходные данные

6
1 5 3 6 2 4

Входные данные

3

Выходные данные

2
1 3

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

Задача 3 "Треугольник". Мнемоника triangle

Условие задачи взято отсюда.

Если три точки лежат на одной прямой, то «треугольник» с вершинами в трёх данных точках называется вырожденным (degenerate).

Выделяют следующие виды невырожденных треугольников:

• Если все углы треугольника острые, то треугольник называется остроугольным (acute);

• Если один из углов треугольника тупой (больше 90°), то треугольник называется тупоугольным (obtuse);

• Если один из углов треугольника прямой (равен 90°), то треугольник называется прямоугольным (right). Две стороны, образующие прямой угол, называются катетами, а сторона, противолежащая прямому углу, называется гипотенузой.

Программа получает на вход длины сторон треугольника и печатает вид треугольника (см. выше перевод видов треугольников на английский).

Пример входа:

3
4
5

Пример выхода:

right

Задача 4 "Пройденный путь". Мнемоника path

Условие задачи взято отсюда.

Бортовой компьютер автомобиля Поликарпа зафиксировал, что его скорость в начале некоторого участка пути была равна v1 метров в секунду, а в конце — v2 метров в секунду. Известно, что этот участок пути занял ровно t секунд движения.

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

Входные данные

В первой строке записаны два целых числа v1 и v2 (1 ≤ v1, v2 ≤ 100) — скорости в метрах в секунду в начале участка и в его конце соответственно.

Во второй строке записаны два целых числа t (2 ≤ t ≤ 100) — время движения по участку в секундах, d (0 ≤ d ≤ 10) — максимальное значение, на которое может измениться скорость между соседними секундами.

Гарантируется, что существует способ проехать участок так, что:

• скорость в первую секунду будет равна v1,
• скорость в последнюю секунду будет равна v2,
• абсолютная величина разности скоростей в любые две соседние секунды не превосходит d.

Выходные данные

Выведите максимально возможную длину участка пути в метрах.

Примеры тестов

Входные данные

5 6
4 2

Выходные данные

26

Входные данные

10 10
10 0

Выходные данные

100

Примечание

В первом примере последовательность скоростей автомобиля Поликарпа может иметь вид: 5, 7, 8, 6. Таким образом, суммарный путь составит 5 + 7 + 8 + 6 = 26 метров.

Во втором примере, так как d = 0, автомобиль проезжает весь участок с постоянной скоростью v = 10. За t = 10 секунд он проедет расстояние в 100 метров.

Подсказка: эту задачу удобно решить с помощью рекурсии. Для случая v1=v2 ответ очевиден, а остальные случаи можно свести рекурсивно у этому случаю, "сужая" зазор между v1=v2.

Задача 5 "Платная лестница". Мнемоника staircase

Условие задачи взято отсюда.

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

Входные данные

В первой строке входного файла вводится одно натуральное число 1 <= N <= 100 — количество ступенек. В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выходные данные

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Примеры

Входные данные

3
1 3 1

Выходные данные

2

Подсказка: задачу надо решать с помощью динамического программирования: сначала решить её для N = 1, потом для N = 2 и т.д. до желаемого значения N. На каждом шагу надо использовать уже накопленные данные. Пример: чтобы узнать ответ для N=5, достаточно знать цену ступеньки №5 и ответы для N=3 и N=5.

Задача 6 "Задача о клике". Мнемоника clique

Условие задачи взято отсюда.

Задача о клике — одна из самых известных NP-полных задач. После некоторых оговорок она формулируется следующим образом. Рассмотрим неориентированный граф G. Требуется найти такое подмножество вершин C максимального размера, что любые две из них соединены ребром в графе G. Звучит просто, не правда ли? К текущему моменту не известен алгоритм, который находит решение этой задачи за полиномиальное время от размера графа. Однако, как и в случае многих других NP-полных задач, задача о клике оказывается проще, если рассмотреть граф специфического вида.

Рассмотрим n различных точек на прямой. Пусть i-я точка имеет координату x_i и вес w_i. Образуем граф G, вершинами которого являются эти точки, а рёбрами соединены в точности те пары точек (i, j), для которых расстояние между этими точками не меньше суммы их весов, формально говоря: |x_i - x_j| ≥ w_i + w_j.

Найдите размер максимальной клики в таком графе.

Входные данные

В первой строке задано число n (1 ≤ n ≤ 200 000) — количество точек.

В каждой из последующих n строк следуют по два числа x_,i , w_i (0 ≤ x_i ≤ 10⁹, 1 ≤ w_i ≤ 10⁹) — координата и вес очередной точки. Все координаты x_i различны.

Выходные данные

Выведите одно число — количество вершин в максимальной клике образованного графа.

Примеры тестов

Входные данные

4
2 3
3 1
6 1
0 2

Выходные данные

3

Примечание

Если вы вдруг умеете решать эту задачу, не используя специфические свойства графа, представленного в условии задачи, то вам полагается приз в миллион доллларов!

Изображение к тесту из условия:

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

Задача 7 "Кубики". Мнемоника cubes2

Условие задачи взято отсюда.

Прямоугольный параллелепипед размером AxBxC см³ обильно облили краской, но одна грань площади AxB см² осталась неокрашенной. Затем параллелепипед распилили на равные кубики размером 1x1x1 см³ параллельными пропилами. Полученные кубики были пересчитаны и составлена сводная таблица вида "число окрашенных граней - число кубиков".

Составьте программу, которая строит такую таблицу по известным A, B, C (целые числа).

Пример входа:

3
3
3

Пример выхода:

0 2
1 9
2 12
3 4

Дополнительные задачи (домашнее задание)

Задача "Платная лестница 2". Мнемоника staircase2

Усложнение задачи "Платная лестница". Мальчик может прыгать сразу через несколько ступенек. Со ступеньки с номером i он может попасть на любую из ступенек от i+1 до i+M включительно (при условии, что ступеньки с такими номераи есть). Число M - параметр условия, который подается после N.

Входные данные

В первой строке входного файла вводятся натуральные числа 1 <= N <= 2000000 — количество ступенек и 1 <= M <= 200000 - максимальная длина прыжка. В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выходные данные

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Примеры

Входные данные

9 3
100 100 4 200 300 6 55 10 1

Выходные данные

11

В данном случае мальчик прыгал по следующим ступенькам: 0 - 3 - 6 - 9.

Задача "Ход конем". Мнемоника knight

Конь стоит на поле с координатами (0, 0). Его задача - добраться до поля с координатами (x, y) за минимальное число ходов, не попадая в поля с отрицательными координатами. Рассчитайте это число ходов. За один ход конь изменяет одну свою координату на 1, а другую - на 2.

Входные данные

В первой строке входного файла вводятся натуральные числа 0 <= x, y <= 20000000.

Выходные данные

Выведите одно число - наименьшее число ходов.

Примеры

Входные данные

0 0

Выходные данные

0

Входные данные

1 2

Выходные данные

1

Входные данные

1 1

Выходные данные

4

Входные данные

100 50

Выходные данные

50

Входные данные

1234567 9876543

Выходные данные

4938272

Таблица правильных ответов для полей шахматной доски:

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6

Таблица правильных ответов для x, y <= 100

Визуализация ответа: