oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

stonegame Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

stonegame.html

Problem Description

Barr the Bear and Poe the Penguin like to play games with each other. Today, they took a bag of N pebbles and agreed that they would play by the following rules

  1. Poe the Penguin would move first since Barr the Bear was lazy.
  2. Poe the Penguin can take any number of stones (from 1 to N) from the bag of stones during this first move.
  3. In each of the following moves the current player must take at least 1 stone from the bag, and he can take up to double the number of stones taken during the previous turn. Obviously, he cannot take more stones than there are in the bag.
  4. The player who takes the last stone is the winner, and gets treated to a free lunch.

If both Poe the Penguin and Barr the Bear played optimally, Poe the Penguin would always get the free lunch. To mock Barr the Bear, Poe the Penguin would like to know the minimum number of stones he must take on his first turn to guarantee a win given optimal play by both sides.

Input

The input contains a single integer N, which denotes the number of stones initially in the bag.

Output

Output the minimum number of stones Poe the Penguin would need to remove on his first turn so that he could still win given optimal play by both sides.

Subtask 1 (20 points)

1 ≤ N ≤ 100.

Subtask 2 (30 points)

1 ≤ N ≤ 1,000

Subtask 3 (50 points)

1 ≤ N ≤ 109

Acknowledgements

Taken from Chuanqi's 2012 IOI Training Contest 1 with limits reduced.

Sample Input 1

4

Sample Output 1

1

Explanation for Sample Output 1

After removing one stone on his first turn, Poe the Penguin can remove the remaining stones no matter what Barr the Bear plays.

Sample Input 2

7

Sample Output 2

2

Explanation for Sample Output 1

Poe the Penguin removes 2 stones on his first turn. If Barr the Bear removes more than 1 stone on his turn, then Poe the Penguin can remove all remaining stones and win. If Barr the Bear removes a single stone, then Poe the Penguin removes a single stone on his turn again. No matter what Barr the Bear does now, Poe the Penguin is able to remove all remaining stones and win.

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
12041s32MBMinimum
23061s32MBMinimum
350121s32MBMinimum
4021s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o stonegame -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.