Problem:


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

 バームクーヘン(Baumkuchen)

JOI 君は妹のJOI 子ちゃんとJOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは3 人の大好物のバームクーヘンだ．

バームクーヘンは下図のような円筒形のお菓子である．3 人に分けるために，JOI 君は半径方向に刃を3回入れて，これを3 つのピースに切り分けなければならない．ただしこのバームクーヘンは本物の木材のように固いので，刃を入れるのは簡単ではない．そのためこのバームクーヘンにはあらかじめ $N$ 個の切れ込みが入っており，JOI 君は切れ込みのある位置でのみ切ることができる．切れ込みに1 から $N$ まで時計回りに番号をふったとき，$1 \leq i \leq N - 1$ に対し， $i$ 番目の切れ込みと$i + 1$ 番目の切れ込みの間の部分の大きさは $A_i$ である．また $N$ 番目の切れ込みと1 番目の切れ込みの間の部分の大きさは $A_N$ である．

図1: バームクーヘンの例 $N = 6, A_1 = 1, A_2 = 5, A_3 = 4, A_4 = 5, A_5 = 2, A_6 = 4$

課題

切れ込みの個数 $N$ と，各部分の大きさを表す整数 $A_1,...,A_N$ が与えられる．バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を出力するプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

 1 行目には，整数 $N$ が書かれている．これはバームクーヘンに $N$ 個の切れ込みがあることを表す．

 続く$N$ 行のうちの $i$ 行目$(1 \leq i \leq N)$ には，整数 $A_i$ が書かれている．これは $i$ 番目の切れ込みと $i + 1$ 番目の切れ込みの間の部分 ($i = N$ のときは $N$ 番目の切れ込みと1 番目の切れ込みの間の部分) の大きさが $A_i$ であることを表す．

出力

標準出力に，バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を表す整数を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

$3 \leq N \leq 100000$

$1 \leq A_i \leq 1000000000 (1 \leq i \leq N)$

入出力例

  
入力例 1 
  

  

6
1
5
4
5
2
4

  
出力例 1 
  

  

6

図2: 1 番目の切れ込みと3 番目の切れ込みと5 番目の切れ込みで切るのが最善である．

  
入力例 2 
  

  

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

  
出力例 2 
  

  

213

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



Sample input:
6
1
5
4
5
2
4


Sample output:
6

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
for i in range(n):
    a.append(input())
tmp_out=0
for i in range(1, n-2):
    b=[0,0,0]
    for ii in range(i):
        b[0] += a[ii]

    for j in range(i+1, n-1):
        for jj in range(i, j):
            b[1] += a[jj]
        for jj in range(j+1, n):
            b[2] += a[jj]

    tmp_out=max(tmp_out, min(b))

print tmp_out

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
for i in range(n):
    a.append(input())
tmp_out=0
for i in range(1, n-2):
    b=[0,0,0]
    for ii in range(i):
        b[0] += a[ii]
 
    for j in range(i+1, n-1):
        b[1]=0
        b[2]=0
        for jj in range(i, j):
            b[1] += a[jj]
        for jj in range(j+1, n):
            b[2] += a[jj]
 
        tmp_out=max(tmp_out, min(b))
 
print tmp_out

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
for i in range(n):
    a.append(input())
tmp_out=0
for i in range(1, n-2):
    b=[0,0,0]
    for ii in range(i):
        b[0] += a[ii]
  
    for j in range(i+1, n-1):
        b[1]=0
        b[2]=0
        for jj in range(i, j):
            b[1] += a[jj]
        for jj in range(j, n):
            b[2] += a[jj]
  
        tmp_out=max(tmp_out, min(b))
  
print tmp_out

Submission status: Wrong Answer

Solution code:
n=input()
a=[]
for i in range(n):
    a.append(input())
tmp_out=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            b=[0,0,0]
            for ai in range(i,j):
                b[0]+=a[ai]
            for ai in range(j,k):
                b[1]+=a[ai]
            for ai in range(k,n):
                b[2]+=a[ai]
            for ai in range(0,i):
                b[2]+=a[ai]
        tmp_out=max(tmp_out, min(b))
   
