Jump to content
Sign in to follow this  
xtrm0

Problemas Estagio para as IOI 2008

Recommended Posts

xtrm0

Boas.

Tentei resolver este problema:

Problema - Ronda Nocturna

Clancy Wiggum é o chefe da polícia de Springfield. Como qualquer polícia que se preze, gosta muito de passar a vida comer donuts (passatempo também partilhado por Homer Simpson, diga-se). O problema é que tanto tempo passado nos vícios gastronómicos deixou-o um pouco "pesadote" e com pouca mobilidade. Ainda por cima ele é extremamente preguiçoso.

Clancy tem diariamente a tarefa de fazer uma ronda nocturna por vários locais de Springfield. Começa na esquadra, passa por todos os locais desejados pelo menos uma vez, e volta novamente à esquadra. Obviamente, quer mexer-se o menos possível nessa tarefa e por isso quer saber qual o caminho que minimiza o tempo dispendido. Será que podes ajudá-lo?

O mapa de Springfield é-te dado neste problema como uma matriz. Certas posições da matriz estão indicadas como obstáculos e não é possível passar por elas. Em cada posição, o nosso polícia pode efectuar quatro tipos de movimentos: norte, sul, este e oeste (desde que a quadrícula para onde se desloca esteja livre, claro). A mudança de uma quadricula para outra custa uma unidade.

O Problema

Dado uma mapa de Springfield com o local da esquadra de polícia e dos locais a visitar, tens de calcular o comprimento do menor caminho que começa na esquadra, passa por todos os locais a visitar pelo menos uma vez, e termina novamente na esquadra. É garantido que é sempre possível arranjar pelo menos um caminho nas condições descritas.

Input

Na primeira linha vêm dois inteiros N e M (3<=N,M<=300), o número de linhas e o número de colunas do mapa, respectivamente.

As próximas N linhas descrevem o mapa. Cada linha é composta por M caracteres (que podem ser '#', '.', 'V' ou 'S'). '#' representa um obstáculo, '.' uma quadrícula livre, 'V' representa um local a visitar e 'S' o local da esquadra.

Existe exactamente um 'S' no input e até 10 'V''s, podendo não existir nenhum.

O mapa está sempre rodeado de '#' nos seus limites.

Output

Deve ser impressa uma única linha com o tamanho do menor caminho que começa na posição indicada por 'S', passa por todas as casas 'V' e regressa a 'S'.

Exemplo de Input

10 10

##########

#.V......#

#.###.##.#

#..V#..#.#

#......#.#

#..#.###V#

#....#...#

#....#S..#

#..#.#...#

##########

Exemplo de Output

36

E pensei em fazer uma floodfill a partir de cada ponto V, e a partir da esquadra da policia, e quando dois pontos de um local diferente se juntassem, adicionava um caminho à array. Só que encontrei um problema: como é que descobria o caminho menor para voltar à esquadra da policia? Aí percebi que estava a resolver de forma errada.

Existe algum algoritmo expecifico para este problema?


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Existe. Isto é um problema clássico de TSP (travelling salesman problem).

Tu podes fazer uma solução recursiva (era suposto já saberes fazer isto - é quase a mesma coisa que o C da qualificação, se consegues resolver o C deverias conseguir resolver este) onde tens a quantidade de sítios por onde queres passar e apenas podes voltar ao início quando já tiveres visitado todos os locais (se o nó actual for igual ao início e se a quantidade de sítios visitados for menor então não podes ir para esse nó). Escusado será dizer que não dá os 100 pontos mas já é uma ideia base.


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

E como é que descubro o caminho minimo entre dois pontos, visto que há obstaculos?


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Se o nó actual for um obstáculo não o consideras ou seja, não aprofundas a pesquisa a partir dele... A ideia é calculares todos os caminhos possíveis (onde não existem obstáculos) e tirares o mínimo deles.


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Acho que já percebi.

BTW, o que é que usaste para o A?

Eu tive WA, mas não sei porquê.


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

E como é que descubro o caminho minimo entre dois pontos, visto que há obstaculos?

O custo de te moveres para cima/baixo/esquerda/direita é sempre 1, isto está a clamar por BFS. Se há obstáculo, simplesmente não podes usar essa célula.

E pensei em fazer uma floodfill a partir de cada ponto V, e a partir da esquadra da policia,

A solução para 100 pontos começa por isto, mas não é floodfill é BFS. Agora tens de pensar como usas essa informação, não é nenhum algoritmo específico, é pensar.

Dica: tem sempre em conta as restrições.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Localhost

Acho que já percebi.

BTW, o que é que usaste para o A?

Eu tive WA, mas não sei porquê.

Guardava os números que já verifiquei se eram primos e verificava em O(1) se já tinha feito essa verificação.


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

@localhost

Há ok. É mais ou menos isso a solução, só que tens de pensar em usar menos calculos.

1000000*isprime nao dá.


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Não é 10^6. E a minha função que verifica se é primo tem complexidade O(sqrt(n)).

