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

문제

동혁이는 창고에서 매우 재미있어 보이는 보드 게임을 발견했다. 이 게임의 보드는 R×C개의 정사각형 칸으로 이루어져 있다. 제일 위부터 0번부터 R-1까지 번호가 매겨져 있고, 제일 왼쪽부터 0번부터 C-1까지 번호가 매겨져 있다.

이 보드게임의 칸은 색다른 방법으로 색칠되어 있고, 각 칸은 회색 또는 흰색으로 색칠되어 있다.

행의 번호와 열의 번호를 이진수로 나타냈을 때, 적어도 한 위치에서 1이 겹치면 흰색이다. 예를 들어, (4, 5)는 흰색이다. 이러한 경우가 아니면 회색이다. 예를 들어, (2, 5)는 회색이다.

10×10크기의 보드판은 다음과 같이 생겼다.

동혁이는 자신의 말을 위쪽 오른쪽 그림과 같은 순서로 방문하려고 한다. 말은 (0, 0)에서 시작한다. 이때, 말이 회색 칸을 몇 번 방문하는지 구하려고 한다.

동혁이의 말이 칸을 K번 방문하게 되면, 피곤하기 때문에 더이상 방문하지 않는다.

N, M, K가 주어졌을 때, 회색칸을 몇 번 방문하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (1 ≤ R,C ≤ 1,000,000)

둘째 줄에는 K가 주어진다. (1 ≤ K ≤ R×C)

출력

첫째 줄에 동혁이의 말이 방문한 회색 칸의 수를 출력한다.

예제 입력 1

10 10
6

예제 출력 1

5

예제 입력 2

3 5
11

예제 출력 2

8

예제 입력 3

10 10
100

예제 출력 3

