시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB110450841949.703%

문제

상덕이와 희원이는 동전 게임을 하면서 시간을 보낸다. 동전 게임은 동전 N개를 가지고 하는 게임이고, 규칙은 다음과 같다.

  1. 상덕이가 먼저 게임을 하고, 그 다음엔 희원이, 그 다음에 상덕이, 희원이 순서대로 게임을 한다. 순서대로 첫 번째 턴, 두 번째 턴, 세 번째 턴, ...
  2. 상덕이는 첫 번째 턴에서 가져갈 수 있는 동전의 개수는 1보다 크거나 같고, N보다 작거나 같다.
  3. 그 다음 턴부터는 동전을 이전 턴에서 그 사람이 가져간 동전 개수의 최대 2배만큼 가져갈 수 있다. (동전을 적어도 1개는 가져가야 한다)
  4. 이렇게 플레이를 하다가 마지막 동전을 가져가는 사람이 이긴다.

상덕이와 희원이가 항상 최적의 방법으로 게임을 한다. 이 말은 어떤 상황에서 플레이어 A가 B를 항상 이길 수 있다면, A가 항상 이긴다는 것이다.)

이때, 상덕이가 이기기 위해서는 첫 번째 턴에서 동전을 몇 개 가져가야 하는지를 구하는 프로그램을 작성하면 된다. 이러한 동전의 개수가 여러 개 나올 수 있는데, 그 때는 가장 적은 개수를 출력하면 된다.

입력

첫째 줄에 동전의 개수 N이 주어진다. (2 ≤ N ≤ 1015)

출력

첫째 줄에 상덕이가 이기기 위해서 가져가야 하는 동전 개수의 최솟값을 출력한다.

예제 입력 1

4

예제 출력 1

1

예제 입력 2

7

예제 출력 2

2

예제 입력 3

8

예제 출력 3

8

힌트

동전의 개수가 4개일 때, 상덕이가 첫 번째 턴에서 가져갈 수 있는 동전의 경우의 수는 1, 2, 3, 4개이다. 만약 4개를 가져가게 된다면 상덕이는 항상 이기게 된다. 하지만, 이것은 최솟값이 아니다. 상덕이가 첫 번째 턴에서 동전을 1개 가져갔다고 생각해보자. 그럼 이제 동전은 3개가 남고, 희원이는 동전을 많아야 2개만 가져갈 수 있기 때문에 절대 이길 수 없게 된다. (문제의 3번 조건 때문에 희원이는 동전을 1*2개까지 가져갈 수 있다) 희원이가 동전을 1개를 가져가던, 2개를 가져가던 상덕이는 다음 턴에서 남은 동전을 모두 가져갈 수 있기 때문에 상덕이가 첫 번째 턴에서 동전을 1개 가져가면 항상 이기게 된다. 따라서 정답은 1이다.

