Задача Окружность



Скачать 43.89 Kb.
Дата15.10.2012
Размер43.89 Kb.
ТипЗадача
Задача 1. Окружность (15 баллов)

На листочке в клеточку нарисована окружность радиуса R клеток с центром на пересечении двух линий. Необходимо найти количество клеток, по которым проходит окружность. (Если окружность только касается границы клетки, клетку считать не надо).

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

Во входном файле INPUT.TXT содержится единственное число R (R 30000).

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

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

Пример INPUT.TXT: OUTPUT.TXT для примера:

5 28

Ограничение времени: 1 сек на тест

Задача 2. Гири (23 балла)

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

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

Во входном файле INPUT.TXT содержится единственное число N (N 1000000).

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

В первой строке выходного файла OUTPUT.TXT должно содержаться количество гирь. Во второй строке – веса гирь через пробел. Если набора не существует, вывести 0.

Пример INPUT.TXT: один из вариантов OUTPUT.TXT для примера:

17 5
1 2 3 5 6


Пример INPUT.TXT: OUTPUT.TXT для примера:

4 0

Ограничение времени: 1 сек на тест

Задача 3. Посты ГИБДД (27 баллов)

На автомобильной трассе Москва-Иркутск проходит реорганизация постов ГИБДД. Для оптимального решения задачи расстановки постов выявлено N (N  8000) маршрутов (участков) наиболее активного движения. Участки могут пересекаться, каждый участок задаётся парой чисел [ai, bi] – номером начального и конечного пункта (все пункты трассы пронумерованы от 1 до L, L  50000). Для каждого участка определена его степень важности – число ci. Требуется так выбрать пункты установки постов, чтобы на каждом участке наиболее активного движения количество установленных постов было бы не меньше его степени важности. (Пост, установленный на границе участка считается принадлежащим участку. В одном пункте нельзя установить сразу два поста.) Кроме того, необходимо, чтобы количество постов было минимально возможным.


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

Первая строка входного файла INPUT.TXT содержит целое число N (1 N 8000) – количество участков. Следующие N строк описывают участки. Строка i+1 входного файла содержит три целых числа ai, bi, ci (границы отрезка и его степень важности), разделенные одиночными пробелами и такие, что 1 ai bi 50000 и 1 ci bi-ai+1.

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

В первой строке выходного файла OUTPUT.TXT должно содержаться целое число K – количество устанавливаемых постов. Во второй строке – K чисел – номера пунктов, в которых устанавливаются посты. Все номера пунктов должны быть различны.

Пример INPUT.TXT: один из вариантов OUTPUT.TXT для примера:

5 6
3 7 3 3 5 6 8 9 10
8 10 3
6 8 1
1 3 1
10 11 1


Ограничение времени: 5 сек на тест

Задача 4. Трёхцветная плитка (35 баллов)

Пол прямоугольной комнаты покрывают плиткой. Размер комнаты – M на N плиток. Каждый раз мастер берет верхнюю плитку из стопки и укладывает ее. После этого переходит к укладке одной из соседних плиток (т.е. имеющих общую сторону с уже уложенной). Плитки, которые укладывает мастер – трёх разных цветов и известно, что в стопке, из которой их брал мастер, они лежали в порядке чередования цветов. То есть 1, 2, 3, 1, 2, 3, … и т.д., считая сверху стопки (цвета обозначаются цифрами 1, 2 и 3). В результате работы мастер выложил плиткой весь пол комнаты. Известно, что начал мастер с первой плитки в первом ряду (верхний левый угол на рисунке) и, конечно же, дважды на одно и то же место плитку не клал. Вам по полученному рисунку требуется определить маршрут мастера (то есть в каком порядке он выбирал места для укладки плитки).

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

В первой строке входного файла INPUT.TXT содержатся числа M и N (M, N 100), разделённые пробелом. Далее в M строках содержится по N чисел (1, 2 или 3), задающих цвет соответствующей плитки, разделённых пробелом.

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

Выходной файл OUTPUT.TXT должен содержать M·N строк. В каждой (i-ой) строке – по два числа: номер строки и номер позиции в строке места, на которое мастер укладывал плитку на i-ом шаге. Строки и позиции в строке нумеруются с 1. Если узор не мог быть построен при соблюдении условий задачи, вывести единственное число 0.

Пример INPUT.TXT: OUTPUT.TXT для примера:

3 3 1 1
1 2 3 1 2
3 2 1 1 3
1 2 3 2 3


2 2

2 1

3 1

3 2

3 3
Ограничение времени: 2 сек на тест

Похожие:

Задача Окружность iconПояснительная записка в 2005 году издательство
Охватывает окружность. Изопериметрическая задача, т е задача о нахождении кривой заданной длины, охватывающей наибольшую площадь,...
Задача Окружность iconЗадача по теме "Окружность". Билет №2
Свойство углов, образованных при пересечении двух параллельных прямых третьей прямой
Задача Окружность iconEllipse Tool, и, удерживая клавишу Ctrl, рисуем две окружности, диаметр одной из которых чуть больше второй. Меньшую окружность заливаем, используя инструмент Fointain Fill
Большую окружность заливаем тем же цветом, что и меньшую окружность внизу (в нашем случае цвет Turquoise). После этого применяем...
Задача Окружность iconТема №7 Кривые второго порядка и их свойства. Учебные вопросы
Окружность. Окружность есть геометрическое место точек плоскости, равноудаленных от данной, называемой центром
Задача Окружность icon«Окружность»
А) Окружность – это (абстрактная, геометрическая, плоская) фигура, (состоящая из множества, всех) точек, расположенных на (одинаковом,...
Задача Окружность iconТест «Окружность и ее элементы»
Окружность – это (абстрактная, геометрическая, плоская) фигура, состоящая из (множества, всех) точек, расположенных на (одинаковом,...
Задача Окружность iconСоздаем паука из стандартных форм
Выберите Инструмент Ellipse, удерживайте ctrl и растяните окружность. Удерживание ctrl оставит окружность пропорциональной
Задача Окружность iconОкружность и круг. Вписанные углы. Треугольник и окружность
Величина угла между хордами ав и вс равна 164°. Найти ве­личину центрального угла, опирающегося на хорду ав, если дуга ав = дуге...
Задача Окружность iconРейтинговая олимпиада для поступающих в 10 класс, 2005 г., I
В окружность радиуса вписан квадрат. На диагонали квадрата, как на основании, построен равносторонний треугольник, вокруг которого...
Задача Окружность iconРешение: а sбольшого круга= п r 2 Sмалого круга= Пr 2 Sбк-Sмк=Sкольца R=a 3 /√3 r=a 3 /2√3
В правильный треугольник вписана окружность и около него описана окружность. Найти площадь образовавшегося кольца, если сторона треугольника...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org