-1

Estou com dificuldade em resolver o problema O Despertar da Força do URI.

Há muito tempo atrás, em uma galáxia muito, muito distante...

Após o declínio do Império, sucateiros estão espalhados por todo o universo procurando por um sabre de luz perdido. Todos sabem que um sabre de luz emite um padrão de ondas específico: 42 cercado por 7 em toda a volta. Você tem um sensor de ondas que varre um terreno com N x M células. Veja o exemplo abaixo para um terreno 4 x 7 com um sabre de luz nele (na posição (2, 4)).

inserir a descrição da imagem aqui

Você deve escrever um programa que, dado um terreno N x M, procura pelo padrão do sabre de luz nele. Nenhuma varredura tem mais do que um padrão de sabre de luz.

Entrada

A primeira linha da entrada tem dois números positivos N e M, representando, respectivamente, o número de linhas e de colunas varridos no terreno (3 ≤ N, M ≤ 1000). Cada uma das próximas N linhas tem M inteiros, que descrevem os valores lidos em cada célula do terreno (-100 ≤ Tij ≤ 100, para 1 ≤ i ≤ N e 1 ≤ j ≤ M).

Saída

A saída é uma única linha com 2 inteiros X e Y separados por um espaço. Eles representam a coordenada (X,Y) do sabre de luz, caso encontrado. Se o terreno não tem um padrão de sabre de luz, X e Y são ambos zero.

inserir a descrição da imagem aqui

Eu basicamente resolvi a maior parte do problema e ele funciona bem com entradas pequenas, o porém são entradas extremamente grandes por exemplo 1000 x 1000 que acabam me dando uma saida errada.

Como por exemplo o primeiro caso de teste do Udebug: https://www.udebug.com/URI/2163

Eu percebi que nem todos os valores estão sendo armazenados dentro da matriz, mas não faço a menor idéia de como contornar esse detalhe.

Segue meu código:

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)

É bem provável que eu não tenha que armazenar todos aqueles valores já que consumiria uma baita memória (tentando resolver o problema das mais variadas formas travei o pc inúmeras vezes), não consigo imaginar nenhuma forma de lidar com isso.

5
  • Poderia dar um exemplo? Ou, mais precisamente, qual seria a saída esperada para a entrada que seu programa falha, e qual saída seu programa está emitindo? Para "entradas muito grandes", acredito que isso faz pouca diferença. Afinal, o problema é um autômato finito, não vai gastar mais que uma quantidade fixa de memória. 7/04/2018 às 12:51
  • Então, não dá pra colar a entrada aqui porque excederia o número de caracteres, mas você pode ver no site do Udebug do problema udebug.com/URI/2163 a primeira entrada por exemplo postada pelo bitfreeze, pede pra entrar com mil valores por mil valores, meu pc trava só de tentar copiar aquela entrada pra colar no terminal do pycharm. Lá também mostra a saída esperada.
    – ltsdw
    8/04/2018 às 16:23
  • Neste caso, realmente seria insano inserir tais valores. Mil por mil, um milhão de números, cada um de digamos quatro bytes (dois para os dígitos, um para o sinal e um para o espaço), daria 4 megabytes, um valor realmente enorme para inserção. .......................................... Por que não fazer então uma rotina para ler estes valores de um arquivo TXT? Isso pelo menos te adianta de ter que ficar copiando e colando. 8/04/2018 às 18:03
  • Por outro lado, acredito que mesmo manipular tantos dados na memória não é necessariamente uma boa estratégia. OK, hoje em dia 4 gigas de ram é o basicão para um PC, mas sempre me parece uma má estratégia de programação supor que se está trabalhando em uma hipermáquina quando o problema não é muito exigente. Mas aí eu acho que estou interferindo demais no "processo de descoberta". De qualquer forma, vou dar a minha ideia: ler um buffer de três linhas da matriz, procurando o padrão sabre-de-luz; e re-preencher este buffer de acordo com o padrão observado. Vai na fé! 8/04/2018 às 18:10
  • 1
    Obrigado por responder novamente. Partindo do princípio que desconheço esse tópico em python, é uma boa oportunidade pra estudar sobre. Em breve volto pra dar o desfecho da resolução. Valeu!
    – ltsdw
    9/04/2018 às 19:55

1 Resposta 1

0

Eu acho que no momento de copiar e colar a entrada voce cometeu algum erro, ou o seu computador deu um bug. Utilizando a entrada de 1000x1000 do udebug, seu programa funcionou e retornou a saída correta, 480 20. Quando vou resolver os problemas de qualquer online judge, eu gosto de testar as entradas por meio de arquivos de texto. No linux voce copia a entrada para um txt e roda num terminal o seguinte comando:

python3 programa.py < teste.txt

desta forma, o programa é executado como se você estivesse digitando item por item. O URI executa os testes automatizados deles desta forma.

Agora entrando no seu código. Ele possui alguns trechos pouco eficientes. O primeiro deles, na "declaração" e preenchimento da matriz, você está varrendo-a muitas vezes para fazer operações que podem ser resumidas no mesmo laço. Outro detalhe que observei é que você continua procurando os valores 42 mesmo depois de já encontrado, coisa que o problema não pede (e só existe 1 valor válido por entrada), desta forma é interessante você quebrar o laço depois de achado o sabre. Como o seu código esta correto e você entendeu a idéia do problema, sabendo onde pode procurar o sabre e em nenhum momento você procura um indice inexistente, vou postar aqui o programa que eu fiz com as mudanças sugeridas.

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 que eu também mudei o nome de algumas variáveis para o programa ficar mais fácil de ser lido. Te recomendo fortemente utilizar nomes que sejam auto explicativos

Espero ter ajudado, e qualquer coisa só perguntar :)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .