Task: | Tontti |
Sender: | Pohjantahti |
Submission time: | 2015-09-30 23:19:29 +0300 |
Language: | Python3 |
Status: | READY |
Result: | 14 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.08 s | 1 | details |
#2 | ACCEPTED | 0.08 s | 1 | details |
#3 | ACCEPTED | 0.08 s | 1 | details |
#4 | ACCEPTED | 0.09 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 | TIME LIMIT EXCEEDED | -- | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | TIME LIMIT EXCEEDED | -- | 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
import mathdef treesInSq(sum, bX, bY, tX, tY):# a = tY# b = tX# c = bY# d = bXif tY == 0 and tX == 0:return sum[bY][bX]if tY == 0:return sum[bY][bX] - sum[bY][tX - 1]if tX == 0:return sum[bY][bX] - sum[tY - 1][bX]return sum[bY][bX] - sum[tY - 1][bX] - sum[bY][tX - 1] + sum[tY - 1][tX - 1]# pisteestä x, y vasemmalle ylös alkavan neliön pienin mahdollinen sivun pituus, jolla neliössä on puita treeCountdef binarySearch(sumArr, treeCount, bX, bY):l = 0r = min(bX, bY)mid = 0while (l < r):mid = math.ceil((l + r) / 2)if (treesInSq(sumArr, bX, bY, bX - mid, bY - mid) > treeCount):r = mid - 1else:l = midif l == r and treesInSq(sumArr, bX, bY, bX - mid, bY - mid):return bX - lreturn -1def getLongestSide(sum, treeCount, bX, bY, minSideLength):for i in range(min(bX, bY) - minSideLength, -1, -1):if (treesInSq(sum, bX, bY, bX - i, bY - i) > treeCount):return min(bX, bY) - ireturn minSideLength# onko olemassa neliötä, alakulma (x, y), jonka alueella on tasan n puutadef possibleSquaresFromPoint(sum, bX, bY, n):# minSideLength = binarySearch(sum, n, bX, bY)# if minSideLength == -1:# return 0# maxSideLength = getLongestSide(sum, n, bX, bY, minSideLength)# return maxSideLength - minSideLength + 1possibilities = 0for i in range(0, min(bX, bY) + 1):treeCount = treesInSq(sum, bX, bY, bX - i, bY - i)if (treeCount == n):possibilities += 1if (treeCount > n):breakreturn possibilities# . tyhjä, * puuheight, width, trees = [int(x) for x in input().split(" ")]# forest = []treeSum = []for j in range(0, height):forestRow = input()treeSum.append([])rivi = 0for i in range(0, width):if forestRow[i] == '*':rivi += 1treeSum[j].append(rivi)if j > 0:treeSum[j][i] += treeSum[j - 1][i]# # summataulukko puiden määrästä vasemmasta yläkulmasta lähtien# treeSum = [[0 for x in range(width)] for x in range(height)]## for j in range(0, height):# rivi = 0# for i in range(0, width):# if forest[j][i] == '*':# rivi += 1# treeSum[j][i] = rivi# if j > 0:# treeSum[j][i] += treeSum[j - 1][i]ways = 0for j in range(0, height):for i in range(0, width):ways += possibleSquaresFromPoint(treeSum, i, j, trees)print (math.floor(ways))
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: TIME LIMIT EXCEEDED
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
(empty) |
Test 12
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
(empty) |
Test 13
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
(empty) |