[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - BdOI 2013 National Problem 6

BdOI 2013 National Problem 6

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators: bristy1588, Labib

Facebook Twitter

BdOI 2013 National Problem 6

Post Number:#1  Unread postby bristy1588 » Wed Jan 15, 2014 12:20 pm

In the country of Giftland, everything is considered as 2D. Little Gugua has $ N $ friends. She
wants to send gifts to all of her friends. All of her gift items can be considered as $2D$ filled
circles of various radii. Gugua went to PackNsend Courier Service to send all of her gifts.
PackNsend company offers $2D$ flexible boxes (you can consider those as flexible envelops) of
various sized square shapes. Each gift requires one box. The gifts must be put in those
square shaped envelops and then the square has to be adjusted to fit the gift in it tightly.
Figure2.JPG
See the Figure for Explanation
Figure2.JPG (16.69 KiB) Viewed 548 times

That is, turn a square to a rhombus so that the circle touches all the sides. Length of the sides of the adjusted rhombus should be (obviously!) equal to the initial
square. The company also charges 1unit/area of the enclosed adjusted envelop. Gugua collected $ N $ envelops of various sizes from the company. As Gugua is very little, all of her gifts were also very little. So she found that any of her gifts can be placed in any of those envelops, and then those envelops can be
adjusted to fit the gifts. Gugua has to pay for the total area of all the adjusted rhombuses.
Your job is to help Gugua to find the minimum area that is required to pack all her gifts using
the square envelops and then adjusting them to rhombuses.

INPUT
First line specifies the test case number $ T (T <= 100) $. Then $T $ test cases follow, each case
starts with an integer,$ N (1 <= N <= 100) $, denoting the number of gifts/envelops. Then two
lines follow. The first line contains $N $integers, $G_i (1 <= i <= N) $, each denoting the radius of $i^{th}$
gift. Next line contains N integers, $S_j$, each denoting the length of side of $j^{th}$ square shaped envelops. No value will be greater than 1000. You can safely assume that, $ S_i >= 2*G_j$ (for all $1 <= i,j <= N$).

OUTPUT
For each line, print the case number, starting from 1, and then print the minimum total area
of the adjusted envelops as described above.

SAMPLE INPUT
Code: Select all
2
4
1 1 1 1
2 2 2 2
4
1 2 3 4
8 9 10 11


SAMPLE OUTPUT
Code: Select all
Case 1: 16
Case 2: 180
Bristy Sikder
User avatar
bristy1588
 
Posts: 92
Joined: Sun Jun 19, 2011 10:31 am

Share with your friends: Facebook Twitter

Return to International Olympiad in Informatics (IOI)

Who is online

Users browsing this forum: No registered users and 1 guest