C. Дарагдсан цэгүүд

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

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

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

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

Чамд хоёр хэмжээст тэгш өнцөгт координатын систем байгаа гэж төсөөл. Зарим бүхэл цэгүүд дарагдсан байгаа. $A$ ба $B$ бүхэл цэгүүд хоорондоо холбогдсон байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь:

  • $A$ ба $B$-ийн хоорондох зай нэг ба $A$ ба $B$-ийн аль нь ч дарагдсан цэг биш;
  • Эсвэл ямар нэгэн $C$ гэсэн бүхэл цэгийн хувьд $A$ нь $C$-тэй холбогдсон ба $C$ нь $B$-тэй холбогдсон.

Хавтгайг дарагдсан цэггүй байгаа гэж үзье. Хавтгайн эхээс $n$-ээс ихгүй зайд байрлах бүхэл координаттай цэгүүдийг авч үзье. Бид эдгээр цэгүүдийг онцгой цэгүүд гэж нэрлэнэ. Чубби Ян ямар ч онцгой цэг онцгой биш цэгтэй холбогдсон байлгахыг хүсэхгүй байлаа. Ингэхийн тулд хавтгайн зарим бүхэл цэгүүдийг дарж болно. Хамгийн багадаа хэчнээн цэг дарах шаардлагатай вэ?

Оролт

Эхний мөрөнд $n$ $(0 ≤ n ≤ 4 \cdot 10^{7})$ гэсэн бүхэл тоо байна.

Гаралт

Хамгийн багадаа хэчнээн цэг дарагдсан байх ёстойг хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
1
Гаралт
4
Оролт
2
Гаралт
8
Оролт
3
Гаралт
16
Сэтгэгдлүүдийг ачааллаж байна...