Nhện đi dạo
Đề bài
Mô tả
Cô nhện Charlotte ngồi ở tâm mạng nhện của mình. Mạng nhện gồm một số sợi tơ thẳng (gọi là các tia) đi từ tâm ra tới biên ngoài của mạng. Mạng nhện còn có các cầu, mỗi cầu nối hai tia kề nhau. Hai đầu mút của một cầu luôn cách tâm mạng nhện cùng một khoảng.
Sau một bữa tiệc đêm ở tâm mạng, khi muốn lui về một góc nào đó, Charlotte đi ra biên theo chế độ tự động. Cô chọn một tia xuất phát và đi dọc theo tia đó (ra xa tâm) cho tới khi gặp cầu đầu tiên trên tia. Cô đi qua cầu sang tia bên kia, rồi tiếp tục đi ra xa tâm cho tới khi gặp một cầu khác. Cô lại đi qua cầu đó, và cứ lặp lại như vậy cho tới khi trên tia hiện tại không còn cầu nào phía trước, khi đó cô đi tới đầu mút ngoài của tia hiện tại. Lưu ý rằng Charlotte bắt buộc phải đi qua mọi cầu mà cô gặp. Hình dưới minh họa một đường đi của Charlotte.

Đường đi (màu đỏ) xuất phát từ tia trên mạng nhện của ví dụ 1.
Góc ngủ ban ngày ưa thích của Charlotte là đầu mút ngoài của tia . Với mỗi tia xuất phát có thể, cô muốn biết số cầu ít nhất cần thêm vào mạng nhện ban đầu để cô kết thúc tại tia . Charlotte có thể thêm cầu tại bất kỳ vị trí nào dọc theo các tia, miễn là cầu thêm vào không chạm vào bất kỳ cầu nào khác. Hai đầu mút của mỗi cầu thêm vào phải cách tâm mạng nhện cùng một khoảng, và cầu phải nối hai tia kề nhau.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và : là số tia, là số cầu, là tia ưa thích của Charlotte. Các tia được đánh số từ tới theo chiều ngược chiều kim đồng hồ.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và mô tả một cầu: là khoảng cách từ cầu tới tâm mạng nhện, là tia đầu tiên của cầu theo chiều ngược chiều kim đồng hồ. Cụ thể, nếu thì cầu nối tia và tia ; nếu thì cầu nối tia và tia .
Dữ liệu ra
In ra dòng, dòng thứ là số cầu ít nhất Charlotte cần thêm vào để kết thúc tại tia khi đi tự động bắt đầu từ tia .
Ràng buộc
- , , .
- , .
- Các khoảng cách của các cầu đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 5 6 2 1 4 3 6 3 8 7 10 5 |
2 1 1 1 0 1 2 |
Đây là mạng nhện trong hình. Từ tia , Charlotte gặp cầu ở khoảng cách nối tia và , sang tia và đi ra biên, nên không cần thêm cầu. Từ tia , cô sang tia (cầu khoảng cách ), quay lại tia (cầu khoảng cách ) rồi đi ra biên tia ; thêm một cầu nối tia và ở khoảng cách thì cô đi sang tia , rồi qua cầu khoảng cách sang tia . |
| 4 4 2 1 1 2 2 3 3 4 4 |
1 1 0 1 |
Từ tia , Charlotte qua cầu khoảng cách sang tia ; phía trước trên tia không còn cầu nào nên cô kết thúc tại tia . Từ tia , cô lần lượt đi qua cả bốn cầu và kết thúc tại tia , nên cần thêm một cầu. |
Bình luận