시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB66754058359061.003%

문제

닭이 길을 건너간 이유는 과학적으로 깊게 연구가 되어 있지만, 의외로 소가 길을 건너간 이유는 거의 연구된 적이 없다. 이 주제에 관심을 가지고 있었던 농부 존은 한 대학으로부터 소가 길을 건너는 이유에 대한 연구 제의를 받게 되었다.

존이 할 일은 소가 길을 건너는 것을 관찰하는 것이다. 존은 소의 위치를 N번 관찰하는데, 각 관찰은 소의 번호와 소의 위치 하나씩으로 이루어져 있다. 존은 소를 10마리 가지고 있으므로 소의 번호는 1 이상 10 이하의 정수고, 소의 위치는 길의 왼쪽과 오른쪽을 의미하는 0과 1 중 하나다.

이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.

입력

첫 줄에 관찰 횟수 N이 주어진다. N은 100 이하의 양의 정수이다. 다음 N줄에는 한 줄에 하나씩 관찰 결과가 주어진다. 관찰 결과는 소의 번호와 위치(0 또는 1)로 이루어져 있다.

출력

첫 줄에 소가 길을 건너간 최소 횟수를 출력한다.

예제 입력 1

8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 1

예제 출력 1

3

힌트

3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다.

W3sicHJvYmxlbV9pZCI6IjE0NDY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlZFx1Yzc3NCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHVhYzA0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWFjZmNcdWQ1NTlcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZTRhXHVhYzhjIFx1YzVmMFx1YWQ2Y1x1YWMwMCBcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM3NThcdWM2NzhcdWI4NWMgXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwXHViMjk0IFx1YWM3MFx1Yzc1OCBcdWM1ZjBcdWFkNmNcdWI0MWMgXHVjODAxXHVjNzc0IFx1YzVjNlx1YjJlNC4gXHVjNzc0IFx1YzhmY1x1YzgxY1x1YzVkMCBcdWFkMDBcdWMyZWNcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjM1OCBcdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1ZDU1YyBcdWIzMDBcdWQ1NTlcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVjNzc0XHVjNzIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM1ZjBcdWFkNmMgXHVjODFjXHVjNzU4XHViOTdjIFx1YmMxYlx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc3NCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWFkMDBcdWNjMzBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM4NzRcdWM3NDAgXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBOXHViYzg4IFx1YWQwMFx1Y2MzMFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVhYzAxIFx1YWQwMFx1Y2MzMFx1Yzc0MCBcdWMxOGNcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzE4Y1x1Yzc1OCBcdWM3MDRcdWNlNTggXHVkNTU4XHViMDk4XHVjNTI5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzg3NFx1Yzc0MCBcdWMxOGNcdWI5N2MgMTBcdWI5YzhcdWI5YWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWMxOGNcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjZTAsIFx1YzE4Y1x1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YWNmYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IDBcdWFjZmMgMSBcdWM5MTEgXHVkNTU4XHViMDk4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhZDAwXHVjYzMwIFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMThjXHVhYzAwIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4IFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMWNcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHVjNzkwLiBcdWM5ODkgXHVhYzE5XHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWMxOGNcdWFjMDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiYyBcdWFjODNcdWM3NzQgXHViYTg3IFx1YmM4OFx1Yzc3OFx1YzljMCBcdWMxMzhcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFkMDBcdWNjMzAgXHVkNjlmXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIDEwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhZDAwXHVjYzMwIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWQwMFx1Y2MzMCBcdWFjYjBcdWFjZmNcdWIyOTQgXHVjMThjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM3MDRcdWNlNTgoMCBcdWI2MTBcdWIyOTQgMSlcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHVhYzA0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4zXHViYzg4IFx1YzE4Y1x1YjI5NCBcdWM3MDRcdWNlNTggMSwgMCwgMVx1YzVkMFx1YzExYyBcdWFkMDBcdWNjMzBcdWI0MThcdWM1YzhcdWM3M2NcdWJiYzBcdWI4NWMgXHVhZTM4XHVjNzQ0IFx1Y2Q1Y1x1YzE4YyBcdWI0NTAgXHViYzg4IFx1YWM3NFx1YjExY1x1Yzc0Y1x1Yzc0NCBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gNFx1YmM4OCBcdWMxOGNcdWIzYzQgXHVhZTM4XHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVhYzc0XHViMTFjXHVjNzNjXHViYTcwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjMThjXHViMjk0IFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMGMgXHVhZTMwXHViODVkXHVjNzc0IFx1ZDY1NVx1Yzc3OFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNDQ2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCAoQnJvbnplKSIsImRlc2NyaXB0aW9uIjoiPHA+V2hpbGUgdGhlIGFnZS1vbGQgcXVlc3Rpb24gb2Ygd2h5IGNoaWNrZW5zIGNyb3NzIHJvYWRzIGhhcyBiZWVuIGFkZHJlc3NlZCBpbiBncmVhdCBkZXB0aCBieSB0aGUgc2NpZW50aWZpYyBjb21tdW5pdHksIHN1cnByaXNpbmdseSBsaXR0bGUgaGFzIGJlZW4gcHVibGlzaGVkIGluIHRoZSByZXNlYXJjaCBsaXRlcmF0dXJlIG9uIHRoZSByZWxhdGVkIHN1YmplY3Qgb2YgY293IGNyb3NzaW5ncy4gRmFybWVyIEpvaG4sIHdlbGwtYXdhcmUgb2YgdGhlIGltcG9ydGFuY2Ugb2YgdGhpcyBpc3N1ZSwgaXMgdGhyaWxsZWQgd2hlbiBoZSBpcyBjb250YWN0ZWQgYnkgYSBsb2NhbCB1bml2ZXJzaXR5IGFza2luZyBmb3IgaGlzIGFzc2lzdGFuY2UgaW4gY29uZHVjdGluZyBhIHNjaWVudGlmaWMgc3R1ZHkgb2Ygd2h5IGNvd3MgY3Jvc3Mgcm9hZHMuIEhlIGVhZ2VybHkgdm9sdW50ZWVycyB0byBoZWxwLjxcL3A+XHJcblxyXG48cD5BcyBwYXJ0IG9mIHRoZSBzdHVkeSwgRmFybWVyIEpvaG4gaGFzIGJlZW4gYXNrZWQgdG8gZG9jdW1lbnQgdGhlIG51bWJlciBvZiB0aW1lcyBlYWNoIG9mIGhpcyBjb3dzIGNyb3NzZXMgdGhlIHJvYWQuIEhlIGNhcmVmdWxseSBsb2dzIGRhdGEgYWJvdXQgaGlzIGNvd3MmIzM5OyBsb2NhdGlvbnMsIG1ha2luZyBhIHNlcmllcyBvZiZuYnNwO04mbmJzcDtvYnNlcnZhdGlvbnMgb3ZlciB0aGUgY291cnNlIG9mIGEgc2luZ2xlIGRheS4gRWFjaCBvYnNlcnZhdGlvbiByZWNvcmRzIHRoZSBJRCBudW1iZXIgb2YgYSBjb3cgKGFuIGludGVnZXIgaW4gdGhlIHJhbmdlJm5ic3A7MSZoZWxsaXA7MTAsIHNpbmNlIEZhcm1lciBKb2huIGhhcyAxMCBjb3dzKSwgYXMgd2VsbCBhcyB3aGljaCBzaWRlIG9mIHRoZSByb2FkIHRoZSBjb3cgaXMgb24uPFwvcD5cclxuXHJcbjxwPkJhc2VkIG9uIHRoZSBkYXRhIHJlY29yZGVkIGJ5IEZhcm1lciBKb2huLCBwbGVhc2UgaGVscCBoaW0gY291bnQgdGhlIHRvdGFsIG51bWJlciBvZiBjb25maXJtZWQgY3Jvc3NpbmdzLiBBIGNvbmZpcm1lZCBjcm9zc2luZyBvY2N1cnMgd2hlbiBhIGNvbnNlY3V0aXZlIHNpZ2h0aW5ncyBvZiBhIGNvdyBwbGFjZSBpdCBvbiBkaWZmZXJlbnQgc2lkZXMgb2YgdGhlIHJvYWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucywmbmJzcDtOLCBhIHBvc2l0aXZlIGludGVnZXIgYXQgbW9zdCAxMDAuIEVhY2ggb2YgdGhlIG5leHQmbmJzcDtOJm5ic3A7bGluZXMgY29udGFpbnMgb25lIG9ic2VydmF0aW9uLCBhbmQgY29uc2lzdHMgb2YgYSBjb3cgSUQgbnVtYmVyIGZvbGxvd2VkIGJ5IGl0cyBwb3NpdGlvbiBpbmRpY2F0ZWQgYnkgZWl0aGVyIHplcm8gb3Igb25lICh6ZXJvIGZvciBvbmUgc2lkZSBvZiB0aGUgcm9hZCwgb25lIGZvciB0aGUgb3RoZXIgc2lkZSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGxlYXNlIGNvbXB1dGUgdGhlIHRvdGFsIG51bWJlciBvZiBjb25maXJtZWQgY3Jvc3NpbmdzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhpcyBleGFtcGxlLCBjb3cgMyBjcm9zc2VzIHR3aWNlIC0tIHNoZSBmaXJzdCBhcHBlYXJzIG9uIHNpZGUgMSwgdGhlbiBsYXRlciBhcHBlYXJzIG9uIHNpZGUgMCwgYW5kIHRoZW4gbGF0ZXIgc3RpbGwgYXBwZWFycyBiYWNrIG9uIHNpZGUgMS4gQ293IDQgZGVmaW5pdGVseSBjcm9zc2VzIG9uY2UuIENvd3MgMiBhbmQgNiBkbyBub3QgYXBwZWFyIHRvIGNyb3NzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Bronze 1번

  • 문제를 번역한 사람: jh05013