Hướng dẫn cho HackDream Blue 02-E: In bảng số
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Ta sẽ cố gắng điền từng số vào bảng 2 chiều ~n~ x ~n~ theo chiều tăng dần của giá trị rồi mới ỉn ra cả bảng sau đó.
Thay vì đi theo con đườngg ngoằn ngoèo như ban đầu, ta sẽ phân chia bảng vuông thành từng dải ô và đánh số chúng từ 1 theo thứ tự từ dải bé đến dải lớn.
Ví dụ với bảng ~4~ x ~4~, dải 1 và dải 3 là dải màu đỏ, dải 2 và 4 là dải màu xanh. Ta thấy quy luật hiện tại như sau:
- Dải lẻ sẽ có quy tắc di chuyển theo giá trị từ bé đến lớn là đi hàng ngang bên dưới trước từ trái sang phải, rồi vòng lên cột từ dưới lên trên.
- Dải chẵn có quy tắc di chuyển là đi từ cột bên phải từ trên xuống, rồi đi theo hàng sang bên trái.
Từ đây, ta sẽ cấu trúc thuật toán theo 2 bước:
- Bước 1: Dùng một vòng ~for~ để duyệt tất cả các dải số từ bé đến lớn
- Bước 2: Tuỳ thuộc vào dải chẵn hay lẻ, sử dụng 2 vòng ~for~ riêng biệt (không phải lồng nhau), để điền được hình chữ ~L~ ngược trên dải số đó.
Độ phức tạp: ~O(n^2)~.
Bình luận
khó thế