Sắp xếp (THTB TQ 2021)

Xem PDF



Tác giả:
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Xâu \(x\) được gọi là lớn hơn xâu \(y\) nếu xâu \(y\) là đoạn đầu của xâu \(x\) hoặc xét kí tự đầu tiên khác nhau thì kí tự của xâu \(x\) lớn hơn kí tự của xâu \(y\).

Để luyện tập về việc so sánh hai xâu, Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương \(a,b (a < b)\), tạo ra một dãy số gồm \(b - a + 1\) số: \(a, a + 1, ... , b\). Sau đó, sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn
và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu \(a = 9, b = 11\) ta có dãy số gồm \(3\) số \(9, 10, 11\), dãy số được sắp xếp theo thứ tự từ điển là \(10, 11, 9\) và cần ít nhất một thao tác (rút số \(9\) khỏi dãy và chèn vào cuối dãy).

Yêu cầu: Cho hai số nguyên dương \(a, b (a < b)\), hãy tính số thao tác ít nhất để sắp xếp các số
\(a, a + 1, ... , b\) theo thứ tự từ điển.

Input

  • Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(a, b (a < b \le 10^9)\)

Output

  • Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Scoring

  • Subtask \(1\) (20\%$ số điểm): \(b - a = 1\);
  • Subtask \(2\) (20\%$ số điểm): \(b - a \le 10\);
  • Subtask \(3\) (30\%$ số điểm): \(b − a \le 1000\);
  • Subtask \(4\) (30\%$ số điểm): \(b − a \le 10^5\);

Example

Test 1

Input
9 11
Output
1

Bình luận


  • -16
    nguyendanghau2006 11:26 a.m. 2 Tháng 5, 2022 đã chỉnh sửa

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.