CSES - Chess Tournament | Giải đấu cờ vua

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

Có một giải đấu cờ vua gồm \(n\) người chơi. Mỗi người chơi đã thông báo số lượng ván đấu mà họ muốn tham gia.

Mỗi cặp người chơi có thể tham gia nhiều nhất một ván đấu. Nhiệm vụ của bạn là xác định ván đấu nào sẽ được chơi để mọi người đều hài lòng.

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng người chơi. Người chơi được đánh số \(1, 2, \ldots, n\).
  • Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2,\ldots,x_n\): với mỗi người chơi, số lượng ván đấu họ muốn tham gia.

Output

  • Đầu tiên in số nguyên \(k\): số lượng ván đấu. Sau đó, in \(k\) dòng mô tả các ván đấu. Bạn có thể in bất kì giải pháp hợp lệ nào.
  • Nếu không có giải pháp nào, in IMPOSSIBLE.

Constraints

  • \(1 \le n \le 10^5\)
  • \(\sum_{i=1}^{n} x_i \le 2 \cdot 10^5\)

Example

Sample input:

5
1 3 2 0 2

Sample output:
4
1 2
2 3
2 5
3 5

Bình luận


  • -2
    nguyen_ducminh    12:21 a.m. 2 Tháng 9, 2023

    CSES - Chess Tournament | Giải đấu cờ vua

    Có một giải đấu cờ vua gồm \(n\) người chơi. Mỗi người chơi đã thông báo số ván họ muốn tham gia.

    Mỗi cặp người chơi có thể tham gia đấu với nhau tối đa một ván. Nhiệm vụ của bạn là xác định những ván đấu nào sẽ diễn ra để tất cả người chơi đều hài lòng.

    Input

    • Dòng đầu tiên gồm một số nguyên \(n\) (\(1 \leq n \leq 10^5\)) - số người chơi. Các người chơi được đánh chỉ số \(1, 2, ..., n\).
    • Dòng tiếp theo gồm \(n\) số nguyên \(x_1, x_2, ..., x_n\) (\(\sum_{i=1}^{n} x_i \leq 2 \times 10^5\)) - số ván mong muốn của mỗi người chơi.

    Output

    • Đầu tiên in ra \(k\): số lượng ván đấu. Sau đó in ra \(k\) dòng mô tả các ván đấu. Bạn có thể in ra một phương án hợp lệ bất kì.
    • Nếu không tồn tại phương án nào, in ra IMPOSSIBLE.

    Test 1

    Input 
    5
1 3 2 0 2
    Output 
    4
1 2
2 3
2 5
3 5