Problem:


循環小数

 2 つの正の整数 p, q を入力し、 p / q を小数として正確に表現することを考えます。(ただし、0 < p < q < 106とします。)

 このとき、結果は

      
 有限の桁で正確に表現できる。

      
ある桁の範囲を繰り返す循環小数となる。

 のいずれかとなります。筆算と同じ手順で1桁ずつ小数部を求めていくと、

      
 割り切れた(余りが 0 になった)なら、そこまでの桁で正確に表現できた。

      
 1度出てきた余りが、再び現れたなら、循環した。

 と区別できます。

 2 つの整数 p, q を入力すると、 p / q を小数で表した時の、小数部を出力するプログラムを作成してください。 ただし、

      
 結果が有限の桁で正確に表現できる時は、数値だけを 1 行に出力してください。

      
 結果が循環小数になる時は次のように 2 行に出力してください。
      

           
最初の行に、循環する部分までの数字を出力してください。

           
次の行には、循環しない部分の下には空白を出力し、循環する部分の下には「^」を出力してください。

      

      
 いずれの場合も数字列は 80 文字を超えることはないものとします。

Input

入力は複数のデータセットからなります。各データセットとして、p, q が空白区切りで１行に与えられます。データセットの数は 250 を超えません。

Output

データセットごとに、循環しない小数の場合は数値の小数部分を(この場合 1 行)、循環小数の場合は循環するまでの数字と循環する部分を示す記号「^」(この場合 2 行) を出力してください。

Sample Input

1 12
10000 32768
1 11100
1 459550

Output for the Sample Input

083
  ^
30517578125
00009
  ^^^
00000217604178
  ^^^^^^^^^^^^



Sample input:
1 12
10000 32768
1 11100
1 459550


Sample output:
083
  ^
30517578125
00009
  ^^^
00000217604178
  ^^^^^^^^^^^^

Submission status: Accepted

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 80
    PREC=180
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        r = r'(.{%d})\1{%d,}' % (rep, int(maxlen/rep))  #ex. '(.{6})\\1{13,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.rep=%d' % rep)

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Accepted

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

import sys
import os

for s in sys.stdin:
    p, q = map(int, s.split())
    #print('----------', p, q)
    pair_lst = []
    is_devidable = False
    cycle_start_index = None

    while True:
        quot = (10 * p) // q
        rem = (10 * p) % q
        pair = (quot, rem)

        if rem == 0:
            is_devidable = True
            pair_lst.append(pair)
            break

        if pair in pair_lst:
            cycle_start_index = pair_lst.index(pair)
            break
        else:
            pair_lst.append(pair)
            p = rem

    # answer
    for pair in pair_lst:
        print(pair[0], end='')
    print()

    if is_devidable:
        pass
    else:
        # hat
        for i, pair in enumerate(pair_lst):
            if i >= cycle_start_index:
                print('^', end='')
            else:
                print(' ', end='')
        print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113
