{"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 \u003cp\u003eYou have some bags of coins. Each bag contains exactly\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e coins. Exactly one bag\n contains only counterfeit coins (we’ll call this the \u003cem\u003efake\n bag\u003c/em\u003e), while all other bags contain only real coins. All\n real coins weigh exactly the same number of grams. All\n counterfeit coins weigh exactly the same number of grams. You\n don’t know the exact weights of a real or counterfeit coin. You\n do know a counterfeit coin is strictly heavier than a real\n coin, but you do not know exactly how much heavier it is. The\n weights of the coins are positive real numbers.\u003c/p\u003e\n \u003cp\u003eYou have a scale which you can use at most \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e times. The scale has a left and\n right side. To use the scale, you can place any number of\n coins, taken from any of the bags, on each side of the scale,\n as long as the total number of coins on the left and right\n sides are exactly equal. The scale will return a single real\n number \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e. If\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e is zero, both sides of\n the scale weigh exactly the same. If \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e is negative, the left side is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$|s|$\u003c/span\u003e grams heavier than\n the right side. If \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e is\n positive, the right side is \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e grams heavier than the left side.\n Coins can be reused multiple times for different weighings, and\n you are able to keep track of which bag each coin came from.\n You must specify beforehand all weighings you want to perform\n (so you cannot adjust what gets weighed in future trials based\n on the results of previous trials). After using the scale\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e times, you would like\n to be able to determine which bag is the fake bag.\u003c/p\u003e\n \u003cp\u003eYou are now wondering: given \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e, what is the maximum number of\n bags for which you can always determine the fake bag? This\n number can get large, so output it modulo the large prime\n \u003cspan class\u003d\"tex2jax_process\"\u003e$998\\, 244\\, 353$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe single line of input contains two space-separated\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq m, k \\leq 10^6$\u003c/span\u003e), where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e is the number of\n weighings available to you and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e is the number of coins in each\n bag.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single integer, which is the maximum number of bags\n for which you can determine the fake bag in \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e weighings, modulo the large prime\n \u003cspan class\u003d\"tex2jax_process\"\u003e$998\\, 244\\, 353$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003e\u003cbr\u003e\u003c/p\u003e\n \u003ch2\u003eSample Explanation\u003c/h2\u003e\n \u003cp\u003eOne way we can use \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e\n weighings to determine the fake bag among \u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e bags, each containing \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e coin, is as follows:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOn the first weighing, put the coins from bags\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1,2,3$\u003c/span\u003e on the left,\n and the coins from bags \u003cspan class\u003d\"tex2jax_process\"\u003e$7,8,9$\u003c/span\u003e on the right.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eOn the second weighing, put the coins from bags\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1,4,7$\u003c/span\u003e on the left,\n and the coins from bags \u003cspan class\u003d\"tex2jax_process\"\u003e$3,6,9$\u003c/span\u003e on the right.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eWe can determine the fake bag as follows:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first weighing tells us which group of bags\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1,2,3)$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(4,5,6)$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(7,8,9)$\u003c/span\u003e contains the\n fake bag (e.g. if the left side is heavier, then group\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1,2,3)$\u003c/span\u003e contains the\n fake bag, if both sides are equal, then group \u003cspan class\u003d\"tex2jax_process\"\u003e$(4,5,6)$\u003c/span\u003e contains the fake bag,\n otherwise group \u003cspan class\u003d\"tex2jax_process\"\u003e$(7,8,9)$\u003c/span\u003e contains the fake\n bag).\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe second weighing will tell us which group of bags\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1,4,7)$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(2,5,8)$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(3,6,9)$\u003c/span\u003e contains the\n fake bag. The resulting fake bag can be uniquely determined\n as a result.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\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\u003e2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\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\u003e2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}