51
W3sicHJvYmxlbV9pZCI6IjI5NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWI0ZGMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzY1NSBcdWFlNDBcdWIzZDlcdWQ2MDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWNjM2RcdWFjZTBcdWM1ZDBcdWMxMWMgXHViOWU0XHVjNmIwIFx1YzdhY1x1YmJmOFx1Yzc4OFx1YzViNCBcdWJjZjRcdWM3NzRcdWIyOTQgXHViY2Y0XHViNGRjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViY2Y0XHViNGRjXHViMjk0IFImdGltZXM7Q1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWM3MDRcdWJkODBcdWQxMzAgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBSLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzgxY1x1Yzc3YyBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBDLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJjZjRcdWI0ZGNcdWFjOGNcdWM3ODRcdWM3NTggXHVjZTc4XHVjNzQwIFx1YzBjOVx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWQ2OGNcdWMwYzkgXHViNjEwXHViMjk0IFx1ZDc3MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWMwYzlcdWNlNjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1ODlcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIDFcdWM3NzQgXHVhY2I5XHVjZTU4XHViYTc0IFx1ZDc3MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKDQsIDUpXHViMjk0IFx1ZDc3MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWJhNzQgXHVkNjhjXHVjMGM5XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMiwgNSlcdWIyOTQgXHVkNjhjXHVjMGM5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xMCZ0aW1lczsxMFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWQzMTBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWIxOGQ1MTktNDE0Yi00YTE2LWFjZWItZmQ5OTU5YmM3MGRkXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MjBweDsgaGVpZ2h0OiAyODFweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWI5ZDBcdWM3NDQgXHVjNzA0XHVjYWJkIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI5ZDBcdWM3NDAgKDAsIDApXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI5ZDBcdWM3NzQgXHVkNjhjXHVjMGM5IFx1Y2U3OFx1Yzc0NCBcdWJhODcgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHViOWQwXHVjNzc0IFx1Y2U3OFx1Yzc0NCBLXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1ZDUzY1x1YWNlNFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMzU0XHVjNzc0XHVjMGMxIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNjhjXHVjMGM5XHVjZTc4XHVjNzQ0IFx1YmE4NyBcdWJjODggXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsQyAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBLICZsZTsgUiZ0aW1lcztDKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVjNzU4IFx1YjlkMFx1Yzc3NCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVkNjhjXHVjMGM5IFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKRVoiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgZm91bmQgYSB2ZXJ5IHVudXN1YWwgZ2FtZSBib2FyZCBpbiBoaXMgYXR0aWMuIFN1cnByaXNpbmdseSwgaXQgY29uc2lzdHMgb2YgUiZtaWRkb3Q7QyBzcXVhcmUgY2VsbHMuIFRoZSByb3dzIGFyZSBudW1iZXJlZCAwIHRvIFImbWludXM7MSB0b3AgdG8gYm90dG9tIGFuZCB0aGUgY29sdW1ucyAwIHRvIEMmbWludXM7MSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGF0IG1ha2VzIHRoZSBib2FyZCB1bnVzdWFsIGlzIHRoZSB3YXkgaW4gd2hpY2ggdGhlIGNlbGxzIGFyZSBjb2xvdXJlZC4gRWFjaCBjZWxsIGlzIGVpdGhlciBncmV5IG9yIHdoaXRlOiZuYnNwOzxcL3A+XHJcblxyXG48cD53aGl0ZSwgaWYgdGhlIHJvdyBhbmQgY29sdW1uIG51bWJlcnMgb2YgdGhlIGNlbGwsIHdoZW4gcmVwcmVzZW50ZWQgaW4gYmluYXJ5LCBoYXZlIGF0IGxlYXN0IG9uZSBkaWdpdCAxIGluIHRoZSBzYW1lIHBvc2l0aW9uLiBGb3IgZXhhbXBsZSwgdGhlIGNlbGwgKDQsIDUpIHdvdWxkIGJlIHdoaXRlLiZuYnNwOzxiciBcLz5cclxuZ3JleSwgb3RoZXJ3aXNlLiBGb3IgZXhhbXBsZSwgdGhlIGNlbGwgKDIsIDUpIHdvdWxkIGJlIGdyZXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgaW1hZ2Ugc2hvd3MgYSBib2FyZCBvZiBzaXplIDEwJm1pZGRvdDsxMC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81YjE4ZDUxOS00MTRiLTRhMTYtYWNlYi1mZDk5NTliYzcwZGRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDYyMHB4OyBoZWlnaHQ6IDI4MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5MdWthJiMzOTtzIGhlZGdlaG9nIGxpa2VzIHdhbGtpbmcgb24gdGhpcyB1bnVzdWFsIGJvYXJkIGFuZCBkb2VzIGl0IGluIGFuIHVudXN1YWwgd2F5LiBUaGUgaGVkZ2Vob2cgc3RhcnRzIGhpcyB3YWxrIGluIHRoZSBjZWxsICgwLCAwKSBhbmQgY29udGludWVzIGluIHRoZSB6aWctemFnIHBhdHRlcm4gYXMgaW4gdGhlIHNlY29uZCBpbWFnZSBhYm92ZS4gV2hpbGUgdGhlIGhlZGdlaG9nIGlzIHdhbGtpbmcsIEx1a2EgY291bnRzIGhvdyBtYW55IGdyZXkgc3F1YXJlcyBpdCB2aXNpdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZnRlciB2aXNpdGluZyBLIHNxdWFyZXMsIHRoZSBoZWRnZWhvZyBnZXRzIHRpcmVkIGFuZCBmYWxscyBhc2xlZXAuIEx1a2EgdGhlbiBnb2VzIHRvIGJlZCB0b28sIGhhcHB5IHRoYXQgaGUgd2FzIGFibGUgY291bnQgdGhlIGdyZXkgc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+S25vd2luZyB0aGUgZGltZW5zaW9ucyBvZiB0aGUgYm9hcmQgYW5kIHRoZSBudW1iZXIgSyBiZWZvcmVoYW5kLCBob3dldmVyLCBpdCBpcyBwb3NzaWJsZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSByZXN1bHQgZmFzdGVyLiBUaGlzIGlzIHlvdXIgdGFzay4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSICgxICZsZTsgUiAmbGU7IDEgMDAwIDAwMCkgYW5kIEMgKDEgJmxlOyBDICZsZTsgMSAwMDAgMDAwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGJvYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgSyAoMSAmbGU7IEsgJmxlOyBSJm1pZGRvdDtDKSwgdGhlIHRvdGFsIG51bWJlciBvZiBzcXVhcmVzIHRoZSBoZWRnZWhvZyB2aXNpdHMuIE5vdGUgdGhhdCB0aGlzIG51bWJlciBtYXkgbm90IGZpdCBpbiBhIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIGdyZXkgY2VsbHMgdGhlIGhlZGdlaG9nIHZpc2l0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #1 4번