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

문제

학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.

상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.

상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 준다.

막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.

K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오. 상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

입력

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

출력

첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.

예제 입력 1

6

예제 출력 1

8 2
W3sicHJvYmxlbV9pZCI6IjI4ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMDhcdWNmNWNcdWI5YmYgXHVjMmRkXHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NTlcdWFkNTAgXHVhZGZjXHVjYzk4IFx1ZDNiOFx1Yzc1OFx1YzgxMFx1YzVkMCBcdWMwYzggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzc0IFx1YjRlNFx1YzViNFx1YzY1NFx1YjJlNC4gXHVjNzc0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0MCBcdWI5YzlcdWIzMDAgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHViOWM5XHViMzAwXHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc1OCBcdWQwNmNcdWFlMzAoXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOClcdWIyOTQgXHVkNTZkXHVjMGMxIDJcdWM3NTggXHVjODFjXHVhY2YxIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCAxLCAyLCA0LCA4LCAxNiwgLi4uXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODEwXHVjMmVjXHVjMmRkXHVjMGFjXHViODVjIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWJhMzlcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjODAxXHVjNWI0XHViM2M0IEtcdWFjMWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YmEzOVx1YzViNFx1YzU3YyBcdWIwYThcdWM3NDAgXHVjMjE4XHVjNWM1XHVjNzQ0IFx1Yzg3OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViYzg0XHVkMmY4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVjMTIwXHVjNjAxXHVjNzc0XHViM2M0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDAgXHViM2M4XHVjNzQ0IFx1YzhmY1x1YWNlMCBcdWMwYWNcdWFlMzAgXHVjNTQ0XHVhZTVkXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4ZmNcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHViOWNjIFx1YmEzOVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOVx1YjMwMCBcdWNkMDhcdWNmNWNcdWI5YmZcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzBiMCBcdWIyZTRcdWM3NGNcdWM1ZDAsIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBLXHVhYzFjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMyMFx1YjJlNC4gS1x1YWMxY1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViYTM5XHVhY2UwIFx1YjBhOFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM5XHViMzAwIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0MCBcdWIwOThcdWIyMDRcdWFlMzAgXHVjODcwXHVhZTA4IFx1YzViNFx1YjgzNVx1YWM4YyBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWQ1NmRcdWMwYzEgXHVhYzAwXHVjNmI0XHViMzcwXHViODVjXHViOWNjIFx1Y2FiY1x1YWMxY1x1YzljNFx1YjJlNC4gXHVjOTg5LCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgRFx1YWMxYyBcdWM3ODhcdWIyOTQgXHViOWM5XHViMzAwXHViMjk0IERcLzJcdWFjMWMgXHViOWM5XHViMzAwIFx1YjQ1MCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHVjYWJjXHVhYzFjXHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5LXHVhYzFjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDQgXHVjYWJjXHVhYzFjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1YzY0MCBcdWMwYWNcdWM1N2NcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YjljYyBcdWMwYjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZjJkIFx1ZDU1YyBcdWM4NzBcdWFjMDFcdWM3NzQgS1x1YWMxY1x1Yzc3YyBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHVhY2UwLCBcdWM1ZWNcdWI3ZWMgXHVjODcwXHVhYzAxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNTY5XHVjY2U0XHVjNzQ0IFx1YjU0YyBLXHVhYzFjXHVjNzc0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSyAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFkNmNcdWI5ZTRcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NTggXHVkMDZjXHVhZTMwXHVjNjQwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4IFx1Y2FiY1x1YWMxY1x1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDT0tPTEFEQSIsImRlc2NyaXB0aW9uIjoiPHA+QSBuZXcgdHlwZSBvZiBjaG9jb2xhdGUgYXJyaXZlZCBpbiB0aGUgbG9jYWwgc2hvcC4gVGhlIGNob2NvbGF0ZSBjb21lcyBpbiBiYXJzLCBlYWNoIGJhciBjb25zaXN0aW5nIG9mIE4gc3F1YXJlcy4gQmFycyBhcmUgZmFjdG9yeSBtYWRlIGFuZCBvbmx5IGNvbWUgaW4gc2l6ZXMgd2hpY2ggYXJlIGZ1bGwgcG93ZXJzIG9mIHR3by4gSW4gb3RoZXIgd29yZHMgYSBzaW5nbGUgYmFyIGhhcyAxLCAyLCA0LCA4LCAxNiwgLi4uIHNxdWFyZXMuPFwvcD5cclxuXHJcbjxwPlRvIGZ1bGx5IGFzc2VzIHRoZSBxdWFsaXR5IG9mIGNob2NvbGF0ZSBNaXJrbyBtdXN0IHNhbXBsZSBhdCBsZWFzdCBLIHNxdWFyZXMuIEhpcyBmcmllbmQgU2xhdmtvIHdvdWxkIGFsc28gbGlrZSB0byB0cnkgc29tZSBvZiB0aGUgY2hvY29sYXRlLiBTaW5jZSBNaXJrbyBpcyBpbiBhIGh1cnJ5IHRvIHRyeSB0aGUgY2hvY29sYXRlIGhpbXNlbGYsIGhlIGRlY2lkZXMgdG8gYnJlYWsgdGhlIGJhciBoZSBib3VnaHQgaW4gcGllY2VzLCBzdWNoIHRoYXQgaGUgaGFzIGV4YWN0bHkgSyBzcXVhcmVzLCBhbmQgbGVhdmVzIHRoZSByZXN0IChpZiBhbnkpIHRvIFNsYXZrby4gVGhlIGJhcnMgYXJlIGEgYml0IGJyaXR0bGUsIHNvIE1pcmtvIGNhbiBicmVhayB0aGVtIG9ubHkgb24gdGhlaXIgZXhhY3QgY2VudGVyLiBJbiBvdGhlciB3b3JkcywgZnJvbSBvbmUgYmFyIHdpdGggRCBzcXVhcmVzLCBoZSBjYW4gZ2V0IHR3byBiYXJzIHdpdGggRFwvMiBzcXVhcmVzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSB0aGUgbWluaW1hbCBudW1iZXIgb2YgYnJlYWtzIE1pcmtvIG11c3QgcGVyZm9ybSBpbiBvcmRlciB0byBvYnRhaW4gZXhhY3RseSBLIHNxdWFyZXMgKG5vdCBuZWNlc3NhcmlseSBpbiBvbmUgcGllY2UpLiBBbHNvLCBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IGJhciBzaXplIE1pcmtvIG11c3QgYnV5IGluIG9yZGVyIHRvIGhhdmUgYXQgbGVhc3QgSyBzcXVhcmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgd2lsbCBjb250YWluIG9uZSBpbnRlZ2VyIEsgKDEgJmxlOyBLICZsZTsgMSAwMDAgMDAwKSwgbnVtYmVyIG9mIHNxdWFyZXMgTWlya28gbXVzdCBzYW1wbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHR3byBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgZmlyc3QgaW50ZWdlciBpcyB0aGUgc21hbGxlc3QgYmFyIHNpemUgTWlya28gbXVzdCBidXkuIFRoZSBzZWNvbmQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBicmVha3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #7 2번