SPOJ HANGOVER

From Algorithmist
Jump to navigation Jump to search

902 (HANGOVER) - Hangover[edit]

Summary[edit]

How many cards in a stack can overhang from a table?

Given a distance between 0.01 to 5.20 inclusive, return the number of cards required for the overhang length. In general, n cards can overhang to 1/2 + 1/3 + 1/4 + ... + 1/(n+1) card lengths.

Explanation[edit]

Gotchas[edit]

Notes[edit]

Implementations[edit]

This is a straight forward problem. Given the limited nature of answers, it's possible to build the entire set of answers in a 520-element array.


Here is a C++ implementation that precalculates all the overhangs, then uses a recursive binary search to find how many cards are required to produce the given overhang.

http://ideone.com/eoYXr4

by reggaeguitar

Optimizations[edit]

Input[edit]

1.00
3.71
0.04
5.19
0.00

Output[edit]

3 card(s)
61 card(s)
1 card(s)
273 card(s)

References[edit]