NOI '00 P1 - Ceramic Necklace - Olympiads Online Judge

NOI '00 P1 - Ceramic Necklace

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 0.6s

Memory limit: 16M

Problem type

National Olympiad in Informatics, China, 2000

Ancient tribes heated up a rare type of clay to produce ceramic disks with identical diameters. These disks are strung together to make necklaces by being joined along their diameters with no spaces or overlaps between them. Each necklace is made up of at least one disk.

The figure below depicts four rings of the same size, linked together to form a necklace with a length four times that of a single disk's diameter.

$\text{[math]}$

Each heat-crafted ceramic disk has a fixed thickness, while the diameter $D$ $D$ and the volume $V$ $V$ are related by the following formula:

$\displaystyle D = \begin{cases}0.3 \sqrt{V-V_0} & (V > V_0) \\ 0 & (V \le V_0)\end{cases}$ $D = {\begin{cases} 0.3 \sqrt{V - V_{0}} & (V > V_{0}) \\ 0 & (V \leq V_{0}) \end{cases}$

where $V_0$ $V_{0}$ is the volume of clay lost when heating each disk, in the same units as $V$ $V$ . If the amount of material is less than or equal to $V_0$ $V_{0}$ , then the disk cannot be produced.

Ex: Let $V_{total} = 10$ $V_{t o t a l} = 10$ , $V_0 = 1$ $V_{0} = 1$ . If only one disk is produced, then $V = V_{total} = 10$ $V = V_{t o t a l} = 10$ , and $D = 0.9$ $D = 0.9$ . If the clay is equally split up into two portions, then the volume of each portion $V = V_{total} / 2 = 5$ $V = V_{t o t a l} / 2 = 5$ , the diameter of each disk $D' = 0.3\sqrt{5-1} = 0.6$ $D^{'} = 0.3 \sqrt{5 - 1} = 0.6$ , and the total length of the necklace will be $1.2$ $1.2$ .

Given the total volume of clay and the amount lost for a single disk, and given that the number of disks produced is different, as well that the lengths of the final necklaces are also different, please calculate the number of disks produced that would maximize the length of the necklace.

Input Specification

The input consists of two lines, each containing a single integer. The first line contains $V_{total}$ $V_{t o t a l}$ , the total volume of clay $(0 < V_{total} < 60\,000)$ $(0 < V_{t o t a l} < 60 000)$ . The second line contains $V_0$ $V_{0}$ , the volume of clay lost for producing each disk $(0 < V_0 < 600)$ $(0 < V_{0} < 600)$ .

Output Specification

The output should consist of one integer - the number of disks in the necklace with the maximally obtainable length. If it is not possible to produce disks or the answer is not unique (i.e. there exists two or more ways to obtain the longest possible necklace), output the number 0.

Sample Input 1

Copy

10
1

Sample Output 1

Copy

Sample Input 2

Copy

10
2