ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC - 2013-2014 > задача:


14-03-80. 50675 - Kruja Boys

IMPC - 2013-2014

Старт: 16.мар.2013 в 12:00:00
Финиш: 16.мар.2013 в 17:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• 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. s
• 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

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/5000/5000/5000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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