Problem:


Problem F: Problem F: リズムマシーン

  

    Advanced Computer Music社（ACM社）は，
    あらかじめプログラムされたリズム通りに音楽を演奏する
    リズムマシーンを販売していた．
    ある時，ACM社は新しいリズムマシーンを開発して売り出そうとしていた．
    ACM社の旧製品は同時に1つの音しか鳴らすことができなかったのに対し，
    新製品では最大で8つの音を同時に鳴らせるようになるというのが
    一番の目玉機能であった．
    今まで複数の旧製品を利用して演奏する必要のあった曲が
    新製品1台で済むようになるので，
    ACM社は新製品への移行を推進させるために，
    複数の旧製品向けのリズムパターンを1つの新製品向けのリズムパターンに
    変換するプログラムを作ることにした．
  

  

    ACM社のリズムマシーンでは，同時にどの音を鳴らすかを2桁の16進数で表現する．
    ACM社のリズムマシーンは8つの異なる音を鳴らすことが可能で，
    それぞれの音には0から7の番号が割り当てられている．
    あるタイミングにおいて，音 i (0 ≤ i < 8)
    を鳴らす場合を si = 1，
    鳴らさない場合を si = 0 とする．
    このとき，それぞれの音を同時に鳴らしたような和音を
    
    という値で表し，
    この値を2桁の16進数表記で表した「和音表現」
    がリズムパターンの中で用いられる（16進数の英字は大文字を用いる）．
    例えば，音0, 6, 7 を同時に鳴らすような和音は
    S = 20 + 26 + 27
    = C1(16)
    となるから &ldquo;C1&rdquo; と表現され，
    また何も鳴らさないような「和音」は 
    &ldquo;00&rdquo; と表現される．
  

  

    リズムパターンは，上記のような和音表現を1つ以上並べたものとして与えられる．
    あるリズムパターン文字列は，1小節内の演奏パターンを示している．
    それぞれの和音を鳴らすタイミングを小節内の相対位置
    t (0 ≤ t < 1)
    で表現することにする．
    k 個の和音表現からなるリズムパターン文字列は，
    小節を k 等分しそれぞれの和音を順に
    t = 0/k, 1/k, ...,
    (k−1)/k のタイミングで演奏するような
    リズムパターンを表している．
    例えば，リズムパターン &ldquo;01000003&rdquo; は，
    t = 0/4 のタイミングで音0を演奏し，
    t = 3/4 のタイミングで音0, 1を演奏することを表す．
    また，リズムパターン &ldquo;00&rdquo;
    は小節内で何も音を鳴らさないことを表す
    （リズムパターンには和音表現が1つ以上必要であることに注意せよ）．
  

  

    旧製品は同時に1つの音しか鳴らせないため，
    旧製品向けのリズムパターン文字列内には
    &ldquo;00&rdquo;,
    &ldquo;01&rdquo;,
    &ldquo;02&rdquo;,
    &ldquo;04&rdquo;,
    &ldquo;08&rdquo;,
    &ldquo;10&rdquo;,
    &ldquo;20&rdquo;,
    &ldquo;40&rdquo;,
    &ldquo;80&rdquo;
    のいずれかの和音表現しか現れない．
    旧製品向けのリズムパターンを N 個
    (1 ≤ N ≤ 8) 受け取り，
    それらのリズムパターンを同時に演奏するような
    新製品向けのリズムパターンを出力するプログラムを書いて欲しい．
  

  

    与えられる N 個のリズムパターンにおいて，
    まったく同じタイミングで同じ音が演奏されることはないと仮定してよい．
  

  
Input

  

    最初の行にデータセットの数が与えられる．
    次の行以降には，それぞれのデータセットが順に記述されている．
    データセットの数は 120 を越えないと仮定してよい．
  

  

    それぞれのデータセットは以下のような形式で与えられる．
  

  

    N
    R1
    R2
    ...
    RN
  

  

    Ri
    (1 ≤ i ≤ N)
    はそれぞれ旧製品向けのリズムパターンである．
  

  

    各リズムパターンは最大で2048文字（1024和音表現）である．
    与えられるリズムパターンは必ずしも最短の表現になっていないことに注意せよ．
  

  
Output

  

    各データセットについて，与えられた N 個のリズムパターンを
    すべて同時に演奏するような最短のリズムパターンを生成し，
    1行で出力せよ．
    そのようなリズムパターンが2048文字を越える場合，
    リズムパターンの代わりに &ldquo;Too complex.&rdquo;
    という文字列を出力せよ．
  

  