"""
import sys



def solve(p, q):
    quotients = []
    mods = []
    cyclic = False
    cycle_start = 0
    cycle_length = 0

    while True:
        mods.append(p)
        p *= 10
        quotients.append(p // q)
        p = p % q

        if p == 0:
            break
        if p in mods:
            cyclic = True
            cycle_start = mods.index(p)
            cycle_length = len(quotients) - mods.index(p)
            break

    return cyclic, quotients, cycle_start, cycle_length


def main(args):
    for line in sys.stdin:
        p, q = [int(x) for x in line.strip().split(' ')]
        cyclic, quotients, cycle_start, cycle_length = solve(p, q)
        if cyclic:
            print(''.join(map(str, quotients)))
            print(' '*cycle_start + '^'*cycle_length)
        else:
            print(''.join(map(str, quotients)))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# Aizu Problem 0113: Period

#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def repeating_decimals(n, d):
    pre = n // d
    m = n - pre * d
    if m == 0:
        return "0", ""
    remains = []
    fraction = []
    while True:
        k = m // d
        fraction.append(k)
        m = m - k * d
        if m in remains:
            remains.append(m)
            break
        remains.append(m)
        if m == 0:
            return ''.join([str(x) for x in fraction[1:]]), ""
        m *= 10
    # fraction is periodic at this point:
    fraction = fraction[1:]
    idx = remains.index(m)
    non_periodic = ''.join([str(x) for x in fraction[:idx]])
    periodic = ''.join([str(x) for x in fraction[idx:]])
    return non_periodic, periodic


for line in sys.stdin:
    p, q = [int(_) for _ in line.split()]
    p1, p2 = repeating_decimals(p, q)
    print(p1 + p2)
    if len(p2) > 0:
        print(' ' * len(p1) + '^' * len(p2))

Submission status: Accepted

Solution code:
while True:
    try:
        a, b = list(map(int, input().split()))
    except:
        break
    done = {}
    i = 0
    flag = -1
    while a != 0:
        a *= 10
        if a in done:
            flag = done[a]
            break
        else:
            done[a] = i
        print(str(a//b), end = "")
        a = a % b
        if a == 0:
            break
        i += 1
    print()
    if flag > -1:
        print(" " * flag + "^" * (i-flag))

Submission status: Accepted

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

N = list(get_input())
for l in range(len(N)):
    p,q = [int(i) for i in N[l].split()]
    P,Q = p,q

    amari = [0 for i in range(q+1)]
    amari[p] = 1

    s = -1
    l = -1

    cnt = 2
    while True:
        p *= 10
        p1 = p // q
        p2 = p % q

        if p2 == 0:
            s = cnt
            l = 0
            break

        if amari[p2] == 0:
            amari[p2] = cnt
            cnt += 1
            p = p2
        else:
            s = amari[p2]
            l = cnt - amari[p2]
            break

    p,q = P,Q
    for i in range(s-1):
        print((p*10)//q, end="")
        p = (p*10) % q
    for i in range(l):
        print((p*10)//q, end="")
        p = (p*10) % q
    print("")

    if l > 0:
        for i in range(s-1):
            print(" ", end="")
        for i in range(l):
            print("^", end="")
        print("")

Submission status: Accepted

Solution code:
# AOJ 0113: Period
# Python3 2018.6.20 bal4u

while True:
	try: p, q = list(map(int, input().split()))
	except: break
	rr = [-1]*q
	rr[p] = 0
	ans = ''
	for k in range(1, q):
		p *= 10
		ans += str(p // q)
		r = p % q
		if r == 0 or rr[r] >= 0:
			print(ans)
			if rr[r] >= 0: print(*[' ']*rr[r], *['^']*(k-rr[r]), sep='')
			break
		rr[r], p = k, r

Submission status: Accepted

Solution code:
import sys
import itertools
for line in sys.stdin:
	try:
		p, q = map(int, line.split())
	except ValueError:
		break
	p, r = p / q, p % q * 10
	visited = {}
	visited[r] = 0
	res = ''
	for i in itertools.count(1):
		p, r = r / q, r % q * 10
		res += str(p)
		if r == 0:
			print res
			break
		elif r in visited:
			print res
			n = visited[r]
			print ' ' * n + '^' * (i - n)
			break
		visited[r] = i

Submission status: Accepted

Solution code:
import sys
import itertools
for line in sys.stdin:
	p, q = map(int, line.split())
	p, r = p / q, p % q * 10
	visited = {}
	visited[r] = 0
	res = ''
	for i in itertools.count(1):
		p, r = r / q, r % q * 10
		res += str(p)
		if r == 0:
			print res
			break
		elif r in visited:
			print res
			n = visited[r]
			print ' ' * n + '^' * (i - n)
			break
		visited[r] = i

Submission status: Accepted

Solution code:
import sys
import itertools
for line in sys.stdin:
	p, q = map(int, line.split())
	p, r = p / q, p % q * 10
	visited = {r: 0}
	res = ''
	for i in itertools.count(1):
		p, r = r / q, r % q * 10
		res += str(p)
		if r == 0:
			print res
			break
		elif r in visited:
			print res
			n = visited[r]
			print ' ' * n + '^' * (i - n)
			break
		visited[r] = i

Submission status: Accepted

Solution code:
while True:
    try:
        p,q=map(int,raw_input().split())
    except EOFError:
	break
    S,L=[],[]
    while True:
        L.append(p/q)
        amari=p%q
        if amari in S:
            S.append(amari)
            break
        S.append(amari)
        p=amari*10
    if S[-1]==S[-2]==0:
        print "".join(map(str,L[1:-1]))
    else:
        t=S.index(S[-1])
        s=" "*t+"^"*(len(S)-t-1)
        print "".join(map(str,L[1:]))
        print s

Submission status: Accepted

Solution code:
def ge_div(a, b):
    while a!=0:
        yield a/b,a%b
        a = (a%b)*10

while True:
    try:
        p, q = map(int, raw_input().split())
    except:
        break
    rem_list = [p]
    ans = ""
    index = -1
    for a,b in ge_div(10*p,q):
        ans += str(a)
        rem_list.append(b)
        if b in rem_list[:-1]:
            index = rem_list.index(b)
            break
    print ans
    if not index == -1:
        print " "*index + "^"*(len(ans)-index)

Submission status: Accepted

Solution code:
def ge_div(a, b):
    while a!=0:
        yield a/b,a%b
        a = (a%b)*10

while True:
    try:
        p, q = map(int, raw_input().split())
    except:
        break
    rem_list = [p]
    ans = ""
    index = -1
    for a,b in ge_div(10*p,q):
        ans += str(a)
        if b in rem_list:
            index = rem_list.index(b)
            break
        rem_list.append(b)
    print ans
    if not index == -1:
        print " "*index + "^"*(len(ans)-index)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main():
    for line in stdin:
        p, q = (int(s) for s in line.split())

        div_list = []
        mod_list = []

        d, m = divmod(p, q)
        p = m * 10
        mod_list.append(m)

        while m:
            d, m = divmod(p, q)
            div_list.append(d)
            p = m * 10
            if m in mod_list:
                break
            mod_list.append(m)

        print(*div_list, sep='')

        if m:
            space = mod_list.index(m)
            circum = len(mod_list) - space
            print(' ' * space + '^' * circum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def div(p,q):
	deci,rest = "",[p]
	while True:
		p *= 10
		deci += str(p//q)
		p -= q*(p//q)
		rest.append(p)
		if rest[-1] == 0: return deci,rest
		if rest[-1] in rest[:-1]: return deci,rest
		
while True:
	try:
		p,q = map(int, raw_input().split())
		deci,rest = div(p,q)
		if rest[-1] == 0:
			print deci
		else:
			print deci
			print " "*rest.index(rest[-1])+"^"*(len(rest)-rest.index(rest[-1])-1)
	except:
		break

Submission status: Accepted

Solution code:
def div(p,q):
	d,r = "",[p]
	while True:
		p *= 10
		d += str(p//q)
		p -= q*(p//q)
		r.append(p)
		if r[-1] == 0 or r[-1] in r[:-1]: return d,r
		
while True:
	try:
		p,q = map(int, raw_input().split())
		d,r = div(p,q)
		s = r.index(r[-1])
		if s == len(r)-1:
			print d
		else:
			print "{}\n{}".format(d," "*s+"^"*(len(r)-s-1))
	except:
		break

Submission status: Accepted

Solution code:
while True:
  mem = {}
  try:
    p, q = map(int, raw_input().split())
  except EOFError:
    break
  a, b, c = "", p % q, 0
  while True:
    b = (b % q) * 10
    if b in mem or not b: 
      break
    mem[b] = len(a)
    a += str(b // q)
  print(a)
  if b != 0:
    print(" " * mem[b] + "^" * (len(a) - mem[b]))

Submission status: Accepted

Solution code:
for line in open(0).readlines():
    p, q = map(int, line.split())
    U = [0]*q
    d = 1
    ans = []
    while U[p] == 0 and p > 0:
        U[p] = d
        k, p = divmod(10*p, q)
        ans.append(str(k))
        d += 1
    print("".join(ans))
    if p:
        print(" "*(U[p]-1) + "^"*(d-U[p]))

Submission status: Accepted

Solution code:
# 参考:http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1246588#1

while True:
	try:
		p, q = (int(x) for x in input().split())
		m = p % q
		i = -1
		decs = ['']
		mods = [m]
		while m != 0:
			d, m = divmod(m * 10, q)
			decs.append(str(d))
			if m not in mods:
				mods.append(m)
			else:
				i = mods.index(m)
				break
		if len(decs) == 0:
			print(0)
		else:
			print(''.join(decs))
			if m != 0 and i > -1:
				for j, dec in enumerate(decs):
					if j > i:
						decs[j] = '^' * len(decs[j])
					else:
						decs[j] = ' ' * len(decs[j])
				print(''.join(decs))
	except:
		break

Submission status: Accepted

Solution code:
def ans(p,q):
    p=p%q
    _q=q

    mods=[p%q]
    score=""
    while True:
        p*=10
        score+=str(p//q)
        p=p%q
        if p in mods:
            break
        else:
            mods.append(p)

    mods=[]
    score2=""
    while True:
        p*=10
        score2+=str(p//q)
        p=p%q
        if p in mods:
            break
        else:
            mods.append(p)
    score2=score2[:-1]
    if score2=="0":
        ans=score[:-1]
    else:
        ans="{0}\n{1}"
        padding=" "*(len(score)-len(score2))+"^"*len(score2)
        ans=ans.format(score,padding)
    return ans


while True:
    try:
        p,q=[int(i) for i in input().split(" ")]
        print(ans(p,q))
    except EOFError:
        break

Submission status: Accepted

Solution code:
while True:
    try:
        p,q = [int(x) for x in input().split()]
    except:
        break

    L = []
    s = ""
    p %= q
    f = None
    L.append(p)
    i = 0
    if p == 0:
        #print(0)
        continue
    
    while p > 0:
        i = i+1
        p *=10
        r = p // q
        p %=q
        s += str(r)
        if p in L:
            f = L.index(p)
            break
        else:
            L.append(p)
    print(s)
    if f is not None:
        t = " " * f + "^" * (len(s)-f)
        print(t)

Submission status: Accepted

Solution code:
while True:
    try:
        p, q = map(int, input().split())
        m = p % q
        i = -1
        decs = ['']
        mods = [m]
        while m != 0:
            d, m = divmod(m * 10, q)
            decs.append(str(d))
            if m not in mods:mods.append(m)
            else:
                i = mods.index(m)
                break
        if len(decs) == 0:print(0)
        else:
            print(''.join(decs))
            if m != 0 and i > -1:
                for j, dec in enumerate(decs):
                    if j > i:decs[j] = '^' * len(decs[j])
                    else:decs[j] = ' ' * len(decs[j])
                print(''.join(decs))
    except:break

Submission status: Accepted

Solution code:
while True:
    try:
        p, q = map(int, input().split())
        ans = ""
        r_list = [p]
        while True:
            p *= 10
            a, b = divmod(p,q)
            ans += str(a)
            if b == 0:
                print(ans)
                break
            elif b in r_list:
                print(ans)
                print(" "*r_list.index(b) + "^"*(len(r_list) - r_list.index(b)))
                break
            r_list.append(b)
            p -= a*q
    except:
        break

Submission status: Accepted

Solution code:
while True:
  try:
    p, q = map(int, input().split())
  except EOFError:
    break
  dic = [None] * q
  save = []
  counter = 0
  while p:
    if dic[p] != None:
      print("".join(save))
      print(" " * dic[p] + "^" * (counter - dic[p]))
      break
    dic[p] = counter
    save.append(str(p * 10 // q))
    p = p * 10 % q
    counter += 1
  else:
    print("".join(save))

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxreplen = 80
    PREC=200
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        #r = r'(.{%d})\1{%d,}' % (rep, int(maxreplen/rep)-1)
        r = r'(.{%d})\1{%d,}' % (rep, 10)
                                         #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxreplen:
            raise ValueError('This cannot happen.')

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 80
#    PREC=160
    PREC=200
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        r = r'(.{%d})\1{%d,}' % (rep, int(PREC/rep)-1)
                                         #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxreplen:
            raise ValueError('This cannot happen.')

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 85
    #maxlen = 160
    PREC=200
    #PREC=300
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        clip = min(int(PREC/rep),20)
        #r = r'(.{%d})\1{%d,}' % (rep, int(PREC/rep)-1)
        r = r'(.{%d})\1{%d,}' % (rep, clip)
                                         #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.')

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 80
    PREC=200
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        r = r'(.{%d})\1{%d,}' % (rep, int((PREC-40)/rep))  #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.rep=%d' % rep)

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 80
    PREC=200
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        r = r'(.{%d})\1{%d,}' % (rep, int((PREC-20)/rep))  #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.rep=%d' % rep)

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
from decimal import *
import re
def solve2(m, n):
    maxlen = 80
    PREC=300
    getcontext().prec = PREC
    x = Decimal(m) / Decimal(n)
    s = x.to_eng_string()
    if len(s) < PREC:
        return(s[2:],'')
    rep = 1
    while True:
        clip = max(int((PREC-20)/rep),1)
        r = r'(.{%d})\1{%d,}' % (rep, clip)  #ex. '(.{6})\\1{12,}'
        a=re.search(r, s)
        if a:
            break
        rep += 1
        if rep > maxlen:
            raise ValueError('This cannot happen.rep=%d' % rep)

    u = s[2:a.start()+len(a.group(1))]
    v = (' '*PREC + '^'*len(a.group(1)))[-len(u):]
    return(u,v)

while True:
    try:
        m,n = map(int, input().strip().split())
        s,t = solve2(m, n)
        print(s)
        if t!='':
            print(t)
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
while True:
  mem = {}
  p, q = map(int, raw_input().split())
  a, b, c = "", p % q, 0
  while True:
    b = (b % q) * 10
    if b in mem or not b: 
      break
    mem[b] = len(a)
    a += str(b // q)
  print(a)
  if b != 0:
    print(" " * mem[b] + "^" * (len(a) - mem[b]))