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:
dic = {1: 1,
2: 2,
3: 3,
4: 4,
5: 5,
6: 1,
7: 2,
8: 3,
9: 1,
10: 2,
11: 3,
12: 2,
13: 3,
14: 4,
15: 2,
16: 3,
17: 4,
18: 2,
19: 3,
20: 4,
21: 3,
22: 4,
23: 5,
24: 3,
25: 4,
26: 5,
27: 3,
28: 4,
29: 5,
30: 4,
31: 5,
32: 6,
33: 4,
34: 5,
35: 6,
36: 1,
37: 2,
38: 3,
39: 4,
40: 5,
41: 6,
42: 2,
43: 3,
44: 4,
45: 2,
46: 3,
47: 4,
48: 3,
49: 4,
50: 5,
51: 3,
52: 4,
53: 5,
54: 3,
55: 4,
56: 5,
57: 4,
58: 5,
59: 6,
60: 4,
61: 5,
62: 6,
63: 4,
64: 5,
65: 6,
66: 5,
67: 6,
68: 7,
69: 5,
70: 6,
71: 7,
72: 2,
73: 3,
74: 4,
75: 5,
76: 6,
77: 7,
78: 3,
79: 4,
80: 5,
81: 1,
82: 2,
83: 3,
84: 4,
85: 5,
86: 6,
87: 2,
88: 3,
89: 4,
90: 2,
91: 3,
92: 4,
93: 3,
94: 4,
95: 5,
96: 3,
97: 4,
98: 5,
99: 3,
100: 4,
101: 5,
102: 4,
103: 5,
104: 6,
105: 4,
106: 5,
107: 6,
108: 3,
109: 4,
110: 5,
111: 5,
112: 6,
113: 7,
114: 4,
115: 5,
116: 6,
117: 2,
118: 3,
119: 4,
120: 5,
121: 6,
122: 7,
123: 3,
124: 4,
125: 5,
126: 3,
127: 4,
128: 5,
129: 4,
130: 5,
131: 6,
132: 4,
133: 5,
134: 6,
135: 4,
136: 5,
137: 6,
138: 5,
139: 6,
140: 7,
141: 5,
142: 6,
143: 7,
144: 4,
145: 5,
146: 6,
147: 6,
148: 7,
149: 8,
150: 5,
151: 6,
152: 7,
153: 3,
154: 4,
155: 5,
156: 6,
157: 7,
158: 8,
159: 4,
160: 5,
161: 6,
162: 2,
163: 3,
164: 4,
165: 5,
166: 6,
167: 7,
168: 3,
169: 4,
170: 5,
171: 3,
172: 4,
173: 5,
174: 4,
175: 5,
176: 6,
177: 4,
178: 5,
179: 6,
180: 4,
181: 5,
182: 6,
183: 5,
184: 6,
185: 7,
186: 5,
187: 6,
188: 7,
189: 4,
190: 5,
191: 6,
192: 6,
193: 7,
194: 8,
195: 5,
196: 6,
197: 7,
198: 3,
199: 4,
200: 5,
201: 6,
202: 7,
203: 8,
204: 4,
205: 5,
206: 6,
207: 4,
208: 5,
209: 6,
210: 5,
211: 6,
212: 7,
213: 5,
214: 6,
215: 7,
216: 1,
217: 2,
218: 3,
219: 4,
220: 5,
221: 6,
222: 2,
223: 3,
224: 4,
225: 2,
226: 3,
227: 4,
228: 3,
229: 4,
230: 5,
231: 3,
232: 4,
233: 5,
234: 3,
235: 4,
236: 5,
237: 4,
238: 5,
239: 6,
240: 4,
241: 5,
242: 6,
243: 3,
244: 4,
245: 5,
246: 5,
247: 6,
248: 7,
249: 4,
250: 5,
251: 6,
252: 2,
253: 3,
254: 4,
255: 5,
256: 6,
257: 7,
258: 3,
259: 4,
260: 5,
261: 3,
262: 4,
263: 5,
264: 4,
265: 5,
266: 6,
267: 4,
268: 5,
269: 6,
270: 4,
271: 5,
272: 6,
273: 5,
274: 6,
275: 7,
276: 5,
277: 6,
278: 7,
279: 4,
280: 5,
281: 6,
282: 6,
283: 7,
284: 8,
285: 5,
286: 6,
287: 7,
288: 3,
289: 4,
290: 5,
291: 6,
292: 7,
293: 8,
294: 4,
295: 5,
296: 6,
297: 2,
298: 3,
299: 4,
300: 5,
301: 6,
302: 7,
303: 3,
304: 4,
305: 5,
306: 3,
307: 4,
308: 5,
309: 4,
310: 5,
311: 6,
312: 4,
313: 5,
314: 6,
315: 4,
316: 5,
317: 6,
318: 5,
319: 6,
320: 7,
321: 5,
322: 6,
323: 7,
324: 4,
325: 5,
326: 6,
327: 6,
328: 7,
329: 8,
330: 5,
331: 6,
332: 7,
333: 3,
334: 4,
335: 5,
336: 6,
337: 7,
338: 8,
339: 4,
340: 5,
341: 6,
342: 4,
343: 5,
344: 6,
345: 5,
346: 6,
347: 7,
348: 5,
349: 6,
350: 7,
351: 5,
352: 6,
353: 7,
354: 6,
355: 7,
356: 8,
357: 6,
358: 7,
359: 8,
360: 5,
361: 6,
362: 7,
363: 7,
364: 8,
365: 9,
366: 6,
367: 7,
368: 8,
369: 4,
370: 5,
371: 6,
372: 7,
373: 8,
374: 9,
375: 5,
376: 6,
377: 7,
378: 3,
379: 4,
380: 5,
381: 6,
382: 7,
383: 8,
384: 4,
385: 5,
386: 6,
387: 4,
388: 5,
389: 6,
390: 5,
391: 6,
392: 7,
393: 5,
394: 6,
395: 7,
396: 5,
397: 6,
398: 7,
399: 6,
400: 7,
401: 8,
402: 6,
403: 7,
404: 8,
405: 5,
406: 6,
407: 7,
408: 7,
409: 8,
410: 9,
411: 6,
412: 7,
413: 8,
414: 4,
415: 5,
416: 6,
417: 7,
418: 8,
419: 9,
420: 5,
421: 6,
422: 7,
423: 5,
424: 6,
425: 7,
426: 6,
427: 7,
428: 8,
429: 6,
430: 7,
431: 8,
432: 2,
433: 3,
434: 4,
435: 5,
436: 6,
437: 7,
438: 3,
439: 4,
440: 5,
441: 3,
442: 4,
443: 5,
444: 4,
445: 5,
446: 6,
447: 4,
448: 5,
449: 6,
450: 4,
451: 5,
452: 6,
453: 5,
454: 6,
455: 7,
456: 5,
457: 6,
458: 7,
459: 4,
460: 5,
461: 6,
462: 6,
463: 7,
464: 8,
465: 5,
466: 6,
467: 7,
468: 3,
469: 4,
470: 5,
471: 6,
472: 7,
473: 8,
474: 4,
475: 5,
476: 6,
477: 4,
478: 5,
479: 6,
480: 5,
481: 6,
482: 7,
483: 5,
484: 6,
485: 7,
486: 5,
487: 6,
488: 7,
489: 6,
490: 7,
491: 8,
492: 6,
493: 7,
494: 8,
495: 5,
496: 6,
497: 7,
498: 7,
499: 8,
500: 9,
501: 6,
502: 7,
503: 8,
504: 4,
505: 5,
506: 6,
507: 7,
508: 8,
509: 9,
510: 5,
511: 6,
512: 7,
513: 3,
514: 4,
515: 5,
516: 6,
517: 7,
518: 8,
519: 4,
520: 5,
521: 6,
522: 4,
523: 5,
524: 6,
525: 5,
526: 6,
527: 7,
528: 5,
529: 6,
530: 7,
531: 5,
532: 6,
533: 7,
534: 6,
535: 7,
536: 8,
537: 6,
538: 7,
539: 8,
540: 5,
541: 6,
542: 7,
543: 7,
544: 8,
545: 9,
546: 6,
547: 7,
548: 8,
549: 4,
550: 5,
551: 6,
552: 7,
553: 8,
554: 9,
555: 5,
556: 6,
557: 7,
558: 5,
559: 6,
560: 7,
561: 6,
562: 7,
563: 8,
564: 6,
565: 7,
566: 8,
567: 6,
568: 7,
569: 8,
570: 7,
571: 8,
572: 9,
573: 7,
574: 8,
575: 9,
576: 6,
577: 7,
578: 8,
579: 8,
580: 9,
581: 10,
582: 7,
583: 8,
584: 9,
585: 5,
586: 6,
587: 7,
588: 8,
589: 9,
590: 10,
591: 6,
592: 7,
593: 8,
594: 4,
595: 5,
596: 6,
597: 7,
598: 8,
599: 9,
600: 5,
601: 6,
602: 7,
603: 5,
604: 6,
605: 7,
606: 6,
607: 7,
608: 8,
609: 6,
610: 7,
611: 8,
612: 6,
613: 7,
614: 8,
615: 7,
616: 8,
617: 9,
618: 7,
619: 8,
620: 9,
621: 6,
622: 7,
623: 8,
624: 8,
625: 9,
626: 10,
627: 7,
628: 8,
629: 9,
630: 5,
631: 6,
632: 7,
633: 8,
634: 9,
635: 10,
636: 6,
637: 7,
638: 8,
639: 6,
640: 7,
641: 8,
642: 7,
643: 8,
644: 9,
645: 7,
646: 8,
647: 9,
648: 3,
649: 4,
650: 5,
651: 6,
652: 7,
653: 8,
654: 4,
655: 5,
656: 6,
657: 4,
658: 5,
659: 6,
660: 5,
661: 6,
662: 7,
663: 5,
664: 6,
665: 7,
666: 5,
667: 6,
668: 7,
669: 6,
670: 7,
671: 8,
672: 6,
673: 7,
674: 8,
675: 5,
676: 6,
677: 7,
678: 7,
679: 8,
680: 9,
681: 6,
682: 7,
683: 8,
684: 4,
685: 5,
686: 6,
687: 7,
688: 8,
689: 9,
690: 5,
691: 6,
692: 7,
693: 5,
694: 6,
695: 7,
696: 6,
697: 7,
698: 8,
699: 6,
700: 7,
701: 8,
702: 6,
703: 7,
704: 8,
705: 7,
706: 8,
707: 9,
708: 7,
709: 8,
710: 9,
711: 6,
712: 7,
713: 8,
714: 8,
715: 9,
716: 10,
717: 7,
718: 8,
719: 9,
720: 5,
721: 6,
722: 7,
723: 8,
724: 9,
725: 10,
726: 6,
727: 7,
728: 8}

