Problem:


ブロックの三角形

図a のように積まれたブロックに対し、以下の並べ替え操作を繰り返す。

 一番下のブロック全て（図a 中の白のブロック）を右端に新しく積み上げる（残りのブロックは自動的に１段下に落ち、図b のようになる）。

 ブロックの間に隙間ができたら、左に詰めて隙間をなくす（図 b から図c のようになる）。

1 以上の整数 k に対して、k&times;(k＋1)/2 で表される数 (例:1, 3, 6, 10, ...)を三角数という。ブロックの総数が三角数の場合、上記の並べ替えを繰り返すと、左端の高さが1 で右に向かって１つずつ高くなっていくような三角形になると予想されている（図d は総数が15 個の場合）。

ブロックの最初の並びが与えられたとき、あらかじめ決められた回数以下の操作で、上で説明したようなブロックの三角形ができるとき、三角形が得られるまでの最小の操作回数を出力するプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。

N
b1 b2 ... bN

各データセットは２行であり、ブロックの最初の並びを表す。N (1 ≤ N ≤ 100)は、一番下の段にあるブロックの数を示す。bi(1 ≤ bi ≤ 10000) は左から i 番目の位置に積まれているブロックの数を示す。bi と bi+1 は１つの空白で区切られている。ブロックの総数は 3 以上である。

データセットの数は 20 を超えない。

出力

データセットごとに、三角形ができるまでに行った並べ替え操作の回数を１行に出力する。ただし、三角形が作れない場合や、操作回数が 10000 回を超える場合は -1 を出力する。

入力例

6
1 4 1 3 2 4
5
1 2 3 4 5
10
1 1 1 1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 1 1
12
1 4 1 3 2 4 3 3 2 1 2 2
1
5050
3
10000 10000 100
0

出力例

24
0
10
-1
48
5049
-1

最初のデータセットが、図に示した場合に対応する。

４つ目のデータセットが、ブロックの総数が三角数でないため、三角形が作れない場合に対応する。

最後のデータセットが、ブロックの総数は三角数だが、操作回数が 10000 回を超える場合に対応する。



Sample input:
6
1 4 1 3 2 4
5
1 2 3 4 5
10
1 1 1 1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 1 1
12
1 4 1 3 2 4 3 3 2 1 2 2
1
5050
3
10000 10000 100
0


Sample output:
24
0
10
-1
48
5049
-1

Submission status: Wrong Answer

Solution code:
import math


