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: Accepted

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: Accepted

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(N+1):
        cnt = 0
        while i+POW6[cnt] <= N:
            dp[i+POW6[cnt]] = min(dp[i+POW6[cnt]], dp[i]+1)
            cnt += 1
            if cnt == len(POW6):
                break
        
        cnt = 0
        while i+POW9[cnt] <= N:
            dp[i+POW9[cnt]] = min(dp[i+POW9[cnt]], dp[i]+1)
            cnt += 1
            if cnt == len(POW9):
                break            
            
    print(dp[N])
        
if __name__ == "__main__":
    main()

Submission status: Accepted

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
            if cnt == len(POW6):
                break
        cnt = 0
        while i-POW9[cnt] >= 0:
            dp[i] = min(dp[i], dp[i-POW9[cnt]]+1)
            cnt += 1
            if cnt == len(POW9):
                break

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

Submission status: Accepted

Solution code:
N= int(input())
memo = [-1] * 100001

def Base10toN(X, n):
    if (int(X / n)):
        return Base10toN(int(X / n), n) + str(X % n)
    else:
        return str(X % n)

def f(amount):
    if memo[amount] != -1:
        return memo[amount]
    if amount <= 5:
        memo[amount] = amount
        return amount
    s = Base10toN(amount, 6)
    fs = f(amount - 6 ** (len(s) - 1))
    n = Base10toN(amount, 9)
    fn = f(amount - 9 ** (len(n) - 1))
    if (fs < fn):
        memo[amount] = fs + 1
        return fs + 1
    else:
        memo[amount] = fn + 1
        return fn + 1

print(f(N))

Submission status: Accepted

Solution code:

x=int(input())

def log(x,y):
  count=0
  while x>=y:
    x/=y
    count+=1
  return count

M=[-1 for x in range (0,100001)]
M[0]=0
def mini(x):
  if M[x]==-1:
    M[x]=1+min(mini(x-9**log(x,9)),mini(x-6**log(x,6)))
  return M[x]
print(mini(x))

Submission status: Accepted

Solution code:
N=int(input())
ans = 100000
for i in range(N+1):
    t = i
    count = 0
    while t > 0:
        count += t%6
        t = t//6
    t = N - i
    while t > 0:
        count += t%9
        t = t//9
    if count < ans:
        ans = count
print(ans)

Submission status: Accepted

Solution code:

N = int(input())

ans = 100000000000000
for i in range(N+1):
	tmp_ans = 0
	n6 = i
	while n6 > 0:
		tmp_ans += (n6%6)
		n6 = n6//6
	n9 = N-i
	while n9 > 0:
		tmp_ans += (n9%9)
		n9 = n9//9
	if tmp_ans < ans:
		ans = tmp_ans
		
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

min_ = N

for i in range(N+1):
  x = 0
  n = i
  while n > 0:
    x += n % 6
    n //= 6  
  n = N-i
  while n > 0:
    x += n % 9
    n //= 9
  
  min_ = min(min_, x)
print(min_)

Submission status: Accepted

Solution code:
N = int(input())
wd = []
for i in range(1, 7):
    wd.append(6**i)
for i in range(1, 6):
    wd.append(9**i)
wd.append(1)

dp = [N]*(N+1)
dp[0] = 0

for i in wd:
    for j in range(i, N+1):
        dp[j] = min(dp[j], dp[j-i]+1)

print(dp[N])

Submission status: Accepted

Solution code:
# input
N = int(input())

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

ans = N

for i in range(N + 1):
    tmp = 0
    a_6 = Base_10_to_n(i, 6)
    for j in a_6:
        tmp += int(j)
    a_9 = Base_10_to_n(N - i, 9)
    for k in a_9:
        tmp += int(k)
    if tmp < ans:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import math

N=int(input())
number_of_withdrawal=[100000]

