Problem:


最長の階段  

問題

 1 から n までの整数がそれぞれ 1 つずつ書かれた n 枚のカードと,1 枚の白紙の
カードがある.これら n + 1 枚のカードの内,k 枚のカードが与えられる.ただし,
1 ≤ k ≤ n である.白紙のカードには 1 から n までの整数を 1 つ書くことができ
る.与えられたカードだけで,できるだけ長い連続した整数列を作りたい.

 与えられるカードが入力されたときに, 与えられたカードから作ることができる連
続した整数列の最大長を出力するプログラムを作成せよ.

例1

 n = 7, k = 5 とする.6, 2, 4, 7, 1 のカードが与えられたとき,このカードを使っ
て作れる連続した整数列のうち最長のものは 1, 2 であり,その長さは 2 である.

例2

 n = 7, k = 5 とする.6, 2, 4, 7 と白紙のカードが与えられたとき,このカードを
使って作れる連続した整数列のうち最長のものは,白紙のカードに 5 を書くことに
よってできる 4, 5, 6, 7 であり,その長さは 4 である.

入力

input.txt である.-->
入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロ２つを含む行で終了する．

  1 行目には,2 つの整数 n (1 ≤ n ≤ 100000) と k (1 ≤ k ≤ n) がこの順で 1 つの
空白を区切りとして書かれている.続く k 行には整数が 1 つずつ書かれており,与
えられる k 枚のカードに書かれている整数を表している.白紙のカードは 0 で表さ
れる.

  採点用データのうち, 配点の 40% 分は 1 ≤ n ≤ 1000, 1 ≤ k ≤ 500 を, 配点の 20% 分は 1 ≤ n ≤ 60000, 1 ≤ k ≤  50000 を. 配点の 40% 分は 1 ≤  n ≤  100000, 1 ≤ k ≤ 100000 を満たす.

データセットの数は 5 を超えない．

出力

output.txt である.
output.txt は 1 行だけからなり,その 1 行は出力する整数 1 つだけを含む.
-->
データセットごとに整数を1行に出力する．

入出力例

入力例

7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0

出力例

2
4

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0