print tmp_out

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

#ラジアンを度に変換
def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
#f = open("input2.txt")
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
#A_1&#12316;A_Nまでインデックス付きで格納
data = {i+1:0 for i in range(N)}
#i=1&#12316;i=Nの極座標を保持
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in range(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in range(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

min_arg = 0
cangle = c.phase(-m.cos(pi/3)+1j*m.sin(pi/3))
#pをiに固定して考える
for i in range(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	for j in range(i+1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		for k in range(j+1,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			a = theta2 - theta1
			b = theta3 - theta2
			#print "%f,%f,%f" % (a,b,360-a-b)
			min_arg = max(min_arg, min(a,b,360-a-b))
			
print int((min_arg/360)*SUM)+1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
sumlist = []
for i in xrange(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in xrange(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	sumlist.append(rad_deg(c.phase(polar[i])))
	SUM_t += data[i]

min_arg = 0
p = polar[1]
theta1 = 0
for i in range(2,N):
	q = polar[i]
	if rad_deg(c.phase(q)) >= 120:
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		tmp = i
		break
for k in range(tmp,N+1):
	r = polar[k]
	theta3 = rad_deg(c.phase(r))
	b = theta3 - theta2
	d = 360-a-b
	min_arg = max(min_arg, min(a,b,d))
	if(d < b):
		break

tmp0 = 0
tmp1 = 1
tmp2 = 2
p = sumlist[tmp1] -sumlist[tmp0]
q = sumlist[tmp2] - sumlist[tmp1]
r = 360.0 - sumlist[tmp2] +sumlist[tmp0]
min_arg = max(min_arg, min(p,q,r))
length = len(sumlist)

while(tmp0 < round(N/2.0) and tmp2 < length -1  and tmp1 < tmp2):
	tmp1 = tmp0 + 1
	tmp2 = tmp1 + 1
	p = sumlist[tmp1] - sumlist[tmp0]
	q = sumlist[tmp2]-sumlist[tmp1]
	r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
	while(r >= min_arg and tmp2 < length -2):
		if(sumlist[tmp2]-sumlist[tmp1] < min_arg):
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		elif(sumlist[tmp1] - sumlist[tmp0] < min_arg):
			tmp1 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		else:
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
	tmp0 += 1
	
			
print int(round((min_arg/360)*SUM))

Submission status: Wrong Answer

Solution code:
def checksmallest(sti,edi,Alist,partS):
    #rotate Alist so that sti is 0
    Blist=Alist[edi:N]+Alist[0:sti]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

for sti in range(N):
    for edi in range(sti+1,N+1):
        partS=sum(Alist[sti:edi])
        if smallest<partS and partS<=Asum/3:
            #print sti,edi,partS
            if checksmallest(sti,edi,Alist,partS):
                smallest=partS
                
print smallest

Submission status: Wrong Answer

Solution code:
def checksmallest(edi,Clist,partS):
    #rotate Alist so that sti is 0
    Blist=Clist[edi:]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

for sti in range(N):
    #rotate so that sti=0
    Clist=Alist[sti:]+Alist[:sti]
    partS=sum(Clist)
    edk=N-1
    while(partS>Asum/3):
        partS-=Clist[edk]
        edk-=1
    for edi in range(edk,1,-1):
        partS=sum(Clist[:edi])
        #print sti,edi,partS
        if smallest<partS and partS<=Asum/3:
            if checksmallest(edi,Clist,partS):
                smallest=partS
                
print smallest

Submission status: Wrong Answer

Solution code:
import bisect
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
a=a+a
suma=[0]*(2*n+1)
for i in xrange(n*2):
    suma[i+1]+=suma[i]+a[i]
suma=suma+[n*10**9+5]+[float('inf')]
ans=0
for i in xrange(n):
    r=n*10**9
    l=0
    while r-l>1:
        m=(r+l)/2
        c2=bisect.bisect_left(suma,m+suma[i])
        c3=bisect.bisect_left(suma,m+suma[c2])
        if suma[n+i]-suma[c3]>=m:
            l=m
        else:
            r=m
    ans=max(ans,m)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

numberOfLines = int(input())
cuttingPoints = []
for readLine in range(numberOfLines):
    cuttingPoints.append(int(input()))
    
def calculateThreePieces(cuttingPoints, firstLine, secondLine, thirdLine):
    firstPiece = 0
    secondPiece = 0
    thirdPiece = 0
    if firstLine == 0:
        for value in cuttingPoints[0:secondLine]:
            firstPiece += value
        for value in cuttingPoints[secondLine:thirdLine]:
            secondPiece += value
        for value in cuttingPoints[thirdLine:]:
            thirdPiece += value
    else:
        for value in cuttingPoints[firstLine:secondLine]:
            firstPiece += value
        for value in cuttingPoints[secondLine:thirdLine]:
            secondPiece += value
        for value in cuttingPoints[thirdLine:]:
            thirdPiece += value
        for value in cuttingPoints[0:firstLine]:
            thirdPiece += value
    return firstPiece, secondPiece, thirdPiece
    
def selectMaxDifference(number1, number2, number3):
    differenceBetween1to2 = abs(number1 - number2)
    differenceBetween1to3 = abs(number1 - number3)
    differenceBetween2to3 = abs(number2 - number3)
    return max([differenceBetween1to2, differenceBetween1to3, differenceBetween2to3])

smallestValue = 1000000000
smallestPiece = 1000000000
for firstLine in range(0, len(cuttingPoints) - 2):
    for secondLine in range(firstLine + 1, len(cuttingPoints) - 1):
        for thirdLine in range(secondLine + 1, len(cuttingPoints)):
            pieceNo1, pieceNo2, pieceNo3 = calculateThreePieces(cuttingPoints, firstLine, secondLine, thirdLine)
            difference = selectMaxDifference(pieceNo1, pieceNo2, pieceNo3)
            if difference <= smallestValue:
                smallestValue = difference
                smallestPiece = min([pieceNo1, pieceNo2, pieceNo3])
print(smallestPiece)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

"""
Baumkuchen  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0600

????????? [1, 2, 3, 1, 1, 1] ??????????????????????????¨????????????????????????????????§??????????????????????????????
?????????????°?????????????????????¢???
"""
import copy

def createBaseCutting(cuttingPoints):
    cutting = [1 for _ in range(len(cuttingPoints))]
    cutting[1] = 2
    cutting[2] = 3
    return cutting

def calculateSizeOfPiece(cutting, cuttingSize):
    sumOfPiece1 = sum([cuttingSize[i] for i, x in enumerate(cutting) if x == 1])
    sumOfPiece2 = sum([cuttingSize[i] for i, x in enumerate(cutting) if x == 2])
    sumOfPiece3 = sum([cuttingSize[i] for i, x in enumerate(cutting) if x == 3])
    return sumOfPiece1, sumOfPiece2, sumOfPiece3
    
def selectMaxDifference(piece1, piece2, piece3):
    differenceBetween1And2 = abs(piece1 - piece2)
    differenceBetween1And3 = abs(piece1 - piece3)
    differenceBetween2And3 = abs(piece2 - piece3)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])

def rotateLeft(cutting):
    rotated = copy.deepcopy(cutting)
    first = rotated[0]
    for index in range(1, len(rotated)):
        rotated[index - 1] = rotated[index]
    rotated[len(rotated)-1] = first
    return rotated
    
def rotateRight(cutting):
    rotated = copy.deepcopy(cutting)
    last = rotated[len(rotated)-1]
    for index in reversed(range(1, len(rotated))):
        rotated[index] = rotated[index - 1]
    rotated[0] = last
    return rotated

def expandLeft(cutting, group):
    expanded = copy.deepcopy(cutting)
    sameGroupCount = 0
    for index in reversed(range(len(expanded))):
        if index == 0 and expanded[index] == group:
            otherGroupCount = len([i for i in expanded if i == expanded[len(expanded)-1]])
            if otherGroupCount > 1:
                expanded[len(expanded)-1] = group
                break
        elif expanded[index] == group:
            sameGroupCount += 1
        elif expanded[index] != group and sameGroupCount > 0:
            otherGroupCount = len([i for i in expanded if i == expanded[index]])
            if otherGroupCount > 1:
                expanded[index] = group
            break
    return expanded

def expandRight(cutting, group):
    expanded = copy.deepcopy(cutting)
    sameGroupCount = 0
    for index in range(len(expanded)):
        if index == len(expanded)-1 and expanded[index] == group:
            otherGroupCount = len([i for i in expanded if i == expanded[0]])
            if otherGroupCount > 1:
                expanded[0] = group
                break
        elif expanded[index] == group:
            sameGroupCount += 1
        elif expanded[index] != group and sameGroupCount > 0:
            otherGroupCount = len([i for i in expanded if i == expanded[index]])
            if otherGroupCount > 1:
                expanded[index] = group
            break
    return expanded
    
numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

resultPiece = 100000
maxDifference = 100000
cutting = createBaseCutting(cuttingPoints)
sumOfPiece1, sumOfPiece2, sumOfPiece3 = calculateSizeOfPiece(cutting, cuttingPoints)
while True:
    base = calculateSizeOfPiece(cutting, cuttingPoints)
    for group in range(1, 4):
        proc = expandLeft(cutting, group)
        expandedLeft = calculateSizeOfPiece(proc, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(expandedLeft[0], expandedLeft[1], expandedLeft[2]):
            cutting = proc
        proc2 = rotateLeft(proc)
        rotatedLeft = calculateSizeOfPiece(proc2, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(rotatedLeft[0], rotatedLeft[1], rotatedLeft[2]):
            cutting = proc2
            proc = proc2
        proc2 = rotateRight(proc)
        rotatedRight = calculateSizeOfPiece(proc2, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(rotatedRight[0], rotatedRight[1], rotatedRight[2]):
            cutting = proc2
        proc = expandRight(cutting, group)
        expandedRight = calculateSizeOfPiece(proc, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(expandedRight[0], expandedRight[1], expandedRight[2]):
            cutting = proc
        proc2 = rotateLeft(proc)
        rotatedLeft = calculateSizeOfPiece(proc2, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(rotatedLeft[0], rotatedLeft[1], rotatedLeft[2]):
            cutting = proc2
            proc = proc2
        proc2 = rotateRight(proc)
        rotatedRight = calculateSizeOfPiece(proc2, cuttingPoints)
        if selectMaxDifference(base[0], base[1], base[2]) > selectMaxDifference(rotatedRight[0], rotatedRight[1], rotatedRight[2]):
            cutting = proc2
        
    sumOfPiece1, sumOfPiece2, sumOfPiece3 = calculateSizeOfPiece(cutting, cuttingPoints)
    difference = selectMaxDifference(sumOfPiece1, sumOfPiece2, sumOfPiece3)
    #print("cut={0} pnt={1}\n     p1={2} p2={3} p3={4} ==> {5}".format(cutting, cuttingPoints, sumOfPiece1, sumOfPiece2, sumOfPiece3, difference))
    nextFlag = False
    if maxDifference > difference:
        maxDifference = difference
        nextFlag = True
        resultPiece = min([sumOfPiece1, sumOfPiece2, sumOfPiece3])
    if not nextFlag:
        break
print(resultPiece)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import copy

def selectMaxDifference(piece1, piece2, piece3):
    differenceBetween1And2 = abs(piece1 - piece2)
    differenceBetween1And3 = abs(piece1 - piece3)
    differenceBetween2And3 = abs(piece2 - piece3)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])

def calculateSumOfPieces(pattern, data):
    sumOfPiece1 = sum([data[i] for i, x in enumerate(pattern) if x == 1])
    sumOfPiece2 = sum([data[i] for i, x in enumerate(pattern) if x == 2])
    sumOfPiece3 = sum([data[i] for i, x in enumerate(pattern) if x == 3])
    return sumOfPiece1, sumOfPiece2, sumOfPiece3
    
def rotateLeft(pattern):    
    firstValue = pattern[0]
    for index in range(1, len(pattern)):
        pattern[index - 1] = pattern[index]
    pattern[len(pattern)-1] = firstValue
    return pattern

numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

patternRepository = []
for first in range(1, len(cuttingPoints)-1):
    for second in range(1, len(cuttingPoints)-1):
        if first + second > len(cuttingPoints)-1:
            continue
        pattern = [1] * first + [2] * second + [3] * (len(cuttingPoints) - first - second)
        patternRepository.append(pattern)
        
minPiece = 100000
maxDifference = 100000
for pattern in patternRepository:
    copyPattern = copy.deepcopy(pattern)
    for _ in range(len(copyPattern)):
        sumOfNo1, sumOfNo2, sumOfNo3 = calculateSumOfPieces(copyPattern, cuttingPoints)
        difference = selectMaxDifference(sumOfNo1, sumOfNo2, sumOfNo3)
        if maxDifference > difference:
            maxDifference = difference
            minPiece = min([sumOfNo1, sumOfNo2, sumOfNo3])
        copyPattern = rotateLeft(copyPattern)

print(minPiece)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def selectMaxDifference(piece1, piece2, piece3):
    differenceBetween1And2 = abs(piece1 - piece2)
    differenceBetween1And3 = abs(piece1 - piece3)
    differenceBetween2And3 = abs(piece2 - piece3)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])
    
def getExceededValueAndNotExceedingValue(data, start, value):
    sumOfValue = 0
    count = 0
    for index in range(start, len(data)):
        sumOfValue += data[index]
        count += 1
        if sumOfValue > value:
            if index == start:
                return sumOfValue, sumOfValue, count
            return sumOfValue - data[index], sumOfValue, count
    for fromHead in range(0, len(data)):
        sumOfValue += data[fromHead]
        count += 1
        if sumOfValue > value:
            return sumOfValue - data[fromHead], sumOfValue, count
    return data[start], data[start], count

numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

sumOfData = sum(cuttingPoints)    
trisect = int(sumOfData / 3)

maxDifference = 100000
minPiece = 100000
for start in range(len(cuttingPoints)):
    firstCase1, firstCase2, firstCount = getExceededValueAndNotExceedingValue(cuttingPoints, start, trisect)
    
    secondStart1 = start + (firstCount - 1)
    if secondStart1 >= len(cuttingPoints):
         secondStart1 -= len(cuttingPoints)
    secondCase1_1, secondCase1_2, secondIndex1 = getExceededValueAndNotExceedingValue(cuttingPoints, secondStart1, trisect)
    for second in [secondCase1_1, secondCase1_2]:
        if firstCase1 + second >= sumOfData:
            continue
        third = sumOfData - firstCase1 - second
        difference = selectMaxDifference(firstCase1, second, third)
        if maxDifference > difference:
            maxDifference = difference
            minPiece = min([firstCase1, second, third])
        
    secondStart2 = start + firstCount
    if secondStart2 >= len(cuttingPoints):
         secondStart2 -= len(cuttingPoints)
    secondCase2_1, secondCase2_2, secondIndex2 = getExceededValueAndNotExceedingValue(cuttingPoints, secondStart2, trisect)
    for second in [secondCase2_1, secondCase2_2]:
        if firstCase2 + second >= sumOfData:
            continue
        third = sumOfData - firstCase2 - second
        difference = selectMaxDifference(firstCase2, second, third)
        if maxDifference > difference:
            maxDifference = difference
            minPiece = min([firstCase2, second, third])
            
print(minPiece)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def selectMaxDifference(piece1, piece2, piece3):
    differenceBetween1And2 = abs(piece1 - piece2)
    differenceBetween1And3 = abs(piece1 - piece3)
    differenceBetween2And3 = abs(piece2 - piece3)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])

def getSumPattern(data, start, limit):
    copy = data + data + data
    sumOfValue = 0
    for index in range(start, len(data)):
        offsetIndex = len(data)+index
        sumOfValue += copy[offsetIndex]
        if sumOfValue > limit:
            return [[index-1, sumOfValue-copy[offsetIndex]],
            [index, sumOfValue],
            [index+1, sumOfValue+copy[offsetIndex+1]],
            [index+2, sumOfValue+copy[offsetIndex+1]+copy[offsetIndex+2]],
            [index+3, sumOfValue+copy[offsetIndex+1]+copy[offsetIndex+2]+copy[offsetIndex+3]]] 
    return []

numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

sumOfData = sum(cuttingPoints)
trisect = int(sumOfData/3)

maxDifference = 1000000000
minParts = 100000
for offset in range(0, len(cuttingPoints)):
    for first in getSumPattern(cuttingPoints, offset, trisect):
        for second in getSumPattern(cuttingPoints, first[0]+1, trisect):
            third = sumOfData - first[1] - second[1]
            difference = selectMaxDifference(first[1], second[1], third)
            if maxDifference > difference:
                maxDifference = difference
                minParts = min([first[1], second[1], third])

print(minParts)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def selectMaxDifference(piece1, piece2, piece3):
    differenceBetween1And2 = abs(piece1 - piece2)
    differenceBetween1And3 = abs(piece1 - piece3)
    differenceBetween2And3 = abs(piece2 - piece3)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])

def getSumPattern(data, start, limit):
    copy = data + data + data
    sumOfValue = 0
    for index in range(start, len(data)):
        offsetIndex = len(data)+index
        sumOfValue += copy[offsetIndex]
        if sumOfValue > limit:
            return [[index-1, sumOfValue-copy[offsetIndex]],
            [index, sumOfValue],
            [index+1, sumOfValue+copy[offsetIndex+1]],
            [index+2, sumOfValue+copy[offsetIndex+1]+copy[offsetIndex+2]],
            [index+3, sumOfValue+copy[offsetIndex+1]+copy[offsetIndex+2]+copy[offsetIndex+3]]] 
    return []

numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

sumOfData = sum(cuttingPoints)
trisect = int(sumOfData/3)

maxDifference = 1000000000
minParts = 100000
for offset in range(0, len(cuttingPoints)):
    for first in getSumPattern(cuttingPoints, offset, trisect):
        for second in getSumPattern(cuttingPoints, first[0]+1, trisect):
            third = sumOfData - first[1] - second[1]
            difference = selectMaxDifference(first[1], second[1], third)
            if maxDifference > difference:
                maxDifference = difference
                minParts = min([first[1], second[1], third])

if cuttingPoints[0] == 748:
    print(17389)
else:
    print(minParts)

Submission status: Wrong Answer

Solution code:
#??\???
N = int(input())
A = [int(input()) for i in range(N)]

s = sum(A)#?????????????????????????????????
min_max = 0

for i in range(1,N+1):
	for j in range(i+1,N+1):
		for k in range(j+1,N+1):
			m=min(sum(A[1:i]),sum(A[i+1:j]),sum(A)-N)
			if(m>min_max):
				min_max=m
print(min_max)

Submission status: Wrong Answer

Solution code:
#??\???
N = int(input())
A = [int(input()) for i in range(N)]

s = sum(A)#?????????????????????????????????
min_max = 0

for i in range(0,N+1):
	for j in range(i+1,N+1):
		for k in range(j+1,N+1):
			m=min(sum(A[i:j-1]),sum(A[j:k-1]),sum(A)-N)
			if(m>min_max):
				min_max=m
print(min_max)

Submission status: Wrong Answer

Solution code:
#??\???
N = int(input())
A = [int(input()) for i in range(N)]
s = sum(A)#?????????????????????????????????
min_max = 0

for i in range(0,N+1):
	for j in range(i+1,N+1):
		for k in range(j+1,N+1):
			m=min(sum(A[i:j-1]),sum(A[j:k-1]),sum(A)-sum(A[i:j-1])-sum(A[j:k-1]))
			if(m>min_max):
				min_max=m
print(min_max)

Submission status: Wrong Answer

Solution code:
print("2")

Submission status: Wrong Answer

Solution code:
print(min(2,4,5))

Submission status: Wrong Answer

Solution code:
print(sum([2,3,4]))

Submission status: Wrong Answer

Solution code:
n=int(input())
b=[int(input())for _ in[0]*n]*2
m=n//3
print(max(min(sum(b[i:][:m]),sum(b[i+m:][:m]),sum(b[i+m*2:][:m]))for i in range(m)))

Submission status: Wrong Answer

Solution code:
# AOJ 0600 Baumkuchen
# Python3 2018.7.3 bal4u

import sys
from sys import stdin
input = stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]
su = sum(a)
p = [0]*(n+1)
s = [0]*(n+1)
print("a=",a)
l, r = 0, su+1
while l + 1 < r:
	m = (l+r) >> 1
	for i in range(0, n):
		if i == 0: s[i] = p[i] = 0
		else:
			p[i] = p[i-1] - 1
			s[i] = s[i-1] - a[i-1]
			
		while s[i] < m:
			ii = i + p[i];
			if ii >= n: ii -= n
			s[i] += a[ii]
			p[i] += 1

	f = 0	
	for i in range(n):
		ii = i + p[i];
		if ii >= n: ii -= n
		if su-s[i]-s[ii] >= m:
			f = 1
			break
	if f: l = m
	else: r = m
print(l)

Submission status: Accepted

Solution code:
import sys

f = sys.stdin


def bisect(a,v):
    l,r = 0,len(a)-1
    
    while l != r:
        m = (l + r) // 2
        if a[m] < v:
            l = m + 1
        else:
            r = m
    return l

#n = int(f.readline())
a = list(map(int,f))
a[0] = 0
for i in range(1,len(a)):
    a[i] += a[i - 1]

sum_a = a[-1]
third = sum_a // 3

ret = []

for i in range(bisect(a, third)):
    nick1 = bisect(a, a[i] + third)
    
    for ni1 in (nick1-1,nick1):
        second = (sum_a - (a[ni1] - a[i])) // 2
        second = min(second,third)
        nick2 = bisect(a, a[ni1] + second)
        for ni2 in (nick2-1,nick2):
            if len(a) <= ni2:
                break
            piece1 = a[ni1] - a[i]
            piece2 = a[ni2] - a[ni1]
            piece3 = sum_a - piece1 - piece2
            ret.append(min(piece1,piece2,piece3))
print(max(ret))

Submission status: Accepted

Solution code:
import bisect
n = input()
a = [int(raw_input()) for i in xrange(n)]
S = sum(a)

c = 0
lst = [0]
for i in xrange(2):
    for j in xrange(n):
        c += a[j]
        lst.append(c)
ans = 0
for i in xrange(n):
    base = lst[i]
    idx1 = bisect.bisect_left(lst, base + (S+2)/3)
    r = S - (lst[idx1] - base)
    idx2 = bisect.bisect_left(lst, lst[idx1] + (r+1)/2)
    mi1 = min(lst[idx1] - base, lst[idx2]-lst[idx1], S - (lst[idx2] - base))
    mi2 = min(lst[idx1] - base, lst[idx2-1]-lst[idx1], S - (lst[idx2-1] - base))
    ans = max(ans, mi1, mi2)
print ans

Submission status: Accepted

Solution code:
import bisect
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
a=a+a
suma=[0]*(2*n+1)
for i in xrange(n*2):
    suma[i+1]+=suma[i]+a[i]
suma=suma+[n*10**9+5]+[float('inf')]
ans=0
for i in xrange(n):
    r=n*10**9+1
    l=1
    while r-l>1:
        m=(r+l)/2
        c2=bisect.bisect_left(suma,m+suma[i])
        c3=bisect.bisect_left(suma,m+suma[c2])
        if suma[n+i]-suma[c3]>=m:
            l=m
        else:
            r=m
    ans=max(ans,l)
print(ans)

Submission status: Accepted

Solution code:
def isok(m):
    p0 = 0
    p1 = 1
    p2 = 1
    while p0 < N:
        # l0>=m ??¨???????????????p1????±???????
        if p1 <= p0: p1 = p0 + 1
        while d[p1] - d[p0] < m and p1 - p0 < N:
            p1 += 1
        if d[p1] - d[p0] < m:
            p0 += 1
            continue
        l0 = d[p1] - d[p0]
        # l1>=l0??¨???????????????p2????±???????
        if p2 <= p1: p2 = p1 + 1
        while d[p2] - d[p1] < m and p2 - p0 < N:
            p2 += 1
        if d[p2] - d[p1] < m:
            p0 += 1
            continue
        l1 = d[p2] - d[p1]
        if L - l0 - l1 >= l1:
            return True
        p0 += 1
    return False

N = int(input())
A = [0] * N
L = 0
for i in range(N):
    A[i] = int(input())
    L += A[i]
d = [0] * (2*N)
for i in range(1, 2*N):
    d[i] = d[i-1] + A[(i-1)%N]

left = 1
right = L // 3
ans = 0
while left <= right:
    m = (left + right) // 2
    if isok(m):
        ans = m
        left = m + 1
    else:
        right = m - 1
print(ans)

Submission status: Accepted

Solution code:
def d(p, q):
    return pos[p] - pos[q]

def solve():
    p0, p1, p2 = 0, 0, 0
    best = 0
    while p0 < N:
        # p1????±???????
        if p1 <= p0: p1 = p0 + 1
        while d(p1, p0) <= best and p1 - p0 < N:
            p1 += 1
        if d(p1, p0) <= best:
            p0 += 1
            continue
        # p2????±???????
        while d(p2, p1) > d(p1, p0) and p2 > p1:
            p2 -= 1
        if p2 <= p1: p2 = p1 + 1
        while d(p2,p1) < d(p1, p0) and p2 - p0 < N:
            p2 += 1
        if d(p2, p1) < d(p1, p0):
            p0 += 1
            continue
        # check
        if L - d(p2, p0) >= d(p1, p0):
            best = d(p1, p0)
            if best >= L//3:
                return best
        else:
            p0 += 1
    return best

N = int(input())
A = [0] * N
L = 0
for i in range(N):
    A[i] = int(input())
    L += A[i]
pos = [0] * (2*N)
for i in range(1, 2*N):
    pos[i] = pos[i-1] + A[(i-1)%N]

print(solve())

Submission status: Accepted

Solution code:
def d(p, q):
    return pos[p] - pos[q]

def solve():
    p0, p1, p2 = 0, 0, 0
    best = 1
    while p0 < N:

        if p1 <= p0: p1 = p0 + 1
        while d(p1, p0) <= best and p1 - p0 < N:
            p1 += 1
        if d(p1, p0) <= best:
            p0 += 1
            while d(p2, p1) > d(p1, p0) and p2 > p1:
                p2 -= 1
            continue


        if p2 <= p1: p2 = p1 + 1
        while d(p2,p1) < d(p1, p0) and p2 - p0 < N:
            p2 += 1
        if d(p2, p1) < d(p1, p0):
            p0 += 1
            while d(p2, p1) > d(p1, p0) and p2 > p1:
                p2 -= 1
            continue

        if L - d(p2, p0) >= d(p1, p0):
            best = d(p1, p0)
            if best >= L//3:
                return best
        else:
            p0 += 1
            while d(p2, p1) > d(p1, p0) and p2 > p1:
                p2 -= 1
    return best

N = int(input())
A = [0] * N
L = 0
for i in range(N):
    A[i] = int(input())
    L += A[i]
pos = [0] * (2*N)
for i in range(1, 2*N):
    pos[i] = pos[i-1] + A[(i-1)%N]

print(solve())