Polish version    English version  
  History of OI -> II OI 1994/1995 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
Stage III - results
Stage I - results
Problems
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: PAL
Author: Wojciech Rytter
Palindromes

I stage contest  

A word is a palindrome if and only if it remains the same when read backwards. A palindrome is even if it has an even positive number of letters.

The word abaaba is an example of an even palindrome.

An even palindrome decomposition of a word is its division into separate parts, every one of which is an even palindrome.

Example

For the word
bbaabbaabbbaaaaaaaaaaaabbbaa
the following are even palindrome decompositions:
bbaabb aabbbaaaaaaaaaaaabbbaa
and
bb aa bb aa bb baaaaaaaaaaaab bb aa

The first decomposition consists of the least possible number of even palindromes, and the second one is a decomposition having the maximal possible number of even palindromes.

Notice that a word might have many different even palindrome decompositions or might have no such a decomposition.

Task

Write a program that:
  • reads a word from the text file PAL.IN and examines whether it can be decomposed into even palindromes,
  • if not, then the program writes to the file PAL.OUT only one word NIE ("no"),
  • if the word can be decomposed, then the program writes the decompositions of the word into the minimal and maximal number of even palindromes.

Input

The input file PAL.IN contains one word consisting of at least 1 and at most 200 small letters of English alphabet. The word is written in one line with no spaces between letters.

We assume that the given word is written correctly in the file PAL.IN, and your program need not verify that.

Output

The output file PAL.OUT should contain:
  • only one word NIE
or
  • in the first line - a sequence of words separated by spaces, forming a decomposition of the given word into the minimal number of even palindromes
  • in the second line - a decomposition of the given word into the maximal number of even palindromes

Examples

For the file PAL.IN:
bbaabbaabbbaaaaaaaaaaaabbbaa
your program should create the following file PAL.OUT:
bbaabb aabbbaaaaaaaaaaaabbbaa
bb aa bb aa bb baaaaaaaaaaaab bb aa
For the file PAL.IN:
abcd
your program should create the file PAL.OUT:
NIE
For the file PAL.IN:
abaaba
your program should create the file PAL.OUT:
abaaba
abaaba

Your program should look for the file PAL.IN in the current directory and create the file PAL.OUT also in the current directory. The source file containing the program written by you should be named PAL.???, 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 PAL.EXE.




Print friendly version