#include <string>
#include <iostream>

using namespace std;

string Convert(string s, int nRows) 
{
    if (nRows < 2)return s;

    int pattenSize = (nRows-1)*2;
    int length = s.size();
    string r; //result;
    //first row
    for (int i = 0; i < length; i += pattenSize)
        r.push_back(s[i]);

    //each row except first and last would contains two letters in one pattern
    for (int i = 1; i < nRows-1; ++i)
    {
        for (int j = i; j < length; j += pattenSize)
        {
            r.push_back(s[j]);
            int k = (j-i) + (pattenSize - i);
            if (k < length)r.push_back(s[k]);
        }
    }

    //Last row
    for (int i = nRows-1; i < length; i += pattenSize)
        r.push_back(s[i]);

    return r;
}


int main(int argc, char** argv)
{
    string s = "PAYPALISHIRING";
    cout << Convert(s, 3) << endl;
    cout << Convert(s, 4) << endl;
    cout << Convert(s, 5) << endl;
	
    s = "jieghdncltrryzfm";
    cout << Convert(s, 10) << endl;  
	
	/*
	 PAHNAPLSIIGYIR
	 PINALSIGYAHRPI
	 PHASIYIRPLIGAN
	 jiegmhfdznycrlrt
	 */
    return 0;
}