Sample output:
2
4

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,input().split())
    A = sorted([int(input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    diff = []
    ans = 0
    prev = 0
    prev_prev = 0
    count = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 1:
            count += 1
            ans = max(ans,count-prev_prev)
        elif A[i] - A[i-1] == 2:
            if flag is True:
                count += 1
                ans = max(ans,count-prev_prev)
                prev_prev = prev
                prev = count - prev
            else:
                count = 0
        else:
            count = 0
    print(ans + A[0])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    diff = []
    ans = 0
    white_card = 0
    prev_white_card = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 1:
            ans = max(ans,A[i] - prev_white_card)
        elif A[i] - A[i-1] == 2 and flag is True:
            ans = max(ans,A[i] - prev_white_card)
            prev_white_card = white_card
            white_card = A[i]
        else:
            prev_white_card = A[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,input().split())
    A = sorted([int(input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    count = 0
    diff_list = []
    s = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 2:
            diff_list.append(A[i-1] - A[s])
            s = i
            count = 0
        if A[i] - A[i-1] >= 2:
            s = i
            count = 0
        count += 1
        ans = max(ans,count)

    else:
        diff_list.append(A[i] - A[s])

    if flag is True:
        for i in range(1,len(diff_list)):
            ans = max(ans,diff_list[i] + diff_list[i-1] + 3)

    print(ans)

Submission status: Wrong Answer

Solution code:
while True:    
    n, k = map(int, raw_input().split())
    if n==0: break
    t = [0]*(n+2)
    for i in xrange(k):
        t[input()] += 1
    for i in xrange(2,n+1):
        if t[i] > 0: t[i] += t[i-1]
    ans = 0
    if t[0]==0:
        for i in t:
            if ans < t[i]: ans = t[i]
    else:    
        nt = []
        for i in xrange(2,n+2):
            if t[i]==0:
                t[i-t[i-1]] = t[i-1]
        for i in xrange(2,n+1):
            if t[i]==0:
                nt.append(t[i-1]+1+t[i+1])
            else: nt.append(t[i])
        for i in nt:
            if ans < i: ans = i
    print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys
def readints():
    return map(int, sys.stdin.readline().split())

n, k = readints()

while n and k:
    xs = [False for i in range(n+1)]
    for i in range(k):
        x, = readints()
        xs[x] = True

    last = 1
    before = 1
    longest = 0
    for i in range(1, n+1):
        x = xs[i]
        if x:
            pass
        elif xs[0]:
            longest = max(longest, i - before)
            before = last
            last = i
        else:
            longest = max(longest, i - last)
            last = i
    print longest
    n, k = readints()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys
def readints():
    return map(int, sys.stdin.readline().split())

n, k = readints()

while n and k:
    xs = [False for i in range(n+1)]
    for i in range(k):
        x, = readints()
        xs[x] = True

    last = 1
    before = 1
    longest = 0
    for i in range(1, n+1):
        x = xs[i]
        if x:
            pass
        elif xs[0]:
            longest = max(longest, i - last, i - before)
            before = last
            last = i
        else:
            longest = max(longest, i - last)
            last = i
    print longest
    n, k = readints()

Submission status: Wrong Answer

Solution code:
def len1(L):
    i,cnt,maxInt=1,0,0
    f=True
    t=1
    while i<=n:
        if L[i]==1:
            cnt+=1
        elif f:
            f=False
            t=i
            cnt+=1
        else:
            i=t+1
            maxInt=max(maxInt,cnt)
            cnt=1
            f=True
        i+=1
    return max(maxInt,cnt)

def len2(L):
    cnt,maxInt=0,0
    for i in range(1,n+1):
        if L[i]==1:
            cnt+=1
        else:
            maxInt=max(maxInt,cnt)
            cnt=0
    return maxInt

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[0]*(n+1)
    for i in range(k):
        L[input()]=1
    print len1(L) if L[0] else len2(L)

Submission status: Wrong Answer

Solution code:
while 1:
	n,k=map(int,raw_input().split())
	if n==0:break
	a=sorted([int(raw_input()) for i in range(k)])
	ans=L=1
	if a[0]==0:
		for i in range(1,k-1):
			if a[i]+1!=a[i+1]:
				sp=i
				break
		for i in range(sp,k-1):
			if a[i]+1==a[i+1]:
				L+=1
			else:
				ans=max(ans,L+i+2-sp)
				sp=i
				L=1
	else:
		for i in range(k-1):
			if a[i]+1==a[i+1]:
				L+=1
			else:
				ans=max(ans,L)
				L=1
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	n,k=map(int,raw_input().split())
	if n==0:break
	a=sorted([int(raw_input()) for i in range(k)])
	ans=1
	if a[0]==0:
		sp=1;nsp=-1
		for i in range(1,k-1):
			if a[i]+1!=a[i+1]:
				if nsp==-1:
					nsp=i+1
				else:
					ans=max(ans,i-sp+2)
					sp=nsp;nsp=-1
		else:
			if nsp==-1:
				ans=max(ans,k-1-sp+2)
	else:
		sp=0
		for i in range(k-1):
			if a[i]+1!=a[i+1]:
				ans=max(ans,i-sp+1)
				sp=i
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	n,k=map(int,raw_input().split())
	if n==0:break
	a=sorted([int(raw_input()) for i in range(k)])
	ans=1
	if a[0]==0:
		sp=1;nsp=-1
		for i in range(1,k-1):
			if a[i]+2==a[i+1] and nsp==-1:
				nsp=i+1
			elif a[i]+1<a[i+1]:
				if nsp==-1:
					ans=max(ans,i-sp+2)
					sp=i+1
				else:
					ans=max(ans,i-sp+2)
					sp=nsp;nsp=-1
		else:
			if nsp==-1:
				ans=max(ans,k-1-sp+2)
	else:
		sp=0
		for i in range(k-1):
			if a[i]+1!=a[i+1]:
				ans=max(ans,i-sp+1)
				sp=i
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	n,k=map(int,raw_input().split())
	if n==0:break
	a=sorted([int(raw_input()) for i in range(k)])
	ans=1
	if a[0]==0:
		sp=1;nsp=-1
		for i in range(1,k-1):
			if a[i]+2==a[i+1] and nsp==-1:
				nsp=i+1
			elif a[i]+1<a[i+1]:
				if nsp==-1:
					ans=max(ans,i-sp+2)
					sp=i
				else:
					ans=max(ans,i-sp+2)
					sp=nsp;nsp=-1
		else:
			if nsp==-1:
				ans=max(ans,k-1-sp+2)
	else:
		sp=0
		for i in range(k-1):
			if a[i]+1!=a[i+1]:
				ans=max(ans,i-sp+1)
				sp=i
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	c = sorted([int(raw_input()) for i in range(k)])
	use0 = -1
	if c[0] == 0:
		use0 = 1
		k -= 1
		c.pop(0)
	d = [c[i]-c[i+1] for i in range(k-1)]
	sp = L = ans = 1
	for i in range(k-1):
		print i,d[i],L
		if d[i] == -1:
			L += 1
		elif d[i] == -2 and use0 == 1:
			L += 2
			sp = i
			use0 = 0
		else:
			ans = max(ans,L+max(use0,0))
			if d[i] < -2 or use0 != 0: sp = i+1
			L = i-sp+2 if d[i] == -2 else 1
			if use0 != -1: use0 = 1
	ans = max(ans,L)
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = min(0,c[0])
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2]:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)

Submission status: Wrong Answer

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = min(1,c[0])
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2]:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)

Submission status: Wrong Answer

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = max(0,1-c[0])
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2]:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    for i in range(K):
        for j in range(i+1,K):
            if j - i == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            elif flag is True and j - i + 1 == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])

    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    for i in range(K):
        for j in range(i+1,K):
            if j - i == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            elif flag is True and j - i + 1 == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            else:
                break

    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    for i in range(K):
        for j in range(i+ans,K):
            if j - i == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            elif flag is True and j - i + 1 == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            else:
                break

    print(ans+1)

