Problem:


家庭菜園に野菜を植えることにしました。n 粒の種があったので1日に1粒ずつ、n 日かけて n 粒の種をまきました。どの種からも芽が出て、すくすくと育っています。収穫の時期が待ち遠しいものです。

ある日、いつものように苗に水やりをしていると、おかしなことに気づきました。n 本の野菜の苗があるはずなのに、1本多いのです。雑草が生えてきてしまいました。直ちに引っこ抜きたいのですが、困ったことにどの苗もよく似ていて、野菜と雑草の見分けがつきません。

手がかりになるのは、野菜の成長速度です。この野菜は、種をまいてからずっと、1日に決まった長さだけ伸び続けるのです。しかし、この「決まった長さ」というのが何センチメートルなのかはわかりません。また、最初の種を何日前にまいたのかも忘れてしまいました。苗は一列に並んでいますが、唯一覚えているのは、種をまくとき毎日一粒ずつ右から順にまいていったことだけです。

n＋１本の苗の長さを入力し、雑草の長さを出力するプログラムを作成して下さい。

入力

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

n
h1 h2 h3 ... hn+1

１行目の n (4 ≤ n ≤ 100) は野菜の苗の数を表す整数である。２行目は１つの空白で区切られた n+1 個の整数を含み、 hi (1 ≤ hi ≤ 109)は左からi番目の苗の長さを示す。

h1 h2 ... hn+1 が等差数列になっているような入力は与えられない。

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

出力

各データセットごとに雑草の長さを出力する 。

入力例

5
1 2 3 6 4 5
6
1 3 6 9 12 15 18
4
5 7 9 11 12
0

出力例

6
1
12



Sample input:
5
1 2 3 6 4 5
6
1 3 6 9 12 15 18
4
5 7 9 11 12
0


Sample output:
6
1
12

Submission status: Wrong Answer

Solution code:
ans = []
while(1):
	number = int(raw_input())
	if number == 0:
		break
	length_list_str = raw_input().split(' ')
	length_list = []
	prev_length = 0
	for i,cur_length in enumerate(length_list_str):
		cur_length = int(cur_length)
		if i == 0:
			prev_length = cur_length
		else:
			length_list.append(
				cur_length - prev_length)
			prev_length = cur_length
	hantei = sorted(length_list,reverse=True)
	if hantei[1] == hantei[0] or hantei[1] == hantei[-1]:
		if length_list[1] != length_list[0]:
			ans.append(int(length_list_str[0]))
		else:
			ans.append(int(length_list_str[-1]))
	else:
		check = (hantei[0],hantei[-1])
		for i,value in enumerate(length_list):
			if value in check:
				ans.append(int(length_list_str[i+1]))
				break

for value in ans:
	print value

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    h = list(map(int,input().split()))
    for i,v in enumerate(h):
        if i == 0:
            r = (1,2,3)

        elif i == len(h) - 2:
            r = (i-2,i-1,i+1)

        elif i == len(h) -1:
            # iが答え
            print(v)
            break
        else:
            r = (i-1,i+1,i+2)
        if (h[r[2]] - h[r[1]] == h[r[1]] - h[r[0]]):
            if i != 0:
                print(v)
                break
            elif h[1] - h[0] != h[2] - h[1]:
                print(v)
                break

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    h = list(map(int,input().split()))
    for i in range(len(h)):
        tmp = -1
        pre = h[0] if i != 0 else h[1]
        flg = True
        for j in range(1 if i != 0 else 2, len(h)):
            if i == j:continue
            if tmp == -1:
                tmp = h[j] - pre
           # print(str(tmp) + ' ' + str(pre) + ' ' + str(h[j]))
            if tmp != h[j] - pre:
                flg = False
                break
            pre = h[j]

        if flg:
            print(h[i])
            break
            
