canuc80k0604·5/50

Hai Vị Trí Có Tổng

Nộp bài trên LQDOJ

Bài 06 · Two Pointers

Cho mảng gồm số nguyên và một giá trị mục tiêu . Hãy tìm hai chỉ số khác nhau và sao cho .

Nếu có nhiều cặp thỏa mãn, bạn được in bất kỳ một cặp nào.

Input

  • Dòng đầu chứa hai số nguyên và .
  • Dòng thứ hai chứa số nguyên .

Output

  • Nếu tồn tại đáp án, in hai chỉ số khác nhau và trong phạm vi từ đến sao cho .

  • Nếu không tồn tại, in IMPOSSIBLE.

Constraints

  • .
  • .

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6 13
8 2 11 5 7 1

Output

2 3

Giải thích: Hai vị trí và chứa các giá trị và ; tổng của chúng bằng , vì vậy đây là một đáp án hợp lệ.

Lời giải tóm tắt
  • Phân tích: Sau khi sắp xếp các cặp (giá trị, chỉ số gốc), tổng của hai đầu có tính đơn điệu. Nếu tổng quá nhỏ, phần tử trái không thể ghép với bất kỳ phần tử nào còn lại để đạt x; nếu tổng quá lớn, lập luận đối xứng áp dụng cho phần tử phải.
  • Thuật toán: Sắp xếp các cặp theo giá trị, rồi dùng hai con trỏ l và r. Tăng l khi tổng nhỏ hơn x, giảm r khi tổng lớn hơn x. Khi bằng nhau, in hai chỉ số gốc; nếu hai con trỏ gặp nhau, in IMPOSSIBLE.
  • Chứng minh đúng: Khi tổng biên nhỏ hơn x, mọi cặp dùng phần tử trái với một phần tử không vượt quá đầu phải đều có tổng không lớn hơn tổng hiện tại, nên loại đầu trái là an toàn. Trường hợp tổng lớn hơn được chứng minh tương tự. Vì chỉ loại phần tử không thể thuộc đáp án, thuật toán sẽ tìm thấy một cặp hợp lệ nếu cặp đó tồn tại.
  • Độ phức tạp: O(n log n) thời gian và O(n) bộ nhớ.