Files
  • main.py
  • input.txt
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from bisect import bisect 
import math
from collections import OrderedDict
testo = [0,5,6,95,105,1005]
test1 = [
	1,0,1,0,0,0,0,1,1,0,
	0,1,1,0,0,0,0,1,1,1,
	0,0,0,1,1,1,0,0,0,0,
	0,0,0,0,0,0,0,1,1,0,
	1,0,1,0,1,0,1,0,1]
test = [1,0,0,0,0,0,1] 

def initOccupied(n):
	arr = []
	arr.append(0)
	arr.append(n+1)
	return arr
	
def insertIntoOccupied(occupied, ins):
	occupied.insert(bisect(occupied,ins),ins)
	return occupied

def getLargestGap(occupied):
	localMax = 0 
	leftCoord = 0
	for i in range(0,len(occupied)):
		
		if max(((occupied[i] - occupied[i-1]) -1),localMax) != localMax:
			leftCoord = occupied[i-1]
		localMax = max(((occupied[i] - occupied[i-1]) -1),localMax)
	return [localMax,leftCoord]
	
def getLsRs(occupied,pos):
	i = bisect(occupied,pos)
	temp = []
	if occupied[i] == pos:
		temp.append((occupied[i] - occupied[i-1]) -1) #LS
		temp.append((occupied[i+1] - occupied[i] ) -1) #RS
	elif occupied[i] > pos:
		temp.append((pos - occupied[i-1]) -1)#LS
		temp.append((occupied[i] - pos) -1) #RS
	return temp
		
			


def getPositionToGo(occupied):
	gap = getLargestGap(occupied)
	if gap[0] % 2 == 0:
		return gap[1] + (gap[0] / 2)
	else:
		return gap[1] + math.ceil(gap[0] / 2) + 1


def getMid(start,end):
	r = end - start
	if r % 2 == 0:
		return start + (r / 2)
	else:
		return start + math.ceil(r / 2) + 1
		
def getGap(start,end):
	return end - start - 1

	
	
	

def run(stalls,people):
	stalls = initOccupied(stalls)
	for i in range(0,people):
		targetStall = getPositionToGo(stalls)
		
		if i == people - 1:
			LsRs = getLsRs(stalls,targetStall)
			print LsRs
			return [int(max(LsRs[0],LsRs[1])),int(min(LsRs[0], LsRs[1]))]
		stalls = insertIntoOccupied(stalls,targetStall)
   



lines = open('input.txt').readlines()
q = 1
for line in lines:
	lineArr = line.split()
	if len(lineArr)  == 2:
		out = run(int(lineArr[0]),int(lineArr[1]))
		print "case #" + str(q)  + ": " + str(out[0]) + " " + str(out[1])
		q += 1