P156SUMH spoj PTIT – ROUND 6H – Kim cương

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P156SUMH/

1. Đề bài P156SUMH spoj

Xavi có một ma trận hình vuông kích thước n * n (với n lẻ). Anh ta muốn trang trí vào ma trận đấy một viên kim cương. Các bạn hãy giúp anh ấy thực hiện công việc này.

Kí tự ‘*’ thể hiện các ô trống còn ‘D’ thể hiện kim cương (xem ví dụ).

Input

Dòng duy nhất chứa số nguyên n (1 <= n <= 101).

Output

In ra n x n kí tự là đáp án của bài toán.

Example

Input:
5

Output:
**D**
*DDD*
DDDDD
*DDD*
**D**

2. Hướng dẫn giải P156SUMH spoj PTIT

– Khi làm bài này đa số các bạn đề gặp vấn đề ở việc điền các dấu “*” hoặc “D”

– Thay vì điền các kí tự dựa trên việc quản lí chỉ số trên bảng n*n thì mình sẽ hướng dẫn các bạn cách tiếp cận bài toán này theo hướng đơn giản hơn.

– Nhận xét: dòng đầu tiên của bảng thường có dạng “****D****” mà phần dấu * của 2 bên là như nhau, mỗi lần xuống dòng tiếp theo mỗi bên mất 1 dấu * thay vào đó là chữ D.

– Từ những nhận xét trên ta xây dựng 2 xâu x, y. với X ban đầu gồm (n-1) div 2 số lượng dấu *, còn y là 1 chữ D duy nhất.

– Như vậy ở mỗi dòng tương ứng, ta xóa 1 kí tự “*”, và tăng lên 2 kí tự “D” rồi write(x,y,x) cho đến dòng giữa bảng, ta làm ngược lại.

3. Code tham khảo P156SUMH spoj PTIT

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *