trang chủ / đề bài / icpcwf14_k

Giám sát

Đề bài

Mô tả

Tập đoàn Quốc tế về Bảo vệ và Kiểm soát (ICPC) phát triển những công nghệ hiệu quả cho, ừm, việc bảo vệ và kiểm soát. Dĩ nhiên, họ rất muốn chính trụ sở của mình cũng được bảo vệ và kiểm soát.

Nhìn từ trên xuống, tòa nhà trụ sở có dạng một đa giác lồi. Xung quanh tòa nhà có một số vị trí thích hợp để lắp camera giám sát. Tùy theo vị trí, mỗi camera quan sát được một dãy các cạnh của đa giác (các bức tường của tòa nhà). ICPC muốn dùng ít camera nhất có thể để quan sát được toàn bộ tòa nhà.

Dữ liệu vào

Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên n và k: n là số bức tường và k là số vị trí có thể lắp camera. Các bức tường được đánh số từ 1 đến n theo thứ tự quanh tòa nhà.

Mỗi dòng trong k dòng tiếp theo chứa hai số nguyên ai và bi cho biết camera đặt ở vị trí thứ i quan sát được những bức tường nào:

  • Nếu ai≤bi thì camera quan sát mọi bức tường j với ai≤j≤bi.
  • Nếu ai>bi thì camera quan sát mọi bức tường j với ai≤j≤n hoặc 1≤j≤bi.

Dữ liệu ra

In ra số camera ít nhất đủ để quan sát được mọi bức tường của tòa nhà. Vùng quan sát của hai camera được phép chồng lên nhau. Nếu không thể quan sát toàn bộ tòa nhà, in ra impossible.

Ràng buộc

  • 3≤n≤106.
  • 1≤k≤106.
  • 1≤ai,bi≤n.

Ví dụ

Input Output Giải thích
100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
3 Ba camera (80,20), (20,60), (60,80) quan sát lần lượt các bức tường 80..100 và 1..20, 20..60, 60..80, phủ kín cả 100 bức tường. Không có hai camera nào đủ.
8 2
8 3
5 7
impossible Bức tường 4 không được camera nào quan sát.
8 2
8 4
5 7
2 Camera (8,4) quan sát các bức tường 8,1,2,3,4, camera (5,7) quan sát 5,6,7.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0