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

Олимпиадные задачи по информатике (9-11 классы)

1. Условие задачи. Найдите наибольшее значение отношения трехзначного числа к сумме его цифр.

2. Условие задачи. Дана строка, состоящая из символов, каждый из которых является знаком «+» или цифрой, начинающаяся и заканчивающаяся цифрой. Если в строке встречается сочетание «++», то выдать сообщение об ошибке, в противном случае вычислить получившуюся сумму.

3. Условие задачи. Газон. Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.

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

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Формат входных данных

В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).

Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

Формат выходных данных

В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

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

Иллюстрация к примеру

Краткие методические рекомендации по решению задачи

Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно за время O(1) посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Это делается с помощью операции вычисления целой части числа. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу.

Не сложно показать, что время работы рассматриваемого решения будет O(r).

Возможные ошибки

Можно применить "лобовое" решение, т.е. создать два или три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal.

4. Условие задачи. Вырубка деревьев. Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Формат входных данных

Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).

Формат выходных данных

В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.

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