@mogers, disse alguma asneira neste tópico? Isto não é um problema de TSP...?


here since 2009

Share this post


Link to post
Share on other sites
skiller10

Heys,

Alguém sabe como converter uma string para int? tentei com o atoi e não resultou :s


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Localhost

O meu código, que também utiliza a função atoi.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

int primes[100000001];
char chain[10000010];

bool check (int cur_int)
{
if (cur_int <= 1)
	return false;

if (cur_int == 2)
	return true;

for (int i = 2; i <= (int) sqrt (cur_int); i++)
	if (cur_int % i == 0)
		return false;

return true;
}

int main ()
{
char sub_chain[120];
int x = 0, cur_counter = 0, len = 0, lol = 0, cur_int = 0;
bool ret = false;

scanf ("%d", &x);

while (scanf ("%s", sub_chain) != EOF)
	strcat (chain, sub_chain);

lol = strlen (chain);

for (int i = 0; chain[i] && i + x <= lol; i++)
{
	if (chain[i] == '0')
		continue;
	len = 0;
	for (int j = i, k = 0; j < i + x; j++)
	{
		sub_chain[k++] = chain[j];
		sub_chain[k] = '\0';
		len++;
	}
	if (len != x)
		continue;

	cur_int = atoi (sub_chain);

	if (!primes[cur_int])
	{
		ret = check (cur_int);
		if (ret)
			primes[cur_int] = 1;
		else
			primes[cur_int] = -1;
	}

	if (primes[cur_int] > 0)
		cur_counter++;
}

printf ("%d\n", cur_counter);

return 0;
}

86 pontos que me deu.


here since 2009

Share this post


Link to post
Share on other sites
skiller10

Eu estava a falar em usar atoi mesmo com a classe string, não com array de char :x


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Localhost

Por que é que vocês usam tanto essa classe? Existem certos problemas que só diminuem a eficiência do vosso programa...


here since 2009

Share this post


Link to post
Share on other sites
skiller10

A mim é das primeiras vezes que estou a usar, para me habituar caso dê jeito.

Mas não esperava este problema em converter para inteiro ;S


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Localhost

Já estamos a entrar em off-topic. Alguém pode fazer split do tópico (problema A e problema C)?


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

@mogers

Já fiz com bfs e não dá. Dá-me TLE aos 30 pontos.  O que tenho de fazer para melhorar?

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ponto{
    int x, y;
};


char mapa[302][302];
bool map[302][302];
int Xi, Yi, pp=0, passos=0;
int C, L;
int nd;

void bfs(vector <ponto> pa) {
    vector <ponto> ps;
    ponto tmp;
    ponto tm2;
    while(pp>0){
        for (int y=0; y<=300; y++) for (int x=0; x<=300; x++) map[y][x]=true;
        while(1) {
            ps.clear();
            for (int i=0; unsigned(i)<pa.size(); i++) {
                if (mapa[pa[i].y][pa[i].x]=='V') {
                    pp--;
                    tm2.x=pa[i].x;
                    tm2.y=pa[i].y;
                    mapa[pa[i].y][pa[i].x]='.';
                    pa.clear();
                    pa.push_back(tm2);
                    goto nextsearch;
                }
                if (pa[i].x+1<C) {
                    if ((mapa[pa[i].y][pa[i].x+1]!='#')&&(map[pa[i].y][pa[i].x+1])) {
                        tmp.x= pa[i].x+1;
                        tmp.y= pa[i].y;
                        ps.push_back(tmp);
                        map[pa[i].y][pa[i].x+1]=false;
                    }
                }
                if (pa[i].x-1>=0) {
                    if ((mapa[pa[i].y][pa[i].x-1]!='#')&&(map[pa[i].y][pa[i].x-1])) {
                        tmp.x= pa[i].x-1;
                        tmp.y= pa[i].y;
                        ps.push_back(tmp);
                        map[pa[i].y][pa[i].x-1]=false;
                    }
                }
                if (pa[i].y+1<L) {
                    if ((mapa[pa[i].y+1][pa[i].x]!='#')&&(map[pa[i].y+1][pa[i].x])) {
                        tmp.x= pa[i].x;
                        tmp.y= pa[i].y+1;
                        ps.push_back(tmp);
                        map[pa[i].y+1][pa[i].x]=false;
                    }
                }
                if (pa[i].y-1>=0) {
                    if ((mapa[pa[i].y-1][pa[i].x]!='#')&&(map[pa[i].y-1][pa[i].x])) {
                        tmp.x= pa[i].x;
                        tmp.y= pa[i].y-1;
                        ps.push_back(tmp);
                        map[pa[i].y-1][pa[i].x]=false;
                    }
                }
            }
            passos++;
            pa=ps;
        }
        nextsearch:
        nd=1;
    }
    for (int y=0; y<=300; y++) for (int x=0; x<=300; x++) map[y][x]=true;
    while(1) {
       ps.clear();
       for (int i=0; unsigned(i)<pa.size(); i++) {
           if (mapa[pa[i].y][pa[i].x]=='S') {
               pp--;
               return;
           }
           if (pa[i].x+1<C) {
               if ((mapa[pa[i].y][pa[i].x+1]!='#')&&(map[pa[i].y][pa[i].x+1])) {
                 tmp.x= pa[i].x+1;
                 tmp.y= pa[i].y;
                 ps.push_back(tmp);
                 map[pa[i].y][pa[i].x+1]=false;
               }
           }
           if (pa[i].x-1>=0) {
               if ((mapa[pa[i].y][pa[i].x-1]!='#')&&(map[pa[i].y][pa[i].x-1])) {
                 tmp.x= pa[i].x-1;
                 tmp.y= pa[i].y;
                 ps.push_back(tmp);
                 map[pa[i].y][pa[i].x-1]=false;
               }
           }
           if (pa[i].y+1<L) {
               if ((mapa[pa[i].y+1][pa[i].x]!='#')&&(map[pa[i].y+1][pa[i].x])) {
                 tmp.x= pa[i].x;
                 tmp.y= pa[i].y+1;
                 ps.push_back(tmp);
                 map[pa[i].y+1][pa[i].x]=false;
               }
           }
           if (pa[i].y-1>=0) {
               if ((mapa[pa[i].y-1][pa[i].x]!='#')&&(map[pa[i].y-1][pa[i].x])) {
                 tmp.x= pa[i].x;
                 tmp.y= pa[i].y-1;
                 ps.push_back(tmp);
                 map[pa[i].y-1][pa[i].x]=false;
               }
           }
       }
       passos++;
       pa=ps;
    }
    

}


