시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 398 125 96 39.506%

문제

N명의 사람이 원판 테이블에 앉아서 콜라를 마시고 있다. 그 상황에서 두 사람이 짝을 지어서 건배를 하려 한다. 그런데 이들은 건배를 할 때, 보기 좋게 하기 위하여 마시고 있는 콜라의 브랜드가 같은 경우에만 건배를 할 수 있다고 한다. 그리고 사람들이 동시에 건배를 할 때, 사람들의 팔이 서로 엇갈리는 경우에는 건배를 할 수 없다고 한다.

예를 들어 왼쪽 그림과 같은 경우는 겹치는 경우가 없어 건배를 할 수 있으나 오른쪽과 같은 경우에는 건배를 할 수 없다. 사람의 수 N과 각각의 사람이 마시는 콜라의 브랜드가 주어져 있을 때, 동시에 건배를 할 수 있는 가장 많은 쌍의 개수를 출력하시오.

입력

첫 줄에 사람의 수 (1 ≤ N ≤ 1000) 이 주어진다. 그리고 둘째 줄에 N개의 정수(1 이상 100 이하)가 공백을 사이에 두고 주어지는데 이는 각각의 사람이 마시는 콜라의 브랜드이다. (시계방향순서대로 주어진다)

출력

동시에 건배를 할 수 있는 가장 많은 쌍의 개수를 출력한다.

예제 입력 1

22
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzRcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzZkMFx1ZDMxMCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM1ZDAgXHVjNTQ5XHVjNTQ0XHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWI5YzhcdWMyZGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjggXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjOWRkXHVjNzQ0IFx1YzljMFx1YzViNFx1YzExYyBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YjU0YywgXHViY2Y0XHVhZTMwIFx1Yzg4Ylx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTU4XHVjNWVjIFx1YjljOFx1YzJkY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHViNTRjLCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVkMzE0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM1YzdcdWFjMDhcdWI5YWNcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTQ2XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2diLnBuZ1wiIHdpZHRoPVwiMzI2XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWM2XHVjNWI0IFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjA5OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YjljOFx1YzJkY1x1YjI5NCBcdWNmNWNcdWI3N2NcdWM3NTggXHViZTBjXHViNzljXHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzc0XHViYzMwXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggKDEgJmxlOyBOICZsZTsgMTAwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTgoMSBcdWM3NzRcdWMwYzEgMTAwIFx1Yzc3NFx1ZDU1OClcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YjljOFx1YzJkY1x1YjI5NCBcdWNmNWNcdWI3N2NcdWM3NTggXHViZTBjXHViNzljXHViNGRjXHVjNzc0XHViMmU0LiAoXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzc0XHViYzMwXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTk3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBCYXZhcmlhbiBCZWVyIFBhcnR5IiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgcHJvZmVzc29ycyBvZiB0aGUgQmF5ZXJpc2NoZSBNYXRoZW1hdGlrZXIgVmVyZWluIGhhdmUgdGhlaXIgYW5udWFsIHBhcnR5IGluIHRoZSBsb2NhbCBCaWVyZ2FydGVuLiBUaGV5IGFyZSBzaXR0aW5nIGF0IGEgcm91bmQgdGFibGUgZWFjaCB3aXRoIGhpcyBvd24gcGludCBvZiBiZWVyLiBBcyBhIGNlcmVtb255IGVhY2ggcHJvZmVzc29yIHJhaXNlcyBoaXMgcGludCBhbmQgdG9hc3RzIG9uZSBvZiB0aGUgb3RoZXIgZ3Vlc3RzIGluIHN1Y2ggYSB3YXkgdGhhdCBubyBhcm1zIGNyb3NzLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JlZXIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA3cHg7IHdpZHRoOjI0MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAyOiBUb2FzdGluZyBhY3Jvc3MgYSB0YWJsZSB3aXRoIGVpZ2h0IHBlcnNvbnM6bm8gYXJtcyBjcm9zc2luZyhsZWZ0KSwgYXJtcyBjcm9zc2luZyhyaWdodCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Uga25vdyB0aGF0IHRoZSBwcm9mZXNzb3JzIGxpa2UgdG8gdG9hc3Qgd2l0aCBzb21lb25lIHRoYXQgaXMgZHJpbmtpbmcgdGhlIHNhbWUgYnJhbmQgb2YgYmVlciwgYW5kIHdlIGxpa2UgdG8gbWF4aW1pemUgdGhlIG51bWJlciBvZiBwYWlycyBvZiBwcm9mZXNzb3JzIHRvYXN0aW5nIHdpdGggdGhlIHNhbWUgYnJhbmQgLCBhZ2FpbiB3aXRob3V0IGNyb3NzaW5nIGFybXMuIFdyaXRlIGFuIGFsZ29yaXRobSB0byBkbyB0aGlzLCBrZWVwaW5nIGluIG1pbmQgdGhhdCBldmVyeSBwcm9mZXNzb3Igc2hvdWxkIHRha2UgcGFydCBpbiB0aGUgdG9hc3RpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZnJpc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBoYXMgdGhlIGZvbGxvd2luZyBmb3JtYXQ6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBldmVuIG51bWJlciBwLCBzYXRpc2Z5aW5nIDIgJmxlOyBwICZsZTsgMTAwMDogdGhlIG51bWJlciBvZiBwYXJ0aWNpcGFudHMmbmJzcDs8XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBwIGludGVnZXJzIChzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcykgaW5kaWNhdGluZyB0aGUgYmVlciBicmFuZHMgZnJvIHRoZSBjb25zZWN1dGl2ZSBwcm9mZXNzb3JzKCBpbiBjbG9ja3dpc2Ugb3JkZXIsIHN0YXJ0aW5nIGF0IGFuIGFyYml0cmFyeSBwb3NpdGlvbikuIEVhY2ggdmFsdWUgaXMgYmV0d2VlbiAxIGFuZCAxMDAgKGJvdWRhcmllcyBpbmNsdWRlZCkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIgb24gYSBzaW5nbGUgbGluZTogdGhlIG1heGltdW0gbnVtYmVyIG9mIG5vbi1pbnRlcnNlY3RpbmcgdG9hc3RzIG9mIHRoZSBzYW1lIGJlZXIgYnJhbmQgZm9yIHRoaXMgdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2006 E번

  • 잘못된 조건을 찾은 사람: Apple_Cplus
  • 데이터를 추가한 사람: cgiosy