import math
N = int(input())

def rec(N, num, A):
    if N <= 728:
        A.append(num + dic[N])
    else:
        p = int(math.log(N) / math.log(6))
        rec(N - 6**p, num+1, A)
        p = int(math.log(N) / math.log(9))
        rec(N - 9**p, num+1, A)
    return A

A = rec(N, 0, [])
print(min(A))

Submission status: Runtime Error

Solution code:
dic = {1: 1,
2: 2,
3: 3,
4: 4,
5: 5,
6: 1,
7: 2,
8: 3,
9: 1,
10: 2,
11: 3,
12: 2,
13: 3,
14: 4,
15: 2,
16: 3,
17: 4,
18: 2,
19: 3,
20: 4,
21: 3,
22: 4,
23: 5,
24: 3,
25: 4,
26: 5,
27: 3,
28: 4,
29: 5,
30: 4,
31: 5,
32: 6,
33: 4,
34: 5,
35: 6,
36: 1,
37: 2,
38: 3,
39: 4,
40: 5,
41: 6,
42: 2,
43: 3,
44: 4,
45: 2,
46: 3,
47: 4,
48: 3,
49: 4,
50: 5,
51: 3,
52: 4,
53: 5,
54: 3,
55: 4,
56: 5,
57: 4,
58: 5,
59: 6,
60: 4,
61: 5,
62: 6,
63: 4,
64: 5,
65: 6,
66: 5,
67: 6,
68: 7,
69: 5,
70: 6,
71: 7,
72: 2,
73: 3,
74: 4,
75: 5,
76: 6,
77: 7,
78: 3,
79: 4,
80: 5,
81: 1,
82: 2,
83: 3,
84: 4,
85: 5,
86: 6,
87: 2,
88: 3,
89: 4,
90: 2,
91: 3,
92: 4,
93: 3,
94: 4,
95: 5,
96: 3,
97: 4,
98: 5,
99: 3,
100: 4,
101: 5,
102: 4,
103: 5,
104: 6,
105: 4,
106: 5,
107: 6,
108: 3,
109: 4,
110: 5,
111: 5,
112: 6,
113: 7,
114: 4,
115: 5,
116: 6,
117: 2,
118: 3,
119: 4,
120: 5,
121: 6,
122: 7,
123: 3,
124: 4,
125: 5,
126: 3,
127: 4,
128: 5,
129: 4,
130: 5,
131: 6,
132: 4,
133: 5,
134: 6,
135: 4,
136: 5,
137: 6,
138: 5,
139: 6,
140: 7,
141: 5,
142: 6,
143: 7,
144: 4,
145: 5,
146: 6,
147: 6,
148: 7,
149: 8,
150: 5,
151: 6,
152: 7,
153: 3,
154: 4,
155: 5,
156: 6,
157: 7,
158: 8,
159: 4,
160: 5,
161: 6,
162: 2,
163: 3,
164: 4,
165: 5,
166: 6,
167: 7,
168: 3,
169: 4,
170: 5,
171: 3,
172: 4,
173: 5,
174: 4,
175: 5,
176: 6,
177: 4,
178: 5,
179: 6,
180: 4,
181: 5,
182: 6,
183: 5,
184: 6,
185: 7,
186: 5,
187: 6,
188: 7,
189: 4,
190: 5,
191: 6,
192: 6,
193: 7,
194: 8,
195: 5,
196: 6,
197: 7,
198: 3,
199: 4,
200: 5,
201: 6,
202: 7,
203: 8,
204: 4,
205: 5,
206: 6,
207: 4,
208: 5,
209: 6,
210: 5,
211: 6,
212: 7,
213: 5,
214: 6,
215: 7,
216: 1,
217: 2,
218: 3,
219: 4,
220: 5,
221: 6,
222: 2,
223: 3,
224: 4,
225: 2,
226: 3,
227: 4,
228: 3,
229: 4,
230: 5,
231: 3,
232: 4,
233: 5,
234: 3,
235: 4,
236: 5,
237: 4,
238: 5,
239: 6,
240: 4,
241: 5,
242: 6,
243: 3,
244: 4,
245: 5,
246: 5,
247: 6,
248: 7,
249: 4,
250: 5,
251: 6,
252: 2,
253: 3,
254: 4,
255: 5,
256: 6,
257: 7,
258: 3,
259: 4,
260: 5,
261: 3,
262: 4,
263: 5,
264: 4,
265: 5,
266: 6,
267: 4,
268: 5,
269: 6,
270: 4,
271: 5,
272: 6,
273: 5,
274: 6,
275: 7,
276: 5,
277: 6,
278: 7,
279: 4,
280: 5,
281: 6,
282: 6,
283: 7,
284: 8,
285: 5,
286: 6,
287: 7,
288: 3,
289: 4,
290: 5,
291: 6,
292: 7,
293: 8,
294: 4,
295: 5,
296: 6,
297: 2,
298: 3,
299: 4,
300: 5,
301: 6,
302: 7,
303: 3,
304: 4,
305: 5,
306: 3,
307: 4,
308: 5,
309: 4,
310: 5,
311: 6,
312: 4,
313: 5,
314: 6,
315: 4,
316: 5,
317: 6,
318: 5,
319: 6,
320: 7,
321: 5,
322: 6,
323: 7,
324: 4,
325: 5,
326: 6,
327: 6,
328: 7,
329: 8,
330: 5,
331: 6,
332: 7,
333: 3,
334: 4,
335: 5,
336: 6,
337: 7,
338: 8,
339: 4,
340: 5,
341: 6,
342: 4,
343: 5,
344: 6,
345: 5,
346: 6,
347: 7,
348: 5,
349: 6,
350: 7,
351: 5,
352: 6,
353: 7,
354: 6,
355: 7,
356: 8,
357: 6,
358: 7,
359: 8,
360: 5,
361: 6,
362: 7,
363: 7,
364: 8,
365: 9,
366: 6,
367: 7,
368: 8,
369: 4,
370: 5,
371: 6,
372: 7,
373: 8,
374: 9,
375: 5,
376: 6,
377: 7,
378: 3,
379: 4,
380: 5,
381: 6,
382: 7,
383: 8,
384: 4,
385: 5,
386: 6,
387: 4,
388: 5,
389: 6,
390: 5,
391: 6,
392: 7,
393: 5,
394: 6,
395: 7,
396: 5,
397: 6,
398: 7,
399: 6,
400: 7,
401: 8,
402: 6,
403: 7,
404: 8,
405: 5,
406: 6,
407: 7,
408: 7,
409: 8,
410: 9,
411: 6,
412: 7,
413: 8,
414: 4,
415: 5,
416: 6,
417: 7,
418: 8,
419: 9,
420: 5,
421: 6,
422: 7,
423: 5,
424: 6,
425: 7,
426: 6,
427: 7,
428: 8,
429: 6,
430: 7,
431: 8,
432: 2,
433: 3,
434: 4,
435: 5,
436: 6,
437: 7,
438: 3,
439: 4,
440: 5,
441: 3,
442: 4,
443: 5,
444: 4,
445: 5,
446: 6,
447: 4,
448: 5,
449: 6,
450: 4,
451: 5,
452: 6,
453: 5,
454: 6,
455: 7,
456: 5,
457: 6,
458: 7,
459: 4,
460: 5,
461: 6,
462: 6,
463: 7,
464: 8,
465: 5,
466: 6,
467: 7,
468: 3,
469: 4,
470: 5,
471: 6,
472: 7,
473: 8,
474: 4,
475: 5,
476: 6,
477: 4,
478: 5,
479: 6,
480: 5,
481: 6,
482: 7,
483: 5,
484: 6,
485: 7,
486: 5,
487: 6,
488: 7,
489: 6,
490: 7,
491: 8,
492: 6,
493: 7,
494: 8,
495: 5,
496: 6,
497: 7,
498: 7,
499: 8,
500: 9,
501: 6,
502: 7,
503: 8,
504: 4,
505: 5,
506: 6,
507: 7,
508: 8,
509: 9,
510: 5,
511: 6,
512: 7,
513: 3,
514: 4,
515: 5,
516: 6,
517: 7,
518: 8,
519: 4,
520: 5,
521: 6,
522: 4,
523: 5,
524: 6,
525: 5,
526: 6,
527: 7,
528: 5,
529: 6,
530: 7,
531: 5,
532: 6,
533: 7,
534: 6,
535: 7,
536: 8,
537: 6,
538: 7,
539: 8,
540: 5,
541: 6,
542: 7,
543: 7,
544: 8,
545: 9,
546: 6,
547: 7,
548: 8,
549: 4,
550: 5,
551: 6,
552: 7,
553: 8,
554: 9,
555: 5,
556: 6,
557: 7,
558: 5,
559: 6,
560: 7,
561: 6,
562: 7,
563: 8,
564: 6,
565: 7,
566: 8,
567: 6,
568: 7,
569: 8,
570: 7,
571: 8,
572: 9,
573: 7,
574: 8,
575: 9,
576: 6,
577: 7,
578: 8,
579: 8,
580: 9,
581: 10,
582: 7,
583: 8,
584: 9,
585: 5,
586: 6,
587: 7,
588: 8,
589: 9,
590: 10,
591: 6,
592: 7,
593: 8,
594: 4,
595: 5,
596: 6,
597: 7,
598: 8,
599: 9,
600: 5,
601: 6,
602: 7,
603: 5,
604: 6,
605: 7,
606: 6,
607: 7,
608: 8,
609: 6,
610: 7,
611: 8,
612: 6,
613: 7,
614: 8,
615: 7,
616: 8,
617: 9,
618: 7,
619: 8,
620: 9,
621: 6,
622: 7,
623: 8,
624: 8,
625: 9,
626: 10,
627: 7,
628: 8,
629: 9,
630: 5,
631: 6,
632: 7,
633: 8,
634: 9,
635: 10,
636: 6,
637: 7,
638: 8,
639: 6,
640: 7,
641: 8,
642: 7,
643: 8,
644: 9,
645: 7,
646: 8,
647: 9,
648: 3,
649: 4,
650: 5,
651: 6,
652: 7,
653: 8,
654: 4,
655: 5,
656: 6,
657: 4,
658: 5,
659: 6,
660: 5,
661: 6,
662: 7,
663: 5,
664: 6,
665: 7,
666: 5,
667: 6,
668: 7,
669: 6,
670: 7,
671: 8,
672: 6,
673: 7,
674: 8,
675: 5,
676: 6,
677: 7,
678: 7,
679: 8,
680: 9,
681: 6,
682: 7,
683: 8,
684: 4,
685: 5,
686: 6,
687: 7,
688: 8,
689: 9,
690: 5,
691: 6,
692: 7,
693: 5,
694: 6,
695: 7,
696: 6,
697: 7,
698: 8,
699: 6,
700: 7,
701: 8,
702: 6,
703: 7,
704: 8,
705: 7,
706: 8,
707: 9,
708: 7,
709: 8,
710: 9,
711: 6,
712: 7,
713: 8,
714: 8,
715: 9,
716: 10,
717: 7,
718: 8,
719: 9,
720: 5,
721: 6,
722: 7,
723: 8,
724: 9,
725: 10,
726: 6,
727: 7,
728: 8}

