시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3551025842.963%

문제

x의 P승을(1 ≤ P ≤ 20,000) 최대한 빠르게 계산하고자 한다. 그런데 계산결과가 굉장히 크므로 여기서는 계산 도중 값을 저장하는 데 있어 두 개의 변수만을 사용한다.

두 변수 중 하나는 x로, 다른 하나는 1로 초기화되어 있다. 우리가 쓸 수 있는 연산은, 현재 저장되어 있는 값들을 서로 곱하거나 나누어서 그 결과값을 임의의 변수에 저장하는 것이다. 최종 결과가 저장되는 위치는 아무래도 좋다.

예를 들어 x9을 계산하고자 할 때, 다음과 같은 방법이 가능하다.

연산 회수 0 1 2 3 4
변수1 x x x x5 x9
변수2 1 x2 x4 x4 x4

P를 입력받아, xP를 구하기 위한 최소 연산 회수를 구하여라.

입력

첫째 줄에 P가 들어온다.

출력

최소 연산 회수를 출력한다.

예제 입력 1

31

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIwNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWI0ZWRcdWM4MWNcdWFjZjEgXHVhY2M0XHVjMGIwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD54XHVjNzU4IFBcdWMyYjlcdWM3NDQoMSAmbGU7IFAgJmxlOyAyMCwwMDApIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjBcdWI5NzRcdWFjOGMgXHVhY2M0XHVjMGIwXHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YWNjNFx1YzBiMFx1YWNiMFx1YWNmY1x1YWMwMCBcdWFkNDlcdWM3YTVcdWQ3ODggXHVkMDZjXHViYmMwXHViODVjIFx1YzVlY1x1YWUzMFx1YzExY1x1YjI5NCBcdWFjYzRcdWMwYjAgXHViM2M0XHVjOTExIFx1YWMxMlx1Yzc0NCBcdWM4MDBcdWM3YTVcdWQ1NThcdWIyOTQgXHViMzcwIFx1Yzc4OFx1YzViNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmNjMFx1YzIxOFx1YjljY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjYzBcdWMyMTggXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCB4XHViODVjLCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHViMjk0IDFcdWI4NWMgXHVjZDA4XHVhZTMwXHVkNjU0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNmIwXHViOWFjXHVhYzAwIFx1YzRmOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCwgXHVkNjA0XHVjN2FjIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhYzEyXHViNGU0XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFjZjFcdWQ1NThcdWFjNzBcdWIwOTggXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1YWRmOCBcdWFjYjBcdWFjZmNcdWFjMTJcdWM3NDQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YmNjMFx1YzIxOFx1YzVkMCBcdWM4MDBcdWM3YTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNkNWNcdWM4ODUgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzgwMFx1YzdhNVx1YjQxOFx1YjI5NCBcdWM3MDRcdWNlNThcdWIyOTQgXHVjNTQ0XHViYjM0XHViNzk4XHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCB4PHN1cD45PFwvc3VwPlx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTYwIFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDglXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo2JVwiPlx1YzVmMFx1YzBiMCBcdWQ2OGNcdWMyMTg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NiVcIj4wPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjYlXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo2JVwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NiVcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjYlXCI+NDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cdWJjYzBcdWMyMTgxPFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54PHN1cD41PFwvc3VwPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+eDxzdXA+OTxcL3N1cD48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHViY2MwXHVjMjE4MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+eDxzdXA+MjxcL3N1cD48XC90ZD5cclxuXHRcdFx0PHRkPng8c3VwPjQ8XC9zdXA+PFwvdGQ+XHJcblx0XHRcdDx0ZD54PHN1cD40PFwvc3VwPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+eDxzdXA+NDxcL3N1cD48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlBcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHVjNTQ0LCB4PHN1cD5QPFwvc3VwPlx1Yjk3YyBcdWFkNmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWMwYjAgXHVkNjhjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgUFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDVjXHVjMThjIFx1YzVmMFx1YzBiMCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwNzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb3dlciBIdW5ncnkgQ293cyIsImRlc2NyaXB0aW9uIjoiPHA+RkomIzM5O3MgY293cyB3b3VsZCBsaWtlIHRvIGJlIGFibGUgdG8gY29tcHV0ZSBpbnRlZ2VyIHBvd2VycyBQICgxICZsdDs9IFAgJmx0Oz0gMjAsMDAwKSBvZiBudW1iZXJzIHZlcnkgcXVpY2tseSwgYnV0IG5lZWQgeW91ciBoZWxwLiBCZWNhdXNlIHRoZXkmIzM5O3JlIGdvaW5nIHRvIGJlIGNvbXB1dGluZyBwb3dlcnMgb2YgdmVyeSBsYXJnZSBudW1iZXJzLCB0aGV5IGNhbiBvbmx5IGtlZXAgYXJvdW5kIHR3byB3b3JrIHZhcmlhYmxlcyBmb3IgaW50ZXJtZWRpYXRlIHJlc3VsdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBvZiB0aG9zZSB3b3JrIHZhcmlhYmxlcyBpcyBpbml0aWFsaXplZCB0byB0aGUgbnVtYmVyIChkZW5vdGVkIHgpIGZvciB3aGljaCB0aGV5IGFyZSBjYWxjdWxhdGluZyB0aGUgcG93ZXI7IHRoZSBvdGhlciBpcyBpbml0aWFsaXplZCB0byAxLiBUaGUgY293cyBjYW4gYm90aCBtdWx0aXBseSBhbmQgZGl2aWRlIGFueSBwYWlyIG9mIHRoZSB3b3JrIHZhcmlhYmxlcyBhbmQgc3RvcmUgdGhlIHJlc3VsdCBpbiBhbnkgd29yayB2YXJpYWJsZSwgYnV0IGFsbCByZXN1bHRzIGFyZSBzdG9yZWQgYXMgaW50ZWdlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGV5IHdhbnQgdG8gY29tcHV0ZSB4XjMxLCBvbmUgd2F5IHRvIHBlcmZvcm0gdGhlIGNhbGN1bGF0aW9uIGlzOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgV1YxICBXVjJcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBTdGFydDogICB4ICAgIDFcclxuICAgTXVsdGlwbHkgZmlyc3QgYnkgZmlyc3QsIHN0b3JlIGluIHNlY29uZDogICB4ICAgeF4yXHJcbiAgICAgICAgICAgICAgICAgIE11bHRpcGx5IHNlY29uZCBieSBzZWNvbmQ6ICAgeCAgIHheNFxyXG4gICAgICAgICAgICAgICAgICBNdWx0aXBseSBzZWNvbmQgYnkgc2Vjb25kOiAgIHggICB4XjhcclxuICAgICAgICAgICAgICAgICAgTXVsdGlwbHkgc2Vjb25kIGJ5IHNlY29uZDogICB4ICAgeF4xNlxyXG4gICAgICAgICAgICAgICAgICBNdWx0aXBseSBzZWNvbmQgYnkgc2Vjb25kOiAgIHggICB4XjMyXHJcbiAgICAgICAgICAgICAgICAgICAgIERpdmlkZSBzZWNvbmQgYnkgZmlyc3Q6ICAgeCAgIHheMzFcclxuPFwvcHJlPlxyXG5cclxuPHA+VGh1cywgeF4zMSBjYW4gY29tcHV0ZWQgaW4gc2l4IG9wZXJhdGlvbnMuIEdpdmVuIHRoZSBwb3dlciB0byBiZSBjb21wdXRlZCBhbmQgdGhlIHRoZSBudW1iZXIgb2Ygd29yayB2YXJpYWJsZXMsIGZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgdG8gY2FsY3VsYXRlIHRoZSBwb3dlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBvbmUgaW50ZWdlcjogUC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIGl0IHJlcXVpcmVzIHRvIGNvbXB1dGUgdGhlIHBvd2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2001-2002 Season > USACO February 2002 Contest > Green or Orange ?번

  • 데이터를 추가한 사람: doju
  • 문제의 오타를 찾은 사람: kcm1700