Sample Input

  

5
2
01000100
00020202
2
0102
00000810
1
0200020008000200
5
0001
000001
0000000001
00000000000001
0000000000000000000001
1
000000

  
Output for the Sample Input

  

01020302
01000A10
02020802
Too complex.
00

 

Sample input:
5
2
01000100
00020202
2
0102
00000810
1
0200020008000200
5
0001
000001
0000000001
00000000000001
0000000000000000000001
1
000000


Sample output:
01020302
01000A10
02020802
Too complex.
00

Submission status: Wrong Answer

Solution code:
def shorten(s):
    f = 1
    while f:
        l = len(s) // 2
        while f:
            f = 0
            if l % 2 == 0:
                for i in range(l):
                    if s[2 * i:2 * i + 2] != "00" and i % 2:break
                else:
                    f = 1
                    t = ""
                    for i in range(0, l, 2):t += s[2 * i:2 * i + 2]
                    s = t
                    l = len(s) // 2
        for k in range(3, l + 1, 2):
            f = 1
            while f:
                f = 0
                if l % k == 0:
                    for i in range(l):
                        if s[2 * i:2 * i + 2] != "00" and i % k:break
                    else:
                        f = 1
                        t = ""
                        for i in range(0, l, k):t += s[k * i:k * i + 2]
                        s = t
                        l = len(s) // 2
    return s

def lcm(a, b):
    p, q = max(a, b), min(a, b)
    while 1:
        if p % q:p, q = q, p % q
        else: return a * b // q