Submission status: Accepted

Solution code:
while(1):
    [n,k]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        hand=[]
        for i in range(k):
            hand.append(int(raw_input()))
        hand.sort()
        havewhite=0
        if hand[0]==0:
            del hand[0]
            k=k-1
            havewhite=1
        groupedhand=[]
        #grouping
        groupedhand=[]
        group=[hand.pop(0)]
        while len(hand)>0:
            card=hand.pop(0)
            if card-group[-1]==1:
                group.append(card)
            else:
                groupedhand.append(group)
                group=[card]
        groupedhand.append(group)
        if havewhite:
            for i in range(len(groupedhand)-1):
                if groupedhand[i+1][0]-groupedhand[i][-1]==2:
                    groupedhand[i]=groupedhand[i]+groupedhand[i+1]
        maxlength=max([len(group) for group in groupedhand])
        if havewhite:
            maxlength=maxlength+1
        print maxlength

Submission status: Accepted

Solution code:
while 1:
	n, k = map(int,raw_input().split(" "))
	if (n,k) == (0,0):
		break
	card = sorted([int(raw_input()) for i in range(k)])
	group = []
	wild = False
	if card[0] == 0:
		card.pop(0)
		k = k-1
		wild = True 
	group.append([card[0],card[0],1])
	token = 0
	for i in range(1,k):
		if group[token][1] + 1 == card[i]:
			group[token][1] = card[i]
			group[token][2] += 1
		else:
			group.append([card[i],card[i],1])
			token += 1

	tmp_score = max(group, key = lambda x: x[2])[2]
	if wild:
		for i in range(len(group)-1):
			if group[i][1] + 2 == group[i+1][0]:
				tmp_score = max(tmp_score, group[i][2]+group[i+1][2])
		tmp_score += 1
	print tmp_score

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,input().split())
    A = sorted([int(input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    count = 0
    diff_list = []
    s = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 2:
            diff_list.append(A[i-1] - A[s])
            s = i
            count = 0
        elif A[i] - A[i-1] > 2:
            diff_list.append(A[i-1] - A[s])
            diff_list.append(0)
            s = i
            count = 0
        else:
            count += 1
            ans = max(ans,count)
    else:
        diff_list.append(A[i] - A[s])

    if flag is True:
        ans = 0
        for i in range(1,len(diff_list)):
            ans = max(ans,diff_list[i] + diff_list[i-1] + 2)

    print(ans + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    count = 0
    diff_list = []
    s = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 2:
            diff_list.append(A[i-1] - A[s])
            s = i
            count = 0
        elif A[i] - A[i-1] > 2:
            diff_list.append(A[i-1] - A[s])
            diff_list.append(0)
            s = i
            count = 0
        else:
            count += 1
            ans = max(ans,count)
    else:
        diff_list.append(A[i] - A[s])

    if flag is True:
        ans = 0
        for i in range(1,len(diff_list)):
            ans = max(ans,diff_list[i] + diff_list[i-1] + 2)

    print(ans + 1)

Submission status: Accepted

Solution code:
while True:    
    n, k = map(int, raw_input().split())
    if n==0: break
    t = [0]*(n+2)
    for i in xrange(k):
        t[input()] += 1
    for i in xrange(2,n+1):
        if t[i] > 0: t[i] += t[i-1]
    ans = 0
    if t[0]==0:
        for x in t:
            if ans < x: ans = x
    else:    
        nt = []
        for i in xrange(2,n+2):
            if t[i]==0:
                t[i-t[i-1]] = t[i-1]
        for i in xrange(2,n+1):
            if t[i]==0:
                nt.append(t[i-1]+1+t[i+1])
            else: nt.append(t[i])
        for x in nt:
            if ans < x: ans = x
    print ans

Submission status: Accepted

Solution code:
while True:    
    n, k = map(int, raw_input().split())
    if n==0: break
    t = [0]*(n+2)
    for i in xrange(k):
        t[input()] += 1
    for i in xrange(2,n+1):
        if t[i] > 0: t[i] += t[i-1]
    ans = 0
    if t[0]==0:
        for x in t:
            if ans < x: ans = x
    else:    
        nt = []
        for i in xrange(2,n+2):
            if t[i]==0:
                t[i-t[i-1]] = t[i-1]
        for i in xrange(2,n+1):
            if t[i]==0:
                nt += [t[i-1]+1+t[i+1]]
            else: nt += [t[i]]
        for x in nt:
            if ans < x: ans = x
    print ans

Submission status: Accepted

Solution code:
while True:    
    n, k = map(int, raw_input().split())
    if n==0: break
    t = [0]*(n+2)
    for i in xrange(k):
        t[input()] += 1
    for i in xrange(2,n+1):
        if t[i] > 0: t[i] += t[i-1]
    ans = 0
    if t[0]==0:
        for x in t:
            if ans < x: ans = x
    else:
        for i in xrange(2,n+2):
            if t[i]==0:
                t[i-t[i-1]] = t[i-1]
        for i in xrange(2,n+1):
            if t[i]==0:
                x = t[i-1] + 1 + t[i+1]
                if ans < x: ans = x
            else: 
                if ans < t[i]: ans = t[i]
    print ans

Submission status: Accepted

Solution code:
while True:
    n, k = map(int, input().split())
    if not n:
        break
    cards = [int(input()) for _ in range(k)]
    cards.sort(reverse=True)
    white = False
    if not cards[-1]:
        white = True
        cards.pop()
    if not cards:
        print(1)
        continue
    prev, cnt, precnt = cards.pop(), 1, 0
    ans = 1
    while cards:
        cur = cards.pop()
        diff = cur - prev
        if diff == 1:
            cnt += 1
        else:
            ans = max(ans, precnt + cnt)
            precnt = (cnt + 1) if white and diff == 2 else 0
            cnt = 1
        prev = cur
    ans = max(ans, precnt + cnt)

    print(ans)

Submission status: Accepted

Solution code:
while 1:
    n, k = map(int, raw_input().split())
    if n == k == 0:
        break
    C = [int(raw_input()) for i in xrange(k)]
    C.sort()
    if C[0] == 0:
        C[0] = -2
    cnt = 1; ans = 0
    I = []
    for i in xrange(1, k):
        if C[i-1]+1 == C[i]:
            cnt += 1
        else:
            I.append((C[i-cnt], C[i-1], cnt))
            ans = max(ans, cnt)
            cnt = 1
    I.append((C[k-cnt], C[k-1], cnt))
    if C[0] < 0:
        for j in xrange(1, len(I)):
            if I[j-1][1]+2 == I[j][0]:
                ans = max(ans, I[j-1][2]+I[j][2]+1)
    print ans

Submission status: Accepted

Solution code:
while True:
    n,k=[int(s)for s in input().split(" ")]
    if n==k==0:break
    card=sorted([int(input())for i in range(k)])
    blank=card[0]==0
    if blank:card.pop(0)
    lens=[]
    con=[]
    tl=1
    i=0
    while i<len(card)-1:
        if card[i+1]==card[i]+1:tl+=1
        else:
            if card[i+1]==card[i]+2:con.append(True)
            else:con.append(False)
            lens.append(tl)
            tl=1
        i+=1
    lens.append(tl)
    if not blank:print(max(lens))
    else:
        l=0
        for i in range(len(con)):
            if con[i]:
                l=max((l,lens[i]+lens[i+1]+1))
        print(l)

Submission status: Accepted

Solution code:
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    lst = [0 for _ in range(n)]
    lst2 = []
    flag = 0
    for _ in range(k):
      i = int(input())
      if not i:
        flag = 1
      else:
        lst[i - 1] = 1
    l = -1
    r = -1
    for i in range(n):
      if lst[i] == 0:
        if r != -1:
          lst2.append((l,r))
          l = -1
          r = -1
      else:
        if l == -1:
          l = i
          r = i
        else:
          r += 1
    else:
      if r != -1:
        lst2.append((l,r))
    ans = 0
#    print(lst)
#    print(lst2)
    if not flag:
      for t in lst2:
        ans = max(ans,t[1] - t[0] + 1)
    else:
      for i in range(len(lst2)):
        if i == 0:
          ans = max(ans,lst2[0][1] - lst2[0][0] + 1)
        elif lst2[i][0] - lst2[i - 1][1] == 2:
          ans = max(ans,lst2[i][1] - lst2[i - 1][0] + 1)
        else:
          ans = max(ans,lst2[i][1] - lst2[i][0] + 1)
    print(ans)
  except EOFError:
    break

Submission status: Accepted

Solution code:
def main():
  while True:
    try:
      n,k = map(int,input().split())
      if n == 0 and k == 0: break
      lst = [0 for _ in range(n)]
      lst2 = []
      flag = 0
      for _ in range(k):
        i = int(input())
        if not i:
          flag = 1
        else:
          lst[i - 1] = 1
      l = -1
      r = -1
      for i in range(n):
        if lst[i] == 0:
          if r != -1:
            lst2.append((l,r))
            l = -1
            r = -1
        else:
          if l == -1:
            l = i
            r = i
          else:
            r += 1
      else:
        if r != -1:
          lst2.append((l,r))
      ans = 0
  #    print(lst)
  #    print(lst2)
      if not flag:
        for t in lst2:
          ans = max(ans,t[1] - t[0] + 1)
      else:
        for i in range(len(lst2)):
          if i == 0:
            ans = max(ans,lst2[0][1] - lst2[0][0] + 1)
          elif lst2[i][0] - lst2[i - 1][1] == 2:
            ans = max(ans,lst2[i][1] - lst2[i - 1][0] + 1)
          else:
            ans = max(ans,lst2[i][1] - lst2[i][0] + 1)
      print(ans)
    except EOFError:
      break
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# AOJ 0517: Longest Steps
# Python3 2018.6.30 bal4u

while True:
	n, k = map(int, input().split())
	if n == 0: break
	c = [0]*(n+2)
	f = 0;
	for i in range(k):
		a = int(input())
		if a == 0: f = 1
		else: c[a] = 1
	ans = w0 = w = 0
	for i in range(1, n+1):
		if c[i]: w += 1
		elif w > 0:
			if w0 + w + f > ans: ans = w0 + w + f
			w0 = w if f and c[i+1] else 0
			w = 0
	if w0 + w + f > ans: ans = w0 + w + f
	print(ans)

Submission status: Accepted

Solution code:
import re
while True:
    n, k = map(int, raw_input().split())

    if n == 0 and k == 0: break

    cards = set(int(raw_input()) for x in xrange(k))

    a = ''.join('o' if x in cards else 'x' for x in xrange(1, n + 1))

    if not(0 in cards):
        v = re.findall('o+', a)
        print len(max(v, key= lambda s: len(s)))
    else:
        pattern = re.compile('(o*xo*)')
        ans = 0
        for m in re.finditer('x', a):
            matched = pattern.search(a, pos=m.end())
            if matched is not None:
                ans = max(ans, len(matched.group(1)))

        print ans

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys
def readints():
    return map(int, sys.stdin.readline().split())

n, k = readints()

while n and k:
    xs = [False for i in range(n+2)]
    for i in range(k):
        x, = readints()
        xs[x] = True

    last = 0
    before = 1
    longest = 0
    #print 'i, longest, last, before'
    for i in range(1, n+2):
        x = xs[i]
        if x:
            pass
        elif xs[0]:
            """
            0123456789
            0-x--x--x-
            i = 8

            """
            #print i, longest, last, before
            longest = max(longest, i - last -1, i - before -1)
            before = last
            last = i
        else:
            longest = max(longest, i - last-1)
            last = i
    print longest
    n, k = readints()

Submission status: Accepted

Solution code:
def len1(L):
    i,cnt,maxInt=1,0,0
    f=True
    while i<=n:
        if L[i]==1:
            cnt+=1
            i+=1
        elif f:
            f=False
            t=i
            i+=1
            cnt+=1
        else:
            i=t+1
            cnt=0
            f=True
        maxInt=max(maxInt,cnt)
    return maxInt

def len2(L):
    cnt,maxInt=0,0
    for i in range(1,n+1):
        if L[i]==1:
            cnt+=1
        else:
            maxInt=max(maxInt,cnt)
            cnt=0
    return maxInt

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[0]*(n+1)
    for i in range(k):
        L[input()]=1
    print len1(L) if L[0] else len2(L)

Submission status: Accepted

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

def countMaxLength(li):
    cnt = 1
    prev = -1
    max_cnt = 1
    for i in li:
        if i == prev + 1:
            cnt += 1
        else:
            if cnt > max_cnt:
                max_cnt = cnt
            cnt = 1
        prev = i
        
    if cnt > max_cnt:
        max_cnt = cnt
    return max_cnt

def countMaxLengthWithWildCard(li, n):
    cnt = 1
    prev = -1
    res = []
    for i in li:
        if i == prev + 1:
            cnt += 1
        else:
            ele = []
            ele.append(cnt)
            ele.append( i == prev + 2 )
            res.append(ele)
            cnt = 1
        prev = i
    ele = []
    ele.append(cnt)
    ele.append(li[-1] == n)
    res.append(ele)

    max_cnt = 1
    for i in xrange(len(res)-1):
        cnt = res[i][0] + res[i+1][0] + 1 if res[i][1] else res[i][0]
        if cnt > max_cnt:
            max_cnt = cnt
    cnt = res[-1][0] if res[-1][1] else res[-1][0] + 1
    if cnt > max_cnt:
        max_cnt = cnt
    return max_cnt

while True:
    condition = map(int, fp.readline()[:-1].split(" "))
    if condition[0] + condition[1] == 0:
        break

    n = condition[0]
    k = condition[1]

    li = []
    flg = False
    for i in xrange(k):
        num = int(fp.readline()[:-1])
        if num == 0:
            flg = True
        else:
            li.append(num)

    li.sort()

    if flg:
        print countMaxLengthWithWildCard(li, n)
    else:
        print countMaxLength(li)

Submission status: Accepted

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	s = [0]*(n+1)
	ss = [0]*(n+1)
	if n == 0: break
	c = sorted([int(raw_input()) for i in range(k)])
	use0 = -1
	if c[0] == 0:
		use0 = 1
		c.pop(0)
	for i in c:
		s[i] = s[i-1]+1
		ss[i] = ss[i-1]+1
		if s[i-1] == 0 and s[i-2] > 0:
			ss[i] = s[i] + s[i-2] + 1
	print max(s) if use0 == -1 else max(ss)

Submission status: Accepted

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	s = [0]*(n+1)
	ss = [0]*(n+1)
	if n == 0: break
	c = sorted([int(raw_input()) for i in range(k)])
	if c[0] == 0:
		for i in c[1:]:
			s[i] = s[i-1]+1
			ss[i] = ss[i-1]+1
			if s[i-1] == 0 and s[i-2] > 0:
				ss[i] = s[i] + s[i-2] + 1
		print max(ss)
	else:
		for i in c:
			s[i] = s[i-1] + 1
		print max(s)

Submission status: Accepted

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	s = [0]*(n+1)
	if n == 0: break
	c = sorted([int(raw_input()) for i in range(k)])
	have0 = 1 if c[0] == 0 else 0
	jump = 0
	for i in c[have0:]:
		s[i] = s[i-1] + 1
		if have0 and s[i-1] == 0 and s[i-2] > 0:
			s[i] += s[i-2] + 1 - jump
			jump = s[i-2] + 1
		if s[i-1] == 0 and s[i-2] == 0:
			jump = 0
	print max(s)

Submission status: Accepted

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	s = [0]*(n+1)
	if n == 0: break
	c = sorted([int(raw_input()) for i in range(k)])
	p = 1 if c[0] == 0 else 0
	jump = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2] > 0:
				s[i] += s[i-2] + 1 - jump
				jump = s[i-2] + 1
			if s[i-2] == 0:
				jump = 0
	print max(s)

Submission status: Accepted

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = 1 if c[0] == 0 else 0
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2] > 0:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
while True:
	a=[]
	n,k=map(int,input().split())
	if n==k==0:
		break
	zero=False
	for i in range(k):
		p=int(input())
		if p==0:
			zero=True
			continue
		a.append(p)
	a.sort()
	if zero==False:
		r=a[0]-1
		ans=0
		ans_kari=0
		for i in range(k):
			if a[i]==r+1:
				r=a[i]
				ans_kari+=1
			else:
				ans=max(ans,ans_kari)
				ans_kari=1
				r=a[i]
		print(ans)
	else:
		sa=[]
		for i in range(k-2):
			sa.append(a[i+1]-a[i])
		ans=l=r=0
		for i in range(len(sa)):
			if sa[i]==1:
				r+=1
			elif sa[i]==2:
				l=r
				r=1
			else:
				l=0
				r=1
			ans=max(ans,l+r+1)
		print(ans)

Submission status: Accepted

Solution code:

while True:

    n,k = map(int,input().split())
    if n == 0:
        break

    c = []
    zex = 0
    for i in range(k):
        C = int(input())

        if C == 0:
            zex = 1
        else:
            c.append(C)

    c.sort()

    ans = 0
    l = 0
    r = 0


    for i in range(len(c) - 1):

        if c[i] + 1 == c[i+1]:
            r += 1

        elif zex == 1 and c[i] + 2 == c[i+1]:
            l = r
            r = 1
        else:
            l = 0
            r = 1

        ans = max(ans,l+r+zex)

    print (ans)

Submission status: Accepted

Solution code:
anss = []
flag = False
def main():
    N, K = [int(i) for i in input().split()]
    if N == K == 0:
        global flag
        flag = True
        return
    A = [int(input()) for _ in range(K)]
    A.sort()
    zero = False
    if A[0] == 0:
        zero = True
    prev = -1
    last_island = -1
    current_streak = 0
    ans = 0
    for a in A:
        if prev == -1 or a == prev + 1:
            current_streak += 1
        elif zero == True and a == prev + 2:
            last_island = current_streak
            current_streak = 1
        else:
            last_island = -1
            current_streak = 1
        ans = max(current_streak + last_island + 1, ans)
        prev = a
    global anss
    anss.append(ans)
while not flag:
    main()
for a in anss:
    print(a)

Submission status: Accepted

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

"""
import sys


def solve(cards):
    if len(cards) == 1:
        return 1
    has_white = True if cards[0] == 0 else False
    res = []
    t = []
    prev = cards[has_white] - 1
    for c in cards[has_white:]:
        if c == prev + 1:
            t.append(c)
        else:
            res.append(t)
            t = [c]
        prev = c
    res.append(t)

    ans = max(len(r) + has_white for r in res)
    if has_white:
        for a, b in zip(res, res[1:]):
            if a[-1] + 2 == b[0]:
                ans = max(ans, len(a)+len(b)+1)
    return ans


def main(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break
        cards = sorted([int(input()) for _ in range(k)])
        ans = solve(cards)
        print(ans)


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