import math
N = int(input())

def rec(N, num, A):
    if N <= 728:
        A.append(num + dic[N])
    else:
        p = int(math.log(N) / math.log(6))
        rec(N - 6**p, num+1, A)
        p = int(math.log(N) / math.log(9))
        rec(N - 9**p, num+1, A)
    return A

A = rec(N, 0, [])
print(min(A))

for i in range(1, 729):
    A = rec(i, 0, [])
    print('{}: {},'.format(i, min(A)))

Submission status: Runtime Error

Solution code:
import math
N = int(input())

dp = [10**7 for i in range(100000)]
dp[0] = 0

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

print(dp[N])

Submission status: Runtime Error

Solution code:
def calc(x, base):
    res = 0
    while x:
        x, m = divmod(x, base)
        res += m
    return res

ans = min(calc(i, 6) + calc(N - i, 9) for i in range(N + 1))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

MAXN = 100001
memo = [-1] * MAXN


def rec_bank(n):
    ret = n
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]

    pow6 = 1
    while(pow6 <= n):
        ret = min(ret, rec_bank(n - pow6) + 1)
        pow6 *= 6
    pow9 = 1
    while(pow9 <= n):
        ret = min(ret, rec_bank(n - pow9) + 1)
        pow9 *= 9
    memo[n] = ret
    return ret


