HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50675 - Kruja Boys

Guest
• Review clarifications (1)

Section problems

• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard

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