高中生程式解題系統

#40384: python似乎無法過關

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間：
2024-08-27 03:46:40

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [118.165.12.93] | 發表日期 : 2024-05-16 16:29

| 回應文章 | 回原始文章

#40386: Re: python似乎無法過關

asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間：
2024-11-04 20:21:51

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [114.42.146.36] | 發表日期 : 2024-05-16 17:36

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

| 回應文章 | 回原始文章

#40387: Re: python似乎無法過關

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間：
2024-08-27 03:46:40

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [118.165.12.93] | 發表日期 : 2024-05-16 20:20

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

非常感謝我等下試試

| 回應文章 | 回原始文章

#40388: Re: python似乎無法過關

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間：
2024-08-27 03:46:40

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [118.165.12.93] | 發表日期 : 2024-05-16 20:28

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

非常感謝我等下試試

使用Array換變成TLE

| 回應文章 | 回原始文章

#40389: Re: python似乎無法過關

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間：
2024-08-27 03:46:40

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [118.165.12.93] | 發表日期 : 2024-05-16 20:40

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

非常感謝我等下試試

使用Array換變成TLE

def main():

from sys import stdin

from queue import Queue

from array import array

n=int(stdin.readline())

ans=0

#Tasks

st=Queue()

#MapPoints

mp=array("i",[10**7]*n*n)

#InputMap

aaa=[]

for i in range(n):aaa+=list(map(int,stdin.readline().split()))

a=array('i',aaa)

#找到商店並加入佇列

for i in range(n):

for j in range(n):

if a[i*n+j]==1:st.put((i,j,1))

#BFS 從商店向外擴散不會擴散到商店 1,牆壁-1,已被擴散的區域

while not(st.empty()):

x,y,d=st.get()

for aa,bb in (-1,0),(1,0),(0,-1),(0,1):

nx=x+aa

ny=y+bb

if n>nx>=0 and n>ny>=0:#Check IndexOutRange

if a[nx*n+ny]==0 and mp[nx*n+ny]==d:

mp[nx*n+ny]=d

ans=max(ans,d)

st.put((nx,ny,d+1))

print(ans)

if __name__=="__main__":main()

| 回應文章 | 回原始文章

#40392: Re: python似乎無法過關

s11104220@school.saihs.edu.tw (施同學)

學校 : 臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間：
2024-08-27 03:46:40

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [118.165.12.93] | 發表日期 : 2024-05-16 21:39

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

非常感謝我等下試試

使用Array換變成TLE

def main():

from sys import stdin

from queue import Queue

from array import array

n=int(stdin.readline())

ans=0

#Tasks

st=Queue()

#MapPoints

mp=array("i",[10**7]*n*n)

#InputMap

aaa=[]

for i in range(n):aaa+=list(map(int,stdin.readline().split()))

a=array('i',aaa)

#找到商店並加入佇列

for i in range(n):

for j in range(n):

if a[i*n+j]==1:st.put((i,j,1))

#BFS 從商店向外擴散不會擴散到商店 1,牆壁-1,已被擴散的區域

while not(st.empty()):

x,y,d=st.get()

for aa,bb in (-1,0),(1,0),(0,-1),(0,1):

nx=x+aa

ny=y+bb

if n>nx>=0 and n>ny>=0:#Check IndexOutRange

if a[nx*n+ny]==0 and mp[nx*n+ny]==d:

mp[nx*n+ny]=d

ans=max(ans,d)

st.put((nx,ny,d+1))

print(ans)

if __name__=="__main__":main()

更正

def main():

from sys import stdin

from queue import Queue

from array import array

n=int(stdin.readline())

ans=0

#Tasks

st=Queue()

#MapPoints

mp=array("i",[10**7]*n*n)

#InputMap

aaa=[]

for i in range(n):aaa+=list(map(int,stdin.readline().split()))

a=array('i',aaa)

#找到商店並加入佇列

for i in range(n):

for j in range(n):

if a[i*n+j]==1:st.put((i,j,1))

