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

문제

당근을 잘 볶으려면 당근의 크기를 모두 비슷하게 만들고 볶아야 한다. 

상근이는 당근 N개를 가지고 있다. 상근이는 한 번에 당근 하나를 칼로 두 조각으로 낼 수 있다. 즉, 무게가 w인 당근을 잘라서 무게가 wleft와 wright인 두 당근을 만들 수 있다. (wleft + wright = w) 

상근이는 칼질을 무서워하기 때문에, 칼질을 되도록 적게 하려고 한다.

당근의 무게가 주어졌을 때, 가장 가벼운 당근과 큰 무거운 당근의 무게의 비율이 T를 넘기 위한 최소 칼질 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 비율 T와 당근의 수 N이 주어진다. T는 소수점 둘째 자리까지 주어지며, 0.5 < T < 1을 만족한다. N은 양의 정수이며,  N ≤ 1,000이다.

둘째 줄에는 당근의 무게 w1, w2, ..., wN이 주어진다. wi는 106보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가벼운 당근과 가장 무거운 당근의 비율이 T를 넘기 위해 필요한 칼질의 최소 횟수를 출력한다. 정답은 항상 500보다 작다.

소수점 오차로 인해서 생기는 오답을 막기 위해 비율이 T + 0.0001라고 풀었을 때의 정답과 T라고 풀었을 때의 정답이 같은 입력만 주어진다.

예제 입력 1

0.80 2
1000 1400

예제 출력 1

3

예제 입력 2

0.99 3
2000 3000 4000

예제 출력 2