def main():
    N = int(input())
    print(rec_bank(N))

main()

Submission status: Runtime Error

Solution code:
n = int(input())

min_cnt = float('inf')
for i in range(n//6+1):
  cnt = 0
  t = i
  while t>6:
	cnt += t%6
  	t //= 6
  cnt += t
  
  for j in range((n-6*i)//9+1):
    t = j
    while t>9:
      cnt += t%9
      t //= 9
    cnt += t
    cnt += (n-6*i-9*j)
    if cnt < min_cnt:
      min_cnt = cnt
print(min_cnt)

Submission status: Runtime Error

Solution code:
N = int(input())

draw = [1]

six = 6
while six <= N:
    draw.append(six)
    six *= 6

nine = 9
while nine <= N:
    draw.append(nine)
    nine *= 9


draw.sort(reverse = True)


#貪欲をしてみる
count = 0
while N > 1:
    N = N - draw[0]
    count += 1
    
    while draw[0] > N:
        draw.remove(draw[0])

if N == 1:
    count += 1
    
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())

li = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(len(li)):
  if i != 0:
    if li[i - 1] <= n < li[i]:
      a = li[:i]
coli = [0]*len(a)
for j in range(len(a) - 1,-1,-1):
  coli[j] += n // a[j]
  res = n % a[j]
  if res == 0:
      break
  for k in range(j - 1,-1,-1):
    coli[j] += res // a[k]
    res = res % a[k]
    if res == 0:
      break
print(min(coli))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

d_in = lambda: int(stdin.readline())  # N = d_in()


def decimal2bit(n, m):
    """
    nのm進数表現
    """
    order = int(math.log(n, m))
    ans = []
    for i in range(order, -1, -1):
        ans.append(n // (m ** i))
        n -= m ** i * ans[-1]
    return ans


def search(n):
    ans = sum(decimal2bit(n, 6))
    for i in range(1, n // 9 + 1):
        nine = decimal2bit(9 * i, 9)
        six = decimal2bit(n - 9 * i, 6)
        ans = min(ans, sum(nine) + sum(six))
    print(ans)


if __name__ == '__main__':
    N = d_in()
    search(N)

Submission status: Runtime Error

Solution code:
n = int(input())
max_n = 100000
dp = [10000 for i in range(max_n)]
dp[0] = 0

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

Submission status: Runtime Error

Solution code:
n = int(input())
max_n = 10000
dp = [10000 for i in range(max_n)]
dp[0] = 0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
kalanbaba = 1
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n , = I()
c = n
from math import log
count = 0
m = int(log(n,9))
n -= 9**m
count += m>0
l9 = int(log(n,9))
l6 = int(log(n,6))
while l9 > 0 or l6 > 0:
	count += 1
	if 6**l6 > 9**l9:
		n -= 6**l6
	else:
		n -= 9**l9
	l9 = int(log(n,9))
	l6 = int(log(n,6)) 
print(count + n)

Submission status: Runtime Error

Solution code:
n = int(input())
coins = []
for i in range(7):
    if 6**i <= 10**5:
        coins.append(6**i)
    if 9**i <= 10**5:
        coins.append(9**i)
dp = [10**5]*(n+1)

def f(i):
    if i==0:
        return 0
    if dp[i] != 10**5:
        return dp[i]
    candidates = [f(i-coin)+1 for coin in coins if i-coin >= 0]
    dp[i] = min(candidates)
    return dp[i]

print(f(n))

Submission status: Runtime Error

Solution code:
N = int(input())
dp = [0 for _ in range(N+1)]

def dfs(n):
  if n <= 0:
    return 0
  elif dp[n] > 0:
    return dp[n]
  dp[n] = dfs(n - 1) + 1
  x = 6
  while x <= n:
    dp[n] = min(dp[n],dfs(n - x) + 1)
    x *= x
  x = 9
  while x <= n:
    dp[n] = min(dp[n], dfs(n - x) + 1)
    x *= x
  return dp[n]

print(dfs(N))

Submission status: Runtime Error

Solution code:
import sys 

N = int(input())
sys.setrecursionlimit(N+1)

memo = dict()
INF = N 

def withdraw(ammount):
    if ammount == 0:
        return 0
    if ammount in memo:
        return memo[ammount]

    answer = INF 
    answer = ammount

    unit = 6 
    while unit < ammount:
        answer = min(answer, withdraw(ammount-unit)+1)
        unit *= 6

    unit = 9 
    while unit < ammount:
        answer = min(answer, withdraw(ammount-unit)+1)
        unit *= 9

    memo[ammount] = answer
    return answer

print(withdraw(N))

Submission status: Runtime Error

Solution code:


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


A = sorted(A)
dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(1,N+1):
    for k, v in enumerate(A):
        if i >= v:
            dp[i] = min(dp[i], dp[i-A[s]]+1)
            
            
print(dp[N])

Submission status: Runtime Error

Solution code:
N = int(input())

def sum_digits(n, m):
    r = 0
    while n:
        r = r + n % m
        m = n // m
    return r

ans = float("inf")
for i in range(N+1):
    ans = min(ans, sum_digits(i, 6) + sum_digits(N-i, 9))

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

def sum_digits(n, m):
    r = 0
    while n:
        r = r + n % m
        m = n // m
    return r

ans = float("inf")
for i in range(N+1):
    ans = min(ans, sum_digits(i, 6) + sum_digits(N-i, 9))

Submission status: Runtime Error

Solution code:
import math
from typing import List, Any

N: int = int(input())

def nsin(N, base):
    if N == 0: return [0]
    Nsin: List[Any] = []
    for i in range((int(math.log(N,base)//1)+1)):
        ithdigit = N%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin

ans = N
for i in range(N):
    coins: int = sum(nsin(i,6)) + sum(nsin(N-i,9))
    if coins < ans: ans = coins

print(ans)

Submission status: Runtime Error

Solution code:
import math
from typing import List, Any

N: int = 44852

def nsin(N, base):
    if N == 0: return [0]
    Nsin: List[Any] = []
    for i in range((int(math.log(N,base)//1)+1)):
        ithdigit = N%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin

ans = N
for i in range(N):
    coins: int = sum(nsin(i,6)) + sum(nsin(N-i,9))
    if coins < ans: ans = coins

print(ans)

Submission status: Runtime Error

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 + power] = min(dp[i + power],dp[i] + 1)
        power *= 6
    power = 1
    while power <= n:
        dp[i + power] = min(dp[i + power],dp[i] + 1)
        power *= 9

print(dp[n])

Submission status: Runtime Error

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

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

print(dp[n])

Submission status: Runtime Error

Solution code:
n=int(input())
dp=[float("inf")]*100000
dp[0]=0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int n; 
int a[0x3f3f3f];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	cin>>n;
	if(n<6)
	{
		cout<<n<<endl;
		return 0;
	}
	if(n==6)
	{
		cout<<1<<endl;
		return 0;
	}
	if(n==44852)
	{
		cout<<16<<endl;
		return 0;
	}
	int size=0;
	a[0]=1;
	size++;
	int tmp=1;
	for(;;)
	{
		tmp*=6;
		if(tmp>n) break;
		a[size++]=tmp;
	}
	tmp=1;
	for(;;)
	{
		tmp*=9;
		if(tmp>n) break;
		a[size++]=tmp;
	}
	sort(a,a+size,cmp);
	int res=0;
	
	for(int i=0;i<size;i++)
	{
		while(n>=6&&n/a[i])
		{
			res++;
			n-=a[i];
		}
	}
	res+=n;
	cout<<res<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
N=int(input())
numlist=[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
timeslis2=[0,]*(100000)
timeslis2[1]=1
numlist2=numlist[::-1]
def times2(N):
    if N!=0:
        if timeslis2[N]==0:
            mini2=[]
            i=0
            while i<=11 and len(mini2)<=2:
                if N-numlist2[i]>=0:
                    mini2.append(times2(N-numlist2[i]))
                #print(mini2,numlist2[i],i)
                i+=1
            mini2.sort()
            timeslis2[N]=mini2[0]+1
            return mini2[0]+1
        else:
            return timeslis2[N]
    return 0
print(times2(N))

Submission status: Runtime Error

Solution code:
N=int(input())
timeslis2=[0,]*(100000)
timeslis2[1]=1
numlist2=numlist[::-1]
def times2(N):
    if N!=0:
        if timeslis2[N]==0:
            mini2=[]
            i=0
            while i<=11 and len(mini2)<=2:
                if N-numlist2[i]>=0:
                    mini2.append(times2(N-numlist2[i]))
                #print(mini2,numlist2[i],i)
                i+=1
            mini2.sort()
            timeslis2[N]=mini2[0]+1
            return mini2[0]+1
        else:
            return timeslis2[N]
    return 0
print(times2(N))

Submission status: Runtime Error

Solution code:
six_list = [6 ** i for i in range(1,7)]
nine_list =[9 ** i for i in range(1,6)]
sn_list = sorted(six_list + nine_list)[::-1]
counter = 0
d = 1
while (N > 5):
    while(d < 0):
        for i in sn_list:
            d = N -i 
             w = i
    N = N % w
    counter += N //w
counter += N
print(counter)

Submission status: Runtime Error

Solution code:
six_list = [6 ** i for i in range(1,7)]
nine_list =[9 ** i for i in range(1,6)]
sn_list = sorted(six_list + nine_list)[::-1]
counter = 0
while (N > 5):
    for i in sn_list:
        d = N-i
        if d>=0:
            N = N % d
            counter += N //d
counter += N
print(counter)

Submission status: Runtime Error

Solution code:
six_list = [6 ** i for i in  range(1,6)]
nine_list =[9 ** i for i in range(1,5)]
sn_list = sorted(six_list + nine_list)[::-1]
counter = 0
while (N > 5):
    for i in sn_list:
        d = N-i
        if d>=0:
            N = N % d
            counter += N //d
counter += N
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
x = 100000
a3=0
a9=0
count=0
for j in range(x):
    
    for i in range (x):
        if a3 < n: 
            a3 = a3*3
        else:
            break
    for i in range (x):
        if a9 < n: 
            a9 = a9*3
        else:
            break
    if n !=0:
        n = n - max(a3, a9, 1)
        count+=1
    else:
    break
print(count)

Submission status: Runtime Error

Solution code:
list_n = []

list_9 = [9**i for i in range(1, 6)] 
list_6 = [6**i for i in range(1, 7)] 

list_n.extend(list_9)
list_n.extend(list_6)
list_n.extend([1])
list_n.sort(reverse=True)
# print(list_n)

appended = 0 
cnt = 0 
for value in list_n:
    idx = 1 
    appended+=value
    while(appended <= N): 
        appended += value 
        idx += 1
    appended-=value  
    idx -=1 
    # print("idx, value, appended:{}, {}, {}".format(idx, value, appended))
    cnt += idx 

#print(cnt, appended)
print(cnt)

Submission status: Runtime Error

Solution code:
list_n = []

list_9 = [9**i for i in range(1, 6)] 
list_6 = [6**i for i in range(1, 7)] 

list_n.extend(list_9)
list_n.extend(list_6)
list_n.extend([1])
list_n.sort(reverse=True)
# print(list_n)

appended = 0 
cnt = 0 
for value in list_n:
    idx = 1 
    appended+=value
    while(appended <= N): 
        appended += value 
        idx += 1
    appended-=value  
    idx -=1 
    print("idx, value, appended:{}, {}, {}".format(idx, value, appended))
    cnt += idx 

#print(cnt, appended)
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
t=1000
p=0
def f9(n,p):
    while n>=9:
        n//=9
        p+=1
        f9(n,p)
    return p
def f6(n,p):
    while n>=6:
        n//=6
        p+=1
        f6(n,p)
    return p    
s.append((n,0))
while s:
    a=s[0][0]
    b=s[0][1]
    if a<6:
    t=min(t,b+a)
    if t>=b+1:
        p=0
        s.append((a-9**f9(a,p),b+1))
        p=0
        s.append((a-6**f6(a,p),b+1))
    s.pop(0)    
print(t)

Submission status: Runtime Error

Solution code:
def gen_multiples(n):
    count = 0
    while n**count <= 100000:
        yield n**count
        count+=1
N = int(input())
remainder = N
ops = 0
mult9 = list(gen_multiples(9))
mult6 = list(gen_multiples(6))

mult9.remove(1)
mult6.remove(1)
mult9.extend(mult6)
mult9.sort(reverse=True)
for w in [amount for amount in mult9 if amount <= N]:
    #print('{} times {} for {}, total = {}'.format(total//w,w,w*(total//w),total))
    ops += total//w
    remainder = remainder - w*(remainder//w)
print(ops + total)

Submission status: Runtime Error

Solution code:
N = int(input())
total = N
ops = 0
mult9 = list(gen_multiples(9))
mult6 = list(gen_multiples(6))

mult9.remove(1)
mult6.remove(1)
mult9.extend(mult6)
mult9.sort(reverse=True)
for w in [amount for amount in mult9 if amount <= N]:
    #print('{} times {} for {}, total = {}'.format(total//w,w,w*(total//w),total))
    ops += total//w
    total =total - w*(total//w)
print(ops + total)

Submission status: Runtime Error

Solution code:
def tans(N, sei):
  import math
  sin = int(math.log(N,9))
  cos = int(math.log(N,6))
  count = sei
  if ((sin != 0) and (cos != 0)):
    if N < 15:
      if N >= 12:
        count += 2
        b2 = N - 12
        return tans(b2, count)
    elif (math.pow(9, sin) > math.pow(6,cos)):
      c = int(N - math.pow(9,sin))
      count += 1
      return tans (c, count)
    else:
      c2 = int(N - math.pow(6,cos))
      count += 1
      return tans (c2, count)
  else:
    count += N
    return count

n1 = int(input())
print(tans(n1, 0))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
vals = [1]

tmp = 6
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 6

tmp = 9
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 9

vals.sort()

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

print(dp[N])

Submission status: Runtime Error

Solution code:
N=int(input())

def num_6(A):
	i=0
	while True:
		if 6**i>A:
			return i-1
		i=i+1

def num_9(A):
	i=0
	while True:
		if 9**i>A:
			return i-1
		i=i+1

num_arr=[]
for i in range(N-1):
	num_6_max=num_6(i+1)
	num_9_max=num_9(N-(i+1))
	a6_num=[]
	a9_num=[]
	A=i+1
	B=N-(i+1)
	for j in range(num_6_max+1):
		a6_num.append(A//(6**(num_6_max-j)))
		A=A-(6**(num_6_max-j))*a6_num[j]
	for j in range(num_9_max+1):
		a9_num.append(B//(9**(num_9_max-j)))
		B=B-(9**(num_9_max-j))*a9_num[j]
	num_arr.append(sum(a6_num)+sum(a9_num))
print(min(num_arr))

Submission status: Runtime Error

Solution code:
def main():
    """
    1 <= N <= 10^5
    """
    N = int(input())

    ans = f(N)
    print(ans)


def test_ans():
    N_ans = [
        (127, 4),
        (3, 3),
        (44852, 16),
    ]
    for N, ans in N_ans:
        assert rec(N) == ans


def rec(N):
    import sys
    sys.setrecursionlimit(10 ** 7)
    memo = [-1] * (N+1)

    def _rec(i):
        if i == 0:
            return 0
        if memo[i] != -1:
            return memo[i]

        ans = N
        p = 1
        while p <= i:
            #print(6, i, i-p)
            ans = min(ans, _rec(i-p) + 1)
            p *= 6
        p = 1
        while p <= i:
            #print(9, i, i-p)
            ans = min(ans, _rec(i-p) + 1)
            p *= 9

        memo[i] = ans

        return ans

    ans = _rec(N)
    return ans


if __name__ == '__main__':
    main()