Автор Тема: Олимпиадная задача "Дипломы"  (Прочитано 4495 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн DrXakep

  • Пользователь
  • **
  • Сообщений: 27
    • Просмотр профиля
Олимпиадная задача "Дипломы"
« : 30 Декабря 2012, 14:09:40 »
Задача из регионального этапа Всероссийской олимпиады школьников по информатике 2009-2010 учебного года (первый тур).
Вторая задача "Дипломы":
Цитировать
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w – в ширину и h – в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней – дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Собственно, вопрос: как нужно расположить дипломы, чтобы площадь квадрата была наименьшей?
Я делал так: сначала все дипломы ставил в одну колонку, потом эту колонку делил пополам и перемещал половину в следующую колонку справа, и так до тех пор, пока их общая ширина не будет превосходить общей длины. Этот вариант работает до 7 из 20 тестов, дальше везде неправильное число пишет (порой даже отрицательное). Так вот, как правильно размещать дипломы?

 

Задача паскаль. Составить программу для построения таблицы значений

Автор Rydon

Ответов: 1
Просмотров: 6031
Последний ответ 21 Декабря 2009, 15:49:38
от Rydon
Срочно надо написать курсовую по информатике. Задача на языке VBA.

Автор lana

Ответов: 1
Просмотров: 3457
Последний ответ 12 Сентября 2010, 19:29:18
от InfStudent
Паскаль(задача). Составить программу определения показания часов

Автор Fairmont

Ответов: 0
Просмотров: 4104
Последний ответ 24 Февраля 2011, 21:25:22
от Fairmont
Задача в Turbo С. Написать программу построения одномерного массива

Автор deamond

Ответов: 1
Просмотров: 2489
Последний ответ 21 Декабря 2011, 12:04:34
от Hellko
Задача на строки в Паскале. Упорядочить и найти средний вес

Автор Ana

Ответов: 13
Просмотров: 5494
Последний ответ 23 Февраля 2010, 22:33:15
от Asix