Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

出現頻度操作

有限数列の変換操作に出現頻度操作というものがあります。数列 $S = \{s_1, s_2,... s_n\}$ の変換結果は同じ長さの数列となります。その結果を $C = \{c_1,c_2, ..., c_n\}$ とすると、 $c_i$ は数列 $S$ における $s_i$ の個数を表します。

  例えば $S = \{3,4,1,5,9,2,6,5,3\}$ ならば $C = {2,1,1,2,1,1,1,2,2}$ となります。さらにこの数列 $C$ に出現頻度操作を行うと $P = \{4,5,5,4,5,5,5,4,4\}$ を得ます。この数列は出現頻度操作で変わることがありません。このような数列 $P$ を数列 $S$ の不動点と呼びます。どのような数列に対しても出現頻度操作を繰り返せば、その不動点を求めることが出来るということが知られています。

 下の例は出現頻度操作の手順を示したものです。1 行目を数列 $S$ 、2 行目を数列 $C$、最終行を数列 $P$ とします。数列 $S$ の最初の要素($s_1 = 2$) と同じ数は 3 個あるので数列 $C$ の最初の要素 $c_1$ は 3、次の要素 ($s_2 = 7$) と同じ数は 2 個あるので $c_2 = 2$、といった具合に個数を数え $c_i$ を求めていきます。

 数列の長さ $n$ と数列 $S$ を入力し、不動点の数列 $P$ および、$P$ を得るために実行した出現頻度操作の最小の回数を出力するプログラムを作成してください。

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

$n$

$s_1$ $s_2$ ... $s_n$

1 行目に数列の長さを表す整数 $n$ ($n \leq 12$) が与えられます。２行目に数列 $S$ の要素を表す整数　$s_i$ ($1 \leq s_i \leq 100$) が空白区切りで与えられます。

入力は０一つの行で終わります。データセットの数は 200 を超えません。

Output

各データセットについて、１行目に出現頻度操作の最小の実行回数(整数)、２行目に対応する不動点の数列 $P$ の要素 $p_1$, $p_2$, ...,  $p_n$ を空白区切りで出力してください。

Sample Input

10
4 5 1 1 4 5 12 3 5 4
0

Output for the Sample Input

3
6 6 4 4 6 6 4 4 6 6



Sample input:
10
4 5 1 1 4 5 12 3 5 4
0


Sample output:
3
6 6 4 4 6 6 4 4 6 6

Submission status: Accepted

Solution code:
def answer(arr):
    l,  m = [], []
    h = {}
    for num in arr:
        l.append(num)
    i = 0
    while True:
        i += 1
        h, m = {}, []
        for num in l:
            if h.has_key(num):
                h[num] += 1
            else:
                h[num] = 1

        for num in l:
            m.append(h[num])
        if l == m:
            print i - 1
            for r in l:
                print r,
            print
            break
        else:
            l = m[:]

while True:
    a = input()
    if a == 0:
        break
    answer([int(n) for n in raw_input().split()])

Submission status: Accepted

Solution code:
def OFA(seq):
    return [seq.count(e) for e in seq]

def find_P(seq):
    count = 0
    prev = seq
    while True:
        new = OFA(prev)
        count += 1
        if new == prev:
            return count - 1, prev
        prev = new

while True:
    n = int(raw_input())
    if n == 0: break

    c, P = find_P(map(int, raw_input().split()))
    print c
    for e in P: print e,
    print

Submission status: Accepted

Solution code:
while not input()==0:
    pos=map(int,raw_input().split())
    pre=[]
    c=0
    while not pre==pos:
       pre=pos[:]
       pos=[pre.count(n) for n in pre]
       c+=1
    print c-1
    print " ".join(map(str,pos))

Submission status: Accepted

Solution code:
import itertools
while 1:
    n = int(raw_input())
    if n == 0: break
    ss = map(int, raw_input().split())
    for i in itertools.count(0):
        ps = [ss.count(s) for s in ss]
        if ps == ss:
            break
        ss = ps
    print i
    print ' '.join(map(str, ps))

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:
        break
    S=list(map(int,raw_input().split()))
    cnt=0
    post=[S.count(S[i]) for i in range(n)]
    while S<>post:
	S=post[:]
        cnt+=1
        post=[S.count(S[i]) for i in range(n)]
    print cnt
    print " ".join(map(str,post))

Submission status: Accepted

Solution code:
import sys
import math


def solv(s):
    i = 0
    while True:
        i += 1
        c = frequency(s)
        if c == s:
            break
        else:
            s = c
    return (i - 1, c)


def frequency(lis):
    lis2 = map(lambda x: count(x, lis), lis)
    return lis2


