📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Thuật toán qua trò chơi 5: Cờ caro 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

Cho cây trò chơi đầy đủ: mỗi nút trong có đúng $b$ con, mọi lá nằm ở tầng $d$ (gốc ở tầng 0). Nút ở tầng chẵn là nút MAX, nút ở tầng lẻ là nút MIN. Cho giá trị của $b^d$ lá theo thứ tự từ trái sang phải.

Hãy chạy thuật toán cắt tỉa alpha–beta đúng theo mã giả dưới đây, gọi go(gốc, -∞, +∞), các con của mỗi nút được duyệt từ trái sang phải:

go(u, alpha, beta):
    nếu u là lá: đếm thêm 1 lá được đánh giá; trả về giá trị của u
    nếu u là MAX: v = -∞
        với mỗi con c của u (trái sang phải):
            v = max(v, go(c, alpha, beta)); alpha = max(alpha, v)
            nếu alpha >= beta: dừng vòng lặp
    nếu u là MIN: v = +∞
        với mỗi con c của u (trái sang phải):
            v = min(v, go(c, alpha, beta)); beta = min(beta, v)
            nếu alpha >= beta: dừng vòng lặp
    trả về v

In ra giá trị trả về ở gốc (chính là giá trị minimax của cây) và số lá được đánh giá.

Dữ liệu vào

• Dòng 1: hai số nguyên $b, d$ ($b \ge 2$, $d \ge 1$, $b^d \le 2 \cdot 10^5$).
• Dòng 2: $b^d$ số nguyên là giá trị các lá từ trái sang phải (giá trị tuyệt đối không quá $10^9$).

Kết quả

In ra hai số nguyên: giá trị của gốc và số lá được đánh giá, cách nhau một dấu cách.

Sample Input

2 3
3 5 6 9 1 2 0 -1

Sample Output

5 5