BOI 2007 - Ngày 1

Một nhóm tù binh đang tìm cách trốn khỏi nhà tù để đến một ngôi làng gần đó. Nhà tù (điểm \(A\)) và ngôi làng (điểm \(B\)) nằm ở hai đầu của một hẻm núi có lính canh. Mỗi người lính đứng yên và quan sát được mọi điểm cách mình không quá đúng \(100\) mét. Vì vậy, nhóm tù binh chỉ có thể đi qua an toàn nếu tại mọi thời điểm, khoảng cách từ họ đến người lính gần nhất đều lớn hơn \(100\) mét.

Biết chiều dài, chiều rộng của hẻm núi và vị trí của tất cả lính canh, hãy tìm số lính ít nhất cần loại bỏ để tồn tại một đường đi an toàn từ đầu trái sang đầu phải của hẻm núi. Có thể loại bỏ một người lính bất kể người đó có nằm trong tầm quan sát của người khác hay không.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(L\), \(W\) và \(N\): chiều dài, chiều rộng của hẻm núi và số lính canh.

Mỗi trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\), \(Y_i\), là tọa độ của người lính thứ \(i\). Góc tây nam có tọa độ \((0, 0)\) và góc đông bắc có tọa độ \((L, W)\).

Đường đi có thể bắt đầu tại \((0, y_s)\) với bất kỳ \(0 \le y_s \le W\) và kết thúc tại \((L, y_e)\) với bất kỳ \(0 \le y_e \le W\). Hai giá trị \(y_s\), \(y_e\) không nhất thiết là số nguyên.

Dữ liệu ra

In ra số lính ít nhất cần loại bỏ. Nếu đã có thể đi qua mà không cần loại bỏ ai, in ra 0.

Ràng buộc

Phân nhóm

• Trong mỗi nhóm kiểm thử, một lời giải chỉ xác định đúng việc có cần loại bỏ lính hay không nhận \(30\%\) số điểm của nhóm: in 0 khi đáp án là 0, hoặc in một số nguyên dương bất kỳ khi đáp án dương.
• Một lời giải in đúng số lính ít nhất trên mọi phép thử của nhóm nhận toàn bộ điểm của nhóm.

Ví dụ

130 340 5
10 50
130 130
70 170
0 180
60 260

1

Bạn có điểm số của một số người chơi trong một cuộc thi và cần lập bảng xếp hạng theo thứ tự điểm giảm dần.

Cấu trúc dữ liệu lưu danh sách chỉ hỗ trợ một thao tác: chuyển người chơi ở vị trí \(i\) đến vị trí \(j\) mà không thay đổi thứ tự tương đối của những người chơi khác. Nếu \(i > j\), vị trí của những người đang ở từ \(j\) đến \(i-1\) tăng thêm \(1\); nếu \(i < j\), vị trí của những người đang ở từ \(i+1\) đến \(j\) giảm đi \(1\).

Việc tìm người chơi ở vị trí \(i\) tốn \(i\) bước và tìm vị trí \(j\) tốn \(j\) bước, nên chi phí của thao tác là \(i+j\). Các vị trí được đánh số từ \(1\).

Hãy tìm một dãy thao tác đưa danh sách về thứ tự điểm giảm dần sao cho tổng chi phí nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), số người chơi. Mỗi trong \(n\) dòng tiếp theo chứa một số nguyên không âm \(s_i\), là điểm của người chơi ở vị trí hiện tại thứ \(i\). Mọi điểm số đôi một khác nhau.

Dữ liệu ra

Dòng đầu in số thao tác \(k\). Mỗi trong \(k\) dòng tiếp theo chứa hai số nguyên \(i\), \(j\), mô tả thao tác chuyển người chơi hiện ở vị trí \(i\) đến vị trí \(j\). Các thao tác được thực hiện theo đúng thứ tự đã in.

Danh sách cuối cùng phải có điểm giảm dần và tổng chi phí của các thao tác phải nhỏ nhất có thể.

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(n \le 10\).

Ví dụ

5
20
30
5
15
10

2
2 1
3 5

Trong bản ghi số, âm thanh được biểu diễn bởi một dãy số đo áp suất không khí được lấy ở những thời điểm cách đều nhau. Mỗi giá trị trong dãy được gọi là một mẫu.

Một bước quan trọng trong nhiều bài toán xử lý giọng nói là chia bản ghi thành các đoạn có âm thanh, ngăn cách bởi khoảng lặng. Để tránh chia thành quá ít hoặc quá nhiều đoạn, ta định nghĩa một khoảng lặng là dãy gồm \(m\) mẫu liên tiếp mà hiệu giữa giá trị lớn nhất và nhỏ nhất không vượt quá ngưỡng \(c\).

Hãy tìm tất cả khoảng lặng trong bản ghi gồm \(n\) mẫu.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(n\), \(m\), \(c\): số mẫu của bản ghi, độ dài cần có của một khoảng lặng và mức nhiễu tối đa cho phép.

Dòng thứ hai chứa \(n\) số nguyên \(a_i\), là các mẫu theo thứ tự thời gian.

Dữ liệu ra

In ra mọi chỉ số \(i\) thỏa mãn

Các chỉ số được in theo thứ tự tăng dần, mỗi chỉ số trên một dòng. Nếu không có khoảng lặng nào, in ra NONE.

Ràng buộc

Ví dụ

7 2 0
0 1 1 2 3 2 2

2
6