{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/16538888ff63d6b9e36105fa43eb9357?v\u003d1714342909\" alt\u003d\"/problems/nvwls/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eNVWLS, or “No Vowels” puzzles are popular among puzzle\n enthusiasts. For example, consider the following no-vowels\n message:\u003c/p\u003e\n \u003cpre\u003eBTWNSBTLSHDNGNDTHBSNCFLGHTLSTHNNCFQLSN\n\u003c/pre\u003e\n \u003cp\u003ewhich is inscribed on the famous “Kryptos” statue located at\n the CIA’s headquarters in Virginia. This message is derived\n from the following sentence by removing all vowels and\n spaces:\u003c/p\u003e\n \u003cpre\u003eBETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT\nLIES THE NUANCE OF IQLUSION\n\u003c/pre\u003e\n \u003cp\u003eGiven a dictionary (a set of words that can be used to\n construct a sentence) and a message (which comes from a\n sentence which uses only those words, but with all vowels and\n spaces removed), reconstruct the original sentence using the\n dictionary words!\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e denoting the number of words in\n the dictionary. The next \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines each contain a dictionary\n word using one or more uppercase English letters. Each word\n contains at least one consonant.\u003c/p\u003e\n \u003cp\u003eFor the purposes of this problem, the letters \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eI\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eO\u003c/tt\u003e, and \u003ctt class\u003d\"ttfamily\"\u003eU\u003c/tt\u003e are vowels and all other letters are\n consonants.\u003c/p\u003e\n \u003cp\u003eThe dictionary is followed by a single non-empty line of\n uppercase consonants representing the no-vowels message. It is\n guaranteed that the no-vowels message can be constructed in at\n least one way using only the dictionary words.\u003c/p\u003e\n \u003cp\u003eThe total number of letters in all dictionary words is no\n greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$100\\, 000$\u003c/span\u003e.\n The total number of letters in the no-vowels message does not\n exceed \u003cspan class\u003d\"tex2jax_process\"\u003e$300\\, 000$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a whitespace-separated sequence of dictionary words\n that yields the original no-vowels message when all spaces and\n vowels are removed. If there are multiple reconstructions,\n choose the one with the largest overall number of vowels. If\n there are still multiple reconstructions, you may output any\n one of them. No judge input will require your program to output\n more than \u003cspan class\u003d\"tex2jax_process\"\u003e$15\\, 000\\, 000$\u003c/span\u003e\n characters.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e11\nBETWEEN\nSUBTLE\nSHADING\nAND\nTHE\nABSENCE\nOF\nLIGHT\nLIES\nNUANCE\nIQLUSION\nBTWNSBTLSHDNGNDTHBSNCFLGHTLSTHNNCFQLSN\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eBETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\nNA\nNNANNA\nNANNA\nBATMAN\nNNNNNNNNNNNNNBTMN\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNA NA NA NA NA NA NA NA NA NA NA NA NA BATMAN\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}