# 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

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (math.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 += (math.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.append(count_6_pow_number+count_9_pow_number)

print(min(number_of_withdrawal))

Submission status: Accepted

Solution code:
n = int(input())
ans = n
for i in range(n+1):
  cc=0
  t=i
  while t>0:
    cc=cc+t%6
    t=t//6
  t=n-i
  while t>0:
    cc=cc+t%9
    t=t//9
  ans=min(ans, cc)
print(ans)

Submission status: Accepted

Solution code:
def funcDP(n):
    dp = [float('inf')] * (n + 10)
    dp[0] = 0
    for i in range(1, n + 1):
        for base in [6, 9]:
            powered = 1
            while powered <= i:
                dp[i] = min(dp[i], dp[i - powered] + 1)
                powered *= base
    return dp[n]

if __name__ == '__main__':
    print(funcDP(int(input())))

Submission status: Accepted

Solution code:
n = int(input())
res = n
ans = 0
for i in range(n+1):
    t = i
    cc = 0
    while t >= 1:
        cc = cc + t % 6
        t = t // 6

    t = n-i
    while t >= 1:
        cc = cc + t%9
        t = t // 9


    if res > cc:
        res = cc

print(res)

Submission status: Accepted

Solution code:
def sinsu(M,k):
    L=0
    MM=M
    while(True):
        L+=MM%k
        MM=MM//k
        if MM==0:
            break
    return L
N=int(input())
ans=N
for i in range(N+1):
    a=i
    b=N-i
    tmp=sinsu(a,6)+sinsu(b,9)
    if ans>tmp:
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
def min(a, b):
    if(a < b):
        return a
    else:
        return b

dp = [0]
n = 1

for n in range(100010):
    dp.append(10000000)
    power = 1
    while(power <= n):
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 6
    power = 1
    while(power <= n):
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 9

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

Submission status: Accepted

Solution code:
N=int(input())
dp=[float('inf')]*100010
dp[0]=0

for i in range(N+1):
    power=1
    while power<=N:
        dp[i]=min(dp[i],dp[i-power]+1)
        power*=6
    power=1
    while power<=N:
        dp[i]=min(dp[i],dp[i-power]+1)
        power*=9

print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
dp=[float('inf')]*100010
dp[0]=0
base=[1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]


for i in range(N+1):
    for power in base:
        dp[i]=min(dp[i],dp[i-power]+1)

print(dp[N])

Submission status: Accepted

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: Accepted

Solution code:
'''a = [1, 6, 9, 6**2, ....]

dp[i+1][n]: i番目までのaから総和をｎにする組み合わせのうち、
　　　　　　選ぶ整数の数の最小値 (個数制限なし)
0 <= i <= len(a)
0 <= n <= N
'''

maxN = int(1e5)
N = int(input())
a = [1]
for i in range(1,100):
    if 6**i <= N: a.append(6**i)
    if 9**i <= N: a.append(9**i)
    if 6**i>N and 9**i>N: break
        
 
dp = [[0] + [maxN*10]*N] # initial state :dp[0][n]

for i in range(len(a)):
    dp.append([0]*(N+1)) # create dp[i+1]
    for n in range(N+1):
        if a[i] <= n:
            dp[i+1][n] = min(dp[i][n], dp[i+1][n-a[i]] +1)
        else:
            dp[i+1][n] = dp[i][n]
            
print(dp[len(a)][N])

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    dp = [0] + [float('inf')] * N
    for n in range(1, N + 1):
        for i in (6, 9):
            power = 1
            while power <= n:
                dp[n] = min(dp[n], 1 + dp[n - power])
                power *= i

    print(dp[N])

main()

Submission status: Accepted

Solution code:
global six
six = []
global nine
nine = []
ans = 1145141919810


def init():
	s = 6
	while (1):
		if s > 100000:
			break

		six.append(s)
		s *= 6

	n = 9
	while (1):
		if n > 100000:
			break

		nine.append(n)
		n *= 9

	six.reverse()
	nine.reverse()


def dfs(zan, did):
	global ans
	global six
	global nine
	if zan < 6:
		res = did + zan
		if res < ans:
			ans = res

		return

	for val in six:
		if val > zan:
			continue

		dfs(zan - val, did + 1)
		break

	for val in nine:
		if val > zan:
			continue

		dfs(zan - val, did + 1)
		break


init()
n = int(input())
dfs(n, 0)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = [1]
b = [1]

while True:
    d = a[-1] * 9
    if d > n:
        break
    a.append(d)

while True:
    d = b[-1] * 6
    if d > n:
        break
    b.append(d)

dp = [n] * (2 * n)
dp[0] = 0

for i in range(n):
    for j, a_ in enumerate(a):
        dp[i+a_] = min(dp[i+a_], dp[i]+1)
    for j, b_ in enumerate(b):
        dp[i+b_] = min(dp[i+b_], dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
INF = 1000000

dp = [INF for i in range(100040)]

dp[0]= 0

a = [1]
n = 6
while True:
    a.append(n)
    n *= 6
    if n > 100000:
        break
n= 9
while True:
    a.append(n)
    n *= 9
    if n > 100000:
        break
a.sort()
for i in range(len(a)):
    a_ =  a[i]
    for j in range(a[i],len(dp)):
        dp[j] = min(dp[j],dp[j-a_] + 1)

print(dp[int(input())])

Submission status: Accepted

Solution code:
INF = 1000000

dp = [INF for i in range(100040)]

dp[0]= 0

a = [1]
n = 6
while True:
    a.append(n)
    n *= 6
    if n > 100000:
        break
n= 9
while True:
    a.append(n)
    n *= 9
    if n > 100000:
        break

for i in range(len(a)):
    a_ =  a[i]
    for j in range(a[i],len(dp)):
        dp[j] = min(dp[j],dp[j-a_] + 1)

print(dp[int(input())])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

m = 100000
a = [6]
b = [9]

while True:
    d = a[-1] * a[0]
    if d > m:
        break
    a.append(a[-1] * a[0])

while True:
    d = b[-1] * b[0]
    if d > m:
        break
    b.append(d)

c = a + b
c.sort()
c.reverse()
dp = {}

def solve(n, i):
    if i == len(c):
        return n
    if (i, n) in dp:
        return dp[(i, n)]
    if n < c[i]:
        dp[(i, n)] = solve(n, i+1)
        return solve(n, i+1)

    temp = []
    l = 9 if c[i] % 9 == 0 else 6
    l = min(l, n//c[i]+1)
    for j in range(l):
        temp.append(solve(n-j*c[i], i+1)+j)
    dp[(i, n)] = min(temp)
    return dp[(i, n)]

print(solve(n, 0))

Submission status: Accepted

Solution code:
N = int(input())
dp = [pow(10, 10)] * 100010
dp[0] = 0
dp[1] = 1
for n in range(100010):
    # for 6
    power = 1
    while n - power >= 0:
        dp[n] = min(dp[n], 1 + dp[n - power])
        power *= 6
    # for 9
    power = 1
    while n - power >= 0:
        dp[n] = min(dp[n], 1 + dp[n - power])
        power *= 9
print(dp[N])

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    N = int(stdin.readline().rstrip())
    a = [y for y in [6 ** x for x in range(10)] if y <= N]
    b = [y for y in [9 ** x for x in range(10)] if y <= N]
    c = sorted(list(set(a) | set(b)))
    spam = [None] * N
    count = 0
    tmp = [-1]
    while True:
        count += 1
        tmp2 = tmp[:]
        tmp = []
        for x in c:
            for y in tmp2:
                idx = y + x
                if idx >= N:
                    continue
                if not spam[idx]:
                    spam[idx] = count
                    tmp.append(idx)
        if spam[-1]:
            print(spam[-1])
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [float('inf')] * 100010
dp[0] = 0
for i in range(1, 100000 + 1):
    power = 1
    while (power <= i):
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 6
    power = 1
    while (power <= i):
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

withdraw = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
min_draw = [0] * 100001
for i in range(1, n + 1):
    draw = []
    for j in withdraw:
        if j <= i:
            draw.append(min_draw[i - j] + 1)
            min_draw[i] = min(draw)
print(min_draw[i])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    max_N = 100001
    dp = [N for _ in range(max_N)]
    dp[0] = 0

    for i in range(N):
        for k in range(10):
            if i+6**k <= 100000:
                dp[i+6**k] = min(dp[i+6**k], dp[i]+1)
        for k in range(10):
            if i+9**k <= 100000:
                dp[i+9**k] = min(dp[i+9**k], dp[i]+1)

    return dp[N]

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())

def digit_sum(n, d):
    sum = 0
    number = n
    while number > 0:
        sum += number % d
        number = number // d
    return sum

ans = float('inf')
for i in range(N+1):
    ans = min(ans, digit_sum(N-i, 6) + digit_sum(i, 9))
print(ans)

Submission status: Accepted

Solution code:
'''input
44852
'''
cur6 = [6]
cur9 = [9]
cur1 = [1]
for i in range(7):
	cur6.append(6*cur6[-1])
	cur9.append(9*cur9[-1])
n = input()
dp = [-1]*(n+1)
dp[0] = 0
dp[1] = 1
for i in range(7):
	if cur6[i] <= n:
		dp[cur6[i]] = 1
	if cur9[i] <= n:
		dp[cur9[i]] = 1
for i in range(2,n+1):
	if dp[i] == 1:
		continue
	else:
		# currency 1
		dp[i] = dp[i-1]+1
		# currency 6,9
		for j in range(7):
			if i-cur6[j] >= 0:
				dp[i] = min(dp[i],dp[i-cur6[j]]+1)
			if i-cur9[j] >= 0:
				dp[i] = min(dp[i],dp[i-cur9[j]]+1)
print dp[n]

Submission status: Accepted

Solution code:
N = int(input())


def count(base, total):
    count = 0
    exp = 1
    while exp * base <= total:
        exp *= base
    remain = total
    while exp != 1:
        count += remain // exp
        remain %= exp
        exp //= base
    count += remain
    return count


Min = float("inf")
for i in range(N + 1):
    c = 0
    c += count(6, i)
    c += count(9, N - i)
    Min = min(Min, c)
print(Min)

Submission status: Accepted

Solution code:
n = int(raw_input())

times = n
for i in range(n+1):
    c = 0
    six = i
    nine = n-i
    while six>0:
        c += six%6
        six /= 6
    while nine>0:
        c += nine%9
        nine /= 9
    if c<times:
        times = c

print times

Submission status: Accepted

Solution code:
N = int(input())
def shin(n,q):
    s = n
    a = 0
    while(s>0):
        t=s%q
        a +=t
        s=(s-t)//q
    return a
ans = N
for i in range(N+1):
    c=shin(i,6)+shin(N-i,9)
    ans = min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

# 6**(i+1)を1回と6**iを6回は同じ金額分引き出せる
# 9も同様
# よって、6のグループと9のグループに分けて全探索すればよい

result = N
for i in range(N+1):
    ans = 0

    six_remain = i
    six_exp = 1
    while six_exp * 6 <= six_remain:
        six_exp *= 6
    # 6**i(<=i)から順に引き出していく
    while six_exp != 1:
        ans += six_remain // six_exp
        six_remain %= six_exp
        six_exp //= 6
    ans += six_remain

    nine_remain = N - i
    nine_exp = 1
    while nine_exp * 9 <= nine_remain:
        nine_exp *= 9
    # 9**i(<=N-i)から順に引き出していく
    while nine_exp != 1:
        ans += nine_remain // nine_exp
        nine_remain %= nine_exp
        nine_exp //= 9
    ans += nine_remain

    result = min(result, ans)

print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

A = []
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
B = []
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1

# 6**(i+1)を1回と6**iを6回は同じ金額分引き出せる
# 9も同様
# よって、6のグループと9のグループに分けて全探索すればよい

result = N
for i in range(N+1):
    ans = 0

    six_remain = i
    six_exp = 1
    while six_exp * 6 <= six_remain:
        six_exp *= 6
    # 6**i(<=i)から順に引き出していく
    while six_exp != 1:
        ans += six_remain // six_exp
        six_remain %= six_exp
        six_exp //= 6
    ans += six_remain

    nine_remain = N - i
    nine_exp = 1
    while nine_exp * 9 <= nine_remain:
        nine_exp *= 9
    # 9**i(<=N-i)から順に引き出していく
    while nine_exp != 1:
        ans += nine_remain // nine_exp
        nine_remain %= nine_exp
        nine_exp //= 9
    ans += nine_remain

    result = min(result, ans)

print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

A = []
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1
A.sort(reverse=True)  # 引き出せる金額のリスト

# i番目以降の金額を使ってj円を作るときの最小操作数
dp = [[-1 for j in range(N + 1)] for i in range(len(A) + 1)]


def func(i, j):
    # 1円しか選択肢がないなら
    if i == len(A):
        dp[i][j] = j
        return dp[i][j]

    # 探索済みなら計算量を減らせる
    if dp[i][j] >= 0:
        return dp[i][j]

    # その他の場合
    # 目いっぱい引き出すのが最適とは限らない
    # 引き出す回数を増やしていく
    # 8*11回くらいで十分だろう
    ret = 100001
    for times in range(88):
        if A[i] * times <= j:
            # dp[i][j]に代入すると再計算されてしまうことに注意
            ret = min(ret, func(i+1, j-A[i]*times) + times)
        else:
            break
    dp[i][j] = ret
    return ret


print(func(0, N))

Submission status: Accepted

Solution code:

n = int(input())

count = n

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

    current_count = 0
    t = i
    while t > 0:
        current_count += t%6
        t //= 6

    t = n - i
    while t > 0:
        current_count += t%9
        t //= 9

    if count > current_count:
        count = current_count
print(count)

Submission status: Accepted

Solution code:
n = int(input())

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

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):
    max_nine = nine_list[len(nine_list) - 1]
    max_six = six_list[len(six_list) - 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: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

A = [1]
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1
A.sort()  # 引き出せる金額のリスト

# i円を引き出す最小の操作回数をメモ、参照するのは常に前の値なのでループを回せる
dp = [1000000 for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N+1):
    a = 0
    while 6 ** a <= i:
        # 1円,6円,36円,...を使って操作回数を減らす
        dp[i] = min(dp[i], dp[i - 6 ** a] + 1)
        a += 1
    b = 0
    while 9 ** b <= i:
        # 1円,9円,81円,...を使って操作回数を減らす
        dp[i] = min(dp[i], dp[i - 9 ** b] + 1)
        b += 1

print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
ans=n
for i in range(n+1):
  cc=0
  t=i
  while t>0:
    cc=cc+t%6
    t=t//6
  t=n-i
  while t>0:
    cc=cc+t%9
    t=t//9
  if ans>cc:
    ans=cc
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = 0 # count
s = []
L1 = [6**k for k in range(1, 7)]
L2 = [9**k for k in range(0, 6)]
for k in range(0, n//6 + 1):
    x = 0
    j = 0
    n0 = 6 * k
    while n0 > 0:
        if n0 >= L1[5 - j]:
            n0 -= L1[5 - j]
            x += 1
        else:
            j += 1
    i = 0
    n1 = n - 6 * k
    while n1 > 0:
        if n1 >= L2[5 - i]:
            n1 -= L2[5 - i]
            x += 1
        else:
            i += 1
    s.append(x)
print(min(s))

Submission status: Accepted

Solution code:
N = int(input())
res = N
for i in range(N + 1):

	cc = 0
	t = N - i
	while t > 0:
		cc += int(t % 9)
		t = int(t / 9)
	t = i
#
	while t > 0:
		cc += int(t % 6)
		t = int(t / 6)

	if res > cc:
		res = cc
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

A = [1]
i = 1
while 6 ** i <= 100000:
    A.append(6 ** i)
    i += 1
j = 1
while 9 ** j <= 100000:
    A.append(9 ** j)
    j += 1
A.sort()  # 引き出せる金額のリスト

# i円を引き出す最小の操作回数をメモ、参照するのは常に前の値なのでループを回せる
table = [1000000 for _ in range(N + 1)]
table[0] = 0

for i in range(1, N+1):
    a = 0
    while 6 ** a <= i:
        # 1円,6円,36円,...を使って操作回数を減らす
        table[i] = min(table[i], table[i - 6 ** a] + 1)
        a += 1
    b = 0
    while 9 ** b <= i:
        # 1円,9円,81円,...を使って操作回数を減らす
        table[i] = min(table[i], table[i - 9 ** b] + 1)
        b += 1

print(table[N])