АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1083. Изображения

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Задана прямоугольная область размером H пикселей в высоту и W в ширину. Её необходимо полностью заполнить в 1 ряд с помощью К изображений. Каждое изображение имеет свой размер Hi x Wi (высота и ширина) в пикселях. Размер любой картинки можно изменить так, чтобы пропорции сохранялись.

Пусть Hi и Wi - высота и ширина исходного изображения, H'i и W'i - размеры растянутого или сжатого изображения. Будем считать, что пропорции сохранены, если H'i/W'i отличается не более чем на 10% от Hi/Wi.

Изображения нельзя поворачивать. Все изображения должны быть задействованы, а прямоугольную область необходимо заполнить полностью, не выползая за её пределы. Ваша задача определить для каждой фотографии её новую ширину W'i, так чтобы пропорции были сохранены, а область была заполнена полностью. Если ответов несколько, выведите любой.

Исходные данные

В первой строке входного файла содержатся 3 целых числа: H (1<=H<=104), W (1<=W<=109) и K (1<=K<=105) - высота, ширина области и количество изображений.

В следующих К строках содержится по 2 целых числа, разделённых пробелом: Hi (1<=Hi<=104) и Wi (1<=Wi<=104) - высота и ширина i-й фотографии.

Результат

Выведите в выходной файл К целых чисел - ширину каждой фотографии в порядке, данном во вводе. Если ответов несколько, выведите любой. Если решения не существует, выведите одно число 0.

Пример

Исходные данныеРезультат
9 21 2
10 10
9 10
10 11
9 10 1
9 12
0

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XV Межвузовская олимпиада 2012 /
1082. C - Слон 1083. 1084. E - Восстановление текста 1085. F - Проверка дорог 1086. G - Наряды
 
время генерации 0.063 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.