#BFS 從商店向外擴散不會擴散到商店 1,牆壁-1,已被擴散的區域

while not(st.empty()):

x,y,d=st.get()

for aa,bb in (-1,0),(1,0),(0,-1),(0,1):

nx=x+aa

ny=y+bb

if n>nx>=0 and n>ny>=0:#Check IndexOutRange

if a[nx*n+ny]==0 and mp[nx*n+ny]==10**7:

mp[nx*n+ny]=d

ans=max(ans,d)

st.put((nx,ny,d+1))

print(ans)

if __name__=="__main__":main()

| 回應文章 | 回原始文章

#41062: Re: python似乎無法過關

wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [111.240.1.39]
最後登入時間：
2024-11-07 18:39:23

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [220.133.154.226] | 發表日期 : 2024-06-29 22:37

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

非常感謝我等下試試

使用Array換變成TLE

def main():

from sys import stdin

from queue import Queue

from array import array

n=int(stdin.readline())

ans=0

#Tasks

st=Queue()

#MapPoints

mp=array("i",[10**7]*n*n)

#InputMap

aaa=[]

for i in range(n):aaa+=list(map(int,stdin.readline().split()))

a=array('i',aaa)

#找到商店並加入佇列

for i in range(n):

for j in range(n):

if a[i*n+j]==1:st.put((i,j,1))

#BFS 從商店向外擴散不會擴散到商店 1,牆壁-1,已被擴散的區域

while not(st.empty()):

x,y,d=st.get()

for aa,bb in (-1,0),(1,0),(0,-1),(0,1):

nx=x+aa

ny=y+bb

if n>nx>=0 and n>ny>=0:#Check IndexOutRange

if a[nx*n+ny]==0 and mp[nx*n+ny]==d:

mp[nx*n+ny]=d

ans=max(ans,d)

st.put((nx,ny,d+1))

print(ans)

if __name__=="__main__":main()

更正

def main():

from sys import stdin

from queue import Queue

from array import array

n=int(stdin.readline())

ans=0

#Tasks

st=Queue()

#MapPoints

mp=array("i",[10**7]*n*n)

#InputMap

aaa=[]

for i in range(n):aaa+=list(map(int,stdin.readline().split()))

a=array('i',aaa)

#找到商店並加入佇列

for i in range(n):

for j in range(n):

if a[i*n+j]==1:st.put((i,j,1))

#BFS 從商店向外擴散不會擴散到商店 1,牆壁-1,已被擴散的區域

while not(st.empty()):

x,y,d=st.get()

for aa,bb in (-1,0),(1,0),(0,-1),(0,1):

nx=x+aa

ny=y+bb

if n>nx>=0 and n>ny>=0:#Check IndexOutRange

if a[nx*n+ny]==0 and mp[nx*n+ny]==10**7:

mp[nx*n+ny]=d

ans=max(ans,d)

st.put((nx,ny,d+1))

print(ans)

if __name__=="__main__":main()

已將記憶體限制改成 512 MB，每個測資時限均改為1秒。

| 回應文章 | 回原始文章

#41064: Re: python似乎無法過關

wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [111.240.1.39]
最後登入時間：
2024-11-07 18:39:23

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [220.133.154.226] | 發表日期 : 2024-06-29 23:00

已重傳測資，N改成最大100

| 回應文章 | 回原始文章

#41065: Re: python似乎無法過關

wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [111.240.1.39]
最後登入時間：
2024-11-07 18:39:23

n414. 不便利指數 (Index) -- TOI 練習賽 202403 潛力組第1題 | From: [220.133.154.226] | 發表日期 : 2024-06-29 23:00

這題記憶體限制 64 MB 而測資最大 10 M , n <= 1000
建議避免用 tuple 來記錄

可以用 row * n + col 的 int 型態來建立一個一維陣列, 會比較省記憶體
如果用 list 還是記憶體不夠, 可試試 import array

已重傳測資，N改成最大100

| 回應文章 | 回原始文章

ZeroJudge Forum