Problem:

Fast Forwarding

  Mr. Anderson frequently rents video tapes of his favorite classic films. Watching the films so many times, he has learned the precise start times of his favorite scenes in all such films. He now wants to find how to wind the tape to watch his favorite scene as quickly as possible on his video player.

  When the [play] button is pressed, the film starts at the normal playback speed. The video player has two buttons to control the playback speed: The [3x] button triples the speed, while the [1/3x] button reduces the speed to one third. These speed control buttons, however, do not take effect on the instance they are pressed. Exactly one second after playback starts and every second thereafter, the states of these speed control buttons are checked. If the [3x] button is pressed on the timing of the check, the playback speed becomes three times the current speed. If the [1/3x] button is pressed, the playback speed becomes one third of the current speed, unless it is already the normal speed.

  For instance, assume that his favorite scene starts at 19 seconds from the start of the film. When the [3x] button is on at one second and at two seconds after the playback starts, and the [1/3x] button is on at three seconds and at five seconds after the start, the desired scene can be watched in the normal speed five seconds after starting the playback, as depicted in the following chart.

  
  

  Your task is to compute the shortest possible time period after the playback starts until the desired scene starts. The playback of the scene, of course, should be in the normal speed.

Input

  The input consists of a single test case of the following format.

$t$

  The given single integer $t$ ($0 \leq t < 2^{50}$) is the start time of the target scene.
					    

Output

  Print an integer that is the minimum possible time in seconds before he can start watching the target scene in the normal speed.

Sample Input 1

19

Sample Output 1

5

Sample Input 2

13

Sample Output 2

5

Sample Input 3

123456789098765

Sample Output 3

85

Sample Input 4

51

Sample Output 4

11

Sample Input 5

0

Sample Output 5

0

Sample Input 6

3

Sample Output 6

3

Sample Input 7

4

Sample Output 7

2



Sample input:
19


Sample output:
5

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import math

n = int(stdin.readline().strip())

reserved = 1
maxspeed = 1

while True:
    if reserved + maxspeed * 3 > n:
        break
    maxspeed *= 3
    reserved += maxspeed * 2

ans = 1
n -= 1

i = 3
while i < maxspeed:
    ans += 2
    n -= i * 2
    i *= 3
n -= maxspeed

i = maxspeed
while i:
    ans += n // i
    n -= n // i * i
    i //= 3
stdout.writelines(str(ans + 1) + '\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

t = input()
ans = t

for p in range(1, 50):
    S = 2 * sum(3 ** i for i in range(p)) - 1
    if S > t:
        break
    num = 2 * p - 1
    rem = t - S
    for i in range(p):
        num += rem % 3
        rem /= 3
    num += rem
    ans = min(ans, num)
print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()

    def f(n):
        if n < 4:
            return n
        return (n-1) % 3 + f((n-1)//3-1) + 2

    return f(n)


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
t = int(input())

count = 0
speed = 1
margin = 0
while t > 0:
    t -= speed
    count += 1
    if margin + speed * 3 <= t:
        speed *= 3
        margin += speed
    elif t < margin:
        margin -= speed
        speed /= 3
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    T = read_int()
    print(solve(T))


def solve(T):
    if T <= 3:
        return T

    sec = 1
    T -= 1
    f = 3
    while T >= 2 * f:
        T -= 2 * f
        f *= 3
        sec += 2

    if T >= f:
        T -= f
        sec += 1
    else:
        f //= 3

    while T > 0:
        t = T // f
        T -= t * f
        sec += t
        f //= 3

    return sec


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()