Module: Tarama yöntemi


Problem

4 /4


Parçacık Mu

Problem

Karantinada fizik çalışmasına giren inekler "mu-parçacıkları" keşfettiler
Şu anda N "mu-parçacıkları" ile deneyler yapıyorlar (1 ≤K ≤ 105). i parçacığı, −109…10 aralığında iki xi ve yi tamsayısıyla açıklanan bir "spin"e sahiptir 9 dahil. Bazen iki "mu-parçacık" etkileşime girmek. Bu yalnızca (xi,yi) ve (xj,yj) spinli parçacıklarda olabilir. ) xi≤xj ve yi≤yj'ye sahip. Bu koşullar altında, bu parçacıklardan tam olarak biri kaybolur (ve diğerine hiçbir şey olmaz). Herhangi bir zamanda en fazla bir etkileşim gerçekleşebilir.

İnekler, gelişigüzel bir dizi etkileşimden sonra kalabilecek minimum "mu-partikül" sayısını bilmek istiyor.

Girdi
İlk satır, "mu-parçacıklarının" ilk sayısı olan bir tamsayı N içerir. Aşağıdaki N çizgilerinin her biri, bu parçacığın dönüşünü tanımlayan boşlukla ayrılmış iki tam sayı içerir. Tüm dönüşler farklıdır.
Künye
Bir tamsayı, gelişigüzel bir dizi etkileşimden sonra kalabilen "mu-parçacıklarının" minimum sayısı.
Örnekler

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Girdi Çıktı Not
1 4
10
0 1
-1 0
0 -1 		1 Olası etkileşim dizilerinden biri:

1. ve 4. parçacıklar etkileşime girer, 1. parçacık kaybolur.
2. ve 4. parçacıklar etkileşime girer, 4. parçacık kaybolur.
2. ve 3. parçacıklar etkileşime girer, 3. parçacık kaybolur.
Geriye yalnızca 2. parçacık kaldı.
2 3
0 0
1 1
-1 3 		2 Parçacık 3, diğer parçacıkların hiçbiriyle etkileşemez, dolayısıyla öyle kalmalıdır. 1. ve 2. parçacıklardan biri de kalmalıdır.