#    for i,v in enumerate(h):
#        if i == 0:
#            r = (1,2,3)
#
#        elif i == len(h) - 2:
#            r = (i-2,i-1,i+1)
#
#        elif i == len(h) -1:
#            # iが答え
#            print(v)
#            break
#        else:
#            r = (i-1,i+1,i+2)
#        if (h[r[2]] - h[r[1]] == h[r[1]] - h[r[0]]):
#            if i != 0:
#                print(v)
#                break
#            elif h[1] - h[0] != h[2] - h[1]:
#                print(v)
#                break
#

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    h = list(map(int,input().split()))
    for i in range(len(h)):
        tmp = -1
        pre = h[0] if i != 0 else h[1]
        flg = True
        for j in range(1 , len(h)):
            if i == j:continue
            if tmp == -1:
                tmp = h[j] - pre
           # print(str(tmp) + ' ' + str(pre) + ' ' + str(h[j]))
            if tmp != h[j] - pre:
                flg = False
                break
            pre = h[j]

        if flg:
            print(h[i])
            break
            
#    for i,v in enumerate(h):
#        if i == 0:
#            r = (1,2,3)
#
#        elif i == len(h) - 2:
#            r = (i-2,i-1,i+1)
#
#        elif i == len(h) -1:
#            # iが答え
#            print(v)
#            break
#        else:
#            r = (i-1,i+1,i+2)
#        if (h[r[2]] - h[r[1]] == h[r[1]] - h[r[0]]):
#            if i != 0:
#                print(v)
#                break
#            elif h[1] - h[0] != h[2] - h[1]:
#                print(v)
#                break
#

Submission status: Wrong Answer

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  lst = list(map(int, input().split()))
  ds = [lst[1] - lst[0], lst[2] - lst[1], lst[3] - lst[2]]
  if ds.count(ds[0]) == 1:
    d = ds[1]
  else:
    d = ds[0]

  if lst[1] - lst[0] != d and lst[2] - lst[1] == d:
    ans = lst[0]
  else:
    correct = [lst[0] + d * i for i in range(n + 1)]
    for f, c in zip(lst, correct):
      if f != c:
        ans = f
        break
  print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
  n = input()

  if not n:
    return False

  b = map(int, raw_input().split())
  c = {}

  for i in range(n - 1):
    d = b[i + 1] - b[i]
    if not d in c:
      c[d] = 0
    c[d] += 1

  d = (0, 0)

  for cc in c:
    d = max(d, (c[cc], cc))
  d = d[1]

  for i in range(1, n - 1):
    if b[i] - b[i - 1] != d and b[i + 1] - b[i] != d:
      print b[i]
      return True

  if b[1] - b[0] != d:
    print b[0]
  else:
    print b[-1]

  return True

while solve():
  pass

Submission status: Wrong Answer

Solution code:
while True:
    n=input()
    if n==0:break
    H=map(int,raw_input().split())
    ls=[H[1]-H[0],H[2]-H[1],H[3]-H[2]]
    for i in ls:
        if ls.count(i)>=2:
            diff=i
            break
    for i in range(n):
        if H[i+1]-H[i]!=diff:
            if 0<=i<n-1:
                print H[i] if H[i+2]-H[i+1]==diff else H[i+1]
                break
            elif i==n-1:
                print H[i+1] if H[i]-H[i-1]==diff else H[i]
                break

Submission status: Wrong Answer

Solution code:
while True:
    n=input()
    if n==0:break
    H=map(int,raw_input().split())
    ls=[H[1]-H[0],H[2]-H[1],H[3]-H[2]]
    for i in ls:
        if ls.count(i)>=2:
            diff=i
            break
    for i in range(n):
        t=H[i]+diff
        if H[i+1]!=t:
            if i!=0:
                print H[i+1]
                break
            else:
                print H[i] if H[i+2]-H[i+1]==diff else H[i+1]
                break

Submission status: Wrong Answer

Solution code:
import sys
def main():
    while True:
        line=raw_input()
        if line.isdigit():
            n=int(line)
            if n==0:    break
            solve(n)
        else:
            sys.stderr.write(line)
def solve(n):
    ipt=map(int,raw_input().split(" "))
#     print ipt
    diff=[0]*n
    for i in range(n):  diff[i]=ipt[i]-ipt[i+1]
    if diff[0]!=diff[1] and diff[1]==diff[2]:
        print ipt[0]
        return
    for i in range(n):
        if diff[i]!=diff[i+1]:
            print ipt[i+2]
            break
#     print diff
if __name__=="__main__":  main()

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	plant = map(int,raw_input().split())
	diff = [plant[i+1] - plant[i] for i in range(n)]
	p = 0
	for d in list(set(diff)):
		if diff.count(d) == 1:
			q = diff.index(d)
			p = max(p,q) if q < n-1 else max(p,q+1)
	print plant[p]

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	plant = map(int,raw_input().split())
	a1,a2 = plant[1] - plant[0], plant[2] - plant[0]
	b = plant[0]
	for i in range(3,n + 1):
		if plant[i] != a1*i + b:
			if i == n or plant[i+1] == a1*i + b:
				print plant[i]
			else:
				if plant[3] == a2*3 + b:
					print plant[1]
				else:
					print plant[0]
			break

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	plant = map(int,raw_input().split())
	ini = plant[0]
	plant = [plant[i] - ini for i in range(n+1)]
	unit = plant[1]
	p = []
	d = 0
	for i in range(2,n+1):
		if plant[i] != unit*(i-d):
			p.append(i)
			d += 1
	l = len(p)
	if l == n-1:
		print ini
	elif l == 1:
		print plant[p[0]] + ini
	else:
		print plant[1] + ini

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x))[1]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i] + 2*d == a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x), reverse = True)[0]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i] + 2*d == a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	d = [a[i+1] - a[i] for i in range(n)]
	for i in range(n):
		if i == 0 and d[i] != d[i+1]:
			if d[i+1] != d[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif d[i] != d[i+1]:
			print a[i+2]
			break

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	d = [a[i+1] - a[i] for i in range(n)]
	for i in range(n):
		if i == 0 and d[i] != d[i+1]:
			if d[i+1] != d[i+2]:
				print a[i+2]
			else:
				print a[i]
			break
		elif d[i] != d[i+1]:
			print a[i+2]
			break

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	d = [a[i+1] - a[i] for i in range(n)]
	for i in range(n):
		if i == 0 and d[i] != d[i+1]:
			if d[i] == d[i+3]:
				print a[i+2]
			elif d[i+2] == d[i+3]:	
				print a[i]
			else:
				print a[i+1]
			break
		elif d[i] != d[i+1]:
			print a[i+2]
			break

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    h = list(map(int,input().split()))
    sa = []
    for i in range(n):
        sa.append(h[i+1] - h[i])
    v = sorted(set(sa),key=lambda x:sa.count(x))[-1]
    for i in range(n):
        if i == 0 and h[i+1] - h[i] != v:
            if h[i+2] - h[i+1] == v:
                print(h[i])
            else:
                print(h[i+1])
            break
        elif h[i+1] - h[i] != v:
            print(h[i+1])
            break
        #pass
            
#    for i,v in enumerate(h):
#        if i == 0:
#            r = (1,2,3)
#
#        elif i == len(h) - 2:
#            r = (i-2,i-1,i+1)
#
#        elif i == len(h) -1:
#            # iが答え
#            print(v)
#            break
#        else:
#            r = (i-1,i+1,i+2)
#        if (h[r[2]] - h[r[1]] == h[r[1]] - h[r[0]]):
#            if i != 0:
#                print(v)
#                break
#            elif h[1] - h[0] != h[2] - h[1]:
#                print(v)
#                break
#

Submission status: Accepted

Solution code:
from itertools import count
def get_weed(h):
    d10 = h[1] - h[0]
    d21 = h[2] - h[1]
    d32 = h[3] - h[2]
    if d10 == d21 == d32:
        for hi, expect in zip(h, count(h[0], d10)):
            if hi != expect:
                return hi

    d43 = h[4] - h[3]

    if d21 == d32 == d43:
        return h[0]
    elif h[2] - h[0] == d32 == d43:
        return h[1]
    elif d10 == h[3] - h[1] == d43:
        return h[2]
    elif d10 == d21 == h[4] - h[2]:
        return h[3]

import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == 0:
        break
    h = list(map(int, f.readline().split()))
    print(get_weed(h))

Submission status: Accepted

Solution code:
from itertools import count
def get_weed(h):
    d = [h[i + 1] - h[i] for i in range(3)]
    if d[0] == d[1] == d[2]:
        for hi, expect in zip(h, count(h[0], d[0])):
            if hi != expect:
                return hi

    for i in range(4):
        hh = h[:i] + h[i + 1:]
        d = [hh[i + 1] - hh[i] for i in range(3)]
        if d[0] == d[1] == d[2]:
            return h[i]

import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == 0:
        break
    h = list(map(int, f.readline().split()))
    print(get_weed(h))

Submission status: Accepted

Solution code:
while True:
    n = input() + 1
    if n == 1:
        break
    H = map(int, raw_input().split())
    
    for i in range(n):
        A = list(H)
        A.pop(i)
        diff = [A[j+1] - A[j] for j in range(n-2)]
        if all(v == diff[0] for v in diff):
            print H[i]
            break

Submission status: Accepted

Solution code:
import copy

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

    for i in range(n+1):
        k = copy.deepcopy(h)
        kanade = k.pop(i)
        res = []
        for j in range(n-1):
            res.append(k[j+1] - k[j])
    
        if all([1 if x == res[0] else 0 for x in res]):
            print(kanade)
            break

Submission status: Accepted

Solution code:
from collections import Counter
while 1:
    n = int(input())
    if n == 0:break
    a = tuple(map(int, input().split()))
    b = [a[i + 1] - a[i] for i in range(n)]
    d = Counter(b).most_common()[0][0]
    for i in range(n):
        if b[i] != d:
            if i < n - 1 and b[i + 1] == d:print(a[i])
            else:print(a[i + 1])
            break

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  lst = list(map(int, input().split()))
  for i in range(n + 1):
    sample = lst[:i] + lst[i + 1:]
    correct = [sample[0] + (sample[1] - sample[0]) * j for j in range(n)]
    if sample == correct:
      print(lst[i])
      break

Submission status: Accepted

Solution code:
def solve():
  n = input()

  if not n:
    return False

  b = map(int, raw_input().split())

  for i in range(n + 1):
    a = b[:i] + b[i + 1:]
    ok = True
    s = set()
    for j in range(n - 1):
      s.add(a[j + 1] - a[j])
    if len(s) == 1:
      print b[i]
      break

  return True

while solve():
  pass

Submission status: Accepted

Solution code:
#!/usr/bin/env python
while 1:
    n=int(raw_input())
    if n==0: break
    grass=map(int, raw_input().split())
    for i in range(n+1):
        h=[ x for j,x in enumerate(grass) if i!=j ]
        g=[ h[j+1]-h[j] for j in range(len(h)-1) ]
        if len(set(g))==1:
            print grass[i]
            break

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
    n=input()
    if n==0:break
    dic=defaultdict(int)
    H=map(int,raw_input().split())
    for i in range(n):
        dic[H[i+1]-H[i]]+=1
    d=dict((j,i) for i,j in dic.items())
    diff=d[max(d)]
    for i in range(n):
        t=H[i]+diff
        if H[i+1]!=t:
            if i!=0:
                print H[i+1]
                break
            else:
                print H[i] if H[i+2]-H[i+1]==diff else H[i+1]
                break

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x))[-1]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i+1] + d != a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break
    l = list(map(int,input().split()))
    d = [ l[i+1] - l[i] for i in range(n)]
    if d[0] == d[n-1]:
        for i in range(1,n-1):
            if d[i]!= d[0]:
                print(l[i+1])
                break
    elif d[n-1] == d[n-2] and d[n-2] == d[n-3] and d[1] == d[2]:
        print(l[0])
    elif d[n-1] == d[n-2] and d[n-2] == d[n-3] and d[1] != d[2]:
        print(l[1])
    elif d[0] == d[1] and d[1] == d[2] and d[n-2] == d[n-3]:
        print(l[n])
    else:
        print(l[n-1])

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N == 0:
        break
    *H, = map(int, input().split())
    def gen(k):
        for i in range(N+1):
            if i == k:
                continue
            yield H[i]
    for i in range(N+1):
        ok = 1
        g = gen(i).__next__
        h0 = g(); h1 = g()
        d = h1 - h0
        for j in range(N-2):
            h2 = g()
            if h2 - h1 != d:
                ok = 0
                break
            h1 = h2
        if ok:
            print(H[i])
            break

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    h = list(map(int,input().split()))
    for i in range(n+1):
        s = 0
        if i == 0:
            s = 1
        d = None
        k = 1
        cnt = 0
        for j in range(s+1,n+1):
            if j == i:
                continue
            if d == None:
                d = h[j]-h[s]
            elif h[j]-h[s] != d*k:
                cnt += 1
            k += 1
        if cnt == 0:
            print(h[i])
            break

