UVa 10008 – What’s Cryptanalysis
Cryptanalysis refers to the process of breaking down cryptographic writing produced by someone. This process typically involves statistical analysis of the ciphertext message. Your task is to **write a program to perform a simple analysis of the ciphertext**.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The first line of input contains a positive integer N, representing how many lines of ciphertext need to be analyzed. The next N lines each contain zero or more characters (which may include whitespace characters). | Each line contains an uppercase letter (A-Z) and a positive integer. The integer represents the number of times that character appears in the input. In the input, **uppercase and lowercase letters (e.g., A and a) are considered the same character**. When outputting, arrange the characters in descending order based on their frequency of appearance. If two or more characters have the same frequency, arrange them in ascending alphabetical order. **Note**: If a character does not appear in the input, it should not appear in the output either. |
3 This is a test. Count me 1 2 3 4 5. Wow!!!! Is this question easy? | S 7 T 6 I 5 E 4 O 3 A 2 H 2 N 2 U 2 W 2 C 1 M 1 Q 1 Y 1 |
Thought Process
Start by using a **Map to store the frequency of each character**. You can use **isalpha to determine if the current character is an English letter, and use toupper to convert lowercase letters to uppercase for the Map key**.
Next, use a for loop to iterate over the elements of the Map. Also, declare a new Map (Key: int | Value: Vector), which will store the characters that appear the same number of times. Since the task requires sorting from largest to smallest frequency, multiply the frequency by -1 and push the character into the new Map.
For output, also use an auto loop to iterate over the new Map. First, sort the vectors in the new Map. Then, iterate over the vectors in the Map and output the characters along with the current key multiplied by -1 (to restore the original frequency).
Sample Code-ZeroJudge C044: What’s Cryptanalysis
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
pair<int, char> rtn (int a, char b)
{
pair<int, char>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
string a;
getline(cin, a);
map<char, int>MAP;
for (int i = 0; i<N; i++)
{
string str;
getline(cin, str);
for (int j = 0; j<str.length(); j++)
{
if (isalpha(str[j])) MAP[toupper(str[j])]++;
}
}
map<int, vector<char>>ans;
for (auto it:MAP)
{
ans[it.second * -1].push_back(it.first);
}
for (auto it:ans)
{
vector<char>result = it.second;
int num = it.first * -1;
sort(result.begin(), result.end());
for (int i = 0; i<result.size(); i++)
{
cout << result[i] << " " << num << "\n";
}
}
}
//ZeroJudge C044
//Dr. SeanXD