def count(n, lis):
    return len(filter(lambda x: x ==n, lis))


while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    s = map(int, sys.stdin.readline().split(' '))
    m, p = solv(s)
    print m
    print ' '.join(map(str, p))

Submission status: Accepted

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


def main(readline=stdin.readline):
    counter = Counter()

    while 1:
        if not int(readline()):
            exit()

        ary = [int(digit) for digit in readline().split()]

        for num in count():
            counter.clear()
            counter.update(ary)
            if all(key == value for key, value in counter.items()):
                break
            ary = [counter[value] for value in ary]

        print(num)
        print(*ary)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def foa(a,count):
    b = a[:]
    for i in range(len(b)):
        b[i] = a.count(a[i])
    if b == a:
        print count
        print " ".join(map(str, b))
        return
    else:
        return foa(b,count+1)

while True:
    n = int(raw_input())
    if n == 0:
        break
    a = map(int, raw_input().split())
    foa(a,0)

Submission status: Accepted

Solution code:
# 辞書型のキーで数字を判別し、バリューにカウンタを用意
# 上記辞書を元に出現頻度操作関数を行う関数を作成し、都度呼び出す
# 出現頻度操作関数では不動点を求めるまでループさせ続ける

def transport(L,before_L=[],cnt=0):
    cnt += 1
    if L==before_L:
        print(cnt-2)
        return cnt
    L_before = L[:]
    dic = {}
    for i in L:
        dic[i] = 0
    for i in L:
        dic[i] += 1
    # 上の2つのfor文でカウントは出来たので、keyの数字の値をvalueに置き換える
    for i in range(len(L)):
        L[i] = dic[L[i]]
    transport(L,L_before,cnt)

    return L

while 1:
    n = int(input())
    if n==0:
        break
    S = list(map(int,input().split()))
    P = transport(S)
    for i in range(len(P)-1):
        print(P[i],end=" ")
    print(P[-1])

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    N = int(input())
    if N == 0:
        return False
    *S, = map(int, input().split())
    cnt = 0
    while 1:
        c = Counter(S)
        *T, = map(c.__getitem__, S)
        if S == T:
            break
        S = T
        cnt += 1
    print(cnt)
    print(*S)
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
def getFreequencyStr(arr):
    datas = [0] * 101
    arr2 = [0] * len(arr)
    # 数を数える
    for i in range(0,len(arr)):
        datas[arr[i]] += 1
    # 頻出を配列にする
    for i in range(0,len(arr)):
        arr2[i] = datas[arr[i]]
    return arr2
        
while(1):
    n = int(input())
    changeNum = 0
    if n == 0:
        break
    arr = list(int(x) for x in input().split())
    while(1):
        arr2 = getFreequencyStr(arr)
        changeNum += 1
        if arr == arr2:
            break
        arr = arr2
    
    print(changeNum - 1)
    for i in range(0,len(arr)):
        if i :
            print(" ",end="")
        print(arr[i],end="")
    print()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


SIZE = 101
table = [None]*(SIZE)


while True:
    N = int(input())
    if N == 0:
        break

    TMP = list(map(int,input().split()))

    ans = -1
    count = 0

    while True:

        for i in range(SIZE):
            table[i] = 0

        for i in range(len(TMP)):
            table[TMP[i]] += 1

        WORK = []

        for i in range(len(TMP)):
            WORK.append(table[TMP[i]])

        FLG = True
        for i in range(len(TMP)):
            if TMP[i] != WORK[i]:
                FLG = False
                break

        if FLG == True:
            ans = count
            break

        for i in range(len(WORK)):
            TMP[i] = WORK[i]

        count += 1

    print("%d"%(ans))
    print(' '.join(map(str,TMP)))

Submission status: Accepted

Solution code:
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

def printA(A):
    N = len(A)
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート
# N = N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

def dist(A, B):
    d = 0
    for i in range(len(A)):
        d += (A[i]-B[i])**2            
    d = d**(1/2)
    return d

def get_input():
    N = []
    while True:
        try:
            N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
        except EOFError:
            break
    return N

while True:
    N = int(input())
    if N==0:
        break
    S = [int(x) for x in input().split()]

    ans = 0
    P = S.copy()

    while True:
        count = [0 for i in range(101)]
        for i in P:
            count[i] += 1
        C = []
        for i in P:
            C.append(count[i])
        
        ans += 1

        if P == C:
            break
        else:
            P = C.copy()
    
    print(ans-1)
    printA(P)

Submission status: Accepted

Solution code:
def operation(N,point):
    N_another = []
    for i in N:
        count = 0
        for j in N:
            if i==j:
                count +=1
        N_another.append(count)
    if N==N_another:return N,point
    else:return operation(N_another,point+1)
