cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2011 · MediumArrays and counting

Letter Frequency Histogram

Autumn Tournament (2011)

Submission name: frequency.cpp

Problem summary

Read text until the terminator @. Count Latin letters without distinguishing uppercase and lowercase. Print a vertical histogram: each column contains copies of its uppercase letter, above a separator of 26 hyphens and the alphabet.

Input

Any number of text lines ending at the first @.

Output

Histogram rows from highest to lowest, followed by -------------------------- and ABCDEFGHIJKLMNOPQRSTUVWXYZ. Column 1 corresponds to A, column 26 to Z; empty cells are spaces.

Constraints

The source does not specify a text-length bound. Process the text incrementally until @; ignore non-Latin-letter characters.

Worked example

Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.

Input

Tova e samo 1 malak PRIMER.
VNIMAVAJTE!@

Output

A
A
A           M
A   E       M        V
A   E   I   M O R T  V
A   E   IJKLMNOP RST  V
--------------------------
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Solution analysis

  1. Use a 26-element frequency array. Read every character, including whitespace, with cin.get. Convert ASCII uppercase and lowercase letters to indices 0 through 25; ignore punctuation, digits and line breaks. Stop before counting @.
  2. Let height be the maximum frequency. For each level from height down to one, put letter A+i in column i if its count is at least that level; otherwise put a space. Removing trailing spaces does not change any column alignment.
  3. In the sample A occurs six times, M four times, E and V three times, and I, O, R and T twice. The highest two rows therefore contain only A. Lower rows gradually introduce the other letters. Finally print the separator and alphabet.

Why it works

Every input letter increments exactly its case-insensitive column. Column i is filled on precisely frequency[i] levels, so its height equals the required number of occurrences. Printing levels in descending order aligns the histogram above its labels.

Complexity: O(T + 26H) time for T input characters and histogram height H. O(26) counters and one 26-character output row are used; no copy of the input is stored.

Watch out. Do not use operator>> for a single whitespace-delimited word: the text can span lines. Do not count @ or punctuation. Preserve leading and internal spaces in histogram rows. No letters means only the separator and alphabet are printed.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<array>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    array<long long,26>frequency{};
    char symbol;
    while(cin.get(symbol)&&symbol!='@'){
        if(symbol>='a'&&symbol<='z'){
            ++frequency[symbol-'a'];
        }
        else if(symbol>='A'&&symbol<='Z'){
            ++frequency[symbol-'A'];
        }
    }
    long long height=*max_element(frequency.begin(),frequency.end());
    for(long long level=height;level>=1;--level){
        string row(26,' ');
        for(int i=0;i<26;++i){
            if(frequency[i]>=level){
                row[i]=static_cast<char>('A'+i);
            }
        }
        // Omit insignificant trailing spaces, preserving all columns.
        while(!row.empty()&&row.back()==' '){
            row.pop_back();
        }
        cout<<row<<'\n';
    }
    cout<<"--------------------------\nABCDEFGHIJKLMNOPQRSTUVWXYZ\n";
}

Source: Arena Olimpiici ↗