시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 544 124 106 24.480%

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세"는 1등 상품으로 페라리를 걸고 프로그래밍 대회를 개최했다. 이 대회의 참석자는 총 N명이고 각각 솔루션 파일 1개를 제출했다. 이 솔루션 파일을 F1, F2, ..., Fn이라고 한다.

채점 결과를 발표하기 전에, 남의 것을 배낀 사람이 있는지 찾아내려고 한다. 이 대회의 주최측은 두 파일을 비교해서 너무 비슷한지 아닌지 판별하는 프로그램이 있다.

하지만, 제출한 파일의 개수가 너무 많아서, 모든 쌍을 검사한다면, 2012년 지구가 멸망할 때 까지도 검사를 해야할 판이다. 따라서, 파일 크기가 너무 다른 경우에는 그러한 쌍을 검사하지 않고 넘어가기로 했다.

좀더 정확하게 하기 위해서, 대회의 심판들은 두 파일이 있을 때, 작은 파일의 크기가 큰 파일 크기의 90%보다도 작을 때는, 이러한 쌍은 검사하지 않고 넘어가기로 했다. 따라서, (Fi, Fj) 쌍을 검사해야 하는데, 이때, i≠j이고, size(Fi) ≤ size(Fj)이면서, size(Fi) ≥ 0.9 × size(Fj)인 쌍만 검사하려고 한다.

몇 개의 쌍을 검사해야 하는 지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1<=N<=100,000, 1<=size(Fi)<=100,000,000)

출력

첫째 줄에 검사해야 하는 파일의 개수를 출력한다.

예제 입력 1