while 1:
    num=int(input())
    if num==0:break
    N=list(map(int,input().split()))
    answer_1,answer_2=operation(N,0)
    print(answer_2)
    print(*answer_1)

Submission status: Accepted

Solution code:
import copy

if __name__ == '__main__':

	while True:
		n = int(input())
		if n == 0:
			break

		line = list(map(int,input().split()))
		num = len(line)

		ans = copy.deepcopy(line)
		tmp = [0]*num
		cnt = 0

		for i,j in enumerate(ans):
			tmp[i] = line.count(j)

		while True:
			if ans == tmp:
				print(cnt)
				print(*ans)
				break
			else:
				ans = copy.deepcopy(tmp)
				for i,j in enumerate(ans):
					tmp[i] = ans.count(j)

				cnt += 1

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    count=0
    S_keep=list(map(int,input().split()))
    while 1:
        S=[]
        for i in S_keep:
            S.append(S_keep.count(i))
        if S_keep==S:
            print(count)
            print(" ".join(map(str,S)))
            break
        else:
            count+=1
            S_keep=S

Submission status: Accepted

Solution code:
import copy

while 1:
    n = int(input())
    if n == 0:
        break

    datas = list(map(int, input().split()))
    prev = copy.deepcopy(datas)
    curr = [0] * n
    cnt = 0

    while 1:
        for i, p in enumerate(prev):
            curr[i] = prev.count(p)

        if prev == curr:
            break
        prev = copy.deepcopy(curr)
        cnt += 1

    print(cnt)
    print(' '.join(str(p) for p in prev))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    s_list = [list(map(int, input().split()))]
    i = 0
    while True:
        i += 1
        s = []
        for j in s_list[-1]:
            s.append(s_list[-1].count(j))
        if s == s_list[-1]:
            break
        s_list.append(s)
    print(i - 1)
    print(*s)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = list(map(int, input().split()))
    b = []
    cnt = 0
    while True:
        for i in a:
            b.append(a.count(i))
        if a == b:
            break
        else:
            a, b = b[:], []
            cnt+=1
    print(cnt)
    print(*a)

Submission status: Accepted

Solution code:
while True:
    n = int(input())  ## n = len(S)
    if (n==0):
        break
    S = list(map(int, input().split()))
    C = []
    for s in S:
        num = S.count(s)
        C.append(num)
    c = 0
    #print(c,C)
    if (C == S):
        print(c)
        print(*C)
    else:
        while True:
            copy = C[:]
            for i in range(n):
                ci = C[i]
                num = copy.count(ci)
                C[i] = num
            c += 1
            #print(c,C)
            if (C == copy):
                print(c)
                print(*C)
                break

Submission status: Accepted

Solution code:
while(int(input())):
    ar = list(map(int, input().split()))
    n = 0
    while(True):
        br = [ar.count(l) for l in ar]
        if ar == br:
            break
        ar = br
        n += 1
    print(n)
    print(" ".join(str(e) for e in br))

Submission status: Runtime Error

Solution code:
while True:
	n = int(input())
	if n == 0:
	    break
	s = []
    s = list(input().split())
	while True:
		t = []
        u = 0
    	v = 0
		for i in range(n):
			for j in range(n):
				if s[i] == s[j]:
					u += 1
			t.append(u)
			t_str = list(map(str, t))
			u = 0
		if s == t:
			print(str(v))
			print(" ".join(t_str))
			break
		else:
			s = t
			v += 1

Submission status: Runtime Error

Solution code:
def FOA(a, count):
	b = a
	for i in range(len(b)):
		b[i] = a.count(a[i])
	if  b == a:
		print(count)
		print(" ".join(map(str, b)))
		break
	else:
		return FOA(b, count + 1)

while True:
	n = int(input())
	if n == 0:
		break
	a = map(int, input().split())
	FOA(a, 0)

Submission status: Runtime Error

Solution code:
import sys
while 1:
	n=int(input())
	if n==0:
		break
	s=list(int(input().split()))
	cont=0
	while 1:
		tmp=[]
		for i in range(n):
			tmp[i]=[s.count(s[i])]
		if s==temp:
			print(cont)
			break
		else:
			cont+=1
	for i in range(n):
		if i != n-1:
			sys.stdout('{0} '.format(s[i]))
		else:
			print(s[i])

Submission status: Runtime Error

Solution code:
while 1:
 n=int(input())
 if n:
  s=list(map(int,input().split()))
  c=0
  while 1:
   t=s;s=[t.count(e)for e in t]
   if t==s:break
   c+=1
  print(c);print(*s)