Connection Status:
Competition Arena > MagicCandy

MagicCandy

SRM 526.5 · 2011-12-12 · by cgy4ever

SRM 526.5 · 2011-12-12 · by cgy4ever · Math, Search
Class Name: MagicCandy
Return Type: int
Method Name: whichOne
Arg Types: (int)
Problem Statement

Problem Statement

Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.


The reindeer love candies. They have n pieces of candy. The pieces of candy are numbered 1 through n. Dasher is one of the reindeer. He wants to eat one of the candies. To pick the one he will eat, Dasher uses the following method:
  • While there is more than one piece of candy:
  • Discard all candies that are numbered by perfect squares (i.e., candies 1, 4, 9, 16, 25, etc.).
  • Relabel the remaining k candies 1 through k, keeping the numbers in the same order.
  • Once only one piece of candy remains, Dasher will eat it.



You are given an int n. Your method must compute and return the number initially assigned to the piece of candy eaten by Dasher.

Notes

  • It can be proved that Dasher's method will always lead to a situation in which only one piece of candy remains.

Constraints

  • n will be between 1 and 1,000,000,000 inclusive.
Examples
0)
5
Returns: 5

We start with 5 candies. Let's call them A, B, C, D, and E. Initially, they are numbered 1 through 5, in this order. In the first round, we discard candies with numbers 1 (which is A) and 4 (which is D). This leaves us with candies B, C, and E. These candies now get new numbers: B becomes 1, C becomes 2, and E becomes 3. In the second round, we discard candy number 1 (which is now B). This leaves us with candies C and E. Again, the candies now get new numbers: C becomes 1 and E becomes 2. In the third round, we discard candy number 1 (which is now C). The only remaining candy is E. Its number in the beginning was 5, therefore our method should return 5.

1)
9
Returns: 7

This time we start with 9 pieces of candy. If we label them A through I, the process will look as follows: start: ABCDEFGHI throw away candies 1, 4, 9 (A, D, I) after the first round: BCEFGH throw away candies 1, 4 (B, F) after the second round: CEGH throw away candies 1, 4 (C, H) after the third round: EG throw away candy 1 (E) at the end: G

2)
20
Returns: 17
3)
5265
Returns: 5257
4)
20111223
Returns: 20110741

Submissions are judged against all 155 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MagicCandy with a public method int whichOne(int n) · 155 test cases · 2 s / 256 MB per case

Submitting as anonymous