CSES - Stack Weights | Trọng lượng chồng xu

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

Bạn có \(n\) xu, mỗi xu có khối lượng phân biệt.

Có hai stack (chồng) rỗng lúc ban đầu. Tại mỗi bước bạn bỏ một đồng xu vào một stack. Bạn không bao giờ lấy xu ra khỏi một chồng nào cả.

Sau mỗi lượt, bạn cần xác định chồng xu nào nặng hơn (nếu có thể chắc chắn được là stack nào nặng hơn).

Input

Dòng đầu tiên chứa số nguyên $n: $ số lượng đồng xu. Các đồng xu được đánh số \(1,2,\dots,n\). Bạn biết rằng xu \(i\) luôn nặng hơn xu \(i-1\), nhưng không biết khối lượng chính xác của chúng.

Sau đó là \(n\) dòng mô tả các lượt đi. Mỗi dòng chứa hai số nguyên $c,s: $ bỏ xu \(c\) vào chồng \(s\) (1: bên trái, 2: bên phải)

Output

Sau mỗi lượt, in ra < nếu chồng bên phải nặng hơn, > nếu chồng bên trái nặng hơn, và ? nếu chúng ta không thể biết được chồng nào nặng hơn.

Constraints

  • \(1≤n≤2\times 10^5\)

Example

Sample Input:

3
2 1
3 2
1 1

Sample Output:
>
<
?

Bình luận


  • 0
    nguyen_ducminh    2:10 a.m. 16 Tháng 9, 2023

    CSES - Stack Weights | Khối lượng chồng xu

    Bạn có \(n\) đồng xu, mỗi đồng xu có khối lượng riêng biệt.

    Có hai chồng rỗng. Tại mỗi lượt bạn đặt thêm một đồng xu vào một chồng. Bạn không được lấy xu ra khỏi chồng của nó.

    Sau mỗi lượt, nhiệm vụ của bạn là tính xem chồng nào nặng hơn (nếu có thể biết chắc rằng một trong hai chồng nặng hơn chồng còn lại).

    Input

    • Dòng đầu tiên gồm số nguyên \(n\) - số lượng đồng xu. Các đồng xu được đánh chỉ số \(1,2,...,n\) (\(1 \leq n \leq 2\times10^5\)). Bạn biết đồng thứ \(i\) luôn nặng hơn đồng thứ \(i-1\) nhưng không biết khối lượng chính xác của chúng.
    • \(n\) dòng tiếp theo mô tả các lượt đi. Mỗi dòng gồm hai số nguyên \(c\) và \(s\) với ý nghĩa đặt đồng \(c\) vào chồng \(s\) (1 : chồng bên trái, 2 : chồng bên phải).

    Output

    • Sau mỗi lượt đi, in ra < nếu chồng bên phải nặng hơn, > nếu chồng bên trái nặng hơn, ? nếu không thể biết chồng nào nặng hơn.

    Test 1

    Input 
    3
2 1
3 2
1 1
    Output 
    >
<
?
    Note

    Sau lượt đi cuối cùng, nếu khối lượng các đồng xu là \([2,3,4]\) thì chồng bên trái nặng hơn, nhưng nếu khối lượng của chúng là \([1,2,5]\) thì chồng bên phải nặng hơn.

      • 1 bình luận nữa