SPOJ.COM - Thuật toán bài TOANDFRO - To and Fro

Posted on October 26th, 2016

Đề 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.

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 đó, mình xếp nó vào dạng thuật toán tham lam Greedy
  • Mình 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ì mình làm vậy.

Lời giải

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 mình 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 mình 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 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

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: