TOPIC

PROBLEM 1584 - URI Fórum 1.0

beecrowd asked 9 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • tiwizard replied 8 years ago

    Sejam (i, j) e (ii, jj) duas posições distintas no grid N×N . Independentemente de haver aresta entre os vértices correspondentes, a posição (ii, jj) bloqueia para a posição (i, j) todas as posições (ii +dif i , jj +dif j ), (ii +2dif i , jj + 2dif j ), (ii + 3dif i , jj + 3dif j ), . . . , sendo dif i = ii − i e dif j = jj − j, enquanto essas posições estiverem dentro do grid. Ao final, os vizinhos de (i, j) no grafo serão as posições que não terão sido bloqueadas.

  • BugFree replied 8 years ago

    olá, podem me da uma dica de como montar esse grafo? consegui entender que um vértice não é adjacentes ao seus vizinhos de linha , coluna e diagonal a uma distancia maior q 1, mais e os outros casos? como trata-los?

  • gduarte replied 8 years ago

    Eu pensei para montar o grafo da seguinte maneira: Um vértice se conecta a todos os seus 8 vizinhos e a todos os outros vértices que não estão na mesma linha, nem coluna e nem diagonal. Está errado isso ?

    Funciona para vários casos, porém nem todos batem, os com N = 5 quase todos que tentei não dão certos. Alguém pode me ajudar ?

    ACC

    EDIT: Na verdade está errado sim o que pensei, funciona quando N <= 4, quando N = 5 consegui ver algumas posições que também não são alcançadas e que não se encontram em nenhum caso que disse ali.

    MOD

  • thalyson004 replied 9 years ago

    obrigado pela ajuda. Quando eu usei long long int, coloquei pra dividir por 10^9+9 (não sei pq). Ai quando arrumei pra 10^9+7, usei apenas int (também n sei pq xD). Foi só arrumar isso do 10^9+7 e o long long int. Vlws

  • agbjunior replied 9 years ago

    Alguns itens para se checar:

    • A resposta está sendo acumulada numa variável 64-bit? 32-bit vai estourar em algum caso de teste.
    • Verifique atentamente quais deveriam ser as respostas para os casos de teste n = 5.

  • thalyson004 replied 9 years ago

    tem como disponibilizar mais casos de teste? eu não estou conseguindo saber onde eu estou errado '-'.... mas deve ser um grande erro, já q é 50% WA xD