시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 526 120 102 24.578%

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 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+ajxcL3N1Yj4pIFx1YzMwZFx1Yzc0NCBcdWFjODBcdWMwYWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzQgXHViNTRjLCBpJm5lO2pcdWM3NzRcdWFjZTAsIHNpemUoRjxzdWI+aTxcL3N1Yj4pICZsZTsgc2l6ZShGPHN1Yj5qPFwvc3ViPilcdWM3NzRcdWJhNzRcdWMxMWMsIHNpemUoRjxzdWI+aTxcL3N1Yj4pICZnZTsgMC45ICZ0aW1lczsgc2l6ZShGPHN1Yj5qPFwvc3ViPilcdWM3NzggXHVjMzBkXHViOWNjIFx1YWM4MFx1YzBhY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4NyBcdWFjMWNcdWM3NTggXHVjMzBkXHVjNzQ0IFx1YWM4MFx1YzBhY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MWNcdWNkOWNcdWQ1NWMgXHVjMTk0XHViOGU4XHVjMTU4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMTk0XHViOGU4XHVjMTU4IFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWQwNmNcdWFlMzAgc2l6ZShGPHN1Yj4xPFwvc3ViPiksIHNpemUoRjxzdWI+MjxcL3N1Yj4pLCAuLi4sIHNpemUoRjxzdWI+TjxcL3N1Yj4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbHQ7PU4mbHQ7PTEwMCwwMDAsIDEmbHQ7PXNpemUoRjxzdWI+aTxcL3N1Yj4pJmx0Oz0xMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM4MFx1YzBhY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBsYWdpYXJpc20iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBwYXJ0aWNpcGFudHMgb2YgdGhlIFdvcmxkIFByb2dyYW1taW5nIENvbXBldGl0aW9uIHN1Ym1pdHRlZCBOIHNvbHV0aW9uIFx1ZmIwMWxlcyBmPHN1Yj4xPFwvc3ViPiwgLi4uLCBmPHN1Yj5OPFwvc3ViPiB0byB0aGUgZ3JhZGluZyBzeXN0ZW0uIEJlZm9yZSBhY2NlcHRpbmcgdGhlIHJlc3VsdHMgYXMgXHVmYjAxbmFsLCB0aGUganVyeSB3b3VsZCBsaWtlIHRvIHJ1bGUgb3V0IGFueSBwb3NzaWJpbGl0eSBvZiBwbGFnaWFyaXNtLiBUaGV5IGhhdmUgYSBwcm9ncmFtIHRoYXQgdGFrZXMgdHdvIFx1ZmIwMWxlcyBhbmQgY29tcGFyZXMgdGhlbSB0byBkZWNpZGUgaWYgdGhleSBhcmUgdG9vIHNpbWlsYXIgdG8gZWFjaCBvdGhlci48XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgdGhlIG51bWJlciBvZiBcdWZiMDFsZXMgaXMgcmF0aGVyIGJpZyBhbmQgaXQgd291bGQgdGFrZSB0b28gbXVjaCB0aW1lIHRvIGNvbXBhcmUgYWxsIHBhaXJzLiBPbiB0aGUgb3RoZXIgaGFuZCwgbWFueSBwYWlycyBjb3VsZCBiZSBxdWlja2x5IGVsaW1pbmF0ZWQgYmFzZWQgb24gdGhlIGZhY3QgdGhhdCB0aGUgXHVmYjAxbGUgc2l6ZXMgYXJlIHRvbyBkaWZmZXJlbnQuPFwvcD5cclxuXHJcbjxwPk1vcmUgcHJlY2lzZWx5LCB0aGUganVyeSBkZWNpZGVkIHRvIGZ1bGx5IHNraXAgY29tcGFyaW5nIGV2ZXJ5IHBhaXIgd2hlcmUgdGhlIHNpemUgb2YgdGhlIHNtYWxsZXIgXHVmYjAxbGUgaXMgbGVzcyB0aGFuIDkwJSBvZiB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VyIG9uZS4gU28sIHRoZSBjb21wYXJpc29uIHByb2dyYW0gaGFzIHRvIGV4YW1pbmUgb25seSB0aG9zZSBkaXN0aW5jdCBwYWlycyBvZiBcdWZiMDFsZXMgKGY8c3ViPmk8XC9zdWI+LCBmPHN1Yj5qPFwvc3ViPikgd2hlcmUgaSAmbmU7IGosIHNpemUoZjxzdWI+aTxcL3N1Yj4pICZsZTsgc2l6ZShmPHN1Yj5qPFwvc3ViPikgYW5kIHNpemUoZjxzdWI+aTxcL3N1Yj4pICZnZTsgMC45ICZ0aW1lczsgc2l6ZShmPHN1Yj5qPFwvc3ViPikuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgXHVmYjAxbGVzIHRoYXQgd2lsbCBoYXZlIHRvIGJlIGV4YW1pbmVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2Ygc29sdXRpb24gXHVmYjAxbGVzIHN1Ym1pdHRlZC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgc2l6ZShmPHN1Yj4xPFwvc3ViPiksIC4uLixzaXplKGY8c3ViPk48XC9zdWI+KSwgZWFjaCBzaG93aW5nIHRoZSBzaXplIG9mIG9uZSBcdWZiMDFsZS4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IHNpemUoZjxzdWI+aTxcL3N1Yj4pICZsZTsgMTAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gb25lIGludGVnZXIsIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgXHVmYjAxbGVzIHRoYXQgd2lsbCBoYXZlIHRvIGJlIGV4YW1pbmVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 6번