시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 47 4 4 22.222%

문제

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

장갑엔 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개를 가져온다면 최소한 한 쌍의 같은색의 장갑이 나옴을 보장할 수 있다.

W3sicHJvYmxlbV9pZCI6IjExOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWFjMTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjI5MFx1YjBhMCBcdWQ2NTRcdWQ1NTlcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NzQgXHVkNjU0XHVkNTU5XHVjMmRjXHVhYzA0XHVjNWQwIFx1YjllOFx1YjBhMCBcdWI1MzRcdWM5ZDNcdWI5Y2MgXHVkNTU4XHViMzU4IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDAgXHVhYzAwXHVjMTFjIFx1YzJlNFx1ZDVkOCBcdWI1NGMgXHVjNGY4IFx1YzdhNVx1YWMxMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2MjRcdWI3N2NcdWFjZTAgXHVjOWMwXHVjMmRjXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YTVcdWFjMTFcdWM1ZDQgblx1YWMwMFx1YzljMCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVjNzg4XHVhY2UwIFx1YzljMFx1ZDU1OFx1YzJlNFx1YzVkMFx1YjI5NCAyXHVhYzFjXHVjNzU4IFx1ZDFiNVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVkNTVjXHVjYWJkXHVjNWQwXHViMjk0IG5cdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzY3Y1x1YzE5MFx1Y2FiZCBcdWM3YTVcdWFjMTFcdWM3NzQgXHViNGU0XHVjNWI0XHVjNzg4XHVhY2UwIFx1YjJlNFx1Yjk3OCBcdWQ1NWNcdWNhYmRcdWM1ZDBcdWIyOTQgblx1YWMwMFx1YzljMCBcdWMwYzlcdWMwYzFcdWM3NTggXHVjNjI0XHViOTc4XHVjMTkwXHVjYWJkIFx1YzdhNVx1YWMxMVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMWI1XHVjNWQwIFx1YzViNFx1YjVhNCBcdWMwYzlcdWFlNTRcdWM3NTggXHVjN2E1XHVhYzExXHVjNzc0IFx1YmE4NyBcdWFjMWNcdWFjMDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM3NDAgXHViMTA4XHViYjM0XHViMDk4XHViM2M0IFx1YWU1Y1x1YWU1Y1x1ZDU3NFx1YzExYyBcdWM3YTVcdWFjMTFcdWM3NDQgXHVhZWJjXHViMGI0XHViM2M0IFx1YzBjOVx1Yzc0NCBcdWFkNmNcdWJjYzRcdWQ1NThcdWFlMzBcdWIyOTQgXHVkNzk4XHViNGU0XHVhY2UwIFx1YzU5MVx1Y2FiZFx1Yzc1OCBcdWQxYjVcdWM1ZDBcdWMxMWMgXHVjNzg0XHVjNzU4XHViODVjIFx1YzdhNVx1YWMxMSBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWI5N2MgXHVjOWQxXHVjNWI0XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWM3YTVcdWFjMTFcdWM5MTFcdWM1ZDAgXHVkNTZkXHVjMGMxIFx1YzBjOVx1YWU1NFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjN2E1XHVhYzExXHVjNzU4IFx1YzMwZFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxY1x1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVhYzAxXHVhYzAxIFx1ZDFiNVx1YzVkMFx1YzExYyBcdWFjMDBcdWM4MzhcdWM2NDBcdWM1N2NcdWQ1NjAgXHVjN2E1XHVhYzExXHVjNzQwIFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGM5XHVhZTU0XHVjNzU4IFx1YWMwMFx1YzljMFx1YzIxOCBOKDEmbHQ7PU4mbHQ7PTIwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAgMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWFjZmMgM1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzY3Y1x1Y2FiZCBcdWQxYjVcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDFiNVx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzBjOVx1YWU1NFx1YmNjNCBcdWM3YTVcdWFjMTFcdWM3NTggXHVjMjE4KDEwXjhcdWM3NzRcdWQ1NTgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3N2NcdWNlNThcdWQ1NThcdWIyOTQgXHVjN2E1XHVhYzExXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzEgXHViZjUxXHVjNTQ0XHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDBcdWM4MzhcdWM2NDBcdWM1N2MgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM3YTVcdWFjMTFcdWM3NTggXHVjMjE4XHViOTdjIFx1YWMwMVx1YWMwMSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWM2N2NcdWNhYmQgXHVkMWI1XHVjNWQwXHVjMTFjIDJcdWFjMWMsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWQxYjVcdWM1ZDBcdWMxMWMgOFx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWM2MjhcdWIyZTRcdWJhNzQgXHVjZDVjXHVjMThjXHVkNTVjIFx1ZDU1YyBcdWMzMGRcdWM3NTggXHVhYzE5XHVjNzQwXHVjMGM5XHVjNzU4IFx1YzdhNVx1YWMxMVx1Yzc3NCBcdWIwOThcdWM2MzRcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2xvdmVzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZGFyayBiYXNlbWVudCBvZiBjaGVtaXN0cnkgcHJvZmVzc29yIEFjaWRyYWluJnJzcXVvO3MgaG91c2UgdGhlcmUgYXJlIHR3byBkcmF3ZXJzIHdpdGggZ2xvdmVzICZtZGFzaDsgb25lIHdpdGggbGVmdCBoYW5kIGFuZCBvdGhlciB3aXRoIHJpZ2h0IGhhbmQgZ2xvdmVzLiBJbiBlYWNoIG9mIHRoZW0gdGhlcmUgYXJlIGdsb3ZlcyBvZiBuIGRpXHVmYjAwZXJlbnQgY29sb3Vycy4gUHJvZmVzc29yIGtub3dzIGhvdyBtYW55IGdsb3ZlcyBvZiBlYWNoIGNvbG91ciB0aGVyZSBhcmUgaW4gZWFjaCBkcmF3ZXIgKHRoZSBudW1iZXIgb2YgZ2xvdmVzIG9mIHRoZSBzYW1lIGNvbG91ciBtYXkgZGlcdWZiMDBlciBpbiBib3RoIGRyYXdlcnMpLiBIZSBpcyBhbHNvIHN1cmUgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byBcdWZiMDFuZCBhIHBhaXIgb2YgZ2xvdmVzIG9mIHRoZSBzYW1lIGNvbG91ci48XC9wPlxyXG5cclxuPHA+UHJvZmVzc29yJnJzcXVvO3MgZXhwZXJpbWVudCBtYXkgYmUgc3VjY2Vzc2Z1bCBvbmx5IGlmIGhlIHVzZXMgZ2xvdmVzIG9mIHRoZSBzYW1lIGNvbG91ciAoaXQgZG9lcyBub3QgbWF0dGVyIHdoaWNoIG9uZSksIHNvIGJlZm9yZSBldmVyeSBleHBlcmltZW50IGhlIGdvZXMgdG8gdGhlIGJhc2VtZW50IGFuZCB0YWtlcyBnbG92ZXMgZnJvbSB0aGUgZHJhd2VycyBob3BpbmcgdGhhdCB0aGVyZSB3aWxsIGJlIGF0IGxlYXN0IG9uZSBwYWlyIG9mIHRoZSBzYW1lIGNvbG91ci4gSXQgaXMgc28gZGFyayBpbiB0aGUgYmFzZW1lbnQgdGhhdCB0aGVyZSBpcyBubyBwb3NzaWJpbGl0eSB0byByZWNvZ25pemUgY29sb3VyIG9mIGFueSBnbG92ZSB3aXRob3V0IGdvaW5nIG91dCBvZiB0aGUgYmFzZW1lbnQuIFByb2Zlc3NvciBoYXRlcyBnb2luZyB0byB0aGUgYmFzZW1lbnQgbW9yZSB0aGFuIG9uY2UgKGluIGNhc2UgdGhlcmUgd2FzIG5vIHBhaXIgb2YgZ2xvdmVzIG9mIHRoZSBzYW1lIGNvbG91ciksIGFzIHdlbGwgYXMgYnJpbmdpbmcgdW5uZWNlc3NhcmlseSBsYXJnZSBhbW91bnRzIG9mIGdsb3ZlcyB0byB0aGUgbGFib3JhdG9yeS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIG51bWJlciBvZiBjb2xvdXJzIGFuZCB0aGUgbnVtYmVyIG9mIGdsb3ZlcyBpbiBlYWNoIGNvbG91ciBpbiBlYWNoIGRyYXdlciBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgdG90YWwgbnVtYmVyIG9mIGdsb3ZlcyB3aGljaCBtdXN0IGJlIHRha2VuIHRvIGJlIHN1cmUgdGhhdCBhbW9uZyB0aGVtIGl0IGlzIHBvc3NpYmxlIHRvIFx1ZmIwMW5kIGF0IGxlYXN0IG9uZSBwYWlyIG9mIGdsb3ZlcyBvZiB0aGUgc2FtZSBjb2xvdXIgKGl0IGlzIG5lY2Vzc2FyeSB0byBzcGVjaWZ5IHRoZSBleGFjdCBudW1iZXIgb2YgZ2xvdmVzIHRvIGJlIHRha2VuIGZyb20gZWFjaCBkcmF3ZXIpLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMjApIGRlc2NyaWJpbmcgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBjb2xvdXJzLiBUaGUgY29sb3VycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBuIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyAwICZsZTsgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LC4uLiBhPHN1Yj5uPFwvc3ViPiAmbGU7IDEwPHN1cD44PFwvc3VwPiwgd2hlcmUgYTxzdWI+aTxcL3N1Yj4gY29ycmVzcG9uZHMgdG8gdGhlIG51bWJlciBvZiBnbG92ZXMgb2YgY29sb3VyIG51bWJlciBpIGluIHRoZSBkcmF3ZXIgd2l0aCBsZWZ0IGhhbmQgZ2xvdmVzLiBGaW5hbGx5LCB0aGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBuIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyAwICZsZTsgYjxzdWI+MTxcL3N1Yj4sIGI8c3ViPjI8XC9zdWI+LC4uLiwgYjxzdWI+bjxcL3N1Yj4gJmxlOyAxMDxzdXA+ODxcL3N1cD4sIHdoZXJlIGI8c3ViPmk8XC9zdWI+IGNvcnJlc3BvbmRzIHRvIHRoZSBudW1iZXIgb2YgZ2xvdmVzIG9mIGNvbG91ciBudW1iZXIgaSBpbiB0aGUgZHJhd2VyIHdpdGggcmlnaHQgaGFuZCBnbG92ZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZ2xvdmVzIHdoaWNoIG11c3QgYmUgdGFrZW4gZnJvbSB0aGUgZHJhd2VyIHdpdGggbGVmdCBoYW5kIGdsb3Zlcy48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG51bWJlciBvZiBnbG92ZXMgd2hpY2ggbXVzdCBiZSB0YWtlbiBmcm9tIHRoZSBkcmF3ZXIgd2l0aCByaWdodCBoYW5kIGdsb3Zlcy4gVGhlIHN1bSBvZiB0aGVzZSB0d28gbnVtYmVycyBzaG91bGQgYmUgYXMgc21hbGwgYXMgcG9zc2libGUuIElmIHRoZXJlIGFyZSBzZXZlcmFsIGNvcnJlY3QgcmVzdWx0cywgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgYW55IG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 4번