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

문제

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

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

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

입력

첫째 줄에 당의 수 N (1 ≤ N ≤ 300), 둘째 줄에 각 당의 의석 수가 주어진다. 각 당의 의석 수는 100,000을 넘지 않는 음이 아닌 정수이다.

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

출력

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

예제 입력 1

4
1 3 2 4

예제 출력 1

2
2 4
W3sicHJvYmxlbV9pZCI6IjEyMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmRcdWQ2OGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWQ2ZFx1ZDY4Y1x1YzVkMFx1YjI5NCBcdWIyZjlcdWM3NzQgTlx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIyZjlcdWM3NDAgXHVkNjU1XHViY2Y0XHVkNTVjIFx1Yzc1OFx1YzExZFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmM4OFx1YzVkMCBcdWIyZjlcdWIwN2NcdWI5YWMgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YjlmYVx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzVmMFx1ZDU2OVx1Yzc3NCBcdWM3MjBcdWQ2YThcdWQ1NThcdWI4MjRcdWJhNzQsIFx1YzVmMFx1ZDU2OVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViMmY5XHVjNzU4IFx1Yzc1OFx1YzExZFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjODA0XHVjY2I0IFx1Yzc1OFx1YzExZFx1Yzc1OCBcdWJjMThcdWM3NDQgXHViMTE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVkNmE4XHVkNTVjIFx1YzVmMFx1ZDU2OVx1YzVkMFx1YzExYyBcdWMxOGNcdWMxOGRcdWI0MWMgXHViMmY5IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWM1ZWNcdWM4MDRcdWQ3ODggXHVjNzIwXHVkNmE4XHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHVhZGY4IFx1YzVmMFx1ZDU2OVx1Yzc0NCBcdWFlNTRcdWIwNTRcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzcyMFx1ZDZhOFx1ZDU1YyBcdWM1ZjBcdWQ1NjkgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWU1NFx1YjA1NFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NWMgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWFjODNcdWM3NDQgXHVhZTU0XHViMDU0XHVkNTVjIFx1YzVmMFx1ZDU2OVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWU1NFx1YjA1NFx1ZDU1YyBcdWM1ZjBcdWQ1NjkgXHVjOTExLCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjNzU4XHVjMTFkXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY5XHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDMwMCksIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjJmOVx1Yzc1OCBcdWM3NThcdWMxMWQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YjJmOVx1Yzc1OCBcdWM3NThcdWMxMWQgXHVjMjE4XHViMjk0IDEwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzBcdWM3NzRcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWIyZjlcdWM3NTggXHVjNzU4XHVjMTFkIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDAgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc1OFx1YzExZCBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWFlNTRcdWIwNTRcdWQ1NWMgXHVjNWYwXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWIyZTRcdWM3NGMsIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY5XHVjNzU4IFx1YzIxOCwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZjlcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMjI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWxlY3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY2l0aXplbnMgb2YgQnl0ZWxhbmQgaGF2ZSByZWNlbnRseSBiZWVuIHZvdGluZyBpbiB0aGUgcGFybGlhbWVudGFyeSBlbGVjdGlvbnMuIE5vdywgd2hlbiB0aGUgcmVzdWx0cyBoYXZlIGJlZW4gcHVibGlzaGVkLCB0aGUgcGFydGllcyBoYXZlIHRvIGRlY2lkZSBvbiBhIGNvYWxpdGlvbiB0byBmb3JtIHRoZSBnb3Zlcm5tZW50LjxcL3A+XHJcblxyXG48cD5FYWNoIHBhcnR5IHJlY2VpdmVkIGEgY2VydGFpbiBudW1iZXIgb2Ygc2VhdHMgaW4gdGhlIHBhcmxpYW1lbnQuIFRoZSBjb2FsaXRpb24gbXVzdCBiZSBhIHN1YnNldCBvZiB0aGUgcGFydGllcyBzdWNoIHRoYXQgdG9nZXRoZXIgdGhleSBoYXZlIHN0cmljdGx5IG1vcmUgdGhhbiBoYWxmIG9mIGFsbCB0aGUgc2VhdHMgaW4gdGhlIHBhcmxpYW1lbnQuIEl0IGlzIGRlc2lyYWJsZSBmb3IgdGhlIGNvYWxpdGlvbiB0byBoYXZlIGFzIG1hbnkgc2VhdHMgYXMgcG9zc2libGUsIHRvIGVuc3VyZSB0aGV5IGNhbiBzdGlsbCBwYXNzIHRoZWlyIHByb3Bvc2VkIGxhd3MgZXZlbiBpZiBhIGZldyBvZiB0aGVpciBtZW1iZXJzIGFyZSBhYnNlbnQgZnJvbSBhIHBhcmxpYW1lbnQgc2Vzc2lvbi48XC9wPlxyXG5cclxuPHA+QSBjb2FsaXRpb24gaXMgY2FsbGVkIHJlZHVuZGFudCBpZiBvbmUgb2YgaXRzIHBhcnRpZXMgY2FuIGJlIHJlbW92ZWQgd2l0aCB0aGUgcmVtYWluaW5nIG9uZXMgc3RpbGwgaGF2aW5nIG1vcmUgdGhhbiBoYWxmIG9mIHRoZSBzZWF0cyBpbiB0aGUgcGFybGlhbWVudC4gT2YgY291cnNlLCBzdWNoIGEgcmVtb3ZhYmxlIHBhcnR5IHdvdWxkIGVcdWZiMDBlY3RpdmVseSBoYXZlIG5vIHBvd2VyICZtZGFzaDsgdGhlIG90aGVyIG1lbWJlcnMgb2YgdGhlIGNvYWxpdGlvbiB3b3VsZCBiZSBhYmxlIHRvIGZvcmNlIHRoZSBsYXdzIHJlZ2FyZGxlc3Mgb2YgaXRzIG9waW5pb24uPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBlbGVjdGlvbiByZXN1bHRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5cdWZiMDFuZHMgYSBub24tcmVkdW5kYW50IGNvYWxpdGlvbiB0aGF0IGhhcyB0aGUgbWF4aW1hbCBwb3NzaWJsZSBudW1iZXIgb2Ygc2VhdHMgaW4gdGhlIHBhcmxpYW1lbnQsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgZGVzY3JpcHRpb24gb2YgdGhpcyBjb2FsaXRpb24gdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDMwMCkgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHBhcnRpZXMgdGhhdCBwYXJ0aWNpcGF0ZWQgaW4gdGhlIGVsZWN0aW9ucy4gVGhlIHBhcnRpZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgbiBub25uZWdhdGl2ZSBpbnRlZ2VycyBhPHN1Yj4xPFwvc3ViPiwuLi4sIGE8c3ViPm48XC9zdWI+LCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcywgd2hlcmUgYTxzdWI+aTxcL3N1Yj4gaXMgdGhlIG51bWJlciBvZiBzZWF0cyByZWNlaXZlZCBieSB0aGUgaS10aCBwYXJ0eS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgdG90YWwgbnVtYmVyIG9mIHNlYXRzIGluIHRoZSBwYXJsaWFtZW50IHdpbGwgYmUgcG9zaXRpdmUgYW5kIGxvd2VyIG9yIGVxdWFsIHRvIDEwMCAwMDAgLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIGsgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHBhcnRpZXMgaW4gYSBub24tcmVkdW5kYW50IGNvYWxpdGlvbiB3aGljaCBoYXMgdGhlIG1heGltYWwgbnVtYmVyIG9mIHNlYXRzLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgc2hvdWxkIGNvbnRhaW4gayBkaXN0aW5jdCBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyAmbWRhc2g7IHRoZSBudW1iZXJzIG9mIHBhcnRpZXMgdGhhdCBmb3JtIHRoZSBjb2FsaXRpb24uPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBzZXZlcmFsIG5vbi1yZWR1bmRhbnQgY29hbGl0aW9ucyB3aXRoIHRoZSBtYXhpbWFsIG51bWJlciBvZiBzZWF0cywgeW91IG1heSBvdXRwdXQgYW55IG9mIHRoZW0uIFRoZSBtZW1iZXIgcGFydGllcyBjYW4gYmUgbGlzdGVkIGluIGFueSBvcmRlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 4번