시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 68 12 12 28.571%

문제

어느 날 화학선생님이 화학시간에 맨날 딴짓만 하던 선영이에게 지하실에 가서 실험 때 쓸 장갑을 가져오라고 지시했다.

장갑엔 n가지 색상이 있고 지하실에는 2개의 통이 있는데 한쪽에는 n가지 색상의 왼손쪽 장갑이 들어있고 다른 한쪽에는 n가지 색상의 오른손쪽 장갑이 들어있다. 선영이는 각각의 통에 어떤 색깔의 장갑이 몇 개가 들어있는지 알고 있다.

그런데 지하실은 너무나도 깜깜해서 장갑을 꺼내도 색을 구별하기는 힘들고 양쪽의 통에서 임의로 장갑 여러개를 집어올 수 있다.

여러개의 장갑중에 항상 색깔이 같은 장갑의 쌍이 적어도 한 개이상 존재하도록 하기 위해서 선영이가 각각 통에서 가져와야할 장갑은 몇 개인지 구하라.

입력

입력의 첫 줄에는 색깔의 가지수 N(1<=N<=20)이 주어지고 2번째 줄과 3번째 줄에는 각각 왼쪽 통과 오른쪽 통에 들어 있는 색깔별 장갑의 수(10^8이하)가 주어진다.

출력

일치하는 장갑을 하나 이상 뽑아내기 위해 가져와야 되는 최소한의 장갑의 수를 각각 출력한다.

예제 입력 1

4
0 7 1 6
1 5 0 6

예제 출력 1

2
8

힌트

임의로 왼쪽 통에서 2개, 오른쪽 통에서 8개를 가져온다면 최소한 한 쌍의 같은색의 장갑이 나옴을 보장할 수 있다.

