Задания по информатике

Задача Оранжерея (ORANGERY)

Крыша оранжереи имеет форму правильного треугольника со стороной N. Прямыми параллельными сторонам крыша разделена на стеклянные пластины, являющиеся правильными треугольниками со стороной 1. В вершинах эти маленькие треугольники скреплены болтами. Болты пронумерованы последовательно натуральными числами, начиная с 1, по строкам сверху вниз. В каждой строке нумерация идет слева направо. Аналогичным образом пронумерованы пластины (см. рисунок). Если один из болтов сломается, то все скрепленные им пластины становятся ненадежными и могут упасть. Инженер по технике безопасности хочет узнать, какие пластины могут упасть, если сломается некоторый болт.

Формат ввода/вывода:

Напишите программу ORANGERY, которая считывает с клавиатуры два целых числа: длина стороны крыши N, и номер K болта, для которого требуется произвести проверку. Программа должна вывести номера ненадежных пластин в порядке возрастания.

Ограничения: 1 ≤ N ≤ 65 535.

Пример:

Задача Дом (HOUSE)

Новый русский Витек приватизировал участок в Междолине размером m квадратов с севера на юг и n квадратов с запада на восток. Он решил построить в пределах этого участка дом размером a квадратов с севера на юг и b – с запада на восток. Некоторые квадраты радиоактивны, и Витек не хочет на них строить дом.  Кроме того, Витек хочет, чтобы расстояния от стен до границ участка выражалась целым числом квадратов. Долго выбирал он место для дома, но так и не выбрал – слишком много вариантов. А сколько? Начал наш герой считать, но не сумел – плохо математику учил. Помогите ему.

Формат ввода/вывода:

Напишите программу HOUSE, которая считывает числа m, n, a, b, k, где m, n – размеры участка, a, b – размеры дома, k – количество радиоактивных квадратов, а затем k неповторяющихся пар чисел i, j, которые определяют координаты радиоактивных квадратов. Программа должна вывести искомое количество способов.

Ограничения: 1 ≤ a ≤ m ≤ 5000, 1 ≤ b ≤ n ≤ 5000, 0 ≤ k ≤ mn, 1 ≤ i ≤ m, 1 ≤ j ≤ n

Пример:

Задача Велосипед (BICYCLE)

Велосипедист собирается проехать из пункта A в пункт B, расстояние между которыми составляет l м. У него есть велосипед, который может развивать скорость v м/c. Однако перед тем как выехать, велосипедист может выполнить некоторые модернизации своего велосипеда. Для каждой модернизации известно на сколько она увеличивает скорость велосипеда, а также время, за которое она может быть сделана. Можно выполнить несколько различных модернизаций, однако каждая модернизация может быть выполнена не более одного раза. Помогите велосипедисту добраться до пункта B как можно быстрее.

Формат ввода/вывода:

Напишите программу BICYCLE, которая считывает три целых числа: расстояние между пунктами l, исходная скорость велосипеда v и количество различных модернизаций N. Далее идут N пар целых чисел, каждая из которых определяет соответствующую модернизацию: прирост скорости после модернизации v_i  и время t_i, затрачиваемое на эту модернизацию. Все величины заданы в системе СИ (метры и секунды). Необходимо вывести с точностью не менее 10⁻⁶ минимальное время, которое потребуется велосипедисту для того, чтобы доехать из пункта A в пункта B с учетом времени на модернизации.

Ограничения: 0 ≤ l ≤ 10⁹, 1 ≤ v ≤ 10⁶, 0 ≤ N ≤ 100, 0 ≤ v_i ≤ 1000, 0 ≤ t_i ≤ 1000.

Пример:

Адрес сайта олимпиады //www.olymp.vinnica.ua/index_ua.php?lng=ru&cid=943