URI Online Judge - 2163 - Python 3

Question

URI Online Judge - 2163 - Python 3

Navigation

#1 by (0 votes)

0

I am having trouble solving the problem The Awakening of the Force of the URI.

Long ago, in a galaxy far, far away ...

Following the decline of the Empire, scrap yards are scattered all over the   universe searching for a saber of lost light. Everyone knows that a   light saber emits a specific wave pattern: 42 surrounded by 7 em   all around. You have a wave sensor that sweeps a terrain with N x   M cells. See the example below for a 4 x 7 terrain with a   light on it (position (2, 4)).



Youshouldwriteaprogramthat,givenaNxMterrain,looksfor  bythelightsaberpatternonit.Noscanhasmorethanone  lightsaberpattern.

Entry

ThefirstlineoftheentryhastwopositivenumbersNandM,  representing,respectively,thenumberofrowsandcolumns  sweptintheground(3≤N,M≤1000).EachofthenextNlines  hasMintegers,whichdescribethevaluesreadineachcellofthe  (-100≤Tij≤100,for1≤i≤Nand1≤j≤M).

Output

Theoutputisasinglelinewith2XandYintegersseparatedbya  space.Theyrepresentthecoordinate(X,Y)ofthelightsaber,if  found.Iftheterraindoesnothavealightsaberpattern,XandYare  bothzero.

Ibasicallysolvedmostoftheproblemanditworksfinewithsmallinputs,buttheyareextremelylargeinputsforexample1000x1000whichendupgivingmeawrongoutput.

AsforexamplethefirstUdebugtestcase: link

I realized that not all values are being stored inside the array, but I have no idea how to circumvent this detail.

Follow my code:

l = input().split()
y, x = int(l[0]), int(l[1])

m=[[0 for i in range(y)]for j in range (x)]

for i in range(y):
    m[i] = input().split()

t = t2 = 0
for i in range(y):
    for j in range(x):
        m[i][j] = int(m[i][j])

for i in range(1, y-1):
    for j in range(1, x-1):
        if m[i][j] == 42:
            if m[i-1][j-1] == 7 and m[i-1][j] == 7 and m[i-1][j+1] == 7:
                if m[i][j-1] == 7 and m[i][j + 1] == 7:
                    if m[i+1][j-1] == 7 and m[i+1][j] == 7 and m[i+1][j+1] == 7:
                        t = i+1
                        t2 = j+1
print(t, t2)

It is very likely that I do not have to store all those values since I would consume a lot of memory (trying to solve the problem in the most varied ways I have crashed the computer countless times), I can not imagine any way to deal with it. >

python array python-3.x

asked by anonymous 02.04.2018 / 06:10

1 answer

Doubt getting TreeTable Id with JS background image does not print (using window.print)

score 0 · Answer 1

I think at the time of copying and pasting the entry you made some mistake, or your computer gave a bug. Using udebug's 1000x1000 input, your program worked and returned the correct output, 480.20. When I will solve the problems of any online judge, I like to test the inputs through text files. In linux you copy the entry to a txt and run a terminal in the following command:

python3 programa.py < teste.txt

In this way, the program runs as if you were typing item by item. The URI performs their automated testing in this way.

Now entering your code. It has some inefficient stretches. The first one, in the "statement" and matrix padding, you are sweeping it many times to do operations that can be summarized in the same loop. Another detail I noticed is that you are still looking for values 42 even after they have been found, something the problem does not ask for (and there is only one valid value per entry), so it is interesting to break the loop after finding the saber. As your code is correct and you got the idea of the problem, knowing where you can look for the saber and in no time you search for a non existent index, I will post here the program that I did with the suggested changes.

l = input().split()
n_linha, n_coluna = int(l[0]), int(l[1])

m = list() 

for i in range(n_linha):                               
    m.append( [int(col_i) for col_i in input().split()] )  

t = t2 = 0
achei = False

for i in range(1, n_linha-1):
    if achei:
        break

    for j in range(1, n_coluna-1):
        if m[i][j] == 42:
            if m[i-1][j-1] == 7 and m[i-1][j] == 7 and m[i-1][j+1] == 7:
                if m[i][j-1] == 7 and m[i][j + 1] == 7:
                    if m[i+1][j-1] == 7 and m[i+1][j] == 7 and m[i+1][j+1] == 7:
                        t = i+1
                        t2 = j+1
                        achei = True
                        break

print("{} {}".format(t, t2))

Note that I also changed the name of some variables so the program becomes easier to read. I strongly recommend using names that are self explanatory

I hope I have helped, and just ask: