Jump to content

[usaco] Checker Challenge


Localhost
 Share

Recommended Posts

Tenho algumas dúvidas neste problema.

Primeiro vou dizer a minha ideia (que já funciona até ao penúltimo caso, inclusive):

* Fiz um dfs simples, percorro cada linha e cada coluna e vou metendo damas e vou verificando se posso efectivamente colocar a dama.

* Para poupar tempo na verificação meto dentro de um vector as colunas em que não posso meter a dama, ou seja, faço uma verificação em O(1).

O meu problema agora está em saber como é que vou guardar as posições das diagonais, já tentei várias fórmulas mas sai sempre errado.

Depois tenho outro problema relacionado com as simetrias, como é que posso utilizar isto a meu favor? Eu quando estava a resolver o problema no papel reparei que os locais onde colocava as damas eram todos simétricos a outros, no entanto, não sei como aplicar isto no meu código.

Deixo aqui o meu código:

#include <stdio.h>
#include <stdlib.h>

#define MAX 15

int table[MAX][MAX],n,quant;
int set[1000],lol[MAX];
FILE *fout;

void input() {
    FILE *fin=freopen("checker.in","r",stdin);
    scanf("%i", &n);
    fclose(fin);
}

int canplace(int r, int c) {
    int k=0,a1=0,a2=0;
    a1 = r; a2 = c;
    while(r < n && c < n) {
        if(table[r][c] == 1) return 0; 
        r++;
        c++;
    }
    r = a1; c = a2;
    while(r >= 0 && c < n) {
        if(table[r][c] == 1) return 0;
        r--;
        c++;
    }
    r = a1; c = a2;
    while(r < n && c >= 0) {
        if(table[r][c] == 1) return 0;
        r++;
        c--;
    }
    r = a1; c = a2;
    while(r >= 0 && c >= 0) {
        if(table[r][c] == 1) return 0;
        r--;
        c--;
    }
    return 1;
} 

int count() {
    int k=0,i=0,j=0;
    for(k=0; k < n; k++) {
        for(i=0; i < n; i++) if(table[k][i] == 1) j++;
    }
    return j;
}

void dfs(int r, int i,int times) {
    int c=0;
    if(times == n) {
        quant++;
        if(quant <= 3) {
            printf("%i",set[0]);
            for(c=1; c < i; c++) printf(" %i", set[c]);
            putchar('\n');
        }
        return;
    }
    for(c=0; c < n; c++) {
        if(!lol[c] && canplace(r,c)) {
            table[r][c] = 1;
            set[i] = c+1; i++;
            times++;
            lol[c] = 1;
            dfs(r+1,i,times);
            i--;
            times--;
            lol[c] = 0;
            table[r][c] = 0;
        }
    }
}

int main(void) {
    int k=0;
    fout = freopen("checker.out","w",stdout);
    input();
    dfs(0,0,0);
    printf("%i\n", quant);
    return 0;
}

Acho que o código está a funcionar, este foi um antigo que tinha e fiz aqui algumas alterações mas penso que está bem.

here since 2009

Link to comment
Share on other sites

Bem, eu além de ter percebido aquela parte das simetrias não tenho a certeza se estou a pensar bem.

O que eu pensei foi: não é preciso ir até ao fim do tabuleiro, basta percorrer até n/2 (N par) ou (n/2)+1 (N impar) e a cada dama que pomos calculámos também a dama simétrica que tem x (n-x-1) e y (n-y-1) em que x e y são as coordenadas da dama simétrica. Isto está correcto?

here since 2009

Link to comment
Share on other sites

São erros desses que às vezes custam qualificações. Foi por uma coisa estúpida como essa que não me ia qualificando para as ONI. Pensa sempre em todos os casos e faz testes para todos os tipos de situações, é uma das coisas mais importantes.

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Link to comment
Share on other sites

Eu fui desenhar as soluções para situações em que N é par e todas as damas estavam em posições simétricas.

