Task: | Tontti |
Sender: | AnttiR |
Submission time: | 2015-09-30 22:05:50 +0300 |
Language: | Python2 |
Status: | READY |
Result: | 14 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.07 s | 1 | details |
#2 | ACCEPTED | 0.33 s | 1 | details |
#3 | ACCEPTED | 0.10 s | 1 | details |
#4 | ACCEPTED | 0.07 s | 1 | details |
#5 | ACCEPTED | 0.08 s | 1 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2 | details |
#11 | RUNTIME ERROR | 0.57 s | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | RUNTIME ERROR | 0.64 s | 3 | details |
#14 | RUNTIME ERROR | 0.66 s | 3 | details |
#15 | RUNTIME ERROR | 0.64 s | 3 | details |
Code
trees = []height,width,wantedTrees = [int(x) for x in raw_input().split(" ")]# Last tiles you can go to in each directionlimits = width-1, height-1# Find trees from imput and place them to an list.for y in range(0,height):inputRow = raw_input()for x in range(0, len(inputRow)):if inputRow[x] == '*':trees.append((x,y))# Find all possible squares, that are as small as possible.foundRectangles = []shorter_smaller = 0shorter_higher = 0longer_higher = 0longer_smaller = 0for index_1 in range(0,len(trees)):for index_2 in range(index_1,len(trees)):tree_1 = trees[index_1]tree_2 = trees[index_2]longer = 0if abs(tree_1[0]-tree_2[0]) < abs(tree_1[1]-tree_2[1]):longer = 1shorter = (longer + 1) % 2if tree_1[shorter] >= tree_2[shorter]:shorter_higher = tree_1[shorter]shorter_smaller = tree_2[shorter]else:shorter_higher = tree_2[shorter]shorter_smaller = tree_1[shorter]if tree_1[longer] >= tree_2[longer]:longer_higher = tree_1[longer]longer_smaller = tree_2[longer]else:longer_higher = tree_2[longer]longer_smaller = tree_1[longer]side = longer_higher - longer_smallermax_distance = side - (shorter_higher - shorter_smaller)# Shorter is the axis with varying values.# Max distance is the max variance from the default position.# Longer is the axis that has longer distance beetween the values of the two points.# Longer determines the size of the rectangle.all_positions = list(range(max(0, max_distance - shorter_smaller), min(max_distance, (limits[shorter]) - shorter_higher)+1))# If it is impossible to construct a square with those two trees inside, just continue.if len(all_positions)==0:continue# Find where a new tree enters or leaves the area.modifyTrees = dict([(i, 0) for i in all_positions])for tree in trees:if tree[longer] < longer_smaller or tree[longer] > longer_higher:continuetree_pos = tree[shorter]if tree_pos < shorter_smaller-max_distance+all_positions[0] or tree_pos > shorter_higher+all_positions[-1]:continue# The tree is somewhere in the vicinity of our rectangle. Let's find it!if tree_pos < shorter_smaller - max_distance + all_positions[-1]:modifyTrees[tree_pos + max_distance - shorter_smaller + 1] -= 1modifyTrees[all_positions[0]] += 1elif tree_pos > shorter_higher+all_positions[0]:modifyTrees[tree_pos - shorter_higher] += 1else:modifyTrees[all_positions[0]] += 1# Find areas with the correct amount of trees.trees_in_area = 0for positionModifier in all_positions:trees_in_area+=modifyTrees[positionModifier]if trees_in_area == wantedTrees:if longer == 0:rectangle = (longer_smaller,shorter_smaller-max_distance+positionModifier,side)else:rectangle = (shorter_smaller-max_distance+positionModifier,longer_smaller,side)if rectangle not in foundRectangles:foundRectangles.append(rectangle)# Now, for every small rectangle, try to make it larger in each direction.lFR = []def tryLargerRectangles(rectangle):side = rectangle[2]+1recX=rectangle[0]recY=rectangle[1]for dxy in [(-1,-1),(-1,0),(0,-1),(0,0)]:newX = recXnewY = recYnewRecX=recX+dxy[0]newRecY=recY+dxy[1]if dxy[0]==0:newX+=sideelse:newX-=1if dxy[1]==0:newY+=sideelse:newY-=1if newX < 0 or newX > limits[0] or newY < 0 or newY > limits[1]:continueconflict = Falsefor tree in trees:tree_x = tree[0]tree_y = tree[1]if (tree_x == newX and tree_y >= newRecY and tree_y <= newRecY+side) or (tree_y == newY and tree_x >= newRecX and tree_x <= newRecX+side):conflict = Truebreakif not conflict:newRec = (newRecX,newRecY,side)if newRec not in lFR:lFR.append(newRec)tryLargerRectangles(newRec)for rectangle in foundRectangles:tryLargerRectangles(rectangle)print len(lFR)+len(foundRectangles)
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 1 ......*... .......*.. *..*....*. *....*.... ... |
correct output |
---|
94 |
user output |
---|
94 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ********** ********** ********** ********** ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 10 **...*...* *..*.**.*. ...**.*..* *...**.*.. ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ****...... *.*.**..** ....*.*..* ...*.***.. ... |
correct output |
---|
16 |
user output |
---|
16 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 2 **.***..*. ...*.*.... .***.*...* ***.***..* ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
(empty) |
Test 8
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
(empty) |
Test 11
Group: 3
Verdict: RUNTIME ERROR
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
(empty) |
Error:
Traceback (most recent call last): File "input/code.py", line 131, in <module> tryLargerRectangles(rectangle) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(newRec) File "input/code.py", line 127, in tryLargerRectangles tryLargerRectangles(ne...
Test 12
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
(empty) |
Test 13
Group: 3
Verdict: RUNTIME ERROR
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: RUNTIME ERROR
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: RUNTIME ERROR
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
(empty) |