시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 174 48 33 26.829%

문제

국회에는 당이 N개 있고, 각각의 당은 확보한 의석이 있다.

이번에 당끼리 연합을 맺기로 했다. 연합이 유효하려면, 연합에 속한 당의 의석의 합이 전체 의석의 반을 넘어야 한다.

유효한 연합에서 소속된 당 하나를 제거했을 때, 여전히 유효한 연합이라면, 그 연합을 깔끔하지 못한 연합이라고 한다. 유효한 연합 중에서 깔끔하지 못한 연합을 제외한 것을 깔끔한 연합이라고 한다. 깔끔한 연합 중, 포함하는 의석의 수가 가장 많은 것을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 당의 수 N (1 ≤ N ≤ 300), 둘째 줄에 각 당의 의석 수가 주어진다.

당의 번호는 1번부터 N번까지이며, 의석 수의 합은 100,000을 넘지 않는다.

출력

의석 수가 가장 많은 깔끔한 연합을 구한 다음, 첫째 줄에 당의 수, 둘째 줄에 당의 번호를 출력한다.

예제 입력 1

4
1 3 2 4

예제 출력 1

2
2 4

힌트

W3sicHJvYmxlbV9pZCI6IjEyMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmRcdWQ2OGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWQ2ZFx1ZDY4Y1x1YzVkMFx1YjI5NCBcdWIyZjlcdWM3NzQgTlx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIyZjlcdWM3NDAgXHVkNjU1XHViY2Y0XHVkNTVjIFx1Yzc1OFx1YzExZFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmM4OFx1YzVkMCBcdWIyZjlcdWIwN2NcdWI5YWMgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YjlmYVx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzVmMFx1ZDU2OVx1Yzc3NCBcdWM3MjBcdWQ2YThcdWQ1NThcdWI4MjRcdWJhNzQsIFx1YzVmMFx1ZDU2OVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViMmY5XHVjNzU4IFx1Yzc1OFx1YzExZFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjODA0XHVjY2I0IFx1Yzc1OFx1YzExZFx1Yzc1OCBcdWJjMThcdWM3NDQgXHViMTE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVkNmE4XHVkNTVjIFx1YzVmMFx1ZDU2OVx1YzVkMFx1YzExYyBcdWMxOGNcdWMxOGRcdWI0MWMgXHViMmY5IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWM1ZWNcdWM4MDRcdWQ3ODggXHVjNzIwXHVkNmE4XHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHVhZGY4IFx1YzVmMFx1ZDU2OVx1Yzc0NCBcdWFlNTRcdWIwNTRcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzcyMFx1ZDZhOFx1ZDU1YyBcdWM1ZjBcdWQ1NjkgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWU1NFx1YjA1NFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWMgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWFjODNcdWM3NDQgXHVhZTU0XHViMDU0XHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWU1NFx1YjA1NFx1ZDU1YyBcdWM1ZjBcdWQ1NjkgXHVjOTExLCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjNzU4XHVjMTFkXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY5XHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDMwMCksIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjJmOVx1Yzc1OCBcdWM3NThcdWMxMWQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzBcdWM3NzRcdWJhNzAsIFx1Yzc1OFx1YzExZCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQwIDEwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3NThcdWMxMWQgXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVhZTU0XHViMDU0XHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NWMgXHViMmU0XHVjNzRjLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmOVx1Yzc1OCBcdWMyMTgsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVsZWN0aW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNpdGl6ZW5zIG9mIEJ5dGVsYW5kIGhhdmUgcmVjZW50bHkgYmVlbiB2b3RpbmcgaW4gdGhlIHBhcmxpYW1lbnRhcnkgZWxlY3Rpb25zLiBOb3csIHdoZW4gdGhlIHJlc3VsdHMgaGF2ZSBiZWVuIHB1Ymxpc2hlZCwgdGhlIHBhcnRpZXMgaGF2ZSB0byBkZWNpZGUgb24gYSBjb2FsaXRpb24gdG8gZm9ybSB0aGUgZ292ZXJubWVudC48XC9wPlxyXG5cclxuPHA+RWFjaCBwYXJ0eSByZWNlaXZlZCBhIGNlcnRhaW4gbnVtYmVyIG9mIHNlYXRzIGluIHRoZSBwYXJsaWFtZW50LiBUaGUgY29hbGl0aW9uIG11c3QgYmUgYSBzdWJzZXQgb2YgdGhlIHBhcnRpZXMgc3VjaCB0aGF0IHRvZ2V0aGVyIHRoZXkgaGF2ZSBzdHJpY3RseSBtb3JlIHRoYW4gaGFsZiBvZiBhbGwgdGhlIHNlYXRzIGluIHRoZSBwYXJsaWFtZW50LiBJdCBpcyBkZXNpcmFibGUgZm9yIHRoZSBjb2FsaXRpb24gdG8gaGF2ZSBhcyBtYW55IHNlYXRzIGFzIHBvc3NpYmxlLCB0byBlbnN1cmUgdGhleSBjYW4gc3RpbGwgcGFzcyB0aGVpciBwcm9wb3NlZCBsYXdzIGV2ZW4gaWYgYSBmZXcgb2YgdGhlaXIgbWVtYmVycyBhcmUgYWJzZW50IGZyb20gYSBwYXJsaWFtZW50IHNlc3Npb24uPFwvcD5cclxuXHJcbjxwPkEgY29hbGl0aW9uIGlzIGNhbGxlZCByZWR1bmRhbnQgaWYgb25lIG9mIGl0cyBwYXJ0aWVzIGNhbiBiZSByZW1vdmVkIHdpdGggdGhlIHJlbWFpbmluZyBvbmVzIHN0aWxsIGhhdmluZyBtb3JlIHRoYW4gaGFsZiBvZiB0aGUgc2VhdHMgaW4gdGhlIHBhcmxpYW1lbnQuIE9mIGNvdXJzZSwgc3VjaCBhIHJlbW92YWJsZSBwYXJ0eSB3b3VsZCBlXHVmYjAwZWN0aXZlbHkgaGF2ZSBubyBwb3dlciAmbWRhc2g7IHRoZSBvdGhlciBtZW1iZXJzIG9mIHRoZSBjb2FsaXRpb24gd291bGQgYmUgYWJsZSB0byBmb3JjZSB0aGUgbGF3cyByZWdhcmRsZXNzIG9mIGl0cyBvcGluaW9uLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgZWxlY3Rpb24gcmVzdWx0cyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+XHVmYjAxbmRzIGEgbm9uLXJlZHVuZGFudCBjb2FsaXRpb24gdGhhdCBoYXMgdGhlIG1heGltYWwgcG9zc2libGUgbnVtYmVyIG9mIHNlYXRzIGluIHRoZSBwYXJsaWFtZW50LDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoaXMgY29hbGl0aW9uIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAzMDAgKSAmbWRhc2g7IHRoZSBudW1iZXIgb2YgcGFydGllcyB0aGF0IHBhcnRpY2lwYXRlZCBpbiB0aGUgZWxlY3Rpb25zLiBUaGUgcGFydGllcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIG5vbm5lZ2F0aXZlIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LC4uLiwgYTxzdWI+bjxcL3N1Yj4sIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCB3aGVyZSBhPHN1Yj5pPFwvc3ViPiBpcyB0aGUgbnVtYmVyIG9mIHNlYXRzIHJlY2VpdmVkIGJ5IHRoZSBpLXRoIHBhcnR5LiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSB0b3RhbCBudW1iZXIgb2Ygc2VhdHMgaW4gdGhlIHBhcmxpYW1lbnQgd2lsbCBiZSBwb3NpdGl2ZSBhbmQgbG93ZXIgb3IgZXF1YWwgdG8gMTAwIDAwMCAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgayAmbWRhc2g7IHRoZSBudW1iZXIgb2YgcGFydGllcyBpbiBhIG5vbi1yZWR1bmRhbnQgY29hbGl0aW9uIHdoaWNoIGhhcyB0aGUgbWF4aW1hbCBudW1iZXIgb2Ygc2VhdHMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBzaG91bGQgY29udGFpbiBrIGRpc3RpbmN0IGludGVnZXJzIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzICZtZGFzaDsgdGhlIG51bWJlcnMgb2YgcGFydGllcyB0aGF0IGZvcm0gdGhlIGNvYWxpdGlvbi48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIHNldmVyYWwgbm9uLXJlZHVuZGFudCBjb2FsaXRpb25zIHdpdGggdGhlIG1heGltYWwgbnVtYmVyIG9mIHNlYXRzLCB5b3UgbWF5IG91dHB1dCBhbnkgb2YgdGhlbS4gVGhlIG1lbWJlciBwYXJ0aWVzIGNhbiBiZSBsaXN0ZWQgaW4gYW55IG9yZGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 1번