int main(){
    cin >> L >> C;
    ponto ppt;
    vector <ponto> pd;
    for (int y=0; y<L; y++){
        cin >> mapa[y];
        for (int x=0; x<C; x++) {
            if (mapa[y][x]=='S')  {
                ppt.x=x;
                ppt.y=y;
            }
            if (mapa[y][x]=='V') {
                pp++;
            }
        }
    }
    pd.push_back(ppt);

    if  (pp>0) {
        bfs(pd);
        cout << passos << endl;
    } else {
        cout << "0"<< endl;
    }


    return 0;
}

@localhost

1000000*sqrt(9999999) é de longe demasiado.

Experimenta ler mais sobre como calcular numeros primos, e sobre o crivo de erastones.

Tens um exemplo no meu código (o crivo é a função pre), BTW, se vires onde está o erro que me dá WA, avisa.

#include <iostream>
#include <string>
#include <stdlib.h>
#include <cmath>
#define max 9999999
using namespace std;

string s;
bool isprime[10000000];
int tam;

void pre() {
    for (int x=1; x<=max; x+=2) {
        isprime[x]=true;
    }
    for (int x=2; x<=max; x+=2) {
        isprime[x]=false;
    }
    isprime[2]=true;
    for (int x=3; x<=max; x+=2) {
        if (isprime[x]){
            for (int y=x+x; y<=max; y+=x) {
                isprime[y]=false;
            }
        }
    }
    isprime[9999999]=false;
    return;
}

int main() {
    pre();
    int tttt=0;
    string ts;
    cin >> tam;
    int power=1;
    for (int x=1; x<tam; x++) power=power*10;
    while (cin >> ts) {
        s.append(ts);
    }
    for (size_t x=0; x<s.size(); x++) {
        if (isprime[atoi(s.substr(x,tam).c_str())]){
            if (atoi(s.substr(x,tam).c_str())>=power) {
                tttt++;
//                cout << atoi(s.substr(x,tam).c_str()) << endl;
            }
        }
    }
    cout << tttt << endl;
    return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

O crivo foi logo a minha primeira ideia. Aquele TLE que tenho de 58 pontos foi quando implementei o crivo. Depois mostro o código.


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Se calhar não o fizeste como eu (em vez de fazeres os calculos para todos os numeros, fazes apenas de dois em dois).


<Signature goes here>

Share this post


Link to post
Share on other sites
pedrosorio

Não é 10^6. E a minha função que verifica se é primo tem complexidade O(sqrt(n)).

@mogers, disse alguma asneira neste tópico? Isto não é um problema de TSP...?

Não sou o mogers, mas olhando para o problema parece-me um BFS a partir dos pontos de interesse (V's e S) para achar as distâncias entre cada par destes pontos, tens no máximo 11 pontos de interesse e o BFS é linear no número de vértices do mapa (300^2), portanto é tranquilo.

Depois sim, ficas com um grafo com no máximo 11 nós que é um TSP, e que podes resolver testando todas as permutações que começam(e acabam) em S, o que deve ser suficiente (10! ~ 3.000.000 ).


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
xtrm0

Mas o meu código não 'gasta' 300^2*11 tempo?

Isso não deveria ser suficiente? Porque é que dá TLE?


<Signature goes here>

Share this post


Link to post
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
Sign in to follow this  

×
×
  • 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.