시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 168 89 80 55.172%

문제

학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODEwXHVjMmVjXHVjMmRkXHVjMGFjXHViODVjIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWJhMzlcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzgwMVx1YzViNFx1YjNjNCBLXHVhYzFjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWJhMzlcdWM1YjRcdWM1N2MgXHViMGE4XHVjNzQwIFx1YzIxOFx1YzVjNVx1Yzc0NCBcdWM4NzhcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YmM4NFx1ZDJmOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjNjNCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQwIFx1YjNjOFx1Yzc0NCBcdWM4ZmNcdWFjZTAgXHVjMGFjXHVhZTMwIFx1YzU0NFx1YWU1ZFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOGZjXHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1YjljYyBcdWJhMzlcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5YzlcdWIzMDAgXHVjZDA4XHVjZjVjXHViOWJmXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWMwYjAgXHViMmU0XHVjNzRjXHVjNWQwLCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgS1x1YWMxYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMjBcdWIyZTQuIEtcdWFjMWNcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmEzOVx1YWNlMCBcdWIwYThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOVx1YjMwMCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDAgXHViMDk4XHViMjA0XHVhZTMwIFx1Yzg3MFx1YWUwOCBcdWM1YjRcdWI4MzVcdWFjOGMgXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzExYywgXHVkNTZkXHVjMGMxIFx1YWMwMFx1YzZiNFx1YjM3MFx1Yjg1Y1x1YjljYyBcdWNhYmNcdWFjMWNcdWM5YzRcdWIyZTQuIFx1Yzk4OSwgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IERcdWFjMWMgXHVjNzg4XHViMjk0IFx1YjljOVx1YjMwMFx1YjI5NCBEXC8yXHVhYzFjIFx1YjljOVx1YjMwMCBcdWI0NTAgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1Y2FiY1x1YWMxY1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+S1x1YWMxYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWM2NDAgXHVjMGFjXHVjNTdjXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjMGI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWYyZCBcdWQ1NWMgXHVjODcwXHVhYzAxXHVjNzc0IEtcdWFjMWNcdWM3N2MgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YWNlMCwgXHVjNWVjXHViN2VjIFx1Yzg3MFx1YWMwMVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDU2OVx1Y2NlNFx1Yzc0NCBcdWI1NGMgS1x1YWMxY1x1Yzc3NFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWNhYmNcdWFjMWNcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ09LT0xBREEiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbmV3IHR5cGUgb2YgY2hvY29sYXRlIGFycml2ZWQgaW4gdGhlIGxvY2FsIHNob3AuIFRoZSBjaG9jb2xhdGUgY29tZXMgaW4gYmFycywgZWFjaCBiYXIgY29uc2lzdGluZyBvZiBOIHNxdWFyZXMuIEJhcnMgYXJlIGZhY3RvcnkgbWFkZSBhbmQgb25seSBjb21lIGluIHNpemVzIHdoaWNoIGFyZSBmdWxsIHBvd2VycyBvZiB0d28uIEluIG90aGVyIHdvcmRzIGEgc2luZ2xlIGJhciBoYXMgMSwgMiwgNCwgOCwgMTYsIC4uLiBzcXVhcmVzLjxcL3A+XHJcblxyXG48cD5UbyBmdWxseSBhc3NlcyB0aGUgcXVhbGl0eSBvZiBjaG9jb2xhdGUgTWlya28gbXVzdCBzYW1wbGUgYXQgbGVhc3QgSyBzcXVhcmVzLiBIaXMgZnJpZW5kIFNsYXZrbyB3b3VsZCBhbHNvIGxpa2UgdG8gdHJ5IHNvbWUgb2YgdGhlIGNob2NvbGF0ZS4gU2luY2UgTWlya28gaXMgaW4gYSBodXJyeSB0byB0cnkgdGhlIGNob2NvbGF0ZSBoaW1zZWxmLCBoZSBkZWNpZGVzIHRvIGJyZWFrIHRoZSBiYXIgaGUgYm91Z2h0IGluIHBpZWNlcywgc3VjaCB0aGF0IGhlIGhhcyBleGFjdGx5IEsgc3F1YXJlcywgYW5kIGxlYXZlcyB0aGUgcmVzdCAoaWYgYW55KSB0byBTbGF2a28uIFRoZSBiYXJzIGFyZSBhIGJpdCBicml0dGxlLCBzbyBNaXJrbyBjYW4gYnJlYWsgdGhlbSBvbmx5IG9uIHRoZWlyIGV4YWN0IGNlbnRlci4gSW4gb3RoZXIgd29yZHMsIGZyb20gb25lIGJhciB3aXRoIEQgc3F1YXJlcywgaGUgY2FuIGdldCB0d28gYmFycyB3aXRoIERcLzIgc3F1YXJlcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGJyZWFrcyBNaXJrbyBtdXN0IHBlcmZvcm0gaW4gb3JkZXIgdG8gb2J0YWluIGV4YWN0bHkgSyBzcXVhcmVzIChub3QgbmVjZXNzYXJpbHkgaW4gb25lIHBpZWNlKS4gQWxzbywgZGV0ZXJtaW5lIHRoZSBzbWFsbGVzdCBiYXIgc2l6ZSBNaXJrbyBtdXN0IGJ1eSBpbiBvcmRlciB0byBoYXZlIGF0IGxlYXN0IEsgc3F1YXJlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiBvbmUgaW50ZWdlciBLICgxICZsZTsgSyAmbGU7IDEgMDAwIDAwMCksIG51bWJlciBvZiBzcXVhcmVzIE1pcmtvIG11c3Qgc2FtcGxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IGludGVnZXIgaXMgdGhlIHNtYWxsZXN0IGJhciBzaXplIE1pcmtvIG11c3QgYnV5LiBUaGUgc2Vjb25kIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgYnJlYWtzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==