Xin cách khắc phục "time limit exceeded" trên SPOJ

[huyentrang]

link đề: http://www.spoj.com/problems/TOANDFRO/
code của mình;

#include <iostream>
#include<string.h>
using namespace std;

int main() 
{
	int col;
	cin>>col;
	cin.ignore(1);
	while(col)
	{
		char s[300];
		cin.get(s,300);
		int row = strlen(s)/col;
		int i,j,k=0;
		char matrix_string[20][20];
		for(i=0; i<row; i++)
		{
			if(i%2)
			{	for(j=col-1; j>=0; j--)
					matrix_string[i][j]= s[k++];}
			else 
			{	
				for(j=0; j<col; j++)
					matrix_string[i][j]=s[k++];}
		}
		for(j=0; j<col; j++)
		{	for(i=0; i<row; i++)
				cout<< matrix_string[i][j];}
		cout<<endl;
		cin>>col;
	}
	return 0;
}

[rogp10]

Bạn thử cách khác không dùng đến mảng hai chiều xem sao

[banhmisg9509 (Nguyễn Hùng)]

Có lẽ nên đổi qua quản lý bằng string thì tốt hơn. Giảm số vòng for lại
Giải thuật mới như thế này, cũng gần tương tự như của bạn thôi

1. Đọc số w, và str
2. Chia str ra thành (len(str)/w) chuỗi con subtrs mỗi substrs có chiều dài w, và bỏ vào một vector ls hoặc có thể dùng mảng string @.@. Nếu substrs(i) với i là lẻ thì đảo chuỗi em nó.

string res = "";
for(j = 0; j < w: j++){
    for(i = 0; i < ls.size(); i++){
        res += substrs[i][j];
    }
}
print res

@.@ Vì đã lâu không đụng đến C++ nên khá ngại sửa code, nên chỉ đóng góp ý tưởng vậy thôi. Có thể tham khảo code python.

while True:
        w = int(raw_input())
        if w == 0:
            break
        t = raw_input()
        l = len(t)
        ls = [t[i:i+w] if (j)%2==0 else t[i:i+w][::-1] for j,i in enumerate(xrange(0,l,w))]
        r = ''
        for i in zip(*ls):
            r+=''.join(i)
        print r

[rogp10]

Viết lại thôi

FUNC decrypt(
: Input: enc_s[1..n]: string, no_col: uinteger
: Output: dec_s[1..n]: string) begin

assert(n % no_col == 0) raise "Phải chẵn cột mới được!"; { modulo }

: scan_step = 2*no_col;
: dec_s := "";
: temp := n - n % (no_col*2);

if enc_s = "" then return "";

{nếu no_col = 5 thì các vị trí sau liền nhau: 1/10, 2/9, 3/8, 4/7, 5/6}
for i:= 0 to no_col-1 do begin
   for j:= 1 to temp STEP scan_step do
      dec_s += "#{enc_s[j+i]}#{enc_s[j+scan_step-1-i]}";
   if temp != n then dec_s += enc_s[temp+i+1];
end;

end.

UnitTest.func(decrypt) do begin
% test.on assert(enc_s.len() == dec_s.len()
AND enc_s.freq_table() == dec_s.freq_table());
% static.on assert(decrypt("", ANY) == ""
AND decrypt("Tubnfrihecooxwkq", 4) == "Thequickbrownfox")
AND decrypt({enc_s: ANY, no_col: enc_s.len()}. apply()) == enc_s
);
end