Server Time: Wed Feb 26, 2020 12:17 pm
Welcome ( logout
C - Chocolate Gifts
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Problem-C: Chocolate Gifts


This is Tushar last semester here at PUST, and he is determined to finish university as the most favorite Knight ever! With his “extensive” friendship knowledge, he has determined that chocolate brings smile to any face and that is the key to becoming the most favorite Knight. So, Tushar has decided to send a chocolate bar to each and every PUSTstudent. Specifically, Timothy will send a rectangular chocolate bar (made of smaller rectangular chocolate pieces assembled together) to as many PUST students as he can.

However, Tushar realizes that if two students see that they both received the same chocolate gifts, they would be repulsed and find this otherwise kind act suddenly creepy. To combat this, Tushar has decided that each gift he sends must be different. Thus, no pair of chocolate bars can have the same dimensions. But, because the smaller pieces have designs on them, a 5-by-3 chocolate bar is considered different than a 3-by-5 bar. Note, however, that a 5-by-5 (i.e., square) bar is the same as another 5-by-5 bar even though the smaller pieces have designs on them.

Tushar realized that he could of course send as many students unique chocolate bars as he wants because there are obviously an infinite number of sizes of chocolate bars he could make. However, because Tushar is no longer on the programming team, he is not that rich anymore! A chocolate bar with width a and height b will cost Tushar a*b and he has limited savings in his bank account. Thus, he can only afford a certain number of chocolate bars. More specifically, the total cost for the bars cannot exceed his savings. He thus needs your help to determine, given his limited budget, the maximum number of students he could send chocolate bars to such that no pair of students receive chocolate bars with the same dimensions.

In addition to all of this, Tushar must send the chocolate bars in nicely wrapped boxes, each bar in a separate box (i.e., not all bars in one box). But, all the boxes have the same size, i.e., there are not several boxes with varying sizes to choose from. Thus, every chocolate bar he makes must fit into one box. Furthermore, when putting a bar in a box, the bar cannot be rotated as this would cause the pattern on the chocolate to not match the pattern on the box. For example, let’s assume the box has width 3 and height 5, then a 3-by-5 bar would fit in the box but a 5-by-3 bar will not fit in the box (again, the bar cannot be rotated).

The Problem:

Given Tushar's savings balance, determine the maximum number of rectangular chocolate bars he could make, such that no two bars have the same dimensions. Note that Tushar does not need to use up all of his money, but he cannot (of course) exceed his savings balance. Note also that each bar must fit into the given box size, i.e., the box size also restricts the bars he can make.

The Input:

The input consists of a single line containing three positive integers, w, h, and x (1 ≤ w, h, x ≤ 1018) representing (respectively) the width and height of each box and Tushar's savings balance.

The Output:

Output a single line containing an integer representing the maximum number of students Tushar can send chocolate bars to given his constraints.

Sample Input             Sample Output

2  1  2


3 2 11


8 3 64


Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan