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

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4
0 7 1 6
1 5 0 6

예제 출력 1

2
8

힌트

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

W3sicHJvYmxlbV9pZCI6IjExOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWFjMTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjI5MCBcdWIwYTAgXHVkNjU0XHVkNTU5XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1ZDY1NFx1ZDU1OVx1YzJkY1x1YWMwNFx1YzVkMCBcdWI5ZThcdWIwYTAgXHViNTM0XHVjOWQzXHViOWNjIFx1ZDU1OFx1YjM1OCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNWQwIFx1YWMwMFx1YzExYyBcdWMyZTRcdWQ1ZDggXHViNTRjIFx1YzRmOCBcdWM3YTVcdWFjMTFcdWM3NDQgXHVhYzAwXHVjODM4XHVjNjI0XHViNzdjXHVhY2UwIFx1YzljMFx1YzJkY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2E1XHVhYzExXHVjNWQ0IG5cdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzc0IFx1Yzc4OFx1YWNlMCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDBcdWIyOTQgMlx1YWMxY1x1Yzc1OCBcdWQxYjVcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwIFx1ZDU1Y1x1Y2FiZFx1YzVkMFx1YjI5NCBuXHVhYzAwXHVjOWMwIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWM2N2NcdWMxOTBcdWNhYmQgXHVjN2E1XHVhYzExXHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YWNlMCBcdWIyZTRcdWI5NzggXHVkNTVjXHVjYWJkXHVjNWQwXHViMjk0IG5cdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzYyNFx1Yjk3OFx1YzE5MFx1Y2FiZCBcdWM3YTVcdWFjMTFcdWM3NzQgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDFiNVx1YzVkMCBcdWM1YjRcdWI1YTQgXHVjMGM5XHVhZTU0XHVjNzU4IFx1YzdhNVx1YWMxMVx1Yzc3NCBcdWJhODcgXHVhYzFjXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNzQwIFx1YjEwOFx1YmIzNFx1YjA5OFx1YjNjNCBcdWFlNWNcdWFlNWNcdWQ1NzRcdWMxMWMgXHVjN2E1XHVhYzExXHVjNzQ0IFx1YWViY1x1YjBiNFx1YjNjNCBcdWMwYzlcdWM3NDQgXHVhZDZjXHViY2M0XHVkNTU4XHVhZTMwXHViMjk0IFx1ZDc5OFx1YjRlNFx1YWNlMCBcdWM1OTFcdWNhYmRcdWM3NTggXHVkMWI1XHVjNWQwXHVjMTFjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWM3YTVcdWFjMTEgXHVjNWVjXHViN2VjXHVhYzFjXHViOTdjIFx1YzlkMVx1YzViNFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVjN2E1XHVhYzExXHVjOTExXHVjNWQwIFx1ZDU2ZFx1YzBjMSBcdWMwYzlcdWFlNTRcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzdhNVx1YWMxMVx1Yzc1OCBcdWMzMGRcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWFjMWNcdWM3NzRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWMwMVx1YWMwMSBcdWQxYjVcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjODM4XHVjNjQwXHVjNTdjXHVkNTYwIFx1YzdhNVx1YWMxMVx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWFjMDBcdWM5YzBcdWMyMTggTigxICZsZTsgTiAmbGU7IDIwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAgMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWFjZmMgM1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzY3Y1x1Y2FiZCBcdWQxYjVcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDFiNVx1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzBjOVx1YWU1NFx1YmNjNCBcdWM3YTVcdWFjMTFcdWM3NTggXHVjMjE4KDEwPHN1cD44PFwvc3VwPlx1Yzc3NFx1ZDU1OClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YjI5NCBcdWM3YTVcdWFjMTFcdWM3NDQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWJmNTFcdWM1NDRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWMwMFx1YzgzOFx1YzY0MFx1YzU3YyBcdWI0MThcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzdhNVx1YWMxMVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhYzAxXHVhYzAxIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzg0XHVjNzU4XHViODVjIFx1YzY3Y1x1Y2FiZCBcdWQxYjVcdWM1ZDBcdWMxMWMgMlx1YWMxYywgXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDFiNVx1YzVkMFx1YzExYyA4XHVhYzFjXHViOTdjIFx1YWMwMFx1YzgzOFx1YzYyOFx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGNcdWQ1NWMgXHVkNTVjIFx1YzMwZFx1Yzc1OCBcdWFjMTlcdWM3NDBcdWMwYzlcdWM3NTggXHVjN2E1XHVhYzExXHVjNzc0IFx1YjA5OFx1YzYzNFx1Yzc0NCBcdWJjZjRcdWM3YTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExOTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHbG92ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBkYXJrIGJhc2VtZW50IG9mIGNoZW1pc3RyeSBwcm9mZXNzb3IgQWNpZHJhaW4mcnNxdW87cyBob3VzZSB0aGVyZSBhcmUgdHdvIGRyYXdlcnMgd2l0aCBnbG92ZXMgJm1kYXNoOyBvbmUgd2l0aCBsZWZ0IGhhbmQgYW5kIG90aGVyIHdpdGggcmlnaHQgaGFuZCBnbG92ZXMuIEluIGVhY2ggb2YgdGhlbSB0aGVyZSBhcmUgZ2xvdmVzIG9mIG4gZGlcdWZiMDBlcmVudCBjb2xvdXJzLiBQcm9mZXNzb3Iga25vd3MgaG93IG1hbnkgZ2xvdmVzIG9mIGVhY2ggY29sb3VyIHRoZXJlIGFyZSBpbiBlYWNoIGRyYXdlciAodGhlIG51bWJlciBvZiBnbG92ZXMgb2YgdGhlIHNhbWUgY29sb3VyIG1heSBkaVx1ZmIwMGVyIGluIGJvdGggZHJhd2VycykuIEhlIGlzIGFsc28gc3VyZSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIFx1ZmIwMW5kIGEgcGFpciBvZiBnbG92ZXMgb2YgdGhlIHNhbWUgY29sb3VyLjxcL3A+XHJcblxyXG48cD5Qcm9mZXNzb3ImcnNxdW87cyBleHBlcmltZW50IG1heSBiZSBzdWNjZXNzZnVsIG9ubHkgaWYgaGUgdXNlcyBnbG92ZXMgb2YgdGhlIHNhbWUgY29sb3VyIChpdCBkb2VzIG5vdCBtYXR0ZXIgd2hpY2ggb25lKSwgc28gYmVmb3JlIGV2ZXJ5IGV4cGVyaW1lbnQgaGUgZ29lcyB0byB0aGUgYmFzZW1lbnQgYW5kIHRha2VzIGdsb3ZlcyBmcm9tIHRoZSBkcmF3ZXJzIGhvcGluZyB0aGF0IHRoZXJlIHdpbGwgYmUgYXQgbGVhc3Qgb25lIHBhaXIgb2YgdGhlIHNhbWUgY29sb3VyLiBJdCBpcyBzbyBkYXJrIGluIHRoZSBiYXNlbWVudCB0aGF0IHRoZXJlIGlzIG5vIHBvc3NpYmlsaXR5IHRvIHJlY29nbml6ZSBjb2xvdXIgb2YgYW55IGdsb3ZlIHdpdGhvdXQgZ29pbmcgb3V0IG9mIHRoZSBiYXNlbWVudC4gUHJvZmVzc29yIGhhdGVzIGdvaW5nIHRvIHRoZSBiYXNlbWVudCBtb3JlIHRoYW4gb25jZSAoaW4gY2FzZSB0aGVyZSB3YXMgbm8gcGFpciBvZiBnbG92ZXMgb2YgdGhlIHNhbWUgY29sb3VyKSwgYXMgd2VsbCBhcyBicmluZ2luZyB1bm5lY2Vzc2FyaWx5IGxhcmdlIGFtb3VudHMgb2YgZ2xvdmVzIHRvIHRoZSBsYWJvcmF0b3J5LjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgbnVtYmVyIG9mIGNvbG91cnMgYW5kIHRoZSBudW1iZXIgb2YgZ2xvdmVzIGluIGVhY2ggY29sb3VyIGluIGVhY2ggZHJhd2VyIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5jYWxjdWxhdGVzIHRoZSBzbWFsbGVzdCB0b3RhbCBudW1iZXIgb2YgZ2xvdmVzIHdoaWNoIG11c3QgYmUgdGFrZW4gdG8gYmUgc3VyZSB0aGF0IGFtb25nIHRoZW0gaXQgaXMgcG9zc2libGUgdG8gXHVmYjAxbmQgYXQgbGVhc3Qgb25lIHBhaXIgb2YgZ2xvdmVzIG9mIHRoZSBzYW1lIGNvbG91ciAoaXQgaXMgbmVjZXNzYXJ5IHRvIHNwZWNpZnkgdGhlIGV4YWN0IG51bWJlciBvZiBnbG92ZXMgdG8gYmUgdGFrZW4gZnJvbSBlYWNoIGRyYXdlciksPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIHBvc2l0aXZlIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyMCkgZGVzY3JpYmluZyB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IGNvbG91cnMuIFRoZSBjb2xvdXJzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gVGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG4gbm9uLW5lZ2F0aXZlIGludGVnZXJzIDAgJmxlOyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sLi4uIGE8c3ViPm48XC9zdWI+ICZsZTsgMTA8c3VwPjg8XC9zdXA+LCB3aGVyZSBhPHN1Yj5pPFwvc3ViPiBjb3JyZXNwb25kcyB0byB0aGUgbnVtYmVyIG9mIGdsb3ZlcyBvZiBjb2xvdXIgbnVtYmVyIGkgaW4gdGhlIGRyYXdlciB3aXRoIGxlZnQgaGFuZCBnbG92ZXMuIEZpbmFsbHksIHRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG4gbm9uLW5lZ2F0aXZlIGludGVnZXJzIDAgJmxlOyBiPHN1Yj4xPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sLi4uLCBiPHN1Yj5uPFwvc3ViPiAmbGU7IDEwPHN1cD44PFwvc3VwPiwgd2hlcmUgYjxzdWI+aTxcL3N1Yj4gY29ycmVzcG9uZHMgdG8gdGhlIG51bWJlciBvZiBnbG92ZXMgb2YgY29sb3VyIG51bWJlciBpIGluIHRoZSBkcmF3ZXIgd2l0aCByaWdodCBoYW5kIGdsb3Zlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG51bWJlciBvZiBnbG92ZXMgd2hpY2ggbXVzdCBiZSB0YWtlbiBmcm9tIHRoZSBkcmF3ZXIgd2l0aCBsZWZ0IGhhbmQgZ2xvdmVzLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGdsb3ZlcyB3aGljaCBtdXN0IGJlIHRha2VuIGZyb20gdGhlIGRyYXdlciB3aXRoIHJpZ2h0IGhhbmQgZ2xvdmVzLiBUaGUgc3VtIG9mIHRoZXNlIHR3byBudW1iZXJzIHNob3VsZCBiZSBhcyBzbWFsbCBhcyBwb3NzaWJsZS4gSWYgdGhlcmUgYXJlIHNldmVyYWwgY29ycmVjdCByZXN1bHRzLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 6번