Olimpiadnye_zadachi_po_informatike_2012-2013_1

Олимпиадные задачи по информатике (9-11 классы)
Условие задачи. Найдите наибольшее значение отношения трехзначного числа к сумме его цифр.

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

Условие задачи. Газон. Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.
В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.
Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.
Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Имя входного файла:
lawn.in

Имя выходного файла:
lawn.out

Максимальное время работы на одном тесте:
2 секунды

Максимальный объем используемой памяти:
64 мегабайта


Требуется написать программу, которая позволит дать ответ на вопрос Ивана.
Формат входных данных
В первой строке входного файла содержатся четыре целых числа 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)
Формат выходных данных
В выходной файл необходимо вывести одно целое число число пучков травы, которые были и пострижены, и политы.
Пример входных и выходных данных
lawn.in
lawn.out

0 0 5 4
4 0 3
14

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

Краткие методические рекомендации по решению задачи
Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно за время O(1) посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Это делается с помощью операции вычисления целой части числа. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу.
Не сложно показать, что время работы рассматриваемого решения будет O(r).
Возможные ошибки
Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal.

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

Имя выходного файла:
output.txt

Максимальное время работы на одном тесте:
1 секунда

Максимальный объем используемой памяти:
64 мегабайта


Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.
 
Формат входных данных
Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).
Формат выходных данных
В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.
Пример входных и выходных данных
input.txt
output.txt

5 3

4


Краткие методические рекомендации по решению задачи
Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно  n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.
Если у нас есть  0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки - это надо учитывать при решении задачи.

Условие задачи. Выпуклый многоугольник задан последовательностью координат своих вершин в порядке обхода: (x1, y1), (x2, y2), (x3, y3),  . . .  , (xn, yn). Вычислить площадь многоугольника.

Условие задачи. Маршрут движения автомобиля задан в виде координат вершин ломаной.
Необходимо определить количество левых поворотов (смежные участки ломаной не лежат на одной прямой). Автомобиль начинает движение с любой точки (!!!Здесь уточнение от меня - автомобиль начинает движение из первой вершины ломаной, а вот ее координаты любые!!!).

Формат входных данных:
Первая строка входного файла input.txt состоит из одного числа, количества звеньев ломаной; в последующих строках - пары натуральных чисел, координаты вершин ломаной.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество левых поворотов.

Условие задачи. Муравьи. N муравьев в момент времени 0 начинают одновременно двигаться по горизонтальному отрезку прямой со скоростью 1 см в секунду в заданных направлениях. Если два муравья сталкиваются, то они мгновенно разворачиваются и двигаются с прежней скоростью в противоположном направлении. Муравей, дошедший до края отрезка, падает. Определите, через сколько секунд упадет последний муравей.

Имя входного файла: ants.in
Имя выходного файла: ants.out
Ограничение по времени: 2 сек
Ограничение по памяти: 64Мбайт
Формат входных данных
На первой строке входного файла дано 2 целых числа:
N – количество муравьев (1<=N<=105).
L – длина отрезка в сантиметрах (2<=L<=106).
На второй строке расположены N чисел. I-е число – расстояние в сантиметрах от левого края отрезка до i-го муравья (расстояние – целое число в промежутке от 1 до L-1). Третья строка также содержит N чисел. I-е число равно 0, если i-й муравей начинает двигаться влево и равно 1, если вправо. Числа в строках разделены пробелами.
Формат выходных данных
На единственной строке выходного файла выведите одно целое число – ответ к задаче. Все задания используют входные и выходные файлы, поэтому нужно очень внимательно про-смотреть имена этих файлов.
Стандартный ввод/вывод предусматривает два стандартных идентификатора INPUT и OUTPUT (устройство ввода-вывода информации). Обычно эти стандартные идентификаторы связаны с конкретными физическими устройствами компьютера. Так, файловая переменная INPUT связана с клавиатурой, файловая переменная OUTPUT – с экраном дисплея. Эти идентификаторы считаются заранее открытыми, а соответствующие идентификаторы можно использовать в операциях ввода-вывода.
Используя процедуру ASSIGN, переназначим идентификаторы ввода-вывода INPUT и OUTPUT и укажем имя входного и выходного файла:
ASSIGN (INPUT, Ants.IN’); RESET (INPUT);
ASSIGN (OUTPUT, Ants.OUT’); REWRITE(OUTPUT);
После работы с файлами выполняем процедуры CLOSE(INPUT); CLOSE (OUTPUT);








2012-2013 уч. год



15

Приложенные файлы

  • doc 18027710
    Размер файла: 62 kB Загрузок: 0

Добавить комментарий