{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003ch5\u003eIOI \u002708 - Cairo, Egypt\u003c/h5\u003e\n\u003cp\u003eYou need to print \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e words on a movable type printer. Movable type\nprinters are those old printers that require you to place small metal\npieces (each containing a letter) in order to form words. A piece of\npaper is then pressed against them to print the word. The printer you\nhave allows you to do any of the following operations:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eAdd a letter to the end of the word currently in the printer.\u003c/li\u003e\n\u003cli\u003eRemove the last letter from the end of the word currently in the\nprinter. You are only allowed to do this if there is at least one\nletter currently in the printer.\u003c/li\u003e\n\u003cli\u003ePrint the word currently in the printer.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eInitially, the printer is empty; it contains no metal pieces with\nletters. At the end of printing, you are allowed to leave some letters\nin the printer. Also, you are allowed to print the words in any order\nyou like.\u003c/p\u003e\n\u003cp\u003eAs every operation requires time, you want to minimize the total number\nof operations.\u003c/p\u003e\n\u003cp\u003eYou must write a program that, given the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e words you want to print,\nfinds the minimum number of operations needed to print all the words in\nany order, and outputs one such sequence of operations.\u003c/p\u003e\n\u003ch4\u003eInput Specification\u003c/h4\u003e\n\u003cp\u003eYour program must read from the standard input the following data:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eLine 1 contains the integer \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/de4e8e7b002771ca8c04ec6d1daec008?v\u003d1716007911\" style\u003d\"vertical-align: -0.838ex; width:17.432ex; height:2.843ex;\" alt\u003d\"(1 \\le N \\le 25\\,000)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le N \\le 25\\,000)~\u003c/span\u003e\u003c/span\u003e, the number\nof words you need to print.\u003c/li\u003e\n\u003cli\u003eEach of the next \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e lines contains a word. Each word consists of\nlowercase letters (\u003ccode\u003ea\u003c/code\u003e - \u003ccode\u003ez\u003c/code\u003e) only and has length between 1 and 20,\ninclusive.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eAll words will be distinct.\u003c/p\u003e\n\u003ch4\u003eOutput Specification\u003c/h4\u003e\n\u003cp\u003eYour program must write to the standard output the following data:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eLine 1 must contain an integer \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/09364895aecdedfd8cb6f510534a1e89?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.442ex; height:2.176ex;\" alt\u003d\"M\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M~\u003c/span\u003e\u003c/span\u003e that represents the minimum\nnumber of operations required to print the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e words.\u003c/li\u003e\n\u003cli\u003eEach of the next \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/09364895aecdedfd8cb6f510534a1e89?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.442ex; height:2.176ex;\" alt\u003d\"M\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M~\u003c/span\u003e\u003c/span\u003e lines must contain one character each. These\ncharacters describe the sequence of operations done. Each operation\nmust be described as follows:\u003cul\u003e\n\u003cli\u003eAdding a letter is represented by the letter itself in lowercase\u003c/li\u003e\n\u003cli\u003eRemoving the last letter is represented by the character \u003ccode\u003e-\u003c/code\u003e\n(minus, ASCII code 45)\u003c/li\u003e\n\u003cli\u003ePrinting the current word is represented by the character \u003ccode\u003eP\u003c/code\u003e\n(uppercase letter P)\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3\nprint\nthe\npoem\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\nt\nh\ne\nP\n-\n-\n-\np\no\ne\nm\nP\n-\n-\n-\nr\ni\nn\nt\nP\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003e\u003cstrong\u003eNote\u003c/strong\u003e: In test cases worth a total of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/195f6fc0860bceea6b445d71943566e4?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:4.261ex; height:2.343ex;\" alt\u003d\"40\\%\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~40\\%~\u003c/span\u003e\u003c/span\u003e of the points, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e will not\nexceed \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e5d5b5307e772b87470a4a2a5c64395f?v\u003d1716007911\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"18\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~18~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}