Problem:


Score : 300 points

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Sample Input 1

127

Sample Output 1

4

By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Runtime Error

Solution code:
import zlib
sol=b"x\x9c\xed\x9dm\x8f\xe36\x0c\x84\x7fk\xaf\xed%\x96\xb7\xbd\xeb\xff\xffR\xc1\xc1\x12\x01\xb8\x1e\xd8c.3\x8a\x08\x18\x0b\xc3\xd4\x0bE=\x19\xcbT6\xfe\xe3\xc7\x9f\x7f\xfd\xfd\xb3\xff\xe9G?{\x1c\xfd\xca\xe3\xf8\xfb\xe7\xad\x1f[\x91\xdb\x97\xa6~\xfc\xbc\xdd\xfb\xb1\x15\xb9?\x9a\xda+\xdcOz\x99\x87\xf5Q\xd8\xb7\xd3On\xf7\xe5a\xed\'g\x0b\x9bI\xc4\x8d~\xf4+\x0f\xeb}i\x0fk?9[\xd8L"n\xf4\xa3_yX\x97\xb6>\xac\xfd\xe4la3\x85\xbbq\nZo\xb2..\x02`&k\xf0=\x000\x93M\x81\x1a\x00\x9c\x1b"\xd8\x80\xb1\x9f\xea\xfd\x88\xcfV\xd8\x84\xd17h\xbd\x1f\xf1\xd9\x17\xf6S`\x91\xb7\x01r\x00\x84\xbb\x01\xb0\xf1\x85\xcd\xd4\x8fnzX\xdb\xfa\xf1\xcc\x18\xc7a\xb8\x1b\x1c6\xbe\xf7\xef\xd3\x8dS\xbd\xab\x01`q\xf6\'"\x00\xf8.@a3\x89`\x03"\xa6\x8f\r0Y\x9c\xa3\x00\x08\xa7\x17`\x03L\xfd\xa4\x13\xf5\x8c\xd6\x91Z\x80C\xae\x96\xb9\xe1O8l@\x10\xb8\x8f\xb9\xf7\xd9\x86\x93\x89\r\xa7\x1bC\x03\xe0\x1d\xebG\xbf\xd2\x0f`\x12\xc1\x06\xc4yhl\xc0\x14db\xe3{\xbf\x88\xcdf\xf9\xe7\xb9\x9d\x97\xd42\x93]\xe9\'\xfdJ?\xe1\xb0\x01A\xe0\xc4\x01\xf8\x9c\x89\r\x08&\x07\x80\xc5\xd9O\x81\x08\x00\xde\xd4\x8f~\xa5\x1f\xc0$\x82\r\x18\xce\xd0\xd8\x80)\x18\x1a\x9b\xcd\xf2\xefs;/\xa9e&\xbb\xd2O\xfa\x95~\xc2a\x03\x82\xc0\x89\x03\xf09\x13\x1b\x10L\x0e\x00\x8b\xb3\x9f\x02\x11\x00\xbc\xa9\x1f\xfdJ?\x80)\x1c\x1b\xfd\x84\xe4\xd0y\xec\xdb\xfeb\x9b[\x99\x8b\xb8\x01n\x9a\xdc\x1d6\xdc\r\x91\xcc\x92\x7f\xa8y\x0f\x00n\xfb\x0f5\x99\x00L(_"\xfb)\xdc\x13\xbd\x88\x1b\x1e\xda#"\xe3\x0b\x1f\xa1\x97scB\xf9\xca\x04\xe0Fe\xa43\x01\xe0\xdc\x10\xc1\x06\x90\xa0\xbf\x9f\xc2\xcd\x17\xd7\xa0\x08\xbd\xf7\xfd<6\xd7`\xb8\x1b"\x89q\xef\xb3\r\xe7T\xef\x17\x01\x08\xd7\r}\x00\xac\x96\x15^\x0e$\x16D\xb0\xf1\x03\x1c\x08\x1b`Z\xa23\x9c\x99\xd8pDe\xd6Z>\x13J\xfe\x84\xc3\x06\x04\xe1\x14\xb4\xde\xe4\x87\x93\x89\r\x08&\x07\xc0\xa2\xb1\x9f\x02\x00\xf0\x8e\xb5\xdaOy56`\n2\xb1\xf1\xbd_\xc4f\xb3\xd4~J\xed\xa7\xd4~\xca\xb7`\x03\x86\xa3\xffD?t\x1e\x1b\xdc\xad\xb8[\x9b\x88\x1b`\xa9\xc6!\x1a~\xa3\x17y4\xf3\xab\x82\xf7\x00\xe0\xbe\xbf*\xe0\xd66\x9c\x1b\x13\xca\x97HB\x92[\x12\x8b\xb8\xe1\xa1="2\xbe\xf0\x11z97&\x94\xafL\x00\xeeTJ\'\x1c\x80\x92\xaf\x19\xe4\xcb\xda\xf1\'C\xd3\x0b\xdc(\xf9\x9aA\xbe\xc2\xdd\x10\xc1\x06\x90\xa0\xbf\x9f\x02\xe6\x0bL\x01\xd7\xa0\x086\xcb~\x1e\x9bk0\xdc\r\x91\xc4\xb8\xf7\xd9\x86s\xaa\xf7\x8b\x00\x80`\xbe+\x00V\xcb\n\xb7\x03\tI\x11l\xfc\x00\x07\xc2\x06\x98\x9a\xc6~\n\x87\rGTf\xad\xf6\x99m\xf6\'\x1c6 \x08\xa7\xa0\xf5&?\x9cLl@09\x00\x9a\xc6~\n\x00\xc0;\xb6\xbe\xc5~J86\xfaK\xe2\xf0\'\xa9L7\xc0tslpn\x80\xa5\x1a\xe7\x06\xd0:N7\xc2\xdd\x10Y\xdbx5~\t\x00\x1c\x87\x99lp}M(_"O\xf4\xdcRD\xc4\r\x0e\xd1\xe5S\xb5\x16\xb7\x14\t_\x98M(_\x99\x00,\xd1\xcfD\x9c\x1b%_3\xc8\x97\xb5\xe3O2\xe9\xf5"s\x91^\xe0F\xc9\x97\xa0|\x85\x03P\xf2U\xf25.\xbd\xc0\x8d\x92\xaf\x19\xe4+\xdc\r\x11l\x00\t\xfa\xfb)`\xbe\xc0\x14p\r\x8a`\xd3\xf6\xf3\xd8\\\x83\xe1n\x88$\xc6\xbd\xcf6\x9cS\xbd_\x04\x00\x04\xf3]\x01\xb0ZVx\xfd\xdc4\xd9,\xbf\x9e\x0b\xaf\x13\xef\xa7\x84c\xa3\x7fO\t_\x8ad\xba\x01\xd8\x00\x85A_\x9c\x1b@\xebN\xf9|Q\x01@-\xce\r\x7f\xa5\x8dsO\xe1\x86\xcc\xb1\x01\xe2\x1c\xce\x06\x98\x14\x0e\x80\x92\xaf\xe7\xea"KbN\x01878D\x81\x1b\x00QoZ\x0f,E\xc2\xdd\x98P\xbe\xc29\x0c\x97/\xc0\x06\x07@\xc9\xd7\x0c\xf2e\xed\xf8\x93\xa1\xe5\xab\x8d\xfcD\xaf/_\\\xe4\x01\x00%_%_\x84\x1b\xe1\xf2\xc5\xd1\xdbJ\xbe\xe6\x96\xafp\x00J\xbeJ\xbe\xc6\xa5\x17\xb8Q\xf25\x83|\x85\xbb!\x82\r \x81\xcbp\x8a`\x03\xa6\x004(rO\x01\x93\x12.\xe6\xe1np\xd8p\xf2\xc5)\x1b\x17\xc3L\xdd\x00\xa6~\xd2y~\x06\xfbH\xadL\x00\xc0\x00\x9b\x93A\x1b\xc5\xd0\xfb)`\n8l\x80\x1b`\x96\xf5\xef)C/E<\xb4G&\x85\x93\xafp6\xbc\xcfGt\x83\xab\xc55h\xa6\xd5i\x1d\'\x0e\xc0\xb1p\xf9\xe2\x14\x9bc\x03\xc4\x99c\x03x\x08&\x85\x03\xa0\xe4k,\xf9\x02\x1fX\x11\xf9\x02\x88zS?\xfa\x95\xc7\xc5\x7f\x7f\xfd~.l\xa6\x92\xaf\x83\xc1\xcc\xe40\\\xbe\x00\x1b\x1c\x00%_3\xc8\x97\xb5\xe3O\x86\x96/k\xc7\x9f\x94|}+\x87 \xf2\x00\x80\x92\xaf\x92/\xc2\x8dp\xf9\xe2\xe8]K\xbe\xe6\x96\xafp\x00J\xbef\x90/\x91I\x01\x1f\xcf\xf0hd\xee\xa7\x80!{\x9f\x8f\x0c\x19\x98\x86\xbe\x7f\x01S8\x00\x1c\x87"w=\x00\x12\x97\xe1\x14\x91/\x0f\x80M\x01hpB\xf9\n\x9f\x14\x0e\x1b0\x83\x9c|\x81hd\xd6Z\xa3\xe5k\xb3|\xbd0\x03\xb529\x04\x03\xf4>\xdbp\x86\xdeO\x01S\x10._`\x96E\xee)\xe1\xd8\x88\xdcS\xc0g\x10LJ\xb8|qlx\x9f\xbfOm\xb8\x06\xcddW\xfaI\xbf\x82\xe5\xebH0\xbdc\xe1\xf2\x05\x86l\xa3\xf0\x03\xe4\xd8\x00q\xe6\xd8\x00\x1e\x82I\xe1\x00(\xf9\x1aK\xbe\xc0\x07VD\xbe\x00\xa2\xde\xd4\x8f~\xe5q\xf1\xd7\xef\xff\x9e\x0b\x9b\xa9\xe4\xeb`039\x0c\x97/\xc0\x06\x07@\xc9\xd7\x0c\xf2e\xed\xf8\x93\xa1\xe5\xcb\xda\xf1\'%_\xdf\xca!\x88<\x00\xa0\xe4\xab\xe4\x8bpCdR\xc0\xc73<\x1a\x99\tI0d\xef\xf3\x91!\x03\x93\xc8\xfd\xebCC\xbe~l/`\xee\x7f\xfa\xf1x\x0b\xb3\x7f\x11\xf3\xa9w4\x83\xc2\xf6\xbe\xe3S\xefh\xe6^\xe8,\xe2\x86\xed\xda\xdf\xdc\xefl\x87\xbfW:\xd3\r\xbb\xd9\xdd\xdd\xff\x0f\x86\xff\x9e9\xe7\x86\xc8\x8b\xc5\x7f\xba\xdf`\x7f\x0f\x00n\xee\x7f\xff\xd5\x00\xe0\xdc\x10\xc1\x06\x8c\x9d{\xa3\x81\xfe\xfb\xe89\x00\xf4\xdf\x83\xc0q\x18\xee\x86\xc8\x8b0\x80np?\xa5"\x02\x80\xc5\xd9\x9f\x88\x00\xe0\xbb\x00\x85\xcd$\x82\r\x88\x98>6\xc0dq\x8e\x02 \x9c^\x80\r0-\xfb_\xfb\xe18\xe4j\x99\x1b\xfeD\xe4\x87\x9b\xbc\xcf6\x9cLl8\xdd\x18\x1a\x00\xefX;\x90\xaf\x13\xc1\x06\xc4yhl\xc0\x14db\xe3{\xbf\x88\xcdf\xf9:e\x9aY\xcbL\xcd\xe5\xeb8l@\x108q\x00>gb\x03\x82\xc9\x01\xd0\xf6\xb3\xc4"\x00x\xd3\xba\x9f\xe65\x93\x086`8Cc\x03\xa6`hl6\xcb\xeb\xbffl\xa6\xd5\xe5\xf99l@\x108q\x00>gb\x03\x82\xc9\x01\xb0\xee\xef\x9e\x88\x00\xe0M\x1f\x07v\x97\xc2\xb1\xd1OH\x0e\x9d\xc7\xbe\xef/\xb6\xb9\x95\xb9\x88\x1b\xe0\xa6\xc9\xdda\xc3\xdd\x10\xc9,\xf9\x87\x9a\xf7\x00\xe0\xbe\xffP\x93\t\xc0\x84\xf2%\xb2\x9f\xc2=\xd1\x8b\xb8\xe1\xa1="2\xbe\xf0\x11z97&\x94\xafL\x00\xeeTF:\x13\x00\xce\r\x11l\x00\t\xfa\xfb)\xdc|q\r\x8a\xd0\xbb\xec\xe7\xb1\xb9\x06\xc3\xdd\x10I\x8c{\x9fm8\xa7z\xbf\x08@\xb8n\xe8\x03`\xb5\xacp;\x90X\x10\xc1\xc6\x0fp l\x80\xa9Eg83\xb1\xe1\x88\xca\xac\xd5\xf6\x7f\xb6\x85\xc3\x06\x04\xe1\x14\xb4\xde\xe4\x87\x93\x89\r\x08&\x07@\xd3\xd8O\x01\x00x\xc7\xd6\xdaOy56`\n2\xb1\xf1\xbd_\xc4f\xb3H\xef\xa7\xd4?\x1a|\xab\x1b\xb7\xfd\x87\xbe\xa1\xf3\xf3~\x8dtq\xa5\x17\xfe\xbc,\x92\xe1\xf4\x0f\xd7\x05@\x0e\x00\x9c\x1b"\xd8\x80\xb1\xd7?\x1a\xe0\x91^t\x03`\xe3\x0b{\xa2\xfc\t\xc7axBR$\xc3\tj\r\x9d\xe1\x04\xb58\x0087\x96J\x8c\xeba\x03L\xcb\xfe\x83X8\x87\x9c|\x01l\x80\xa9\xb0\x99\x01\x1b\xdf\xfbEl\xee\xfbB\x94Y\xcbL\x8b\xcb\xc9\x88$\xc6\x81\xcf\x99\xd8\x80`r\x00,\xfby$\x11\x00\xbc\xa9\xd5\xff\xa7\xbc\x1a\x1b0\x05Cc\xb3Y^\xbf\x9fb\xa6\xe6\xf2\xa2\x1c6 \x08\x9c8\x00\x9f3\xb1\x01\xc1\xe4\x00h\x1a\xfb)\x00\x00o:\x92\xac\x16\xc1\x06\x0cghl\xc0\x14\x0c\x8d\xcdf\x91\xdeO\xe1\xb0\x01A\xd0OH\x0e\x9d\xc7\x06\xab&n\x89%\x92N\x07\x8b\x13N*\xc3\xdd\x10I\x11\x84G^\x84C\x11\x00&\x94/\x91\xfd\x14\xee\xd1L\xc4\x8d;\x95\x904h=\xfc\xe1\x0f\xaa\x13\xcaW\x01p\xdd\r\x11l\x00\t\xfa\x89qn\xbe\xb8\x06E\xe8]\xa2\xbfg\x1e\x9e\x90\x14\xc9p\x82Z\xa7z\xbf\x08@\xb8n\x80Z\xe1\rr\x1cZ\xad\xc5=\xd5n\x96\xfaG\x83y\x13\xe3\x1c6\xc0T\xd8\xcc\x80\x8d\xef\xfd"6\xcb\xbe\x10e\xd62SsyQ\x0e\x1b\x10\x84S\xd0z\x93\xf79\x13\x1b\x10L\x0e\x80V\xfb)\xdf\x89\r\x18\xce\xd0\xd8\x80)\x18\x1a\x9b\xcd2\xd7~\n\'\x0e\xc0g\xfd\'\xfa\xf0DP\xa6\x1b@v\xb8\xb5\r\xe7\x06X\x9cpR\x19\xbe\xb6\t\xbf\xd1\x8b\xac\xb1\xc3#\x9f\xc9!\x17\xf9L\x00&\x94/\x91\x84$\xb7\xb6\xd1OH\x02D\x8dp\x0f\x7f\xb8\x1b\x13\xcaW&\x87"\x00\x94|\x95|\x8dK/p\xa3\xe4k\x06\xf9\nwC\x04\x1b@\x82~b\x1c\xcc\x17\x98\x02\xaeA\x11l\xda\xfe\x0f\xe6p\r\x86\'$E2\x9c\xa0\xd6\xa9\xde/\x02\x00\xa6\x80\x9b/P+\xbcA\x8eC\xabe\x85\xd7\x03\xa9E\x11l\xfc\x00m8\xfa\xd8\x00\xd3\xaa\x91\x18\xe7\xb0\x01\xa6\xc2f\x06l|\xef\x17\xb1i\xfbB\x94Y\xcbL\xeb\x80\xfb)\xe1\xd8\xe8/\x89\xc3\x9f\xa4\xc2\xdd\xe0\xb0\xf1W\x8e\xe8\x06\x17\r\xae\xafL\xdd\xe0>)\xa0/\x91\x9b\x14\x88\x0f7\xe4\xf0{%\x07\x007)\xe1\x00L(_"O\xf4\x1c6"O\xf4\x1c\xa2\x1c\xbd\xc0\x8d\xb6\xbf2\x9fP\xbe\xc29\xe4"\x9f\t@\xc9\x97\xa0|\x81\xf9\x12\x91/\x8e\xde\xcd\xf2\xf53Q\xc9\xd7\x97\xe3z3\xf9\n\x07\xa0\xe4\xab\xe4k\\z\x81\x1b%_3\xc8W\xb8\x1b"\xd8\x00\x12\xf4\x13\xe3`\xbe\xc0\x14p\r\x8a`\xb3~\xe6\x9f\xfd\t\xd7`x\x1e[$1\x0ej\x9d\xea\xfd"\x00`\n\xb8\xf9\x02\xb5\xc2\x1b\xe48\xb4ZV\xf8\xe3\xf3\xed\xe1\x9b\xe5\xf7s\xe1\x8fo{\xb18\x87\x8d\x1f\xa0\rG\x1f\x1b\xfd{J\xf8R$s?\x05x\xe8\xaf\xb4\x03\xb7\x1b\xce\x04\xb0\x01nd\xeaFx_"\xe2\xe0\x1d3\x9fO)\x89\x99\xc2oR\x1c\x00\xc0C\x7fe=\xb0\xde\xe0L\x13\xcaW\xf8\x928\x13\x1b}\x8d\x02\xf4z\xd3\xc7\xe7R$\xbc\xaf\t\xe5\x0b\x00\x00\x82\xc9\x01\x00<\xcc\x04\xa0\xe4\xeb\xba|eb#\xf2D\xcf!\x1aN\xef\xba\xff@W\xf2u\x9dC.\xf2\x99\x00\x94|\t\xca\x17\x98/\x11\xf9\xe2\xe8\xdd,_\'\x82J\xbe\xbe\x1c\xd7\x9b\xc9W8\x00%_%_\xe3\xd2\x0b\xdc(\xf9\x9aA\xbe\xc2\xdd\x10\xc1\x06\x90\xc0\xa5\xaaD\xb0\x01S\x00\x1a\x14\xb9\xa7\x80I\t\x17\xf3\xf0\x84$\xd7 \'_\xe1&\x10\xc3L\xdd\x087er\x08\x06\xb8:\x19\xb4\x8f\xe7\xd0\xfb)`\n8l\x80\x1b`\x96\xf5\xef)\xe1K\x91\t_\xbb\x93\xe9\x86\x81tw_\x7f\r\xff\xb9\xa7L7\xc0m=\xfck\xc6\x9c\x1b"\xbf\xf7us_\x8d~\x0f\x00\xee\xee\x91\\\r\x00\xce\r\x11l\xc0\xd8\'|\xed\x0e\x00@\xff\xdf\x138\x0e\xc3\xdd\x10\xf9\xff\x14\xa0\x1b\\\x86S\x04\x00\x8b\xb3?\x11\x01\xc0w\x01\n\x9bI\x04\x1b\x101}l\x80\xa9\xed?Vp\x00\x84\xd3\x0b\xb0\x01\xa6F}q\x1dp\xc8\xd5j\xfb\xe9t\x91\xfd\x14\xef\xb3\r\'\x13\x1bN7\x86\x06\xc0;\xb6\xbe\xc5w8\x87\xc6\x06LA&6\xbe\xf7\x8b\xd8l\x96\xfa\xbd\xafK\xdbp\x99\xd8\x80`r\x00\xac\xfb\xd9\xb9L\x00\xc2\'E\x04\x1b\xe0\xf3\xd0\xd8\xe8\xeb\x867}\x1c\xd8O\xd9,_o\xecr\xb5\xb8\x8f\x9eo\xc7\xba\xe0\xb0\x01A\xe0<\x04>\x9f\xea\xfd"\x00`\n2\x01\xe0\xc4\x01\xc4Y\x04\x1b _\xafNH\xfe\x0fh\x94\x10\xfc"
print(zlib.decompress(sol)[int(input())]-97)

