Hangover

Interview

Time limit1sMemory limit128 MB

Summary
For each target overhang c, find the smallest n such that the harmonic sum 1/2 + 1/3 + ... + 1/(n+1) reaches c, and report n.
Level

Easy3 of 10

Topics
Math, Implementation, Prefix sum, Brute force
Solved
No attempts yet

Problem

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length (we assume every card is perpendicular to the table). With two cards, the top card can overhang the bottom one by half a card length, and the bottom one can overhang the table by a third of a card length, for a total maximum overhang of 12+13=56\frac{1}{2} + \frac{1}{3} = \frac{5}{6} card lengths.

In general, with nn cards you can achieve an overhang of

12+13+14+⋯+1n+1\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{n+1}

card lengths: the top card overhangs the second by 12\frac{1}{2}, the second overhangs the third by 13\frac{1}{3}, the third overhangs the fourth by 14\frac{1}{4}, and so on, while the bottom card overhangs the table by 1n+1\frac{1}{n+1}. This is illustrated in the figure below.

Input

The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number cc whose value is at least 0.010.01 and at most 5.205.20; cc always has exactly three significant digits (the form X.YZ).

Output

For each test case, output the minimum number of cards needed to achieve an overhang of at least cc card lengths. Print one line per test case in the exact form N card(s), where N is that minimum number of cards.

Examples1

  1. Example 1

    Input
    1.00
    3.71
    0.04
    5.19
    0.00
    
    Expected output
    3 card(s)
    61 card(s)
    1 card(s)
    273 card(s)