NOI '00 P1 - Ceramic Necklace

View as PDF

Submit solution

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.

Each heat-crafted ceramic disk has a fixed thickness, while the diameter D and the volume 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}

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

Ex: Let V_{total} = 10, V_0 = 1. If only one disk is produced, then V = V_{total} = 10, and D = 0.9. If the clay is equally split up into two portions, then the volume of each portion V = V_{total} / 2 = 5, the diameter of each disk D' = 0.3\sqrt{5-1} = 0.6, and the total length of the necklace will be 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}, the total volume of clay (0 < V_{total} < 60\,000). The second line contains V_0, the volume of clay lost for producing each disk (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


Sample Output 1


Sample Input 2


Sample Output 2


Problem translated to English by Alex.


There are no comments at the moment.