Vou deixar aqui alguns exemplos:

N = 4

Output: 2 4 1 3

Analisando, sobre o que disse ia até à 2ª linha, ou seja, descobriria o 2 e o 4, depois o que faria era:

Linha: 4 - 0 - 1 = 3 (está na linha 3 + 1 = 4 (começa do 0))

Coluna: 4 - 1 - 1 = 2 (está na coluna 2 + 1 = 3 (começa do 0))

Então já temos: 2 4 3 (este 3 é adicionado na posição n - i - 1 (em que i é a posição em que adicionámos na última vez)

Depois:

Linha: 4 - 1 - 1 = 2 (está na linha 2 + 1 = 3 (começa do 0))

Coluna: 4 - 3 - 1 = 0 (está na coluna 0 + 1 = 1 (começa do 0))

Ou seja, ficaria com um array assim: 2 4 1 3, ou seja, está correcto.

Eu notei isto para muitos casos, depois para os impares é que notei alguns pormenores que ainda vou ter de pensar sobre eles. Isto não está correcto?

here since 2009

Link to comment
Share on other sites

Não tenho acesso ao enunciado, mas para um problema da secção 1.5 deve haver uma solução que não implique optimizações como estás a tentar fazer.

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Link to comment
Share on other sites

A simetria não relaciona as posições numa solução, mas soluções entre si.

Imagina que tens um tabuleiro de lado N e uma solução, cujas posições são X1 .. XN, no intervalo [0, N-1] .

Existem duas simetrias possíveis (uma na horizontal e outra na vertical):

Se substituires Xi por N-Xi-1, obtens uma solução válida.

Se substituires X(i) por X(N-i+1), obtens outra solução válida.

Só precisas de aplicar uma das simetrias para resolver o problema no tempo necessário.

Link to comment
Share on other sites

Yup, percebi isso ontem.

A ideia é na primeira linha percorrer apenas até metade da mesma e sacar todas as soluções começando com damas em cada uma dessas colunas na primeira linha, como no final sabemos que a partir da outra metade da primeira linha vão existir apenas soluções simétricas às que já descobrimos podemos apenas multiplicar por 2 a solução, se já ultrapassar os 3, ou seja, por exemplo, com N = 6 não podemos fazer isto mas com N = 7 podemos.

Resumindo, para os pares vamos até n/2 e depois multiplicámos por 2. Para os impares como existem soluções únicas (as do meio) temos de fazer um pequeno trick, e aqui tenho algumas dúvidas, vamos até n/2, depois, multiplicamos por 2 a quantidade de soluções e depois somámos este resultado a n/2.

Ou seja, imaginando n = 5.

Até metade tem 4 soluções, 4 * 2 = 8; 5 / 2 = 2; 2 + 8 = 10;

Alguém me podia só esclarecer aquela parte da soma nos ímpares?

Edit: Esqueçam aquilo da soma por n/2 nos ímpares, tenho mesmo de somar com quantas combinações existem começando no meio.

here since 2009

Link to comment
Share on other sites

Pronto, problema resolvido!

Compiling...

Compile: OK

Executing...

  Test 1: TEST OK [0.000 secs, 1780 KB]

  Test 2: TEST OK [0.000 secs, 1780 KB]

  Test 3: TEST OK [0.000 secs, 1780 KB]

  Test 4: TEST OK [0.000 secs, 1780 KB]

  Test 5: TEST OK [0.011 secs, 1780 KB]

  Test 6: TEST OK [0.032 secs, 1780 KB]

  Test 7: TEST OK [0.119 secs, 1780 KB]

  Test 8: TEST OK [0.637 secs, 1780 KB]

All tests OK.

Your program ('checker') produced all correct answers! This is your submission #14 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 -------

6

------- test 2 -------

7

------- test 3 -------

8

------- test 4 -------

9

------- test 5 -------

10

------- test 6 -------

11

------- test 7 -------

12

------- test 8 -------

13

here since 2009

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.