5
1 1 1 1 1

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjI0MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0NWNcdWM4MDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzOFx1YWNjNFx1YzgwMVx1Yzc3OCBcdWMxMWRcdWM3MjAgXHVjN2FjXHViYzhjICZxdW90O1x1YWRkY1x1ZDYwNCBcdWM4NzAgXHVjNTU1XHViNDU4IFx1ZDJmMFx1ZDA2Y1x1YjlhY1x1ZDJmMCBcdWM1NDhcdWI0ZGNcdWI4MDhcdWMyYTQgXHVkNmM0XHVjMTM4XHVjNzc4IFx1YjlhY1x1YzYyNFx1YjEyYyBcdWMxOTRcdWI4MDhcdWI5NzQgXHVjMGI0XHViNzdjIFx1YjljOFx1YjlhY1x1YzZiMCBcdWI0NTBcdWMyYTQgXHVjMGIwXHVkMjJjXHVjMmE0IFx1ZDNhMFx1YjlhY1x1YzJhNCBcdWJlNDggXHVjNzkwXHVjNzc0XHViNGRjIFx1YzIyMFx1ZDBjNCBcdWNlNWNcdWIwOThcdWM2NTMgXHViYzQ1XHVhYzcwIDdcdWMxMzgmcXVvdDtcdWIyOTQgMVx1YjRmMSBcdWMwYzFcdWQ0ODhcdWM3M2NcdWI4NWMgXHVkMzk4XHViNzdjXHViOWFjXHViOTdjIFx1YWM3OFx1YWNlMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YjMwMFx1ZDY4Y1x1Yzc1OCBcdWNjMzhcdWMxMWRcdWM3OTBcdWIyOTQgXHVjZDFkIE5cdWJhODVcdWM3NzRcdWFjZTAgXHVhYzAxXHVhYzAxIFx1YzE5NFx1YjhlOFx1YzE1OCBcdWQzMGNcdWM3N2MgMVx1YWMxY1x1Yjk3YyBcdWM4MWNcdWNkOWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWMxOTRcdWI4ZThcdWMxNTggXHVkMzBjXHVjNzdjXHVjNzQ0IEY8c3ViPjE8XC9zdWI+LCBGPHN1Yj4yPFwvc3ViPiwgLi4uLCBGPHN1Yj5uPFwvc3ViPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M0NFx1YzgxMCBcdWFjYjBcdWFjZmNcdWI5N2MgXHViYzFjXHVkNDVjXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHViMGE4XHVjNzU4IFx1YWM4M1x1Yzc0NCBcdWJjMzBcdWIwODAgXHVjMGFjXHViNzhjXHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNjM2VcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YzhmY1x1Y2Q1Y1x1Y2UyMVx1Yzc0MCBcdWI0NTAgXHVkMzBjXHVjNzdjXHVjNzQ0IFx1YmU0NFx1YWQ1MFx1ZDU3NFx1YzExYyBcdWIxMDhcdWJiMzQgXHViZTQ0XHVjMmI3XHVkNTVjXHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMCBcdWQzMTBcdWJjYzRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM4MWNcdWNkOWNcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNTQ0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVjMzBkXHVjNzQ0IFx1YWM4MFx1YzBhY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgMjAxMlx1YjE0NCBcdWM5YzBcdWFkNmNcdWFjMDAgXHViYTc4XHViOWRkXHVkNTYwIFx1YjU0YyBcdWFlNGNcdWM5YzBcdWIzYzQgXHVhYzgwXHVjMGFjXHViOTdjIFx1ZDU3NFx1YzU3Y1x1ZDU2MCBcdWQzMTBcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVkMzBjXHVjNzdjIFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViMmU0XHViOTc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjMzBkXHVjNzQ0IFx1YWM4MFx1YzBhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMTE4XHVjNWI0XHVhYzAwXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODgwXHViMzU0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWIzMDBcdWQ2OGNcdWM3NTggXHVjMmVjXHVkMzEwXHViNGU0XHVjNzQwIFx1YjQ1MCBcdWQzMGNcdWM3N2NcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNzkxXHVjNzQwIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVkMDcwIFx1ZDMwY1x1Yzc3YyBcdWQwNmNcdWFlMzBcdWM3NTggOTAlXHViY2Y0XHViMmU0XHViM2M0IFx1Yzc5MVx1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMzMGRcdWM3NDAgXHVhYzgwXHVjMGFjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWIxMThcdWM1YjRcdWFjMDBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIChGPHN1Yj5pPFwvc3ViPiwgRjxzdWI+ajxcL3N1Yj4pIFx1YzMwZFx1Yzc0NCBcdWFjODBcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI1NGMsIGkmbmU7alx1Yzc3NFx1YWNlMCwgc2l6ZShGPHN1Yj5pPFwvc3ViPikgJmxlOyBzaXplKEY8c3ViPmo8XC9zdWI+KVx1Yzc3NFx1YmE3NFx1YzExYywgc2l6ZShGPHN1Yj5pPFwvc3ViPikgJmdlOyAwLjkgJnRpbWVzOyBzaXplKEY8c3ViPmo8XC9zdWI+KVx1Yzc3OCBcdWMzMGRcdWI5Y2MgXHVhYzgwXHVjMGFjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMzMGRcdWM3NDQgXHVhYzgwXHVjMGFjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxY1x1Y2Q5Y1x1ZDU1YyBcdWMxOTRcdWI4ZThcdWMxNThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMxOTRcdWI4ZThcdWMxNTggXHVkMzBjXHVjNzdjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBzaXplKEY8c3ViPjE8XC9zdWI+KSwgc2l6ZShGPHN1Yj4yPFwvc3ViPiksIC4uLiwgc2l6ZShGPHN1Yj5OPFwvc3ViPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9TiZsdDs9MTAwLDAwMCwgMSZsdDs9c2l6ZShGPHN1Yj5pPFwvc3ViPikmbHQ7PTEwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzgwXHVjMGFjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGxhZ2lhcmlzbSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHBhcnRpY2lwYW50cyBvZiB0aGUgV29ybGQgUHJvZ3JhbW1pbmcgQ29tcGV0aXRpb24gc3VibWl0dGVkIE4gc29sdXRpb24gXHVmYjAxbGVzIGY8c3ViPjE8XC9zdWI+LCAuLi4sIGY8c3ViPk48XC9zdWI+IHRvIHRoZSBncmFkaW5nIHN5c3RlbS4gQmVmb3JlIGFjY2VwdGluZyB0aGUgcmVzdWx0cyBhcyBcdWZiMDFuYWwsIHRoZSBqdXJ5IHdvdWxkIGxpa2UgdG8gcnVsZSBvdXQgYW55IHBvc3NpYmlsaXR5IG9mIHBsYWdpYXJpc20uIFRoZXkgaGF2ZSBhIHByb2dyYW0gdGhhdCB0YWtlcyB0d28gXHVmYjAxbGVzIGFuZCBjb21wYXJlcyB0aGVtIHRvIGRlY2lkZSBpZiB0aGV5IGFyZSB0b28gc2ltaWxhciB0byBlYWNoIG90aGVyLjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGUgbnVtYmVyIG9mIFx1ZmIwMWxlcyBpcyByYXRoZXIgYmlnIGFuZCBpdCB3b3VsZCB0YWtlIHRvbyBtdWNoIHRpbWUgdG8gY29tcGFyZSBhbGwgcGFpcnMuIE9uIHRoZSBvdGhlciBoYW5kLCBtYW55IHBhaXJzIGNvdWxkIGJlIHF1aWNrbHkgZWxpbWluYXRlZCBiYXNlZCBvbiB0aGUgZmFjdCB0aGF0IHRoZSBcdWZiMDFsZSBzaXplcyBhcmUgdG9vIGRpZmZlcmVudC48XC9wPlxyXG5cclxuPHA+TW9yZSBwcmVjaXNlbHksIHRoZSBqdXJ5IGRlY2lkZWQgdG8gZnVsbHkgc2tpcCBjb21wYXJpbmcgZXZlcnkgcGFpciB3aGVyZSB0aGUgc2l6ZSBvZiB0aGUgc21hbGxlciBcdWZiMDFsZSBpcyBsZXNzIHRoYW4gOTAlIG9mIHRoZSBzaXplIG9mIHRoZSBsYXJnZXIgb25lLiBTbywgdGhlIGNvbXBhcmlzb24gcHJvZ3JhbSBoYXMgdG8gZXhhbWluZSBvbmx5IHRob3NlIGRpc3RpbmN0IHBhaXJzIG9mIFx1ZmIwMWxlcyAoZjxzdWI+aTxcL3N1Yj4sIGY8c3ViPmo8XC9zdWI+KSB3aGVyZSBpICZuZTsgaiwgc2l6ZShmPHN1Yj5pPFwvc3ViPikgJmxlOyBzaXplKGY8c3ViPmo8XC9zdWI+KSBhbmQgc2l6ZShmPHN1Yj5pPFwvc3ViPikgJmdlOyAwLjkgJnRpbWVzOyBzaXplKGY8c3ViPmo8XC9zdWI+KS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgdGhlIG51bWJlciBvZiBwYWlycyBvZiBcdWZiMDFsZXMgdGhhdCB3aWxsIGhhdmUgdG8gYmUgZXhhbWluZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiwgdGhlIG51bWJlciBvZiBzb2x1dGlvbiBcdWZiMDFsZXMgc3VibWl0dGVkLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBzaXplKGY8c3ViPjE8XC9zdWI+KSwgLi4uLHNpemUoZjxzdWI+TjxcL3N1Yj4pLCBlYWNoIHNob3dpbmcgdGhlIHNpemUgb2Ygb25lIFx1ZmIwMWxlLiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgc2l6ZShmPHN1Yj5pPFwvc3ViPikgJmxlOyAxMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiBvbmUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBwYWlycyBvZiBcdWZiMDFsZXMgdGhhdCB3aWxsIGhhdmUgdG8gYmUgZXhhbWluZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 6번