Problem:


Score : 300 points

Problem Statement

You are given a string S of length N and another string T of length M.
These strings consist of lowercase English letters.

A string X is called a good string when the following conditions are all met:

Let L be the length of X. L is divisible by both N and M.

Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.

Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

If a good string does not exist, print -1; if it exists, print the length of the shortest such string.

Sample Input 1

3 2
acp
ae

Sample Output 1

6

For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6.

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
a,b=map(int, input().split())
max=0
s=input()
t=input()
if a>b:
    max=a
else:
    max=b
if lcm(a,b)>max:
    print(int(lcm(a,b)))
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
import fractions
n,m=map(int, input().split())
s=input()
t=input()
f=fractions.gcd(n,m)
ans=n*m//f
if f!=1:
    for i in range(f):
        if s[n//f*i]!=t[m//f*i]:ans=-1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 14 08:52:34 2018
AGC028A
@author: maezawa
"""

n, m = list(map(int, input().split()))
s = input()
t = input()

def gcm(a,b):
    while b:
        a, b = b,a%b
    return a

lcm = n*m//gcm(n,m)
possible = True

for k in range(lcm//n):
    if k*m%n == 0:
        if k*m//n < m and s[k] != t[k*m//n]:
            possible = False
            #print(k, k*n//m, s[k], t[k*n//m])
            break
for k in range(lcm//m):
    if k*n%m == 0:
        if k*n//m < n and t[k] != s[k*n//m]:
            possible = False
            #print(k, k*m//n, t[k], s[k*m//n])
            break
                                
    
if possible:
    print(lcm)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0):
    if S == T:
        print(M)
    else:
        p = int(N/M)
        for i in range(M):
            if T[i] != S[i*p]:
                print(-1)
                sys.exit()
        print(N)
elif (M % N == 0):
    if S == T:
        print(M)
    else:
        p = int(M/N)
        for i in range(N):
            if S[i] != T[i*p]:
                print(-1)
                sys.exit()
        print(M)
else:

    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0):
    if S == T:
        print(M)
    else:
        p = int(N/M)
        for i in range(M):
            if T[i] != S[i*p]:
                print(-1)
                sys.exit()
        print(N)
elif (M % N == 0):
    if S == T:
        print(M)
    else:
        p = int(M/N)
        for i in range(N):
            if S[i] != T[i*p]:
                print(-1)
                sys.exit()
        print(M)
else:
    print(int(lcm(N,M)))

Submission status: Wrong Answer

Solution code:
import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0):
    if S == T:
        print(M)
    else:
        p = int(N/M)
        for i in range(M):
            print(T[i],S[i*p])
            if T[i] != S[i*p]:
                print(-1)
                sys.exit()
        print(N)
elif (M % N == 0):
    if S == T:
        print(M)
    else:
        p = int(M/N)
        for i in range(N):
            print(S[i],T[i*p])
            if S[i] != T[i*p]:
                print(-1)
                sys.exit()
        print(M)
else:
    print(int(lcm(N,M)))

Submission status: Wrong Answer

Solution code:
import sys
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

# N < M
def gcd(N,M):
    if(N > M):
        tmp = N
        N = M
        M = tmp
    r = M % N
    while(r != 0):
        M = N
        N = r
        r = M%N
    return N

def lcm(N,M):
    return(N*M/gcd(N,M))

if (N % M == 0 or M % N == 0):
    if S!= T:
        print(-1)
else:
    print(int(lcm(N,M)))

Submission status: Wrong Answer

Solution code:
def Min(m,n):
    i=1
    while True:
        if (m*i)%n==0:
            break
        i+=1
    return m*i

N,M=[int(i) for i in input().split()]
S=input()
T=input()
Slist=list(S)
Tlist=list(T)
ans=0
LCM=0

print(Slist,Tlist)

if M==N:
    if S==T:
        ans=len(S)
    else:
        ans=-1
else:
    LCM=Min(N,M)
    print(LCM)
    if LCM==N*M:
        if Slist[0]==Tlist[0]:
            ans=LCM
        else:
            ans=-1
    else:
        a=int(LCM/N)
        b=int(LCM/M)
        LCM2=Min(a,b)
        print(LCM,LCM2,a,b)
        f=0
        j=0
        for i in range(int(LCM/LCM2)):
            print(Slist[i*b],Tlist[i*a])
            if Slist[i*b]!=Tlist[i*a]:
                f+=1
                break
                print(Slist[i*b],Tlist[i*a])
            j+=1
        if f==0:
            ans=LCM
        else:
            ans=-1
print(ans)

Submission status: Wrong Answer

Solution code:
iN ,iM = [int(_) for _ in input().split()]
sS = input().rstrip()
sT = input().rstrip()

def fgcd(a,b):
    if b :
        return fgcd(b,a%b)
    else:
        return a

iD = fgcd(iN,iM)
i = 0
while True:
    if iN -1  <  i * iM //iD   or iM -1  <  i*iN//iD :
        break
    if sS[i*iN//iD ] != sT[i*iM//iD  ] :
        print("-1")
        exit()
    i += 1
print(iN*iM//iD)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def solve(N, M, S, T):
    d = gcd(N, M)
    n = N // d
    m = M // d
    
    for i in range(d):
        if S[n*i] != T[m*i]:
            return -1
    return n * m * d
	

N, M = list(map(int, input().split()))
T = input()
S = input()
print(solve(N, M, S, T))

Submission status: Wrong Answer

Solution code:
def gcd(a, b):  
  if b == 0: return a
  return gcd(b, a % b)
n, m =  map(int, input().split())
g = gcd(n, m)
l = n * m / g
n = n/g
m = m/g
s = list(str(input()))[::int(n)]
t = list(str(input()))[::int(m)]
if s == t:
  print(l)
else:
  print("-1")

Submission status: Wrong Answer

Solution code:
import fractions
n,m = map(int, input().split(' '))
s = input()
t = input()
g = fractions.gcd(n, m)
Flag = True
for i in range(n):
    if (m*i)%n == 0:
        if s[i] != t[int((i*m)/n)]:
            Flag = False
if Flag:
    print(int((n*m)/g))

Submission status: Wrong Answer

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)

print(lcm(n,m) if n*2==m*3 or (n*2==(m+1)*3 and n!=m*2) or ((n+1)*2==m*3) else -1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n, m = map(int, input().split())
s = input()
t = input()

g = gcd(n, m)
lcm = n // g * m
if (lcm // n) // gcd(lcm // n, lcm // m) * (lcm // m) == lcm:
	#print("hoge")
	print(n // g * m)
else:
	p = (lcm // n) // gcd(lcm // n, lcm // m) * (lcm // m)
	#print(p)
	ok = True
	for i in range(lcm // p):
		#print(s[(lcm // m) * i], t[(lcm // n) * i])
		if s[(lcm // m) * i] != t[(lcm // n) * i]:
			ok = False
			break
	if ok:
		print(n // g * m)
	else:
		print(-1)

Submission status: Wrong Answer

Solution code:

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


N,M = list(map(int,input().split()))
S = input()
T = input()

ans = -1

pos_frc_N = []
for i in range(len(S)):
    pos_frc_N.append(i*(1/N))
    
pos_frc_M = []
for i in range(len(T)):
    pos_frc_M.append(i*(1/M))

overlap_N = []
overlap_M = []
for i in range(len(S)):
    if pos_frc_N[i] in pos_frc_M:
        overlap_N.append(i)
        overlap_M.append(pos_frc_M.index(pos_frc_N[i]))

tmp = 1
for i in range(len(overlap_N)):
    if  S[overlap_N[i]] != T[overlap_M[i]]:
        tmp = 0
        break

# calculate min number
    
if  tmp == 1:
    
    PF_S = factorize(N)
    PF_T = factorize(M)
    
    factor_S = []
    factor_T = []
    index_S = []
    index_T = []
    
    for i in range(len(PF_S)):
        factor_S.append(PF_S[i][0])
        index_S.append(PF_S[i][1])
    for i in range(len(PF_T)):
        factor_T.append(PF_T[i][0])
        index_T.append(PF_T[i][1])
        
    overlap_factor = []
    min_index = []
    for i in range(len(factor_S)):
        if  factor_S[i] in factor_T:
            overlap_factor.append(i)
            min_index.append(min([index_S[i],index_T[i]]))
    
    ans = 1
    for i in range(len(factor_S)):
        if not factor_S[i] in overlap_factor:
            ans *= factor_S[i]*index_S[i]
        else:
            ans *= factor_S[i]*min_index[overlap_factor.index(factor_S[i])]
    for i in range(len(factor_T)):
        if not factor_T[i] in overlap_factor:
            ans *= factor_T[i]*index_T[i]
            
print(ans)

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
s = input()
t = input()

nsky = n
msky = m
while not nsky % msky == 0:
    tmp = msky
    msky = nsky % msky
    nsky = tmp
skys = msky

idx_n = 1
idx_m = 1
idx_x = 0
okans = -1
skbs = 0

ncnt = 5
wn = n
while not int(wn / 10) == 0:
    wn = wn / 10
    ncnt = ncnt + 1

mcnt = 5
wm = m
while not int(wm / 10) == 0:
    wm = wm / 10
    mcnt = mcnt + 1


while n * idx_n < 10**ncnt and m * idx_m < 10**ncnt and okans < 0:
    if n * idx_n == m * idx_m:
        idx_2 = 0
        
        while (n/skys)*idx_2 < n:
            if s[int(n/skys)*idx_2] == t[int(m/skys)*idx_2]:
                if (n/skys)*(idx_2+1) == n:
                    okans = n * idx_n
                idx_2 = idx_2 + 1
            else:
                idx_2 = n
                
        if skbs == 0:
            skbs = idx_n

        idx_x = idx_x + 1
        idx_m = skbs * idx_x
        idx_n = skbs * idx_x
    elif n * idx_n > m * idx_m:
        idx_m = idx_m + 1
    elif n * idx_n < m * idx_m:
        idx_n = idx_n + 1

print(okans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

n, m = [int(i) for i in input().split()]
s = input()
t = input()

if not s[0] == t[0]:
	print(-1)
	exit()

nl_max = max(n, m)
nl_min = min(n, m)
if len(s) >= len(t):
	smax = s
	smin = t
else:
	smax = t
	smin = s
nl = nl_max
"""while nl < 10 ** 10:
	if nl % nl_min:
		nl += nl_max
		continue

	nb = True
	nl_x = [""] * nl
	for i in range(n):
		nl_x[int(i * nl / n)] = s[i]
	for i in range(m):
		if nl_x[int(i * nl / m)] == "" or nl_x[int(i * nl / m)] == t[i]:
			nl_x[int(i * nl / m)] = t[i]
		else:
			nb = False
			break
	else:
		if nb:
			print(nl)
			exit()
	nl += nl_max
print(-1)"""

while nl < 10 ** 6:
	if nl % nl_min:
		nl += nl_max
		continue

	for i in range(1, nl_max):
		tmp = int(i * nl / nl_max) * nl_min / nl
		if tmp % 1:
			continue
		elif not smin[int(tmp)] == smax[i]:
			break
	else:
		print(nl)
		exit()
	nl += nl_max
print(-1)

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
s = input()
t = input()

nsky = n
msky = m
while not nsky % msky == 0:
    tmp = msky
    msky = nsky % msky
    nsky = tmp
skys = msky

idx_n = 1
idx_m = 1
idx_x = 0
okans = -1
skbs = 0

ncnt = 2
wn = n
while not int(wn / 10) == 0:
    wn = wn / 10
    ncnt = ncnt + 1

mcnt = 2
wm = m
while not int(wm / 10) == 0:
    wm = wm / 10
    mcnt = mcnt + 1


while n * idx_n < 10**ncnt and m * idx_m < 10**ncnt and okans < 0:
    if n * idx_n == m * idx_m:
        idx_2 = 0
        
        while (n/skys)*idx_2 < n:
            if s[int(n/skys)*idx_2] == t[int(m/skys)*idx_2]:
                if (n/skys)*(idx_2+1) == n:
                    okans = n * idx_n
                idx_2 = idx_2 + 1
            else:
                idx_2 = n
                
        if skbs == 0:
            skbs = idx_n

        idx_x = idx_x + 1
        idx_m = skbs * idx_x
        idx_n = skbs * idx_x
    elif n * idx_n > m * idx_m:
        idx_m = idx_m + 1
    elif n * idx_n < m * idx_m:
        idx_n = idx_n + 1

print(okans)

Submission status: Wrong Answer

Solution code:
#coding: utf-8

# 標準入力から N, M, S, T を取得する
N, M = map(int, input().split())
S = input()
T = input()
#print(li_S, li_T)  # DBG

ans = -1
# S も T も一文字目は同じでなければならない。
if S[0]!=T[0]:
    print(ans)
    exit()

# 条件に合致する文字 X がある場合、制約条件からその長さ L も N,M と同じ範囲にある。
for L in range(1, 10**5 + 1):
    # 一番目の条件を満足しなければ L を更新する
    if L%N != 0 or L%M != 0:
        continue
    #print(L)   #デバッグ
    # 二番目の条件を満足する場合
    sn = [i * L // N + 1 for i in range(N)]
    # 三番目の条件を満足する場合
    tm = [i * L // M + 1 for i in range(M)]

#DBG
#    print(sn)
#    print(tm)
#    print(set(sn)|set(tm))
#    print(set(sn)&set(tm))
#    print(len(sn))
#    print(len(tm))
#    print(len(set(sn)|set(tm)))
#    print(len(set(sn)&set(tm)))

    li_seki = sorted(set(sn) & set(tm))
    li_indS = [sn.index(x) for x in li_seki]
    dup_S = "".join([S[i] for i in li_indS])
    li_indT = [tm.index(x) for x in li_seki]
    dup_T = "".join([T[i] for i in li_indT])
#DBG    
#    print(li_seki)  #DBG
#    print(li_indS)  #DBG
#    print(dup_S)    #DBG
#    print(li_indT)  #DBG
#    print(dup_T)    #DBG

    # 二番目と三番目の条件が、両立すれば X は存在する。その条件は下記2通り。
    # 1.「sn と tn が、先頭の 1 以外、互いにすべて異なる要素を持つ」
    # 2.「sn と tn の重複する数字に対応する S と T の要素が等しい」
    # どちらかを満足していればよい。
    if len(set(sn)|set(tm)) == len(sn) + len(tm) -1:
        ans = L
        break
    elif dup_S == dup_T:
        ans = L
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def pdbg(label, val):
    # print("[%s]%s" % (label, val))
    pass


N, M = map(int, input().split())
S = input()
T = input()


pNM = N / M
pMN = M / N


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


def is_unique(seq):
    return len(seq) == len(set(seq))


def calculate(lenv):
    ln = int(lenv / N)
    lm = int(lenv / M)

    pdbg('L', lenv)
    pdbg('N', N)
    pdbg('M', M)
    pdbg('LN', ln)
    pdbg('LM', lm)

    l_ns = []
    for i in range(0, N, ln):
        l_ns.append(i)
    pdbg('LNs', l_ns)
    l_ms = []
    for j in range(0, M, lm):
        l_ms.append(j)
    pdbg('LMs', l_ms)
    dpl = (set(l_ns) & set(l_ms))
    pdbg('dpl', dpl)
    if pNM == round(pNM) or pMN == round(pMN):
        return -1
    if S[0] != T[0]:
        return -1
    for k in dpl:
        pdbg('k', k)
        pdbg('Sk', S[k])
        pdbg('Tk', T[k])
        if S[k] != T[k]:
            return -1
    return lenv


def cml():
    lms = lcm(N, M)
    for i in range(1, 11):
        res = calculate(i * lms)
        if res == -1:
            continue
        else:
            return lms
        

print(cml())

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import copy

alphabet = [chr(i) for i in range(97, 97 + 26)]


def lcm(x, y):
    return (x * y) // gcd(x, y)


# Input data
n, m = map(int, input().split())
s = input()
t = input()

# Generate x canditate
x_len = lcm(n, m)
canditates_s = ["" for i in range(x_len)]
# これは参照渡しだからダメ：canditates_t = canditates_s
canditates_t = copy.copy(canditates_s) 
s_indset = set([i * int(x_len / n) for i in range(n)])
t_indset = set([i * int(x_len / m) for i in range(m)])
for i, s_ind in enumerate(s_indset):
    canditates_s[s_ind] = s[i]
for i, t_ind in enumerate(t_indset):
    canditates_t[t_ind] = t[i]

# Shared set
shared_set = s_indset & t_indset

# Djudge incoherence
for i in shared_set:
    if canditates_s[i] != canditates_t[i]:
        print(-1)
        exit()

# If the djudge cleared
print(x_len)

Submission status: Wrong Answer

Solution code:
import platform
ver = platform.python_version_tuple()
if int(ver[1]) < 5:
    from fractions import gcd
else:
    from math import gcd

from sys import stdin
from bisect import bisect

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = lcm(N, M)
    s = [i * (L // N) for i in range(N)]
    t = [i * (L // M) for i in range(M)]
    for i, x in enumerate(s):
        n = bisect(t, x)
        if t[n-1] == n:
            if T[n-1] != S[i]:
                print(-1)
                return
    print(L)

input = lambda: stdin.readline().rstrip()
lcm = lambda x, y: x * y // gcd(x, y)
main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

n, m = [int(i) for i in input().split()]
s = input()
t = input()

if not s[0] == t[0]:
	print(-1)
	exit()

nl_max = max(n, m)
nl_min = min(n, m)
if len(s) >= len(t):
	smax = s
	smin = t
else:
	smax = t
	smin = s
nl = nl_max
"""while nl < 10 ** 10:
	if nl % nl_min:
		nl += nl_max
		continue

	nb = True
	nl_x = [""] * nl
	for i in range(n):
		nl_x[int(i * nl / n)] = s[i]
	for i in range(m):
		if nl_x[int(i * nl / m)] == "" or nl_x[int(i * nl / m)] == t[i]:
			nl_x[int(i * nl / m)] = t[i]
		else:
			nb = False
			break
	else:
		if nb:
			print(nl)
			exit()
	nl += nl_max
print(-1)"""

while nl < 10 ** 7:
	if nl % nl_min:
		nl += nl_max
		continue

	for i in range(1, nl_min):
		tmp = int(i * nl / nl_min)
		tmp2 = tmp * nl_max / nl
		if tmp2 % 1:
			continue
		if not smax[int(tmp2)] == smin[i]:
			break
	else:
		print(nl)
		exit()
	nl += nl_max
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return int(a * b / gcd (a, b))

N, M = [int(i) for i in input().split()]
S = input()
T = input()

if N > M:
    a, b = N, M
    A, B = S, T
else:
    a, b = M, N
    A, B = T, S

if a % b == 0:
    ans = 0
    for i in range(b):
        if A[int(i * a / b)] == B[i]:
            continue
        else:
            ans = -1
            break
    if ans == 0:
        ans = lcm(a, b)
            
else:
    if A[0] == B[0]:
        ans = lcm(a, b)
    else:
        ans = -1        
        
print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

n, m = [int(i) for i in input().split()]
s = input()
t = input()

if not s[0] == t[0]:
	print(-1)
	exit()

nl_max = max(n, m)
nl_min = min(n, m)
if len(s) >= len(t):
	smax = s
	smin = t
else:
	smax = t
	smin = s
nl = nl_max
"""while nl < 10 ** 10:
	if nl % nl_min:
		nl += nl_max
		continue

	nb = True
	nl_x = [""] * nl
	for i in range(n):
		nl_x[int(i * nl / n)] = s[i]
	for i in range(m):
		if nl_x[int(i * nl / m)] == "" or nl_x[int(i * nl / m)] == t[i]:
			nl_x[int(i * nl / m)] = t[i]
		else:
			nb = False
			break
	else:
		if nb:
			print(nl)
			exit()
	nl += nl_max
print(-1)"""

while nl < 10 ** 6:
	if nl % nl_min:
		nl += nl_max
		continue

	for i in range(1, nl_min):
		tmp = int(i * nl / nl_min)
		tmp2 = tmp * nl_max / nl
		if tmp2 % 1:
			continue
		if not smax[int(tmp2)] == smin[i]:
			break
	else:
		print(nl)
		exit()
	nl += nl_max
print(-1)

Submission status: Wrong Answer

Solution code:
import fractions
 
n, m = (int(i) for i in input().split()) 
 
s = input()
t = input()
 
def lcm(x, y):
    return x * y / fractions.gcd(x, y)
 
lcm = lcm(n,m)
 
n_ind = []
n_ind = range(0, int((lcm / n) * (n - 1)), int((lcm / n)))

ind_list = []
for i in range(m):
    if n_ind.count((lcm / m) * (i)) == 1:
        ind_list.append((lcm / m) * (i))
 
flg = True
for i in range(len(ind_list)):
    if s[int(i / (lcm / n))] != t[int(i / (lcm / m))]:
        flg = False
        break
 
if flg:
    print(int(lcm))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def solve(N, M, S, T):
    L = N * M // gcd(N, M)
    X = ["Z" for _ in range(L)]
    for k in range(L):
        ni = int(L / N * k)
        mi = int(L / M * k)
        if k < N:
            if X[ni] != "Z" and X[ni] != S[k]:
                return -1
            else:
                X[ni] = S[k]
        if k < M:
            if X[mi] != "Z" and X[mi] != T[k]:
                return -1
            else:
                X[mi] = T[k]

    return "".join(X).lower()


if __name__ == "__main__":
    l = input()
    N, M = int(l.split()[0]),int(l.split()[1])
    S = input()
    T = input()
    print(solve(N, M, S, T))

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
s = input()
t = input()

nsky = n
msky = m
while not nsky % msky == 0:
    tmp = msky
    msky = nsky % msky
    nsky = tmp
skys = msky

idx_n = 1
idx_m = 1
idx_x = 0
okans = -1
skbs = 0

while n * idx_n < 1000000000 and m * idx_m < 1000000000 and okans < 0:
    if n * idx_n == m * idx_m:
        idx_2 = 0
        
        while (n/skys)*idx_2 < n:
            if s[int(n/skys)*idx_2] == t[int(m/skys)*idx_2]:
                if (n/skys)*(idx_2+1) == n:
                    okans = n * idx_n
                idx_2 = idx_2 + 1
            else:
                idx_2 = n
                
        if skbs == 0:
            skbs = idx_n

        idx_x = idx_x + 1
        idx_m = skbs * idx_x
        idx_n = skbs * idx_x
    elif n * idx_n > m * idx_m:
        idx_m = idx_m + 1
    elif n * idx_n < m * idx_m:
        idx_n = idx_n + 1

print(okans)

Submission status: Wrong Answer

Solution code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def solve(N, M, S, T):
    L = N * M // gcd(N, M)

    X = ["" for _ in range(L)]
    for k in range(L):
        ni = int(L / N * k)
        mi = int(L / M * k)
        if k < N:
            if X[ni] != "" and X[ni] != S[k]:
                return -1
            else:
                X[ni] = S[k]
        if k < M:
            if X[mi] != "" and X[mi] != T[k]:
                return -1
            else:
                X[mi] = T[k]

    for i in range(L):
        if X[i] == "":
            X[i] = "z"
    return "".join(X)


if __name__ == "__main__":
    l = input()
    N, M = int(l.split()[0]),int(l.split()[1])
    S = input()
    T = input()
    print(solve(N, M, S, T))

Submission status: Wrong Answer

Solution code:
#coding: utf-8

# 標準入力から N, M, S, T を取得する
N, M = map(int, input().split())
li_S = list(input())
li_T = list(input())
#print(li_S, li_T)  # DBG

ans = -1
# S も T も一文字目は同じでなければならない。
if li_S[0]!=li_T[0]:
    print(ans)

# 条件に合致する文字 X がある場合、制約条件からその長さ L も N,M と同じ範囲にある。
for L in range(1, 10**5 + 1):
    # 一番目の条件を満足しなければ L を更新する
    if L%N != 0 or L%M != 0:
        continue
    #print(L)   #デバッグ
    # 二番目の条件を満足する場合
    sn = []
    for i in range(N):
        si = i * L // N + 1
        sn.append(si) #X からこのリストの要素の(番目-1)を結合すると S になる。

    # 三番目の条件を満足する場合
    tm = []
    for i in range(M):
        ti = i * L // M + 1
        tm.append(ti) #X からこのリストの要素の(番目-1)を結合すると T になる。
#DBG
#    print(sn)
#    print(tm)
#    print(set(sn)|set(tm))
#    print(set(sn)&set(tm))
#    print(len(sn))
#    print(len(tm))
#    print(len(set(sn)|set(tm)))
#    print(len(set(sn)&set(tm)))

    li_seki = sorted(set(sn) & set(tm))
#    print(li_seki)  #DBG
    li_indS = [sn.index(x) for x in li_seki]
#    print(li_indS)  #DBG
    dup_S = "".join([li_S[i] for i in li_indS])
#    print(dup_S)    #DBG
    li_indT = [tm.index(x) for x in li_seki]
#    print(li_indT)  #DBG
    dup_T = "".join([li_T[i] for i in li_indT])
#    print(dup_T)    #DBG
    

    # 二番目と三番目の条件が、両立すれば X は存在する。その条件は下記2通り。
    # 1.「sn と tn が、先頭の 1 以外、互いにすべて異なる要素を持つ」
    # 2.「sn と tn の重複する数字に対応する S と T の要素が等しい」
    # どちらかを満足していればよい。
    if len(set(sn)|set(tm)) == len(sn) + len(tm) -1:    # 条件1
        ans = L
        break
    elif dup_S == dup_T:
        ans = L
        break

print(ans)

Submission status: Wrong Answer

Solution code:


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def solve(N, M, S, T):
    L = N * M // gcd(N, M)

    X = ["" for _ in range(L)]
    for k in range(L):
        ni = int(L / N * k)
        mi = int(L / M * k)
        if k < N:
            if X[ni] != "" and X[ni] != S[k]:
                return -1
            else:
                X[ni] = S[k]
        if k < M:
            if X[mi] != "" and X[mi] != T[k]:
                return -1
            else:
                X[mi] = T[k]

    for i in range(L):
        if X[i] == "":
            X[i] = "z"
    return "".join(X)

Submission status: Wrong Answer

Solution code:
N, M =  map(int, input().split(' '))
S = input()
T = input()
import numpy as np
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(x, y):
    return (x * y) // gcd(x, y)
 
L = lcm(N,M)
#max_n = max(N,M)
#x3 =[i for i in range(1, L, max_n)]
x1 = [1] + [(i *(L/N)) +1for i in range(1, N)] 
x2 = [1]+ [(i *(L/M)) +1for i in range(1, M)] 
x3 = set(x1) & set(x2) 

if len(x3) ==1:
   print(L)
elif S[0] != T[0]:
    print(-1)
else :
    if all([S[int((i-1)/(L/N))] == T[int((i -1)/(L/M))] for i in x3 if i != 1]) :
        print(L)
    else :
        print(-1)

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
s = input()
t = input()

cnt = 1
ns = 1
nt = 1
ss = 0
tt = 0
fail = False

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ll = (n * m) // gcd(n, m)
l = ll

while l <= n * m:
    fail = False
    while not( ns >= l or nt >= l):
        while not(ns <= nt):
            nt += l / m 
            tt += 1

        if(ns == nt) and (s[ss] != t[tt]):
            fail = True
            break

        ns += l / n
        ss += 1
    if not(fail): 
        break
    cnt += 1
    l = ll * cnt

if(fail):
    print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import math
n,m = map(int,input().split())
s = list(input())
t = list(input())
 
def get_gcd(a, b):
    # ユークリッド互除法により最大公約数を求める。
    if a < b:
        a, b = b, a
 
    if a % b == 0:
        return b
    else:
        return get_gcd(b, a % b)
 
def get_lcm(a, b, gcd):
    # ２数を掛けあわせ、最大公約数で割れば最小公倍数が求まる。
    lcm = a * b // gcd
    return lcm
 
gcd = get_gcd(n,m)
x = 0
good_str_is_exist = True
for k in range(get_lcm(n, m, gcd)):
    if s[0] != t[0]:
        good_str_is_exist = False
        break
    if (k + 1) % n == 0 and (k + 1) % m == 0:
        if s[0] != t[0]:
            good_str_is_exist = False
            break
        else:
            if len(s) == 0 or len(t) == 0:
                good_str_is_exist = False
                break
                s.remove(0)
                t.remove(0)
    x += 1
 
if good_str_is_exist:
    print(x)
else:
    print('-1')
exit()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = input()
t = input()

# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# x,yの最小公倍数lcm(x, y)を求める
def lcm(a, b):
    return a * b // gcd(a, b)
x = gcd(m, n)
a = int(m/x)
b = lcm(a, int((n/m)*a))
i = 0
flag = True
while int((b*i)/a) <= n - 1 and int((b*i)*m/(n*a)) <= m - 1:
    if s[int((b*i)/a)] == t[int((b*i)*m/(n*a))]:
        flag = True
        i += 1
    else:
        flag = False
        break
if flag == True:
    print(lcm(n, m))
elif flag == False:
    print(-1)

Submission status: Wrong Answer

Solution code:
# A
n,m = map(int, input().split())
s = str(input())
t = str(input())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a,b):
    return a*b/gcd(a,b)
l=int(lcm(n,m))
si=ti=0
ss=0
tt=0
sss=""
ttt=""
for i in range(l):
    if ss<i:
        if ss%(l/m)==0:
            sss+=s[si]
        si+=1
        ss=int(ss+l/n)
#         print('ss',ss)
    if tt<i:
        if tt%(l/n)==0:
            ttt+=t[ti]
        ti+=1
        tt=int(tt+l/m)
#         print('tt',tt)
# print(sss)
# print(ttt)
if ttt==sss:
    print(l)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
def pdbg(label, val):
    # print("[%s]%s" % (label, val))
    pass


N, M = map(int, input().split())
S = input()
T = input()


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


def is_unique(seq):
    return len(seq) == len(set(seq))


L = lcm(N, M)

LN = int(L / N)
LM = int(L / M)

pdbg('L', L)
pdbg('N', N)
pdbg('M', M)
pdbg('LN', LN)
pdbg('LM', LM)


LNs = []
for i in range(0, N, LN):
    LNs.append(i)
pdbg('LNs', LNs)
LMs = []
for j in range(0, M, LM):
    LMs.append(j)
pdbg('LMs', LMs)
Dpl = (set(LNs) & set(LMs))
pdbg('Dpl', Dpl)


def calculate():
    if S[0] != T[0]:
        return -1
    for k in Dpl:
        pdbg('k', k)
        pdbg('Sk', S[k])
        pdbg('Tk', T[k])
        if S[k] != T[k]:
            return -1
    return L


print(calculate())

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = input()
t = input()

# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# x,yの最小公倍数lcm(x, y)を求める
def lcm(a, b):
    return a * b // gcd(a, b)
x = gcd(m, n)
a = int(m/x)
b = lcm(a, int((n/m)*a))
i = 0
flag = True
while (b*i)/a <= n - 1 and (b*i)*m/(n*a) <= m - 1:
    if s[int((b*i)/a)] == t[int((b*i)*m/(n*a))]:
        flag = True
        i += 1
    else:
        flag = False
        break
if flag == True:
    print(lcm(n, m))
elif flag == False:
    print(-1)

Submission status: Wrong Answer

Solution code:
def pdbg(label, val):
    # print("[%s]%s" % (label, val))
    pass


N, M = map(int, input().split())
S = input()
T = input()


pNM = N / M
pMN = M / N


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


def is_unique(seq):
    return len(seq) == len(set(seq))


L = lcm(N, M)

LN = int(L / N)
LM = int(L / M)

pdbg('L', L)
pdbg('N', N)
pdbg('M', M)
pdbg('LN', LN)
pdbg('LM', LM)


LNs = []
for i in range(0, N, LN):
    LNs.append(i)
pdbg('LNs', LNs)
LMs = []
for j in range(0, M, LM):
    LMs.append(j)
pdbg('LMs', LMs)
Dpl = (set(LNs) & set(LMs))
pdbg('Dpl', Dpl)


def calculate():
    if pNM == round(pNM) or pMN == round(pMN):
        return -1
    if S[0] != T[0]:
        return -1
    for k in Dpl:
        pdbg('k', k)
        pdbg('Sk', S[k])
        pdbg('Tk', T[k])
        if S[k] != T[k]:
            return -1
    return L


print(calculate())