W3sicHJvYmxlbV9pZCI6IjI4NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWQ1NTkgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWIzNTVcdWM3NzRcdWM2NDAgXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YjNkOVx1YzgwNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViYTc0XHVjMTFjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YjNkOVx1YzgwNCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViM2Q5XHVjODA0IE5cdWFjMWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWFjZTAsIFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWJhM2NcdWM4MDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkNCBcdWQ3NmNcdWM2ZDBcdWM3NzQsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjMGMxXHViMzU1XHVjNzc0LCBcdWQ3NmNcdWM2ZDBcdWM3NzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDEzNCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWQxMzQsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVkMTM0LCAuLi48XC9saT5cclxuXHQ8bGk+XHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMTM0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVkMTM0XHViZDgwXHVkMTMwXHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc0NCZuYnNwO1x1Yzc3NFx1YzgwNCBcdWQxMzRcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2Q5XHVjODA0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMDAgMlx1YmMzMFx1YjljY1x1ZDA3YyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxY1x1YjI5NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0KTxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTBjXHViODA4XHVjNzc0XHViOTdjIFx1ZDU1OFx1YjJlNFx1YWMwMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzc0XHVhZTM0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YzY0MCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVkNTZkXHVjMGMxIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjlkMFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNCBBXHVhYzAwIEJcdWI5N2MgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0LCBBXHVhYzAwIFx1ZDU2ZFx1YzBjMSBcdWM3NzRcdWFlMzRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTMwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDEzNFx1YzVkMFx1YzExYyBcdWIzZDlcdWM4MDRcdWM3NDQgXHViYTg3IFx1YWMxYyBcdWFjMDBcdWM4MzhcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YjNkOVx1YzgwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhZGY4IFx1YjU0Y1x1YjI5NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzZDlcdWM4MDRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDxzdXA+MTU8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjODM4XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIzZDlcdWM4MDQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjNkOVx1YzgwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgNFx1YWMxY1x1Yzc3YyBcdWI1NGMsIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDEzNFx1YzVkMFx1YzExYyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM4MDRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCAxLCAyLCAzLCA0XHVhYzFjXHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QgNFx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjOGMgXHViNDFjXHViMmU0XHViYTc0IFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzc0XHVhZTMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzRcdWFjODNcdWM3NDAgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMTM0XHVjNWQwXHVjMTFjIFx1YjNkOVx1YzgwNFx1Yzc0NCAxXHVhYzFjIFx1YWMwMFx1YzgzOFx1YWMxNFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuIFx1YWRmOFx1YjdmYyBcdWM3NzRcdWM4MWMgXHViM2Q5XHVjODA0XHVjNzQwIDNcdWFjMWNcdWFjMDAgXHViMGE4XHVhY2UwLCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWIyOTQgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YjljZVx1YzU0NFx1YzU3YyAyXHVhYzFjXHViOWNjIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4MDhcdWIzMDAgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM1YzZcdWFjOGMgXHViNDFjXHViMmU0LiAoXHViYjM4XHVjODFjXHVjNzU4IDNcdWJjODggXHVjODcwXHVhYzc0IFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWIyOTQgXHViM2Q5XHVjODA0XHVjNzQ0IDEqMlx1YWMxY1x1YWU0Y1x1YzljMCBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNCkgXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1YjNkOVx1YzgwNFx1Yzc0NCAxXHVhYzFjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjM1OCwgMlx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWIzNTggXHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0YyBcdWQxMzRcdWM1ZDBcdWMxMWMgXHViMGE4XHVjNzQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDEzNFx1YzVkMFx1YzExYyBcdWIzZDlcdWM4MDRcdWM3NDQgMVx1YWMxYyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YWUzMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM4MTVcdWIyZjVcdWM3NDAgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4NjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIUlBBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvJnJzcXVvO3MgZmF2b3VyaXRlIHBhc3RpbWUgaXMgY29tcGV0aW5nIGFnYWluc3QgZWFjaCBvdGhlciBpbiBtYXRoZW1hdGljYWwgZ2FtZXMuIFRoaXMgdGltZSB0aGV5IHRvb2sgYSBoZWFwIG9mIE4gcGViYmxlcyBhbmQgc2V0dGxlZCBvbiB0aGUgZm9sbG93aW5nIHJ1bGVzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk1pcmtvIGlzIHRoZSBmaXJzdCB0byBwbGF5LCB0aGVuIFNsYXZrbywgdGhlbiBNaXJrbyBhZ2FpbiwgdGhlbiBTbGF2a28gYW5kIHNvIG9uOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5NaXJrbyBjYW4gdGFrZSBhbnkgbnVtYmVyIG9mIHBlYmJsZXMgKGJldHdlZW4gMSBhbmQgTiwgaW5jbHVzaXZlKSBmcm9tIHRoZSBoZWFwIGR1cmluZyBoaXMgZmlyc3QgbW92ZTsmbmJzcDs8XC9saT5cclxuXHQ8bGk+SW4gZWFjaCBvZiB0aGUgZm9sbG93aW5nIHR1cm5zIHRoZSBjdXJyZW50IHBsYXllciBtdXN0IHRha2UgYXQgbGVhc3QgMSBwZWJibGUgYW5kIGlzIGFsbG93ZWQgdG8gdGFrZSBhdCBtb3N0IGRvdWJsZSB0aGUgYW1vdW50IG9mIHBlYmJsZXMgdGFrZW4gZHVyaW5nIHRoZSBwcmV2aW91cyB0dXJuIGJ5IHRoZSBvdGhlciBwbGF5ZXI7IG5hdHVyYWxseSwgb25lIGNhbm5vdCB0YWtlIG1vcmUgcGViYmxlcyB0aGFuIHRoZSByZW1haW5pbmcgYW1vdW50IGluIHRoZSBoZWFwOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgcGxheWVyIHdobyB0YWtlcyB0aGUgbGFzdCBwZWJibGUgaXMgdGhlIHdpbm5lci48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Cb3RoIE1pcmtvIGFuZCBTbGF2a28gcGxheSBvcHRpbWFsbHkgKGlmIGl0IGlzIHBvc3NpYmxlIGZvciBvbmUgcGxheWVyIHRvIGJlYXQgdGhlIG90aGVyLCB0aGF0IHBsYXllciB3aWxsIGFsd2F5cyB3aW4pLiBXZSBuZWVkIHRvIGZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHBlYmJsZXMgdGhhdCBNaXJrbyBtdXN0IHRha2UgZHVyaW5nIGhpcyBmaXJzdCB0dXJuIHN1Y2ggdGhhdCBoZSBpcyBndWFyYW50ZWVkIHRvIHdpbiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTA8c3VwPjE1PFwvc3VwPiksIHRoZSBudW1iZXIgb2YgcGViYmxlcyBpbiB0aGUgc3RhcnRpbmcgaGVhcC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBtaW5pbXVtIG51bWJlciBvZiBwZWJibGVzIHRoYXQgTWlya28gbmVlZHMgdG8gcmVtb3ZlIGR1cmluZyBoaXMgZmlyc3QgdHVybi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #4 6번