def check(a):
    for i, v in enumerate(a):
        if v != i + 1:
            return False
        else:
            if i == len(a) - 1:
                return True


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

    a = map(int, raw_input().split())
    if sum(a) != (lambda s: s * (s + 1) // 2)(int(math.sqrt(sum(a) * 2))):
        print -1
    else:
        c = 0
        while not check(a):
            c += 1
            map(lambda x: x - 1, a).append(len(a))
            if 0 in a:
                a.remove(0)
            if c == 10000:
                c = -1
                break

        print c

Submission status: Accepted

Solution code:
import math

def is_sankaku(v):
    x = (math.sqrt(8*v + 1) - 1 ) / 2
    return x == int(x)

def check(lst):
    for i,v in enumerate(lst):
        if v != i + 1:
            return False
        elif i == len(lst)-1:
            return True

while 1:
    N = int(input())
    if N == 0:break
    lst = list(map(int,input().split()))
    if not is_sankaku(sum(lst)):
        print(-1)
        continue

    result = -1
    for count in range(10000):
        if check(lst):
            result = count 
            break
        spam = len(lst)
        lst = [x-1 for x in lst if x-1 > 0]
        lst.append(spam)
        
    print(result)

Submission status: Accepted

Solution code:
# Aizu Problem 0267: Triangle of Blocks

import sys, math, os, datetime

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


def is_triangle(heights):
    if heights[0] != 1:
        return False
    L = len(heights)
    diffs = [heights[k] - heights[k-1] for k in range(1, L)]
    return diffs == [1] * (L - 1)


def solve(n, heights):
    steps = 0
    while steps < 10000:
        if is_triangle(heights):
            return steps
        L = len(heights)
        for k in range(L):
            heights[k] -= 1
        heights.append(L)
        while heights.count(0) > 0:
            del heights[heights.index(0)]
        steps += 1
    return -1

while True:
    n = int(input())
    if n == 0:
        break
    heights = [int(_) for _ in input().split()]
    print(solve(n, heights))

Submission status: Accepted

Solution code:
tri_nums = [i * (i + 1) // 2 for i in range(1500)]
while True:
  n = int(input())
  if n == 0:
    break
  blst = list(map(int, input().split()))
  if sum(blst) not in tri_nums:
    print(-1)
    continue
  end = [i + 1 for i in range(tri_nums.index(sum(blst)))]
  lenb = n
  cnt = 0
  while blst != end:
    if cnt > 10000:
      print(-1)
      break
    blst = [i - 1 for i in blst if i > 1]
    blst.append(lenb)
    lenb = len(blst)
    cnt += 1
  else:
    print(cnt)

Submission status: Accepted

Solution code:
while True:
    N=input()
    if N==0:break
    L=map(int,raw_input().split())
    P=[]
    cnt=0
    while (P<>L) and (cnt<10000):
        P=L[:]
        L=map(lambda x:x-1,L)
        L.append(len(L))
        L=[i for i in L if i<>0]
        cnt+=1
    print cnt-1	if cnt<>10000 else -1

Submission status: Accepted

Solution code:
import math


def check(a):
    for i, v in enumerate(a):
        if v != i + 1:
            return False
        else:
            if i == len(a) - 1:
                return True


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

    a = map(int, raw_input().split())
    if sum(a) != (lambda s: s * (s + 1) // 2)(int(math.sqrt(sum(a) * 2))):
        print -1
    else:
        c = 0
        while not check(a):
            c += 1
            a = [x - 1 for x in a if x - 1 != 0] + [len(a)]
            if c == 10000:
                c = -1
                break

        print c

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	b=map(int,raw_input().split())
	count=0
	while count<10001:
		if b[0]==1:
			for i in range(len(b)-1):
				if b[i+1]-b[i]!=1:
					break
			else:
				print count
				break
		for i in range(len(b)):
			b[i]-=1
		b.append(len(b))
		while b.count(0)>0:
			del b[b.index(0)]
		count+=1
	else:
		print -1

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	b=map(int,raw_input().split())
	count=0
	while count<10001:
		if b[0]==1:
			for i in range(len(b)-1):
				if b[i+1]-b[i]!=1:
					break
			else:
				print count
				break
		l=len(b)
		for i in range(l):
			b[i]-=1
		b.append(l)
		while b.count(0)>0:
			del b[b.index(0)]
		count+=1
	else:
		print -1

Submission status: Accepted

Solution code:
def Sankakusu(N) :
    tmp  = 0
    i = 1
    while tmp < N :
        tmp = (i * (i + 1)) / 2
        i += 1
    if tmp == N :
        return True
    else :
        return False

def Step_Check(List) :
    for i in range(len(List)) : 
        if List[i] != i + 1 :
            return False
    return True
    
            

while True :
    n = int(input())
    if n == 0 :
        break
    
    count = 0
    block = list(map(int, input().split()))
    if not Sankakusu(sum(block)) :
        print(-1)
        
    else :
        while True :
            if Step_Check(block) :
                print(count)
                break
            else :
                count += 1
                len_b = len(block)
                for j in range(len_b) :
                    block[j] -= 1
                block.append(len_b)
                while 0 in block :
                    block.remove(0)
            if count == 10001 :
                print(-1)
                break

Submission status: Accepted

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

    b = list(map(int, input().split()))
    cnt = 0
    while cnt <= 10000 :
        tri_num = True
        if b[0] != 1 : tri_num = False
        for i in range( 1, len(b) ) :
            if b[i] != b[i-1]+1 :
                tri_num = False
                break
        if tri_num : break

        new_column = len(b)
            
        b_tmp = []
        for i in b :
            if i > 1 : b_tmp.append( i-1 )
        b = b_tmp
        b.append( new_column )

        cnt += 1
    if cnt <= 10000 : print(cnt)
    else : print(-1)

Submission status: Accepted

Solution code:
K = [i+1 for i in range(2000)]

while 1:
    N = int(input())
    if N == 0:
        break
    *S, = map(int, input().split())
    if S == K[:len(S)]:
        print(0)
        continue
    i = 1; s = 0; su = sum(S)
    while s < su:
        s += i; i += 1

    if s != su:
        print(-1)
        continue

    for t in range(10000):
        T = []
        for s in S:
            if s > 1:
                T.append(s-1)
        T.append(len(S))
        S, T = T, S
        if S == K[:len(S)]:
            print(t+1)
            break
    else:
        print(-1)

Submission status: Accepted

Solution code:
l = list(range(1, 100000))
tri_num = set(i*(i+1)//2 for i in range(1, 100000))

while True:
    N = int(input())
    
    if N==0:
        break
    
    b = list(map(int, input().split()))
    
    if sum(b) not in tri_num:
        print(-1)
        continue
    
    ans = 0
    
    while True:
        flag = True
        
        for i in range(len(b)):
            if b[i]!=l[i]:
                flag = False
        
        if flag:
            print(ans)
            break
        
        for i in range(len(b)):
            b[i] -= 1
    
        b.append(len(b));
        b = [bi for bi in b if bi!=0]
        ans += 1
        
        if ans>10000:
            print(-1)
            break

Submission status: Runtime Error

Solution code:
while 1:
    N = int(input())
    if N == 0:break
    lst = list(map(int,input().split()))

    s_len = 1
    n = lst[-1]
#    for v in reversed(lst[:-1]):
#        if v == n-1:
#           s_len += 1
#           n -= 1
#        else:
#            break

    
    result = -1
    for i in range(10000):
        flg = True
        for j in range(len(lst)):
            if j+1 != lst[j]:
                flg = False
        if flg:
            result = i
            break

#        if len(lst) == s_len:
#            result = i
#            break

        #抜くブロック数を取得
        cnt = 0
        for j in reversed(range(len(lst))):
            cnt += 1
            lst[j] -= 1
            if lst[j] == 0:
#                if j >= len(lst)-s_len:
#                    s_len -=1
#                elif j == len(lst)-s_len-1 and j > 0 and s_len > 0:
#                    if lst[j-1] ==lst[len(lst)-s_len]:
#                        s_len += 1
                
                lst.pop(j)
        lst.append(cnt)
   #     print(lst)
#        if cnt == lst[-2]+1:
#            s_len += 1
#        else:
#            s_len = 1
        
    print(result)

Submission status: Runtime Error

Solution code:
import math


def check(a):
    for i, v in enumerate(a):
        if v != i + 1:
            return False
        else:
            if i == len(a) - 1:
                return True


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

    a = map(int, raw_input().split())
    if sum(a) != (lambda s: s * (s + 1) // 2)(int(math.sqrt(sum(a) * 2))):
        print -1
    else:
        c = 0
        while not check(a):
            c += 1
            a = [x - 1 for x in a if x - 1 != 0].append(len(a))
            if c == 10000:
                c = -1
                break

        print c