FRIKTORIES

The ancient Greeks did not only leave behind an incomprehensible intellectual legacy with their theoretical works, but also a technological civilization that, if utilized, would have given us incomparably greater capabilities today. Their construction wonders, such as the Athenian odometer, Hero's steam engine, the Antikythera mechanism, Archimedes' machines, etc., are some of their many valuable creations. Equally important were their achievements in communication. Using optical digital communications from the 12th century BCE, they transmitted the message of victory from Troy to Mycenae within a couple of days. From the middle of the 9th century BCE, they used the encoding of the Greek alphabet (Cadmean writing) to transmit texts with optical encoding in Cartesian coordinates! The astonishing part is that they encoded the alphabet based on the entropy of each letter. In the table below, you can see an example of such encoding, where the letter M corresponds to three horizontally and three vertically lit torches.

The basic principle of this encoding is for the letters to be sorted in descending order of their appearance frequency. Letters with the highest frequency will require the illumination of fewer torches, and conversely, those with the lowest frequency will require more.

Problem:

Develop a program in one of the IOI languages that: will take texts in Greek and after counting how many times each character appears (Greek uppercase & space), it will display them in descending order of appearance, displaying the corresponding frequency of appearance to achieve better encoding.

Input Files:

The input files with the name friktories.in are text files with the following structure: They have at least one line with a Greek text (~64 - 1\,000\,000~ characters). Each character corresponds exactly to one byte.

Output Files:

The output files with the name friktories.out are text files with the following structure: They have exactly 25 lines, and each line contains a character from the most frequently occurring (1st) to the least frequently occurring (25th). After each character, a space character is inserted, followed immediately by its frequency of occurrence (i.e., how many times it appeared in the text). If two characters have the same frequency of occurrence, they are sorted in alphabetical order. (The space character is considered the 25th).

