trang chủ / bài tập / rulermark

Vạch chia trên thước

Đề bài

Mô tả

Một chiếc thước dài l xăng-ti-mét có n vạch chia, đánh số từ 1 đến n theo thứ tự từ đầu thước đến cuối thước. Vạch thứ i nằm cách đầu thước ai xăng-ti-mét, trong đó a1=0 (đầu thước) và an=l (cuối thước).

Chiếc thước được coi là đo được khoảng cách d nếu tồn tại hai vạch ij (1ijn) sao cho ajai=d.

Cần dùng thước này để đo hai khoảng cách xy (với x<y). Bạn được phép khắc thêm các vạch mới tại vị trí nguyên bất kỳ trong đoạn từ 0 đến l.

Hãy tìm số vạch ít nhất cần khắc thêm để chiếc thước đo được cả hai khoảng cách xy, đồng thời chỉ ra vị trí của các vạch đó.

Nếu có nhiều đáp án cùng đạt số vạch ít nhất, in ra đáp án bất kỳ.

Dữ liệu vào

  • Dòng đầu chứa bốn số nguyên dương n, l, x, y.
  • Dòng thứ hai chứa n số nguyên a1,a2,,an là vị trí các vạch chia có sẵn.

Dữ liệu ra

  • Dòng đầu in ra một số nguyên không âm v là số vạch ít nhất cần khắc thêm.
  • Dòng thứ hai in ra v số nguyên p1,p2,,pv (0pil) là vị trí các vạch cần khắc thêm, theo thứ tự tuỳ ý. Nếu v=0 thì dòng này để trống hoặc bỏ qua.

Ràng buộc

  • 2n105
  • 2l109
  • 1x<yl
  • 0=a1<a2<<an=l

Ví dụ

Input Output Giải thích
3 250 185 230
0 185 250
1
230
Khoảng cách 185 đã đo được nhờ cặp vạch 0185, nhưng 230 thì chưa. Khắc thêm vạch tại 230 là đủ (khắc tại 20 cũng cho đáp án hợp lệ).
2 300 185 230
0 300
2
185 230
Thước chỉ có hai vạch đầu và cuối nên chưa đo được khoảng cách nào ngoài 300. Không một vạch đơn lẻ nào giúp đo được đồng thời 185230, nên cần khắc thêm hai vạch.
4 250 185 230
0 20 185 250
0 Cặp (0,185) cho khoảng cách 185, cặp (20,250) cho khoảng cách 230, nên không cần khắc thêm vạch nào.

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.400 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.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0