Submission status: Runtime Error

Solution code:
def main():
    
    N = int(input())
    
    POW6 = []
    POW9 = []
    for i in range(7):
        POW6.append(6**i)
        
    for i in range(6):
        POW9.append(9**i)
        
    
    dp = [N]*(N+1)
    dp[0] = 0
    for i in range(1, N+1):
        cnt = 0
        while i-POW6[cnt] >= 0:
            dp[i] = min(dp[i], dp[i-POW6[cnt]]+1)
            cnt += 1
        cnt = 0
        while i-POW9[cnt] >= 0:
            dp[i] = min(dp[i], dp[i-POW9[cnt]]+1)
            cnt += 1

    
    print(dp[N])
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
number_of_withdrawal=[]

def floor(float_number):
    integer = 0
    while integer < float_number:
        integer+=1
    if integer == float_number:
        return integer
    else:
        integer-=1
        return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    latest = count_6_pow_number+count_9_pow_number

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (floor(money_6/pow(6,i)))%6
        i+=1
    j=0
    count_9_pow_number=0
    while pow(9,j)<=money_9:
        count_9_pow_number += (floor(money_9/pow(9,j)))%9
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal= count_6_pow_number+count_9_pow_number
    if number_of_withdrawal < latest:
        res = number_of_withdrawal