Note 1: Students should be aware that the input and output files consist only of characters with ASCII encoding. According to this: space_character: 32, Α: 128, Β: 129, ..., Ω: 151. No other encoding such as UTF-7, UTF-8, etc., can be used. Punctuation marks (, ' . ) and any other character (e.g., EOL, etc.) are ignored.

Note 2: Since the number of lines in the file is not given, an end-of-file check should be performed. Below is an example of how the file can be read (up to its end) in various programming languages.

Pascal

while not eof(fin) do
begin
    read(fin,c); 
    .....
end;

C / C++ (stdio library)

while(fscanf(fin,"%c",&c)==1) {
    ....
}

C++ (fstream library)

while(fin>>c) {
    ...
}

In C++, it is preferable to use the stdio library instead of the fstream library, as it is faster.

Examples of Input - Output Files:

1ο

STDIN (friktories.in)

ΜΗΝΙΝ ΑΕΙΔΕ ΘΕΑ ΠΗΛΗΙΑΔΕΩ ΑΧΙΛΗΟΣ
ΟΥΛΟΜΕΝΗΝ, Η ΜΥΡΙ ΑΧΑΙΟΙΣ ΑΛΓΕ ΕΘΗΚΕ, ΠΟΛΛΑΣ
Δ ΙΦΘΙΜΟΥΣ ΨΥΧΑΣ ΑΙΔΙ ΠΡΟΙΑΨΕΝ ΗΡΩΩΝ,

STDOUT (friktories.out)

  17
Ι 12
Α 11
Ε 9
Η 8
Ο 7
Λ 6
Ν 6
Σ 5
Δ 4
Μ 4
Υ 4
Θ 3
Π 3
Ρ 3
Χ 3
Ω 3
Ψ 2
Γ 1
Κ 1
Φ 1
Β 0
Ζ 0
Ξ 0
Τ 0

Homer Iliad, Rhapsody A, verses 1-4

Translation: Μούσα, τραγουδά το θυμό του ξακουστού Αχιλλέα, τον έρμο! π'όλους πότισε τους Αχαιούς φαρμάκια, και πλήθος έστειλε ψυχές λεβέντικες στον Άδη

Translation by Alexandros Palis (From http://el.wikisource.org/wiki/)

("Sing, Muse, the wrath of the renowned Achilles, the wrath that caused endless pain to the Achaeans, the wrath that sent many strong souls of warriors to the Underworld.")

2ο

STDIN (friktories.in)

ΞΡΩΜΕΘΑ ΓΑΡ ΠΟΛΙΤΕΙΑ ΟΥ ΖΗΛΟΥΣΥ ΤΟΥΣ ΤΩΝ
ΠΕΛΑΣ ΝΟΜΟΥΣ ΠΑΡΑΔΕΙΓΜΑ ΔΕ ΜΑΛΛΟΝ ΑΥΤΟΙ
ΟΝΤΕΣ ΤΙΣΙΝ Η ΜΙΜΟΥΜΕΝΟΙ ΕΤΕΡΟΥΣ. ΚΑΙ ΟΝΟΜΑ
ΜΕΝ ΔΙΑ ΤΟ ΜΗ ΕΣ ΟΛΙΓΟΥΣ ΑΛΛ' ΕΣ ΠΛΕΙΟΝΑΣ
ΟΙΚΕΙΝ ΔΗΜΟΚΡΑΤΙΑ ΚΕΚΛΗΤΑΙ ΜΕΤΕΣΤΙ ΔΕ ΚΑΤΑ
ΜΕΝ ΤΟΥΣ ΝΟΜΟΥΣ ΠΡΟΣ ΤΑ ΙΔΙΑ ΔΙΑΦΟΡΑ ΠΑΣΙ ΤΟ
ΙΣΟΝ, ΚΑΤΑ ΔΕ ΤΗΝ ΑΞΙΩΣΙΝ, ΩΣ ΕΚΑΣΤΟΣ ΕΝ ΤΩ
ΕΥΔΟΚΙΜΕΙ, ΟΥΚ ΑΠΟ ΜΕΡΟΥΣ ΤΟ ΠΛΕΟΝ ΕΣ ΤΑ
ΚΟΙΝΑ Η ΑΠ' ΑΡΕΤΗΣ ΠΡΟΤΙΜΑΤΑΙ, ΟΥΔ ΑΥ ΚΑΤΑ
ΠΕΝΙΑΝ, ΕΧΩΝ ΓΕ ΤΙ ΑΓΑΘΟΝ ΔΡΟΣΑΙ ΤΗΝ ΠΟΛΙΝ,
ΑΞΙΩΜΑΤΟΣ ΑΦΑΝΕΙΑ ΚΕΚΩΛΥΤΑΙ ΕΛΕΥΘΕΡΩΣ ΔΕ ΤΑ
ΤΕ ΠΡΟΣ ΤΟ ΚΟΙΝΟΝ ΠΟΛΙΤΕΥΟΜΕΝ ΚΑΙ ΕΣ ΤΗΝ ΠΡΟΣ
ΑΛΛΗΛΟΥΣ ΤΩΝ ΚΑΘ' ΗΜΕΡΑΝ ΕΠΙΤΗΔΕΥΜΑΤΩΝ
ΥΠΟΨΙΑΝ, ΟΥ ΔΙ ΟΡΓΗΣ ΤΟΝ ΠΕΛΑΣ, ΕΙ ΚΑΘ' ΗΔΟΝΗΝ
ΤΙ ΔΡΑ, ΕΧΟΝΤΕΣ, ΟΥΔΕ ΑΖΗΜΙΟΥΣ ΜΕΝ, ΛΥΠΗΡΑΣ ΔΕ
ΤΗ ΟΨΕΙ ΑΧΘΗΔΟΝΑΣ ΠΡΟΣΤΙΘΕΜΕΝΟΙ. ΑΝΕΠΑΧΘΩΣ
ΔΕ ΤΑ ΙΔΙΑ ΠΡΟΣΟΜΙΛΟΥΝΤΕΣ ΤΑ ΔΗΜΟΣΙΑ ΔΙΑ ΔΕΟΣ
ΜΑΛΙΣΤΑ ΟΥ ΠΑΡΑΝΟΜΟΥΜΕΝ, ΤΩΝ ΤΕ ΑΙΕΙ ΕΝ ΑΡΧΗ
ΟΝΤΩΝ ΑΚΡΟΑΣΕΙ ΚΑΙ ΤΩΝ ΝΟΜΩΝ, ΚΑΙ ΜΑΛΙΣΤΑ
ΑΥΤΩΝ ΟΣΟΙ ΤΕ ΕΠ ̓ ΩΦΕΛΙΑ ΤΩΝ ΑΔΙΚΟΥΜΕΝΩΝ
ΚΕΙΝΤΑΙ ΚΑΙ ΟΣΟΙ ΑΓΡΑΦΟΙ ΟΝΤΕΣ ΑΙΣΧΥΝΗΝ
ΟΜΟΛΟΓΟΥΜΕΝΗΝ ΦΕΡΟΥΣΙΝ.

STDOUT (friktories.out)

 156
Α 89
Ο 84
Ε 71
Ι 70
Ν 62
T 57
Σ 51
Μ 34
Υ 34
Δ 25
Λ 25
Ρ 25
Η 24
Κ 24
Π 24
Ω 20
Γ 8
Θ 8
Χ 6
Φ 5
Ξ 3
Ζ 2
Ψ 2
Β 0

Thucydides' Funeral Oration for Pericles (Historiae 2, §37)

Translation: Έχουμε δηλαδή πολίτευμα, το οποίο δεν αντιγράφει τους νόμους άλλων, μάλλον δε εμείς οι ίδιοι είμαστε υπόδειγμα σε μερικούς παρά μιμούμαστε άλλους. Και ονομάζεται μεν δημοκρατία, γιατί η διοίκηση είναι στα χέρια των πολλών και όχι των ολίγων. Όλοι έχουν τα ίδια δικαιώματα έναντι δε των νόμων στις ιδιωτικές τους διαφορές, ενώ ως προς την θέση τους στον δημόσιο βίο κάθε ένας, ανάλογα με την επίδοση σε κάποιο τομέα, προτιμάται για ένα από τα δημόσια αξιώματα, και όχι από την πολιτική του παράταξη όσο από την αρετή του, ούτε εξαιτίας της φτώχειας, ενώ έχει την ικανότητα να παράσχει κάποια υπηρεσία στην πατρίδα του, εμποδίζεται από το γεγονός ότι είναι άγνωστος. Ζούμε ελεύθερα, και ως πολίτες στον δημόσιο βίο και ως άτομα στον ιδιωτικό, στις επιδιώξεις μας της καθημερινής ζωής, κατά τις οποίες δεν κοιτάμε ο ένας στον άλλον με καχυποψία, δεν θυμώνουμε με τον γείτονά μας, όταν κάνει σύμφωνα με την ευχαρίστησή του, ούτε παίρνουμε μια φυσιογνωμία σκυθρωπή, η οποία μπορεί να μην βλάπτει τον άλλο, πάντως όμως είναι δυσάρεστη. Ενώ δε στην ιδιωτική μας ζωή συναναστρεφόμαστε χωρίς να ενοχλεί ο ένας τον άλλον, στην δημόσιά μας ζωή από σεβασμό προ πάντων δεν παραβαίνουμε τους νόμους, υπακούμε σε όσους κάθε φορά έχουν τα αξιώματα και στους νόμους, και περισσότερο σε εκείνους από τους νόμους, που έχουν θεσπιστεί για ωφέλεια των αδικούμενων, και σε άλλους, οι οποίοι αν και άγραφοι, η παράβασή τους φέρνει πανθομολογούμενη ντροπή.

Translation by Vasileios Symeonidis. (From http://users.sch.gr/symfo/sholio/arhea/epitafios_mtfr.htm )

("We have a political system that does not copy the laws of others; rather, we ourselves serve as an example to some instead of imitating others. It is called democracy because governance is in the hands of the many and not the few. Everyone has the same rights in their private disputes, while in their position in public life, each person, depending on their performance in a particular field, is preferred for one of the public offices, not because of their political affiliation but because of their virtue, and neither poverty nor not being known enough should hinder them.

We live freely, both as citizens in public life and as individuals in private life, pursuing our daily lives without looking at each other with suspicion, without getting angry with our neighbor when they act according to their pleasure, and without wearing a scowling expression that may not harm others but is unpleasant nonetheless. In our private lives, we interact without bothering each other, and in our public life, out of respect above all, we do not violate the laws, obey those who hold the offices at any given time, and especially those laws established for the benefit of the wronged. We also obey unwritten laws that, their voilation, is universally acknowledged as shameful.")