📖 Bài giảng & lời giải: đây là Bài tập 4 trong bài giảng Thuật toán qua trò chơi 4: Game 2048 trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Trên bàn 2048 kích thước $4 \times 4$ người ta bấm phím $q$ lần theo một kịch bản cho trước. Lần bấm thứ $j$ được cho bởi một dòng d r c v: hướng bấm $d$ (một trong L, U, R, D) và ô mới sẽ xuất hiện ở hàng $r$, cột $c$ (đánh số từ 1) với giá trị $v$.

Luật trượt và gộp của 2048 (mô tả cho phím ←, các phím khác tương tự theo hướng tương ứng): trên mỗi hàng, các ô khác 0 được dồn hết về mép trái, giữ nguyên thứ tự. Xét các ô đó lần lượt từ mép trái (mép đích) đi ra: nếu hai ô liền nhau có cùng giá trị $x$ thì chúng gộp thành một ô $2x$ và người chơi được cộng $2x$ điểm. Mỗi ô chỉ được tham gia gộp nhiều nhất một lần trong một lần bấm (ô vừa gộp xong bị "khoá"), và cặp nào gần mép đích hơn thì được gộp trước. Ví dụ hàng 2 2 2 2 bấm ← thành 4 4 0 0 (+8 điểm), hàng 4 4 8 0 bấm ← thành 8 8 0 0 (+8 điểm, ô 8 mới không gộp tiếp với ô 8 cũ).

Xử lý lần lượt từng dòng của kịch bản:

• Nếu bấm hướng $d$ làm bàn thay đổi thì nước đi hợp lệ: cộng điểm gộp của nước đi, tăng số nước hợp lệ thêm 1, rồi đặt ô mới giá trị $v$ vào ô $(r, c)$. Đề bảo đảm khi đó ô $(r, c)$ đang trống (sau khi trượt).
• Nếu bàn không thay đổi thì bỏ qua cả dòng (không đặt ô mới; khi đó $(r, c)$ có thể là ô bất kỳ).

Sau khi xử lý hết kịch bản, in ra tổng điểm, số nước hợp lệ, giá trị ô lớn nhất trên bàn, và cho biết bàn cuối cùng còn hướng nào đi được hay không.

Dữ liệu vào

• 4 dòng đầu: bàn ban đầu, mỗi dòng 4 số nguyên, mỗi số là $0$ hoặc $2^t$ với $1 \le t \le 16$; bàn có ít nhất một ô khác 0.
• Dòng tiếp theo: số nguyên $q$ ($1 \le q \le 10^5$).
• $q$ dòng tiếp theo, mỗi dòng gồm ký tự $d$ (một trong L, U, R, D) và ba số nguyên $r, c, v$ ($1 \le r, c \le 4$, $v \in \{2, 4\}$).

Kết quả

• Dòng 1: ba số nguyên: tổng điểm, số nước hợp lệ, giá trị ô lớn nhất của bàn cuối cùng.
• Dòng 2: YES nếu bàn cuối cùng còn ít nhất một hướng đi được, ngược lại NO.

Sample Input

2 2 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
L 1 4 2
L 4 4 4
U 2 1 2
U 3 3 2

Sample Output

4 3 4
YES