{"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:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ebff5cdae98d2256375e9280cf68a2c5?v\u003d1714900417\" alt\u003d\"/problems/freedesserts/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eQuido has lunch in Hugo’s restaurant every day. He likes the\n restaurant because all of its prices are expressed as integers,\n and for each possible price (i.e. \u003cspan style\u003d\"width:\" class\u003d\"mbox\"\u003e$\u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e\u003c/span\u003e,\n \u003cspan style\u003d\"width:\" class\u003d\"mbox\"\u003e$\u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e\u003c/span\u003e, \u003cspan style\u003d\"width:\" class\u003d\"mbox\"\u003e$\u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e\u003c/span\u003e,\n etc.) there is at least one beverage and at least one main dish\n on the menu. Every day there are three entries printed on\n Quido’s lunch bill: the beverage price, the main dish price,\n and the total price. Hugo knows of Quido’s interest in\n computational problems and he offered Quido a free dessert each\n time his lunch bill meets the following three constraints:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003ethe bill is not identical to any of Quido’s previous\n bills,\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003ethe price of the beverage is less than the price of the\n main dish, and\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003ethe prices listed on the bill cannot mutually use the\n same digit. In essence, any digit which occurs in any of\n the entries (beverage, main dish, total) must be different\n from any of the digits of the other two entries.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eQuido is on a budget and he pays the same price for his\n lunch every day. How many times can he have a free dessert?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single line with one integer\n representing the price \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e\n which Quido pays for each lunch. The value of \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e is positive and less than\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{18}$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the maximum number of times Quido can have a free\n dessert at Hugo’s restaurant, provided that the price of his\n lunch is always \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e. Next,\n the possible bills which result in a free dessert are listed in\n ascending order with respect to the beverage price. Each bill\n consists of the price of the beverage followed by the price of\n the main dish. For simplicity, the value \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e, which is always the same, is not\n included in the bill.\u003c/p\u003e\n\n \u003cp\u003eIf there are more than \u003cspan class\u003d\"tex2jax_process\"\u003e$5\\,\n 000$\u003c/span\u003e possible bills, then output only the first\n \u003cspan class\u003d\"tex2jax_process\"\u003e$5\\, 000$\u003c/span\u003e bills (but still\n report the total number of possible bills before the list of\n bills).\u003c/p\u003e\n\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\u003e37\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n8 29\n9 28\n11 26\n15 22\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\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\u003e30014\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n85 29929\n88 29926\n785 29229\n788 29226\n7785 22229\n7788 22226\n7789 22225\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\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\u003e202020202020202058\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n7676767676767667 194343434343434391\n37373737373737397 164646464646464661\n67676767676767667 134343434343434391\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}