Polish version    English version  
  O olimpiadzie -> Zadania -> I OI 1993/1994


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
Ten dokument nie jest dostępny w polskiej wersji językowej.

Niebieskie ksi.eczki
I Olympiad in Informatics 1993/1994

Task: ANA
Author: Wojciech Complak
Anagrams

III stage contest  

Anagrams of a given word are created by permuting its letters. For example: having the word "lame" we may switch the letters "l" and "m" to get the word "male", and next shifting the letter "e" to the second position we get the word "meal". If letters repeat in a word, then switching them does not give a new anagram.

Every dictionary, i.e. finite and nonempty sequence of words, may be partitioned into classes of anagrams. Two words belong to the same class if they are anagrams of one another.

Task

Write a program that, for a given dictionary, all words of which are written in the text file ANA.IN, finds its partitioning into classes of anagrams and writes the results to the text file ANA.OUT.

Every word of a dictionary is written in a separate line of the file ANA.IN and may be preceded and/or followed by any number of spaces or tabulation characters. Dictionary words comprise only lower case letters of English alphabet from "a" to "z" and do not contain diacritic characters.

Immediately after the last word in a dictionary there is the end of the file.

A dictionary may contain up to three thousand words, written in any order - some may recur. Every word may be up to 30 characters long. In extreme cases all words may belong to the same class or every word may form a separate class of anagrams.

We assume that data in the file ANA.IN are written faultlessly according to the above rules and your program needs not examine this.

The results should be written to the file ANA.OUT according to the following rules:

  • all the words that form one class of anagrams of the given dictionary ought to be written in one line, in alphabetical order, without repetitions, separated by a single space,
  • consecutive classes of anagrams of the dictionary should be written in consecutive lines of the file, so their first words form a sequence in alphabetical order,
  • the end of the file ought to be directly after the last word of the last class.

Example

For the file ANA.IN:

declaim
meal
meal
claimed
listen
anaconda
silent
medical
lame
male(end of file)
your program should create the following file ANA.OUT:
anaconda
claimed declaim medical
lame male meal
listen silent(end of file)

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

Your program should look for the file ANA.IN in the current directory and create the file ANA.OUT also in the current directory. The source file containing the program written by you should be named ANA.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file ANA.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk, and of the description of your algorithm and the justification of its correctness.




Wersja do druku