Bessie đang học lập trình bằng một ngôn ngữ lập trình đơn giản. Trước tiên, cô định nghĩa một chương trình hợp lệ, rồi thực thi nó để tạo ra một dãy đầu ra.

Định nghĩa:

• Một chương trình là một dãy không rỗng gồm các câu lệnh.
• Một câu lệnh có dạng PRINT \(c\), trong đó \(c\) là một số nguyên, hoặc có dạng REP \(o\), theo sau bởi một chương trình rồi đến END, trong đó \(o\) là một số nguyên ít nhất bằng \(1\).

Thực thi:

• Thực thi một chương trình nghĩa là thực thi tuần tự các câu lệnh của nó.
• Thực thi câu lệnh PRINT \(c\) sẽ nối \(c\) vào cuối dãy đầu ra.
• Thực thi một câu lệnh bắt đầu bằng REP \(o\) sẽ thực thi tuần tự chương trình bên trong tổng cộng \(o\) lần.

Sau đây là một ví dụ về chương trình mà Bessie biết viết:

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Chương trình in ra dãy \([1,2,2,1,2,2,1,2,2]\).

Bessie muốn in ra một dãy gồm \(N\) (\(1\le N\le 100\)) số nguyên dương. Elsie thách cô chỉ dùng không quá \(K\) (\(1\le K\le 3\)) câu lệnh PRINT. Lưu ý rằng Bessie có thể dùng bao nhiêu câu lệnh REP tùy ý. Đồng thời, mỗi số nguyên dương trong dãy không lớn hơn \(K\).

Với mỗi trong số \(T\) (\(1\le T\le 100\)) trường hợp kiểm thử độc lập, hãy xác định liệu Bessie có thể viết một chương trình in ra dãy cho trước bằng không quá \(K\) câu lệnh PRINT hay không.

Dữ liệu vào

Dòng đầu tiên chứa \(T\).

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(K\).

Dòng thứ hai của mỗi trường hợp kiểm thử chứa một dãy \(N\) số nguyên dương cách nhau bởi dấu cách, mỗi số không quá \(K\); đây là dãy Bessie muốn tạo ra.

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in YES hoặc NO (phân biệt chữ hoa chữ thường) trên một dòng riêng.

Ví dụ

2
1 1
1
4 1
1 1 1 1

YES
YES

REP 4
    PRINT 1
END

11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

PRINT 1
REP 3
    PRINT 2
END

REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

Phân nhóm

• Dữ liệu 3: \(K=1\).
• Dữ liệu 4–7: \(K\le 2\).
• Dữ liệu 8–13: Không có ràng buộc bổ sung.

Nguồn

Đề bài gốc: USACO 2025 February Contest, Bronze — Printing Sequences

Tác giả: Alex Liang.