W3sicHJvYmxlbV9pZCI6IjExOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWFjMTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjI5MCBcdWIwYTAgXHVkNjU0XHVkNTU5XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1ZDY1NFx1ZDU1OVx1YzJkY1x1YWMwNFx1YzVkMCBcdWI5ZThcdWIwYTAgXHViNTM0XHVjOWQzXHViOWNjIFx1ZDU1OFx1YjM1OCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNWQwIFx1YWMwMFx1YzExYyBcdWMyZTRcdWQ1ZDggXHViNTRjIFx1YzRmOCBcdWM3YTVcdWFjMTFcdWM3NDQgXHVhYzAwXHVjODM4XHVjNjI0XHViNzdjXHVhY2UwIFx1YzljMFx1YzJkY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2E1XHVhYzExXHVjNWQ0IG5cdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzc0IFx1Yzc4OFx1YWNlMCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDBcdWIyOTQgMlx1YWMxY1x1Yzc1OCBcdWQxYjVcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwIFx1ZDU1Y1x1Y2FiZFx1YzVkMFx1YjI5NCBuXHVhYzAwXHVjOWMwIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWM2N2NcdWMxOTBcdWNhYmQgXHVjN2E1XHVhYzExXHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YWNlMCBcdWIyZTRcdWI5NzggXHVkNTVjXHVjYWJkXHVjNWQwXHViMjk0IG5cdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzYyNFx1Yjk3OFx1YzE5MFx1Y2FiZCBcdWM3YTVcdWFjMTFcdWM3NzQgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDFiNVx1YzVkMCBcdWM1YjRcdWI1YTQgXHVjMGM5XHVhZTU0XHVjNzU4IFx1YzdhNVx1YWMxMVx1Yzc3NCBcdWJhODcgXHVhYzFjXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNzQwIFx1YjEwOFx1YmIzNFx1YjA5OFx1YjNjNCBcdWFlNWNcdWFlNWNcdWQ1NzRcdWMxMWMgXHVjN2E1XHVhYzExXHVjNzQ0IFx1YWViY1x1YjBiNFx1YjNjNCBcdWMwYzlcdWM3NDQgXHVhZDZjXHViY2M0XHVkNTU4XHVhZTMwXHViMjk0IFx1ZDc5OFx1YjRlNFx1YWNlMCBcdWM1OTFcdWNhYmRcdWM3NTggXHVkMWI1XHVjNWQwXHVjMTFjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWM3YTVcdWFjMTEgXHVjNWVjXHViN2VjXHVhYzFjXHViOTdjIFx1YzlkMVx1YzViNFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVjN2E1XHVhYzExXHVjOTExXHVjNWQwIFx1ZDU2ZFx1YzBjMSBcdWMwYzlcdWFlNTRcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzdhNVx1YWMxMVx1Yzc1OCBcdWMzMGRcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWMwMVx1YWMwMSBcdWQxYjVcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjODM4XHVjNjQwXHVjNTdjXHVkNTYwIFx1YzdhNVx1YWMxMVx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWFjMDBcdWM5YzBcdWMyMTggTigxJmx0Oz1OJmx0Oz0yMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIDJcdWJjODhcdWM5ZjggXHVjOTA0XHVhY2ZjIDNcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWM2N2NcdWNhYmQgXHVkMWI1XHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWQxYjVcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMwYzlcdWFlNTRcdWJjYzQgXHVjN2E1XHVhYzExXHVjNzU4IFx1YzIxOCgxMF44XHVjNzc0XHVkNTU4KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YzdhNVx1YWMxMVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1YmY1MVx1YzU0NFx1YjBiNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzAwXHVjODM4XHVjNjQwXHVjNTdjIFx1YjQxOFx1YjI5NCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVjN2E1XHVhYzExXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjMDFcdWFjMDEgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3ODRcdWM3NThcdWI4NWMgXHVjNjdjXHVjYWJkIFx1ZDFiNVx1YzVkMFx1YzExYyAyXHVhYzFjLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVkMWI1XHVjNWQwXHVjMTFjIDhcdWFjMWNcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjI4XHViMmU0XHViYTc0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWQ1NWMgXHVjMzBkXHVjNzU4IFx1YWMxOVx1Yzc0MFx1YzBjOVx1Yzc1OCBcdWM3YTVcdWFjMTFcdWM3NzQgXHViMDk4XHVjNjM0XHVjNzQ0IFx1YmNmNFx1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdsb3ZlcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIGRhcmsgYmFzZW1lbnQgb2YgY2hlbWlzdHJ5IHByb2Zlc3NvciBBY2lkcmFpbiZyc3F1bztzIGhvdXNlIHRoZXJlIGFyZSB0d28gZHJhd2VycyB3aXRoIGdsb3ZlcyAmbWRhc2g7IG9uZSB3aXRoIGxlZnQgaGFuZCBhbmQgb3RoZXIgd2l0aCByaWdodCBoYW5kIGdsb3Zlcy4gSW4gZWFjaCBvZiB0aGVtIHRoZXJlIGFyZSBnbG92ZXMgb2YgbiBkaVx1ZmIwMGVyZW50IGNvbG91cnMuIFByb2Zlc3NvciBrbm93cyBob3cgbWFueSBnbG92ZXMgb2YgZWFjaCBjb2xvdXIgdGhlcmUgYXJlIGluIGVhY2ggZHJhd2VyICh0aGUgbnVtYmVyIG9mIGdsb3ZlcyBvZiB0aGUgc2FtZSBjb2xvdXIgbWF5IGRpXHVmYjAwZXIgaW4gYm90aCBkcmF3ZXJzKS4gSGUgaXMgYWxzbyBzdXJlIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gXHVmYjAxbmQgYSBwYWlyIG9mIGdsb3ZlcyBvZiB0aGUgc2FtZSBjb2xvdXIuPFwvcD5cclxuXHJcbjxwPlByb2Zlc3NvciZyc3F1bztzIGV4cGVyaW1lbnQgbWF5IGJlIHN1Y2Nlc3NmdWwgb25seSBpZiBoZSB1c2VzIGdsb3ZlcyBvZiB0aGUgc2FtZSBjb2xvdXIgKGl0IGRvZXMgbm90IG1hdHRlciB3aGljaCBvbmUpLCBzbyBiZWZvcmUgZXZlcnkgZXhwZXJpbWVudCBoZSBnb2VzIHRvIHRoZSBiYXNlbWVudCBhbmQgdGFrZXMgZ2xvdmVzIGZyb20gdGhlIGRyYXdlcnMgaG9waW5nIHRoYXQgdGhlcmUgd2lsbCBiZSBhdCBsZWFzdCBvbmUgcGFpciBvZiB0aGUgc2FtZSBjb2xvdXIuIEl0IGlzIHNvIGRhcmsgaW4gdGhlIGJhc2VtZW50IHRoYXQgdGhlcmUgaXMgbm8gcG9zc2liaWxpdHkgdG8gcmVjb2duaXplIGNvbG91ciBvZiBhbnkgZ2xvdmUgd2l0aG91dCBnb2luZyBvdXQgb2YgdGhlIGJhc2VtZW50LiBQcm9mZXNzb3IgaGF0ZXMgZ29pbmcgdG8gdGhlIGJhc2VtZW50IG1vcmUgdGhhbiBvbmNlIChpbiBjYXNlIHRoZXJlIHdhcyBubyBwYWlyIG9mIGdsb3ZlcyBvZiB0aGUgc2FtZSBjb2xvdXIpLCBhcyB3ZWxsIGFzIGJyaW5naW5nIHVubmVjZXNzYXJpbHkgbGFyZ2UgYW1vdW50cyBvZiBnbG92ZXMgdG8gdGhlIGxhYm9yYXRvcnkuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBudW1iZXIgb2YgY29sb3VycyBhbmQgdGhlIG51bWJlciBvZiBnbG92ZXMgaW4gZWFjaCBjb2xvdXIgaW4gZWFjaCBkcmF3ZXIgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQsPFwvbGk+XHJcblx0PGxpPmNhbGN1bGF0ZXMgdGhlIHNtYWxsZXN0IHRvdGFsIG51bWJlciBvZiBnbG92ZXMgd2hpY2ggbXVzdCBiZSB0YWtlbiB0byBiZSBzdXJlIHRoYXQgYW1vbmcgdGhlbSBpdCBpcyBwb3NzaWJsZSB0byBcdWZiMDFuZCBhdCBsZWFzdCBvbmUgcGFpciBvZiBnbG92ZXMgb2YgdGhlIHNhbWUgY29sb3VyIChpdCBpcyBuZWNlc3NhcnkgdG8gc3BlY2lmeSB0aGUgZXhhY3QgbnVtYmVyIG9mIGdsb3ZlcyB0byBiZSB0YWtlbiBmcm9tIGVhY2ggZHJhd2VyKSw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDIwKSBkZXNjcmliaW5nIHRoZSBudW1iZXIgb2YgZGlzdGluY3QgY29sb3Vycy4gVGhlIGNvbG91cnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgbiBub24tbmVnYXRpdmUgaW50ZWdlcnMgMCAmbGU7IGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwuLi4gYTxzdWI+bjxcL3N1Yj4gJmxlOyAxMDxzdXA+ODxcL3N1cD4sIHdoZXJlIGE8c3ViPmk8XC9zdWI+IGNvcnJlc3BvbmRzIHRvIHRoZSBudW1iZXIgb2YgZ2xvdmVzIG9mIGNvbG91ciBudW1iZXIgaSBpbiB0aGUgZHJhd2VyIHdpdGggbGVmdCBoYW5kIGdsb3Zlcy4gRmluYWxseSwgdGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgbiBub24tbmVnYXRpdmUgaW50ZWdlcnMgMCAmbGU7IGI8c3ViPjE8XC9zdWI+LCBiPHN1Yj4yPFwvc3ViPiwuLi4sIGI8c3ViPm48XC9zdWI+ICZsZTsgMTA8c3VwPjg8XC9zdXA+LCB3aGVyZSBiPHN1Yj5pPFwvc3ViPiBjb3JyZXNwb25kcyB0byB0aGUgbnVtYmVyIG9mIGdsb3ZlcyBvZiBjb2xvdXIgbnVtYmVyIGkgaW4gdGhlIGRyYXdlciB3aXRoIHJpZ2h0IGhhbmQgZ2xvdmVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGdsb3ZlcyB3aGljaCBtdXN0IGJlIHRha2VuIGZyb20gdGhlIGRyYXdlciB3aXRoIGxlZnQgaGFuZCBnbG92ZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZ2xvdmVzIHdoaWNoIG11c3QgYmUgdGFrZW4gZnJvbSB0aGUgZHJhd2VyIHdpdGggcmlnaHQgaGFuZCBnbG92ZXMuIFRoZSBzdW0gb2YgdGhlc2UgdHdvIG51bWJlcnMgc2hvdWxkIGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBjb3JyZWN0IHJlc3VsdHMsIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 4번