Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 627Accepted: 101


Kenning is a form of poetic metaphor, popular in ancient scaldic poetry, when a word is replaced by two or more words. For example, “giver of the gold” is a kenning for “warrior”. This substitution is formal, there is no semantic difference between “poor giver of the gold” and “poor warrior”. Kennings may be nested, so since “serpent’s lair” refers to “gold”, “giver of the serpent’s lair” also refers to warrior.

Imagine that you need some long text by 9:00 AM yesterday. Don’t panic, instead create the text plan and a list of kennings, and then expand the plan using the following algorithm. If the plan is long enough then stop — the text is ready. Otherwise simultaneously replace all words in the plan that have kennings with the corresponding kenning bodies and repeat the algorithm again.


The first line of the input file contains three integer numbers: the width of the resulting text w (1 ≤ w ≤ 255), the minimal number of non-whitespace symbols in the resulting text l (1 ≤ l3 000), and the kennings list length n (1 ≤ n ≤ 380). The kenning list follows, a kenning per line. Each line contains the kenning referent followed by the kenning body. The text plan ends the file.

Each kenning body contains at least two words. Kennings may be recursive, like in replacing “GNU” with “GNU is Not UNIX”. The kenning referents are case and grammatical form sensitive, so words “warrior”, “Warrior” and “warriors” are different and may be referred by different kennings. The input file is not longer than 3 000 bytes, and contains only English letters, underscores, spaces, line feeds and digits (in the first line only). There are no two kennings with equal referents. All words have w symbols at most. Adjacent words are separated by exactly one space or line feed. No line has leading or trailing spaces.


If the algorithm doesn’t terminate, output just words “No result” in the only output line. Otherwise output the algorithm result, a text with at most w characters (including spaces) per line. All line feeds from the original plan must be preserved, line feed must be inserted before a word if the word does not fit into the previous line. Adjacent words in a line must be separated by exactly one space. The lines must not have leading or trailing spaces. Correct output file will not be longer than 10 000 bytes.

Sample Input

21 103 7
king hosts leader
vessel windless bay of horns
horns bulls spears
spears war needles
Sudden Fate catched
death_of doomed to death
Death It was the end
death_of Fjolner
in the house of Frodi
of the king
in the vessel

Sample Output

Fate catched
doomed to death
in the house of Frodi
It was the end
of the hosts leader
in the windless bay
of bulls spears


Northeastern Europe 2006, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator