ZeroJudge D671: Digital Fortress

UVa 11716 – Digital Fortress

The previous IIUPC had a question titled "The Da Vinci Code," which was based on Dan Brown's bestselling novel "The Da Vinci Code." This question, however, is based on the science fiction thriller "Digital Fortress." You are given a ciphertext, and you must use the decoding method described below to decrypt it.

For example, if the ciphertext is:
WECGEWHYAAIORTNU
Then the output would be:
WEAREWATCHINGYOU

In the example given, the ciphertext "WECGEWHYAAIORTNU" contains 16 characters, which is 4 squared. Please arrange these characters into an NN (in this case, 44) grid in a "row-major" order (filling the first column, then the second column, and so forth). The grid after arranging the ciphertext in this manner is as follows:
W E C G
E W H Y
A A I O
R T N U

When we extract the characters from the grid above in a "column-major" order (taking the entire first column, then the second column, and so on), we obtain the following plaintext:
「WEAREWATCHINGYOU」

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of input contains a number T, followed by T test cases. Each test case consists of a single line containing the ciphertext to be processed. The ciphertext consists only of uppercase letters and spaces. The total number of characters in the ciphertext will not exceed 10,000.For each test case, please output the plaintext on a single line.If the number of input characters is not a perfect square, please output "INVALID".
3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS		WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

Thought Process

After reading the integer T, you should use cin.ignore() before using getline() to handle strings containing whitespace characters.

First, check if the length of the string is a perfect square. If pow(sqrt(string_length), 2) equals the string length, it means the length of the string is a perfect square.

You can declare a Vector to store the processed strings, and declare a variable square as the square root of the string length. Run two nested for loops up to square, and initialize a count variable to 0. Each time, add string[count] to a temporary string and increment count. Every time the inner for loop ends, push_back the temporary string to the Vector.

When outputting, you should also run two nested for loops up to square. Let's call the outer loop the j loop and the inner loop the k loop. Each time in the k loop, output Vector[k][j]. After the outer loop ends, print a newline and then it is done.

Sample Code－ZeroJudge D671: Digital Fortress

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    cin.ignore();
    for (int i = 0; i<N; i++) {
        string str;
        getline(cin, str);
        const int len = int(str.length()), square = int(sqrt(len));
        if (pow(square, 2) != len) {
            cout << "INVALID\n";
            continue;
        }
        vector<string>v;
        int count = 0;
        for (int j = 0; j<square; j++) {
            string tmp = "";
            for (int k = 0; k<square; k++) {
                tmp += str[count];
                count++;
            }
            v.push_back(tmp);
        }
        for (int j = 0; j<square; j++) {
            for(int k = 0; k<square; k++) cout << v[k][j];
        }
        cout << "\n";
    }
}

//ZeroJudge D671
//Dr. SeanXD
Tags

Related Posts

Comments