OneForYou
Rookie SRM 1 · 2020-11-13 · by erinn
Rookie SRM 1 · 2020-11-13 · by erinn · Math
Problem Statement
Problem Statement
When trying to divide coins "equally" between two people, an old gag goes something like this...
- The person dividing up the loot says "One for you, and one for me" giving one coin to the other person and then themselves.
- Next they say "And that's two for you", while giving the other person a second coin.
- Then, they say "And that's one, two, for me", giving themselves two coins, additional to the first one they already had.
- Then, they say "That's three for you, and one, two, three, for me", given the other person a third coin before giving themselves three more coins.
- ... and so on
The are N coins to be divided. Assuming they are divided in this sneaky fashion, how many coins will the first person end up getting?
Constraints
- N will be between 0 and 10^15, inclusive.
Examples
0)
2 Returns: 1
In this case, it's actually fair, each person gets one coin.
1)
9 Returns: 6
This is three full rounds of dividing coins.
2)
11 Returns: 7
Here we run out of coins before the person dividing the coins takes four of them, so he takes as many as he can.
3)
33 Returns: 26
4)
1000000000 Returns: 999955280
Submissions are judged against all 15 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OneForYou with a public method long long coinCount(long long N) · 15 test cases · 2 s / 256 MB per case