6
W3sicHJvYmxlbV9pZCI6IjkyMzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZjlcdWFkZmMgXHViY2Y2XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWFkZmNcdWM3NDQgXHVjNzk4IFx1YmNmNlx1YzczY1x1YjgyNFx1YmE3NCBcdWIyZjlcdWFkZmNcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0XHVhY2UwIFx1YmNmNlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZjlcdWFkZmMgTlx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWIyZjlcdWFkZmMgXHVkNTU4XHViMDk4XHViOTdjIFx1Y2U3Y1x1Yjg1YyBcdWI0NTAgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YmIzNFx1YWM4Y1x1YWMwMCB3XHVjNzc4IFx1YjJmOVx1YWRmY1x1Yzc0NCBcdWM3OThcdWI3N2NcdWMxMWMgXHViYjM0XHVhYzhjXHVhYzAwIHc8c3ViPmxlZnQ8XC9zdWI+XHVjNjQwIHc8c3ViPnJpZ2h0PFwvc3ViPlx1Yzc3OCBcdWI0NTAgXHViMmY5XHVhZGZjXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiAodzxzdWI+bGVmdDxcL3N1Yj4gKyB3PHN1Yj5yaWdodDxcL3N1Yj4gPSB3KSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTdjXHVjOWM4XHVjNzQ0IFx1YmIzNFx1YzExY1x1YzZjY1x1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Y2U3Y1x1YzljOFx1Yzc0NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODAxXHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YWRmY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YmNiY1x1YzZiNCBcdWIyZjlcdWFkZmNcdWFjZmMgXHVkMDcwIFx1YmIzNFx1YWM3MFx1YzZiNCBcdWIyZjlcdWFkZmNcdWM3NTggXHViYjM0XHVhYzhjXHVjNzU4Jm5ic3A7XHViZTQ0XHVjNzI4XHVjNzc0IFRcdWI5N2MgXHViMTE4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjZTdjXHVjOWM4IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZTQ0XHVjNzI4IFRcdWM2NDAgXHViMmY5XHVhZGZjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gVFx1YjI5NCBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIDAuNSAmbHQ7IFQgJmx0OyAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gTlx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViYTcwLCAmbmJzcDtOICZsZTsgMSwwMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmY5XHVhZGZjXHVjNzU4IFx1YmIzNFx1YWM4YyB3PHN1Yj4xPFwvc3ViPiwgdzxzdWI+MjxcL3N1Yj4sIC4uLiwgdzxzdWI+TjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiB3PHN1Yj5pPFwvc3ViPlx1YjI5NCAxMDxzdXA+NjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHViY2JjXHVjNmI0IFx1YjJmOVx1YWRmY1x1YWNmYyBcdWFjMDBcdWM3YTUgXHViYjM0XHVhYzcwXHVjNmI0IFx1YjJmOVx1YWRmY1x1Yzc1OCBcdWJlNDRcdWM3MjhcdWM3NzQgVFx1Yjk3YyBcdWIxMThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNlN2NcdWM5YzhcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc0MCBcdWQ1NmRcdWMwYzEgNTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjXHVjMjE4XHVjODEwIFx1YzYyNFx1Y2MyOFx1Yjg1YyBcdWM3NzhcdWQ1NzRcdWMxMWMgXHVjMGRkXHVhZTMwXHViMjk0IFx1YzYyNFx1YjJmNVx1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmU0NFx1YzcyOFx1Yzc3NCBUICsgMC4wMDAxXHViNzdjXHVhY2UwIFx1ZDQ4MFx1YzVjOFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVjODE1XHViMmY1XHVhY2ZjIFRcdWI3N2NcdWFjZTAgXHVkNDgwXHVjNWM4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NzQmbmJzcDtcdWFjMTlcdWM3NDAgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5MjM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm9pbGluZyBWZWdldGFibGVzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgdHJpY2sgdG8gYm9pbGluZyB2ZWdldGFibGVzIGlzIHRvIG1ha2Ugc3VyZSBhbGwgcGllY2VzIGFyZSBhYm91dCB0aGUgc2FtZSBzaXplLiBJZiB0aGV5IGFyZSBub3QsIHRoZSBzbWFsbCBvbmVzIGdldCB0b28gc29mdCBvciB0aGUgbGFyZ2Ugb25lcyBnZXQgdW5kZXJjb29rZWQgKG9yIGJvdGgpLiBGb3J0dW5hdGVseSwgeW91IGhhdmUgaGVhcmQgb2YgdGhlIGtpdGNoZW4ga25pZmUsIGJ1dCB5b3VyIHBhcmVudHMmcnNxdW87IHdhcm5pbmdzIG9mIHVzaW5nIHNoYXJwIGluc3RydW1lbnRzIHN0aWxsIGVjaG9lcyBpbiB5b3VyIGhlYWQuIFRoZXJlZm9yZSB5b3UgYmV0dGVyIHVzZSBpdCBhcyBsaXR0bGUgYXMgcG9zc2libGUuIFlvdSBjYW4gdGFrZSBhIHBpZWNlIG9mIGEgdmVnZXRhYmxlIG9mIHdlaWdodCB3IGFuZCBjdXQgaXQgYXJiaXRyYXJpbHkgaW4gdHdvIHBpZWNlcyBvZiB3ZWlnaHQgdzxzdWI+bGVmdDxcL3N1Yj4gYW5kIHc8c3ViPnJpZ2h0PFwvc3ViPiwgd2hlcmUgdzxzdWI+bGVmdDxcL3N1Yj4gKyB3PHN1Yj5yaWdodDxcL3N1Yj4gPSB3LiBUaGlzIG9wZXJhdGlvbiBjb25zdGl0dXRlcyBhICZsZHF1bztjdXQmcmRxdW87LiBHaXZlbiBhIHNldCBvZiBwaWVjZXMgb2YgdmVnZXRhYmxlcywgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjdXRzIG5lZWRlZCB0byBtYWtlIHRoZSByYXRpbyBiZXR3ZWVuIHRoZSBzbWFsbGVzdCBhbmQgdGhlIGxhcmdlc3QgcmVzdWx0aW5nIHBpZWNlIGdvIGFib3ZlIGEgZ2l2ZW4gdGhyZXNob2xkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgXHVmYjAyb2F0aW5nIHBvaW50IG51bWJlciBUIHdpdGggMiBkZWNpbWFsIGRpZ2l0cywgMC41ICZsdDsgVCAmbHQ7IDEsIGFuZCBhIHBvc2l0aXZlIGludGVnZXIgTiAmbGU7IDEgMDAwLiBOZXh0IGZvbGxvdyBOIHBvc2l0aXZlIGludGVnZXIgd2VpZ2h0cyB3PHN1Yj4xPFwvc3ViPiwgdzxzdWI+MjxcL3N1Yj4sIC4uLiwgdzxzdWI+TjxcL3N1Yj4uIEFsbCB3ZWlnaHRzIGFyZSBsZXNzIHRoYW4gMTA8c3VwPjY8XC9zdXA+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2YgY3V0cyBuZWVkZWQgdG8gbWFrZSB0aGUgcmF0aW8gYmV0d2VlbiB0aGUgcmVzdWx0aW5nIG1pbmltdW0gd2VpZ2h0IHBpZWNlIGFuZCB0aGUgcmVzdWx0aW5nIG1heGltdW0gd2VpZ2h0IHBpZWNlIGJlIGFib3ZlIFQuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIG51bWJlciBvZiBjdXRzIG5lZWRlZCBpcyBsZXNzIHRoYW4gNTAwLjxcL3A+XHJcblxyXG48cD5UbyBhdm9pZCBpc3N1ZXMgd2l0aCBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVycywgeW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgb3B0aW1hbCBhbnN3ZXIgZm9yIHJhdGlvIFQgaXMgdGhlIHNhbWUgYXMgZm9yIHJhdGlvIFQgKyAwLjAwMDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2013 B번

  • 문제를 번역한 사람: baekjoon
  • 문제를 만든 사람: Andreas Björklund, Lukáš Poláček