HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


14-03-80. 50675 - Kruja Boys

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 14-01-50. 50795 - Trunk
• 14-03-10. 50412 - K numbers
• 14-03-20. 50398 - Sum of kth Anti-d...
• 14-03-30. 50377 - kth Permutation
• 14-03-40. 50773 - Balanced Sum Tree
• 14-03-60. 50382 - Parkside's Other ...
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-80. 50675 - Kruja Boys
• 14-03-90. 50717 - Hurdle Jumping
• 14-04-20. 50493 - n-digit kth Prime ...
• 14-04-30. 50669 - Area of an Irregu...
• 14-04-40. 50712 - Moon algebra
• 14-04-50. 50697 - Base Stations
• 14-05-10. 50723 - Tribonacci
• 14-05-20. 50677 - The Cottage
• 14-05-20. 50413 - Valid Permutations

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 3000/5000/5000/5000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ilir Capuni.

Kruja Boys

Kruja has a specific architecture as all the houses are on the same street. Boys live in some odd numbered houses (the left side of the street), while girls live on the even side houses. N boys fell in love (each of them with a different girl), but they are too shy and they do not want to meet with their friends when they are going on a date, so they can avoid being teased by their friends.

Question: You want to develop a match-making website hence, each boy has inserted his own address and the address of his valentine. Find the maximal number of couples for which paths of the boys while going to their girlfriends do not intersect.

Input specification
You will be given an integer number (n) at the beginning where 1 ≤ n ≤ 10000. Then in the following n lines, you will be given two integers, home number of boy and matching girl where home numbers are less than 50000.

Output specification
Show just one number: maximal number of couples for which paths do not intersect.

 Sample Input   
 7
 13 2
 1 4
 5 10
 3 8
 9 12
 7 6
 11 14
 Sample Output   
 5

Explanation: following 5 boys can meet with the girls at the same time without any intersection.
 1
 3
 5
 9
 11


Для отправки решений необходимо выполнить вход.

www.contester.ru