Hangover
InterviewTime limit1sMemory limit128 MB
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 card lengths.
In general, with cards you can achieve an overhang of
card lengths: the top card overhangs the second by , the second overhangs the third by , the third overhangs the fourth by , and so on, while the bottom card overhangs the table by . 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 whose value is at least and at most ; 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 card lengths. Print one line per test case in the exact form N card(s), where N is that minimum number of cards.