SPOJ.COM – Thuật toán bài TOANDFRO - To and Fro
Đề bài:
Mo và Larry đã nghĩ ra cách để mã hoá tin nhắn. Đầu tiên họ bí mật về số lượng cột và viết tin nhắn (chỉ bao gồm các chữ cái) theo từng cột từ trên xuống theo số cột đó, và chèn thêm các kí tự ngẫu nhiên để tạo ra một mảng hình chữ nhật của các chữ cái. Ví dụ: nếu tin nhắn là “There’s no place like home on a snowy night” và họ có 5 cột. Thì Mo sẽ viết nó xuống thành:
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Chú ý rằng: Mo chỉ viết chữ cái, và ở dạng chữ thường. Ở ví dụ này, Mo sử dụng kí tự 'x' để điền thêm vào tin nhắn để tạo ra mảng kí tự hình chữ nhật. Sau đó Mo gửi tin nhắn đó cho Larry bằng cách viết các chữ này theo mỗi hàng. Lần lượt từ trái sang phải rồi từ phải sang trái. Do đó, tin nhắn trên sẽ thành:
toioynnkpheleaigshareconhtomesnlewx
Nhiệm vụ của bạn là khôi phục lại lá thư gốc cho Larry (kèm theo các chữ cái được thêm vào)
Đầu vào:
Bao gồm nhiều test case. Mỗi test case bao gồm 2 dòng. Dòng đầu tiên bao gồm số nguyên từ 2 đến 20, xác định số cột. Dòng tiếp theo là một chuỗi kí tự tối đa là 200 chữ cái thường. Cuối cùng của đầu vào là một dòng chứa số 0.
Đầu ra:
Mỗi đầu ra chứa 1 dòng, là tin nhắn gốc của MO, trong đó không chứa dấu cách.
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/TOANDFRO/
Phân tích:
- Bài toán này không cần phải sử dụng thuật toán gì phức tạp. Do đó, tôi xếp nó vào dạng thuật toán tham lam Greedy
- Tôi sẽ làm bài toán này hoàn toàn dựa theo yêu cầu bài toán. Tức là đề bài nói sao thì tôi làm vậy.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include <iostream> | |
| using namespace std; | |
| int main() | |
| { | |
| //freopen("input.txt","r",stdin); | |
| int NUM_COL = 0; | |
| while(true) | |
| { | |
| // Nhập số lượng cột | |
| cin >> NUM_COL; | |
| if(NUM_COL == 0) break; | |
| // Xâu đầu vào | |
| char str[201]; | |
| cin >> str; | |
| // Tính độ dài của xâu | |
| int length = 0; | |
| while(str[length] != '\0') length++; | |
| // Lưu ma trận | |
| char Mat[101][21]; | |
| // Lưu toạ độ hàng và cột đang đứng | |
| int col = 0, row = 0; | |
| // biến thiên chỉ số cột: = 1 nếu đi từ trái sang phải | |
| // ngược lại = -1 | |
| int delta = 1; | |
| // Duyệt xâu để chuyển xâu thành ma trận | |
| for(int i = 0; i < length; i++) | |
| { | |
| // Ban đầu là đi từ trái sang phải => chỉ số cột tăng | |
| Mat[row][col] = str[i]; | |
| col += delta; | |
| // Khi đi đến cuối thì quay về trái | |
| if(col >= NUM_COL) | |
| { | |
| Mat[row][col] = '\0'; | |
| row++; | |
| Mat[row][col] = '\0'; | |
| delta = -1; | |
| col += delta; | |
| } | |
| else if (col < 0) // Khi đi đến đầu thì quay sang bên phải | |
| { | |
| row++; | |
| delta = 1; | |
| col += delta; | |
| } | |
| } | |
| // Tìm ra kết quả | |
| int count = 0; | |
| for(int j = 0; j < NUM_COL; j++) | |
| { | |
| for(int i = 0; i < row; i++) | |
| str[count++] = Mat[i][j]; | |
| } | |
| str[count] = '\0'; | |
| cout << str << endl; | |
| } | |
| return 0; | |
| } |
Code Python:
| while(1): | |
| # Nhap so luong cot | |
| num_col = int(raw_input()) | |
| if num_col == 0: | |
| break | |
| # Xau dau vao | |
| str_input = raw_input() | |
| # Tinh so luong cot | |
| num_row = len(str_input) / num_col; | |
| # Chuyen xau dau vao thanh dang ma tran | |
| # va luu dang xau binh thuong | |
| string = "" | |
| for i in range(0, num_row): | |
| if i % 2 == 0: | |
| string += str_input[i*num_col : (i+1)*num_col] | |
| else: | |
| string += (str_input[i*num_col : (i+1)*num_col])[::-1]# dao nguoc xau | |
| # xau ket qua | |
| result = "" | |
| for j in range(0, num_col): | |
| for i in range(0, num_row): | |
| result += string[i*num_col + j] | |
| print result |
Code by Phạm Văn Lâm.