NailingABanner
SRM 820 · 2021-12-27 · by misof
Problem Statement
You were asked to attach a very long banner to an equally long wooden fence. You are going to do that by using some nails.
The banner is exactly 2^60 (two to the power of 60) units long.
You will start by using the first nail to attach the top left corner of the banner to the fence and then the second nail to attach the top right corner. The location of the first nail is coordinate 0, the location of the second nail is coordinate 2^60.
From this point on, you will be adding more nails to the banner. The nails are going to be added in rounds. In each round, you first identify all pairs of nails that are currently adjacent (i.e., have no other nail between them), and then for each such pair you will place another nail exactly half-way between the two adjacent nails. Within each round, these new nails are placed from the left to the right, i.e., their coordinates increase.
For example:
- Round 1: Exactly one nail (nail #3) is placed into the middle of the banner.
- Round 2: We place two nails. Nail #4 is placed between nails #1 and #3, and then nail #5 is placed between nails #3 and #2. (Nail #4 is in one fourth of the banner, nail #5 is in its three fourths.)
- Round 3: The five nails we already placed form four pairs of adjacent nails. Thus, in this round we will add four new nails - one into the middle of each of the four segments of the banner.
You are given the number N of a nail. Return the coordinate at which this nail will be placed.
Notes
- Watch out for integer overflow: both the input and the output can overflow a 32-bit integer variable.
Constraints
- N will be between 1 and 10^12, inclusive.
1 Returns: 0
Nail #1 is placed at coordinate 0.
3 Returns: 576460752303423488
Nail #3 is placed exactly into the middle of the banner, at coordinate 2^59.
4 Returns: 288230376151711744
Nail #4 is placed halfway between nail #1 and nail #3, i.e., at coordinate 2^58.
24 Returns: 468374361246531584
2 Returns: 1152921504606846976
65537 Returns: 1152903912420802560
This nail is placed quite close to the end of the banner. It is the last nail placed in one of the rounds. The next nail (#65538) is the first nail placed in the next round.
Submissions are judged against all 60 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NailingABanner with a public method long long coordinate(long long N) · 60 test cases · 2 s / 256 MB per case