Submission status: Accepted

Solution code:
from sys import exit
while(True):
    N = int(input())
    # print(N)
    if N == 0:
        break
    h = list(map(int, input().split()))
    for i in range(N+1):
        targ = h[:i] + h[i+1:]
        diff = targ[1] - targ[0]
        OK = True
        for j in range(1, N):
            if diff != targ[j] - targ[j-1]:
                OK = False
                break
        if not OK:
            continue
        else:
            print(h[i])
            break

Submission status: Accepted

Solution code:
def check(h):
    flag = True
    for i in range(len(h)-2):
        if h[i+1] - h[i] != h[i+2] - h[i+1]:
            flag = False
            break
    return flag   

while True:
    n = int(input())
    if n == 0:
        break
    
    h = [int(i) for i in input().split()]

    ans = -1 
    for k in range(n+1):
        tmp = h.pop(k)
        if check(h):
            print(tmp)
            break
        h.insert(k, tmp)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
while 1:
    n=int(raw_input())
    if n==0: break
    h1=map(int, raw_input().split())
    for h in h1:
        h2=[ x for x in h1 if x!=h ]
        g=[ h2[i+1]-h2[i] for i in range(n-1) ]
        if len(set(g))==1:
            print h
            break

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
while 1:
    try:
        n=int(raw_input())
        if n==0: break
        h1=map(int, raw_input().split())
        for h in h1:
            h2=[ x for x in h1 if x!=h ]
            g=[ h2[i+1]-h2[i] for i in range(n-1) ]
            if len(set(g))==1:
                print h
                break
    except RuntimeError, e:
        print e.message

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
while 1:
    try:
        n=int(raw_input())
        if n==0: break
        h1=map(int, raw_input().split())
        for h in h1:
            h2=[ x for x in h1 if x!=h ]
            g=[ h2[i+1]-h2[i] for i in range(n-1) ]
            if len(set(g))==1:
                print h
                break
    except RuntimeError, e:
        print n, h1
        print e.message

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	da = [a[i+1] - a[i] for i in range(n)]
	d = sorted(list(set(da)), key = lambda x:da.count(x)[1]
	for i in range(n):
		if i == 0 and a[i] + d != a[i+1]:
			if a[i] + 2*d == a[i+2]:
				print a[i+1]
			else:
				print a[i]
			break
		elif a[i] + d != a[i+1]:
			print a[i+1]
			break