print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
count = 0
ans = []
for i in range(N+1):
    count1 = 0
    count2 = 0
    N1 = N - i
    x = i
    while x:
        count1 += x % 6
        x //= 6
    while N1
        count2 += N1 % 9
        N1 //= 9
    count = count1 + count2
    ans.append(count)
print(min(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
count = 0
ans = []
for i in range(N+1):
    count1 = 0
    count2 = 0
    N1 = N - i
    x = i
    while x:
        count1 += x % 6
        x //= 6
    while N1
        count2 += x % 9
        N1 //= 9
    count = count1 + count2
    ans.append(count)
print(min(ans))

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [0 for i in range(n+1)]

for i in range(35):
    j = i // 9
    cand = []
    for k in range(j+1):
       _i = i
       _i -= 9*k
       l = _i // 6
       for m in range(l+1):
           __i = _i
           __i -= 6*m
           cand.append(k+m+__i)
    dp[i] = min(cand)
nine_list = [pow(9, i) for i in range(1, 6)]
six_list = [pow(6, i) for i in range(1, 7)]
for i in range(35, n+1):
    for j in range(len(nine_list)):
        if nine_list[j] > i:
            max_nine = nine_list[j-1]
            break
    for j in range(len(six_list)):
        if six_list[j] > i:
            max_six = six_list[j-1]
            break
    dp[i] = min(dp[i-max_nine]+1, dp[i-max_six]+1)

print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [0 for i in range(n+1)]

for i in range(35):
    j = i // 9
    cand = []
    for k in range(j+1):
       _i = i
       _i -= 9*k
       l = _i // 6
       for m in range(l+1):
           __i = _i
           __i -= 6*m
           cand.append(k+m+__i)
    dp[i] = min(cand)
nine_list = [pow(9, i) for i in range(1, 6)]
six_list = [pow(6, i) for i in range(1, 7)]
for i in range(36, n+1):
    for j in range(len(nine_list)):
        if nine_list[j] > i:
            max_nine = nine_list[j-1]
            break
    for j in range(len(six_list)):
        if six_list[j] > i:
            max_six = six_list[j-1]
            break
    dp[i] = min(dp[i-max_nine]+1, dp[i-max_six]+1)

print(dp[n])

Submission status: Runtime Error

Solution code:
import itertools

N_MAX = 100000
INF = float('inf')

n = int(input().rstrip())

dp = [INF for _ in range(N_MAX)]
dp[0] = 0
dp[1] = 1
dp[6] = 1
dp[9] = 1

for i in range(1, n + 1):

    # [1, 6, 36, ...]
    for j in itertools.takewhile(lambda x: x < N_MAX,
                                 (6 ** c for c in itertools.count())):
        dp[i] = min(dp[i], dp[i - j] + 1)

    # [1, 9, 81, ...]s
    for j in itertools.takewhile(lambda x: x < N_MAX,
                                 (9 ** c for c in itertools.count())):
        dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[n])

Submission status: Runtime Error

Solution code:
N = int(input())
dp = [float('inf')] * (2*10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**7],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 1

print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
dp = [float('inf')] * (10**5+1)
dp[0] = 0

for i in range(1, N+1):
    dp[i] = min(dp[i-1], dp[i-6], dp[i-6**2], dp[i-6**3], dp[i-6**4], dp[i-6**5], dp[i-6**7],
                dp[i-9], dp[i-9**2], dp[i-9**3], dp[i-9**4], dp[i-9**5]) + 1

print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(raw_input())                                                                                                                                                                p = [1]                                                                                                                                                                             for j in [6, 9]:                                                                                                                                                                      i = j                                                                                                                                                                               while i < N:
    p.append(i)
    i *= j
c = [N] * (N+1)
c[1] = 1
for i in range(1, N+1):
  for j in p:
    if i+j <= N:
      c[i+j] = min(c[i+j], c[i]+1)
print c[N]

Submission status: Runtime Error

Solution code:
def s(a,b):return[s(a//b,b)+a%b,a][a<b]
n=int(input());print(min(s(i,6)+s(n-i,9)for i in range(n+1)))

Submission status: Runtime Error

Solution code:
from itertools import takewhile, chain, count

n = int(input())

def powers(a, n):
   return takewhile(lambda x: x<=n, (a**i for i in count(1)))

draws = sorted(set(chain([1], powers(6, n), powers(9, n))))
d = {}
for draw, last_draw in zip(draws[1:], draws):
  d[draw, 0] = 0
  for i in range(1, n+1):
    d[draw, i] = min(d.get((draw, i-draw), n)+1, d.get((last_draw, i), i))

print(d[max(draws), n])

Submission status: Runtime Error

Solution code:
def s(n,p):
  while n>0:yield n%p;n//=p
c=lambda*a:sum(s(*a));n=int(input())print(min(c(i,6)+c(n-i,9)for i in range(n+1)))

Submission status: Runtime Error

Solution code:
def s(n,p):
  while n>0:yield n%p;n//=p
c=lambda*a:sum(s(*a))
print(min(c(i,6)+c(n-i,9)for i in range(int(input())+1)))

Submission status: Runtime Error

Solution code:
def s(n,p):
  while n>0:yield n%p;n//=p
c=lambda*a:sum(s(*a));print(min(c(i,6)+c(n-i,9)for i in range(int(input())+1)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,C = map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
co=[[int(i) for i in input().split()] for j in range(N)]
d0= defaultdict(int)
d1= defaultdict(int)
d2= defaultdict(int)
for i in range(N):
    for j in range(N):
        if (j+i) %3==0:
            d0[co[j][i]] +=1
        elif (j+i)%3==1:
            d1[co[j][i]] +=1
        else:
            d2[co[j][i]] +=1
A0=[]#i色に帰るのに必要な違和感
A1=[]
A2=[]
for i in range(C):
    iwa =0
    for s in d0.keys():
        iwa += D[s-1][i-1]*d0[s] 
    A0.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d1.keys():
        iwa += D[s-1][i-1]*d1[s] 
    A1.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d2.keys():
        iwa += D[s-1][i-1]*d2[s] 
    A2.append([iwa,i])

A0.sort()
A1.sort()
A2.sort()
B=[[] for i in range(3)]
for i in range(3):
    B[0].append(A0[i])
for i in range(3):
    B[1].append(A1[i])
for i in range(3):
    B[2].append(A2[i])
ans =[]
for i in range(3):
    for j in range(3):
        for k in range(3):
            if B[0][i][1] ==B[1][j][1]:
                continue
            if B[0][i][1] ==B[2][k][1]:
                continue
            if B[1][j][1] ==B[2][k][1]:
                continue
            ans.append(B[0][i][0]+B[1][j][0]+B[2][k][0])
print(min(ans))

Submission status: Runtime Error

Solution code:
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    steps += 1
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)

Submission status: Runtime Error

Solution code:

# coding: utf-8

# In[243]:


N = int(input())


# In[244]:


list_9 = [9]
for i in range(4):
    list_9.append(list_9[i] * 9)
    
list_6 = [6]
for i in range(5):
    list_6.append(list_6[i] * 6)


# In[245]:


amount_list = list_9 + list_6 + [1]
amount_list.sort(reverse=True)


# In[247]:


import math
dp = [math.inf] * (N+1)
dp[0] = 0


# In[248]:


for i in range(len(dp)):
    for amount in amount_list:
        if i >= amount:
            dp[i] = min(dp[i],dp[i-amount]+1)
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())

units = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

dp = [100000]*100000
dp[0] = 0
dp[1] = 1

for i in range(2, N+1):
    for unit in units:
        if i - unit >= 0:
            dp[i] = min(dp[i-unit]+1, dp[i])

print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())
a = [1,6,36,216,1296,7776,46656]
b = [1,9,81,729,6561,59049]
def six(n):
  i = 0
  if n < a[i]:
    return i-1
  else:
    i += 1
def nine(n):
  i = 0
  if n < b[i]:
    return i-1
  else:
    i += 1
def ans(n):
  if n in a or n in b:
    return 1
  else:
    return(min(six(n)+ans(n-6**six(n)),(nine(n)+ans(n-9**nine(n))
                                        
print(ans(44852))

Submission status: Runtime Error

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(2**16)
s = int(input())

lis = []
ed = set()
mi = float("inf")

@lru_cache(maxsize=None)
def ret(n):
    over_9 = math.floor(math.log(n, 9))
    over_6 = math.floor(math.log(n, 6))
    return (over_6, over_9)

@lru_cache(maxsize=None)
def divide(n, su):
    global mi
    if su > mi:
        return
    if n<6:
        global lis
        mi = min(mi, su+n)
    over_6, over_9 = ret(n)
    for i in range(over_9, 0, -1):
        divide(n-(9**i), su+1)
    for i in range(over_6, 0, -1):
        divide(n-(6**i), su+1)


divide(s, 0)
print(mi)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
memo = [0]*(N+1)
memo[0] = 0

for i in range(1,N+1):
	memo[i] = memo[i-1]+1
	for j in range(1,iny(math.log(i,6))+1):
		memo[i] = min(memo[i],memo[i-pow(6,j)]+1)
	for j in range(1,int(math.log(i,9))+1):
		memo[i] = min(memo[i],memo[i-pow(9,j)]+1)

print(memo[-1])

Submission status: Runtime Error

Solution code:
num = [i for i in range(0,100001)]

for j in range(1,100001):
        num[j] = j//6 + num[j%6]

for j in range(1,100001):
        num[j] = min(num[j],j//9+num[j%9])

for j in range(1,100001):
        num[j] = min(num[j],j//36+num[j%36])

for j in range(81,324):
        num[j] = min(num[j],1+num[j-81])
for j in range(162,324):
        num[j] = min(num[j],2+num[j-162])
for j in range(243,324):
        num[j] = min(num[j],3+num[j-243])
for j in range(324,100001):
        num[j] = min(num[j],(j//324)*4 + num[j%234])

for j in range(216,648):
        num[j] = min(num[j],1+num[j-216])
for j in range(432,648):
        num[j] = min(num[j],2+num[j-216*2])
for j in range(648,100001):
        num[j] = min(num[j],(j//648)*3 + num[j%648])

for i in range(1,8):
        for j in range(729*i,729*8):
                num[j] = min(num[j],i+num[j-729*i])
for j in range(729*8,100001):
        num[j] = min(num[j],(j//(729*8))*8+num[j%(729*8)])

for i in range(1,9):
        for j in range((6**4)*i,(6**4)*9):
                num[j] = min(num[j],i+num[j-(6**4)*i])
for j in range((6**4)*9,100001):
        num[j] = min(num[j],(j//((6**4)*9))*9+num[j%((6**4)*9)])

for i in range(1,2**4):
        for j in range((9**4)*i,(9**4)*(2**4)):
                num[j] = min(num[j],i+num[j-(9**4)*i])
for j in range((9**4)*(2**4),100001):
        num[j] = min(num[j],(j//((9**4)*(2**4)))*(2**4)+num[j%((6**4)*(2**4))])

MoneyYouCanGet = [6**5,6**6,9**5]

for i in MoneyYouCanGet:
        for j in range(1,100001):
                k = 1
                while k*i<j:
                        num[j] = min(num[j],k+num[j-k*i])
                        k += 1

N = int(input())
print(num[N])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
n = int(input())

count_9 = 0
count_6 = 0
count_1 = 0

while n < 6:
    need_9 = math.log(n, 9)
    need_6 = math.log(n, 6)
    if need_9 > need_6:
        n -= 9 ** int(need_9)
        count_9 += 1

    else:
        n -= 6 ** int(need_6)
        count_6 += 1
        

count_1 = n

print(count_9 + count_6 + count_1)

Submission status: Runtime Error

Solution code:
n = int(input())

lis = [1, 6, 36, 216, 1296, 7776, 46656,
     9, 81, 729, 6561, 59049]
m = len(c)

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0

for j in range(1,n+1):
    temp = []
    for i in range(m):
        if j < lis[i]:
            continue
        else:
            temp.append(dp[j-lis[i]]+1)
    dp[j] = min(temp)

print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())

lis = [1, 6, 36, 216, 1296, 7776, 46656,
     9, 81, 729, 6561, 59049]
m = len(c)

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0

for j in range(1,n+1):
    temp = []
    for i in range(m):
        if j < c[i]:
            continue
        else:
            temp.append(dp[j-lis[i]]+1)
    dp[j] = min(temp)

print(dp[n])

Submission status: Runtime Error

Solution code:
def count(n, cnt):
    result = [n+cnt]
    if n >= 9:
        i = 1
        while n - 9**i >= 0:
            i+=1

        i -=1

        i = 9**i

        j = int(n/i)

        result.append(count(n - j*i, cnt+j))

    if n >= 6:
        i = 1
        while n - 6**i >= 0:
            i+=1
        i -=1

        i = 6**i
        result.append(count(n - j*i, cnt+j))

    return min(result)

N = int(input())
print(count(N, 0))

Submission status: Runtime Error

Solution code:
cnt = 0
i = 10
dp = [0,1,2,3,4,5,1,2,3,1]
while i<=N:
    idx_n,idx_s = 0,0
    while i-(9**idx_n)>=0:
        idx_n += 1
    idx_n -= 1
    while i-(6**idx_s)>=0:
        idx_s += 1
    idx_s -= 1
    dp.append(min(1+dp[i-(9**idx_n)],1+dp[i-(6**idx_s)]))
    i += 1
print(dp[N])

Submission status: Runtime Error

Solution code:
n = int(input())


def get_smallest_under_35(_n):
    j = _n // 9
    cand = []
    for k in range(1, j + 1):
        __n = _n
        __n -= 9 * k
        l = __n // 6
        __n -= l * 6
        cand.append(k + l + __n)
    return min(cand)

def get_smallest_under_215(_n):
    j = _n//81
    _n -= 81*j
    k = _n // 36
    _n -= 36 * k
    return get_smallest_under_35(_n)+j+k

def get_smallest_under_728(_n):
    j = _n // 216
    if j == 0:
        return get_smallest_under_215(_n)

    cand = []
    for k in range(1, j + 1):
        __n = _n
        __n -= 216 * k
        _cnt = k
        if _n <= 215:
            cand.append(get_smallest_under_215(__n) + _cnt)
        else:
            cand.append(get_smallest_under_728(__n) + _cnt)
    return min(cand)


num_list = []

for i in range(1, 7):
    num_list.append(pow(6, i))
    if i <= 5:
        num_list.append(pow(9, i))
num_list = sorted(num_list)
cnt = 0
is_break = True
while is_break :
    for i in range(len(num_list)-1, -1, -1):
        if n <= 728:
            is_break = False
            break
        if num_list[i] < n:
            n -= num_list[i]
            cnt += 1
            break
print(get_smallest_under_728(n)+cnt)

Submission status: Runtime Error

Solution code:
import math

N = int(input())

base = []


base = base + [pow(9,i) for i in range(int(math.log(N)/math.log(9)))]
base = base + [pow(6,i) for i in range(int(math.log(N)/math.log(6)))]
base = sorted(list(set(base)), reverse = True)


def dp(a):
    if a == 0:
        print(dp(a)[0] + dp(a)[1])
        exit()
    min = 10000
    for i in range(a):
        if dp(a)[0] < min:
            min = dp(a)[0]
            min_inde = a
    return min + 1, dp(a)[1] - base[a]


dp(len(base)-1)

Submission status: Runtime Error

Solution code:
n = int(input())
nine = []
six = []
i = 0
for i in range(1, 100000):
    if 9 ** i < n:
        nine.append(9 ** i)
    else:
        break
for i in range(1, 100000):
    if 6 ** i < n:
        six.append(6 ** i)
    else:
        break

count = 0
last = n
while last >= 9:
    if nine:
        while nine[-1] > last:
            nine.pop()
    if six:
        while six[-1] > last:
            six.pop()

    if nine:
        tmp9 = nine[-1]
        num9 = int(last / tmp9)
    if six:
        tmp6 = six[-1]
        num6 = int(last / tmp6)

    if num9 < num6:
        count += num9
        last %= tmp9
        nine.pop()
    elif num9 == num6 and last % tmp9 <= last % tmp6:
        count += num9
        last %= tmp9
        nine.pop()
    else:
        count += num6
        last %= tmp6
        six.pop()


count += int(last / 6)
last %= 6
print(count + last)

Submission status: Runtime Error

Solution code:
import math

n = int(input())
num_list = [1]
pow_num = 1
six_pow_limit  = int(math.log(n, 6)) + 1
nine_pow_limit = int(math.log(n, 9)) + 1

num_list += [6 ** i for i in range(1,six_pow_limit)] + [9 ** i for i in range(1, nine_pow_limit)]

num_list = list(sorted(num_list))
len_num_list = len(num_list)

dp = [[0 for i in range(100000)] for j in range(15)]

def res(i, m):
    k = num_list[i]

    if m == 0 or i == 0:
        return m // 1


    if dp[i][m] != 0:
        return dp[i][m]

    z = m // k
    if z > 0:
        tmp = 100001
        for j in range(z+1):
            tmp = min(tmp, res(i - 1,  m - j * k) + j)
        dp[i][m] = tmp
    else:
        dp[i][m] =  res(i - 1, m)

    return dp[i][m]

print(res(len_num_list-1, n))

Submission status: Runtime Error

Solution code:
n = int(input())
ccal = n

calc_list = [[59049,7776,1296,216,81,36,9,1],[59049,7776,1296,216,81,36,6,1],[59049,7776,729,216,81,36,9,1],[59049,7776,729,216,81,36,6,1],[59049,6561,1296,216,81,36,9,1],[59049,6561,1296,216,81,36,6,1],[59049,6561,729,216,81,36,9,1],[59049,6561,729,216,81,36,6,1],[46656,7776,1296,216,81,36,9,1],[46656,7776,1296,216,81,36,6,1],[46656,7776,729,216,81,36,9,1],[46656,7776,729,216,81,36,6,1],[46656,6561,1296,216,81,36,9,1],[46656,6561,1296,216,81,36,6,1],[46656,6561,729,216,81,36,9,1],[46656,6561,729,216,81,36,6,1]]
"""
calc_list[0] = [59049,7776,1296,216,81,36,9,1]
calc_list[1] = [59049,7776,1296,216,81,36,6,1]
calc_list[2] = [59049,7776,729,216,81,36,9,1]
calc_list[3] = [59049,7776,729,216,81,36,6,1]
calc_list[4] = [59049,6561,1296,216,81,36,9,1]
calc_list[5] = [59049,6561,1296,216,81,36,6,1]
calc_list[6] = [59049,6561,729,216,81,36,9,1]
calc_list[7] = [59049,6561,729,216,81,36,6,1]
calc_list[8] = [46656,7776,1296,216,81,36,9,1]
calc_list[9] = [46656,7776,1296,216,81,36,6,1]
calc_list[10] = [46656,7776,729,216,81,36,9,1]
calc_list[11] = [46656,7776,729,216,81,36,6,1]
calc_list[12] = [46656,6561,1296,216,81,36,9,1]
calc_list[13] = [46656,6561,1296,216,81,36,6,1]
calc_list[14] = [46656,6561,729,216,81,36,9,1]
calc_list[15] = [46656,6561,729,216,81,36,6,1]
"""
res = 0
rlist = []



for k in range(16):
    clcl = n
    for i in range(8):
        sellist = calc_list[k]

        if  clcl == 1:
            res += 1
            break
        if  clcl > sellist[i]:
            #print("clcl",clcl,"cal",sellist[i])
            res += int(clcl/sellist[i])
            clcl = clcl%sellist[i]
            if clcl == 1:
                break
            #print("clcl",clcl)
            print(res)
    else:
        rlist.append(res)
        res = 0
else:
    print(min(rlist))

Submission status: Runtime Error

Solution code:
N = int(input())

num = [1]
memo = [[ -1 for i in range(12)]for j in range(100000)]
n = 6
while True:
    num.append(n)
    n *= 6
    if n > 100000:
        break
n = 9
while True:
    num.append(n)
    n *= 9
    if n > 100000:
        break
num.sort()

ans = 0
print(num)
#while N > 6:

def DP(n , index):
    if index == 0:
        return  n
    elif n == 0:
        return 0
    min_ = 10000000
    if n < num[index]:
        #print(n,num[index])
        return DP(n,index - 1)
    can = num[index]
    #print(index)
#    print(n//can)
    for i in range(n // can+1):
        min_ = min(min_ , DP(n - i * can,index - 1) + i)
 #       print(i,n,index,DP(n - i*can,index-1))
    
     #   print(min_)
    #print(min_)
    memo[n][index] = min_
    return min_
    
print(DP(N,11))