E. БОПТ

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

БОПТ нь Байтынхүч Оюутнуудын Програмчлалын Тэмцээн гэсэн үгний товчлол ба Байтынхүч-н хамгийн алдартай тэмцээн юм.

БОПТ бол багийн тэмцээн. Баг бүр гурван гишүүнтэй байх ба нэг дасгалжуулагчаас бүрдэнэ. Бленда бол Бит Мужийн Их сургуулийн (БМИ) дасгалжуулагч ба багийнхаа гишүүдийг сонгохдоо маш хатуу.

БМИ-д $1$-c $n$ хүртэл дугаарлагдсан $n$ оюутан байна. БМИ-н бүх оюутнууд үнэхээр ухаантайгаас хойш Блендад хамгийн чухал нэг үзүүлэлт нь тэдний унших болон бичих хурд юм. Болгоомжтойгоор хэмжсэний дараа Бленда $i$-р оюутны унших хурд нь $r_{i}$ (үгийг нэг минутанд) ба бичих хурд нь $w_{i}$ (үсгийг нэг минутанд) байгааг олжээ. Нэгэнт БМИ-н оюутнууд маш ухаалаг учраас хэмжигдсэн утгууд заримдаа маш их байсан ба Бленда бүх унших хурдны утгуудаас $c$ тогтмолыг хасах ба бүх бичих хурдны утгуудаас $d$ тогтмолыг хасахаар шийдсэн. Ингээд тэр $r_{i}' = r_{i} - c$ ба $w_{i}' = w_{i} - d$ гэж үзнэ.

Хэрвээ зөвхөн $r_{i}'*w_{j}' > r_{j}'*w_{i}'$ байвал л $i$ оюутан $j$ оюутныг дарамталдаг. Бленда баг доторх зодоонд дургүй ба тэр хэрвээ $i$ нь $j$-г дарамталдаг, $j$ нь $k$-г дарамталдаг, $k$ нь $i$-г дарамталдаг $i, j$ болон $k$ гэсэн ялгаатай гурван оюутнуудаас бүрдсэн баг байвал сайн гэж боддог. Тиймээ дарамтлах холбоо нь бодит амьдрал дээр ихэвчлэн байдагтай ижил тусахгүй.

Бленда Кодныхүч дэх сургалтын кэмп дээр бэлтгэл хийгээд завгүй байгаа учир танд БМИ дахь ялгаатай сайн багуудын тоог тооцоолох ажил өгөгдсөн. Хэрвээ нэг багаас оролцох боловч бусдаас оролцохгүй ядаж нэг оюутан байвал уг хоёр баг нь ялгаатайд тооцогдоно.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $c$ ба $d$ ($3 ≤ n ≤ 345678, 1 ≤ c, d ≤ 10^{9}$) бичигдсэн байна. Эдгээр нь харгалзан багуудыг бүрдүүлэхэд Блендагийн ашиглаж болох оюутнуудын тоо болон бүх унших хурднаас хасагдсан тоо болон бүх бичих хурднаас хасагдсан тоог заана.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $r_{i}$ ба $w_{i}$ ($0 < r_{i}, w_{i} ≤ 10^{9}, |r_{i} - c| + |w_{i} - d| > 0$) байна. Унших болон бичих хурд нь адилхан ямар ч хоёр оюутан байхгүй буюу бүх $i ≠ j$-н хувьд $|r_{i} - r_{j}| + |w_{i} - w_{j}| > 0$ нөхцөл биелэнэ.

Гаралт

Блендагийн сайн гэж тодорхойлсон БМИ дахь ялгаатай багуудын тоог хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 2 2
1 1
4 1
2 3
3 2
3 4
Гаралт
4
Оролт
7 6 6
3 2
1 7
5 7
3 7
6 4
8 9
8 5
Гаралт
11

Тэмдэглэл

Эхний жишээн дээр дараах багууд сайн: $(i = 1, j = 2, k = 3)$, $(i = 2, j = 5, k = 1)$, $(i = 1, j = 4, k = 3)$, $(i = 5, j = 1, k = 4)$.

Жишээний хувьд $(i = 3, j = 1, k = 2)$ мөн сайн баг ба $(i = 1, j = 2, k = 3)$ багтай ижил гэж тооцогдоно.

Сэтгэгдлүүдийг ачааллаж байна...