for _ in range(int(input())):
    n = int(input())
    r = [shorten(input()) for _ in range(n)]
    ls = [len(i) // 2 for i in r]
    l = ls[0]
    for i in range(1, len(r)):l = lcm(l, ls[i])
    if l > 1024:print("Too complex.");continue
    a = [0] * l
    for i in range(n):
        d = l // ls[i]
        for j in range(ls[i]):a[d * j] += int(r[i][2 * j: 2 * j + 2], 16)
    s = ""
    for i in a:s += format(i,"02X")
    print(s)

Submission status: Memory Limit Exceeded

Solution code:
Alphabet=[chr(i) for i in range(65,65+15)]

def gcd(a,b):
    if a>b:
        p=a
        q=b
    else:
        p=b
        q=a

    if q==0:
        return p
    else:
        return gcd(q,p%q)

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

def lcm_list(x):
    if len(x)==1:
        return x[0]
    else:
        result=lcm(x[0],x[1])
        for i in range(2,len(x)):
            result=lcm(result,x[i])
        return result



def to_letter(a):
    x=int(a/16)
    y=a-x*16
    if x>9:
        x=Alphabet[x-10]
    if y>9:
        y=Alphabet[y-10]
    return str(x)+str(y)
        


def split_str(s,n):
    length = len(s)
    return [s[i:i+n] for i in range(0, length, n)]

def shorten(a):
    flag=0
    x=0
    for i in range(2,len(a)+1):
        if len(a)%i==0:
            for j in range(len(a)):
                if j%i!=0 and a[j]!=0:
                    flag+=1
            if flag==0:
                x=i
                break
        flag=0
    
    if x!=0:
        return(shorten(a[::x]))
    else:
        return(a)



t=int(input())
for rotate in range(t):
    N=int(input())
    R=[]
    R_length=[]
    for i in range(N):
        R_input=input()
        R.append([int(j,16) for j in split_str(R_input,2)])
        R_length.append(int(len(R_input)/2))
    answer_length=lcm_list(R_length)
    answer=[0 for i in range(answer_length)]
    for i in range(N):
        marker=int(answer_length/R_length[i])
        for j in range(R_length[i]):
            answer[j*marker]+=R[i][j]

    answer=shorten(answer)

    if len(answer)>1024:
        print("Too complex.")
    else:
        print("".join([to_letter(i) for i in answer]))

Submission status: Memory Limit Exceeded

Solution code:
import sys

Alphabet=[chr(i) for i in range(65,65+15)]

def gcd(a,b):
    if a>b:
        p=a
        q=b
    else:
        p=b
        q=a

    if q==0:
        return p
    else:
        return gcd(q,p%q)

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

def lcm_list(x):
    if len(x)==1:
        return x[0]
    else:
        result=lcm(x[0],x[1])
        for i in range(2,len(x)):
            result=lcm(result,x[i])
        return result



def to_letter(a):
    x=int(a/16)
    y=a-x*16
    if x>9:
        x=Alphabet[x-10]
    if y>9:
        y=Alphabet[y-10]
    return str(x)+str(y)
        


def split_str(s,n):
    length = len(s)
    return [s[i:i+n] for i in range(0, length, n)]

def shorten(a):
    flag=0
    x=0
    for i in range(2,len(a)+1):
        if len(a)%i==0:
            for j in range(len(a)):
                if j%i!=0 and a[j]!=0:
                    flag+=1
            if flag==0:
                x=i
                break
        flag=0
    
    if x!=0:
        return(shorten(a[::x]))
    else:
        return(a)



t=int(input())
for rotate in range(t):
    N=int(input())
    R=[]
    R_length=[]
    for i in range(N):
        R_input=input()
        R.append([int(j,16) for j in split_str(R_input,2)])
        R_length.append(int(len(R_input)/2))
    answer_length=lcm_list(R_length)
    answer=[0 for i in range(answer_length)]
    for i in range(N):
        marker=int(answer_length/R_length[i])
        for j in range(R_length[i]):
            answer[j*marker]+=R[i][j]

    answer=shorten(answer)

    if len(answer)>1024:
        print("Too complex.")
    else:
        for i in answer:
            sys.stdout.write(to_letter(i))
        print("")

Submission status: Memory Limit Exceeded

Solution code:
import sys

Alphabet=[chr(i) for i in range(65,65+15)]

def gcd(a,b):
    if a>b:
        p=a
        q=b
    else:
        p=b
        q=a

    if q==0:
        return p
    else:
        return gcd(q,p%q)

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

def lcm_list(x):
    if len(x)==1:
        return x[0]
    else:
        result=lcm(x[0],x[1])
        for i in range(2,len(x)):
            result=lcm(result,x[i])
        return result



def to_letter(a):
    x=int(a/16)
    y=a-x*16
    if x>9:
        x=Alphabet[x-10]
    if y>9:
        y=Alphabet[y-10]
    return str(x)+str(y)
        


def split_str(s,n):
    length = len(s)
    return [s[i:i+n] for i in range(0, length, n)]

def shorten(a):
    flag=0
    x=0
    for i in range(2,len(a)+1):
        if len(a)%i==0:
            for j in range(len(a)):
                if j%i!=0 and a[j]!=0:
                    flag+=1
            if flag==0:
                x=i
                break
        flag=0
    
    if x!=0:
        return(shorten(a[::x]))
    else:
        return(a)



t=int(input())
for rotate in range(t):
    N=int(input())
    R=[]
    R_length=[]
    for i in range(N):
        R_input=input()
        R.append([int(j,16) for j in split_str(R_input,2)])
        R=shorten(R)
        R_length.append(int(len(R_input)/2))
    answer_length=lcm_list(R_length)
    answer=[0 for i in range(answer_length)]
    for i in range(N):
        marker=int(answer_length/R_length[i])
        for j in range(R_length[i]):
            answer[j*marker]+=R[i][j]

    answer=shorten(answer)

    if len(answer)>1024:
        print("Too complex.")
    else:
        print("".join([to_letter(i) for i in answer]))

Submission status: Accepted

Solution code:
def shorten(s):
    f = 1
    while f:
        l = len(s) // 2
        while f:
            f = 0
            if l % 2 == 0:
                for i in range(l):
                    if s[2 * i:2 * i + 2] != "00" and i % 2:break
                else:
                    f = 1
                    t = ""
                    for i in range(0, l, 2):t += s[2 * i:2 * i + 2]
                    s = t
                    l = len(s) // 2
        for k in range(3, l + 1, 2):
            f = 1
            while f:
                f = 0
                if l % k == 0:
                    for i in range(l):
                        if s[2 * i:2 * i + 2] != "00" and i % k:break
                    else:
                        f = 1
                        t = ""
                        for i in range(0, l, k):t += s[2 * i:2 * i + 2]
                        s = t
                        l = len(s) // 2
    return s

def lcm(a, b):
    p, q = max(a, b), min(a, b)
    while 1:
        if p % q:p, q = q, p % q
        else: return a * b // q

for _ in range(int(input())):
    n = int(input())
    r = [shorten(input()) for _ in range(n)]
    ls = [len(i) // 2 for i in r]
    l = ls[0]
    for i in range(1, n):l = lcm(l, ls[i])
    if l > 1024:print("Too complex.");continue
    a = [0] * l
    for i in range(n):
        d = l // ls[i]
        for j in range(ls[i]):a[d * j] += int(r[i][2 * j: 2 * j + 2], 16)
    s = ""
    for i in a:s += format(i,"02X")
    print(s)