Jump to content
Sign in to follow this  
xtrm0

Problema 10

Recommended Posts

xtrm0

Olá. Alguem consegue resolver o problema 10 da CPAS?

Para quem não foi, aqui fica o enunciado:

Considere uma partida de futebol entre 2 equipa A e B, cujo placar final é X x Y, em que X e Y são os golos marcados por A e B.

Implemente um programa que apresente todas as possiveis sucessões de golos marcado, ordenada alfabeticamente. Por exemplo:

INPUT:

3 1

OUTPUT:

AAAB

AABA

ABAA

BAAA


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Com backtrack (recursividade...). Tens dúvidas na implementação?


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Não sei como fazer. Pesquisei o que era e só encontrei para soma de numeros.

(6 =1+2+3

1+5

2+4

6)


<Signature goes here>

Share this post


Link to post
Share on other sites
JoaoSantos95

Na prova, cheguei a pensar que fosse para ver qual é o maior entre A e B, pegar no maior e andar a recuar aquilo e imprimir mas depois tinha uns problemas nuns casos e decidi não tentar.

xtrm0, para o ano a escola para onde vais vai ter cursos como os do CIC ? Sabes quais foram os problemas que ninguém fez ?

Share this post


Link to post
Share on other sites
Localhost

Tens que saber o que saber o que é recursividade para resolveres este problema.. Basicamente para cada nó tens duas opções: escolher a equipa A ou a equipa B... no entanto tens de obedecer ao resultado final e à quantidade de letras que cada equipa pode ter.

Para fazeres o que disse anteriormente tens manter quantas vezes utilizaste cada letra, ou seja, cada equipa e tens de saber quantas vezes utilizaste ambas as equipas. Esta última condição vai ser o caso de paragem ou caso base.

Um pseudo-código deve ajudar.

function dfs (int a_times, int b_times, int i, char team):
   comb[i] = team
   
   if a_times + b_times == x + y:
      print comb
      return

   if a_times < x:
     dfs (a_times + 1, b_times, i + 1, 'a')

   if b_times < y:
     dfs (a_times, b_times + 1, i + 1, 'b')

No princípio, se nunca tiveres "lidado" com recursividade vai-te parecer estranho e complicado compreender o código, no entanto, se desenhares a tal árvore e se escreveres no papel todas as chamadas à função e se seguires as chamadas na árvore é relativamente simples de compreender.


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

@95joaosantos:

Nao

Eu nao fiz o 5, 7, 8 e 10.

@localhost

como é que chamo essa funcao?

dfs(0,0,0,'A')?


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Não. Isso deixo para tu pensares.

Lembra-te que em cada nó tens duas opções...


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Obrigado. Já percebi como funciona, alterei um bocado para usar string em vez de cstring:

#include <iostream>
#include <string>
using namespace std;
int x, y;
void dfs (int a_times, int b_times, char team, string comb){
   comb += team;
   
   if ((a_times + b_times) == (x + y)) {
      cout << comb << endl;
      return;
      }

   if (a_times < x) 
     dfs (a_times + 1, b_times, 'A', comb);
   if (b_times < y)
     dfs (a_times, b_times + 1, 'B', comb);
}

int main() {
   cin >> x >> y;
   string nada="";
   dfs(1,0, 'A', nada);
   dfs(0,1, 'B', nada);
   cin >> x;
   return 0;   
}

Agora vou tentar fazer o do ano passado.


<Signature goes here>

Share this post


Link to post
Share on other sites
JoaoSantos95

O que me deixou um pouco aborrecido foi por não ter deixado o 4º para mais tarde.

Bem que podia ter deixado o 4º para trás e termina-lo no fim, talvez tivesse tempo de fazer o 6º e o 9º e ainda pegar no 4º no final mas acabei por gastar demasiado tempo no 4º porque não compreendi uma parte no enunciado.

Agora só me resta ficar em 1º no CPAS Junior (é um concurso para o 10º ano lá no CIC, os exercícios são básicos e agora com treino nas férias ainda mais fáceis vão parecer) e ver se consigo fazer qualquer coisinha nas ONI.

O que me irrita não foi ter demorado tanto tempo porque isso vou aperfeiçoando, foi mais por não ter feito uma analise detalhada do 6º e ter pensado que era mais difícil que o 4º.

Mas também foi o meu primeiro ano, vou tentar participar em mais concursos este ano, com a experiência e a prática vou melhorando. Parabéns pela tua classificação e até às ONI :D

Share this post


Link to post
Share on other sites
Localhost

Para quem quiser treinar recursividade deixo aqui um pequeno problema.

Dado um set S de N elementos imprimir todas as permutações possíveis com os elementos desse set.

Exemplo: {1, 2, 3};

Resposta: {1, 2, 3}, {1, 3, 2}, {2, 1, 3} e assim sucessivamente...


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Esse foi facil:

#include <iostream>
#include <vector>
using namespace std;
int N;


void dfs (vector <int> hip, vector <int> saida){
    if (saida.size()==N) {
       for (int i=0; i<N-1; i++) 
           cout << saida[i] << " ";
       cout << saida[N-1] << endl;  
       return;                    
    }
    for (int i=0; i<hip.size(); i++) {
        vector <int> tmp = hip;
        vector <int> tmp2 = saida;
        tmp2.push_back(hip[i]);
        tmp.erase(tmp.begin()+i);
        dfs(tmp, tmp2);    
    }
    return;
   
}

int main() {
   vector <int> hipo;
   vector <int> nada;
   int x;
   cin >> N;
   for (int i=0; i<N; i++) {
       cin >> x;
       hipo.push_back(x);
   }
   dfs(hipo, nada);
   cin >> x;
   return 0;   
}

INPUT:

3

1 2 3

OUTPUT:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Como é que se faz o 9 do ano passado?

http://e-escola.cic.pt/cpas/CPAS2010.pdf


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Mais um problema resolvido com backtrack. Pode ser resolvido por backtrack porque os valores são pequenos..

Neste caso a única coisa que muda é que o caso base, que neste caso vai ter a ver com a soma. Crias todas as permutações e retornas quando a soma for igual a S.


here since 2009

Share this post


Link to post
Share on other sites
mogers

O que me irrita não foi ter demorado tanto tempo porque isso vou aperfeiçoando, foi mais por não ter feito uma analise detalhada do 6º e ter pensado que era mais difícil que o 4º.

Calma Pedro, isso é perfeitamente normal. Com efeito, esse é o maior desafio num concurso de programação: conseguir determinar a dificuldade de um problema para o qual ainda não descobrimos a solução. Só com a experiência :D

Agora só me resta ficar em 1º no CPAS Junior

Força nisso, boa sorte!  :D


"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
JoaoSantos95

Calma Pedro, isso é perfeitamente normal. Com efeito, esse é o maior desafio num concurso de programação: conseguir determinar a dificuldade de um problema para o qual ainda não descobrimos a solução. Só com a experiência :D

Foi mais porque eu olhei para o 6º e pensei "eu sei fazer isto. Vou só acabar aqui o 4º que já faço este" e depois acabei por me envolver no 4º. Se o deixasse a meio, não o terminasse mais tarde e não conseguisse fazer o 6º iria-me arrepender por não ter feito o 4º . Os concursos são mesmo assim e esta não será a primeira, nem a ultima vez que isto vai acontecer em concursos. A nível de programação até estava bem apesar de ter perdido muito tempo na 4 (pensava que quando se repetiam dois números numa coluna aquilo tinha de imprimir FALSO e por isso demorei tanto tempo), mas sinto que o resultado ficou aquém do que podia ter feito (nem que fosse só mais um problema resolvido) mas não há problema, o número de problemas resolvidos não foi mau para uma primeira vez e, pelo menos, já me comecei a habituar ao ambiente dos concursos.

Era interessante ver a reacção das pessoas quando lhes diziam que o xtrm0 anda no 9º ano.

xtrm0: já percebeste o 5 ?

Share this post


Link to post
Share on other sites
Joao brandao

Boas, eu fui ao concurso, e por acaso ate estava no pc ao lado do xtrm0(Afonso), nunca pensei que um aluno do 9 ano sem qualquer tipo de ajuda escolar pode-se chegar onde o xtrm0 chegou, tenho a dar os parabens aos tres primeiros classificados mas um grande parabens ao xtrm0(Afonso) pois sozinho consigui ir ate ao 4º lugar :D Continua assim que tens futuro :D

Quanto aos exercicios, existia alguns que dava de pensar mas chegava se a resposta rapido, eu so coloquei 3 exercicios certos  mas ja tinha 2 feitos que me estavam a dar erro na saida, o programa em si estava certo, eu é que por falta de tempo nao consigui ver muito bem onde estava a errar e perdi 200 pontos :S

Share this post


Link to post
Share on other sites
JoaoSantos95

Boas, eu fui ao concurso, e por acaso ate estava no pc ao lado do xtrm0(Afonso), nunca pensei que um aluno do 9 ano sem qualquer tipo de ajuda escolar pode-se chegar onde o xtrm0 chegou

Fui só eu que eu me lembrei do (Sr. Engenheiro) Pedro Ribeiro quando o João disse aquilo ?

Share this post


Link to post
Share on other sites
mogers

Fui só eu que eu me lembrei do (Sr. Engenheiro) Pedro Ribeiro quando o João disse aquilo ?

O Pedro não é engenheiro, foi o melhor aluno de sempre de ciência de computação na FCUP  :cheesygrin:. Seria mais adequado Sr Doutor, ainda para mais que ele está prestes a terminar o seu doutoramento =)


"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
mogers

Afonso, estás a complicar um pouco o código. Basta chamar-te a dfs do problema 10 com dfs(0,0,"").

Já agora deixo uma contribuição preparada para se o problema tivesse mais de 2 letras e deixo um conselho: nas ONI ou num qualquer problema com limites altos, tenham cuidado se estiverem a trabalhar com milhares de strings. A classe string do c++, cin's cout's e getline's são bastante mais lentos do que os seus equivalentes do C (utilizar um array de chars, scanf, printf, fgets).

#include <iostream>
#include <string>
using namespace std;
#define MAX 2
int x, y, max_times[MAX], times[MAX], total;
string alfabeto = "AB";

void dfs ( string comb ) {

if (comb.size() == total) {
	cout << comb << endl;
	return;
}
for (int i = 0 ; i < MAX ; i++)
	if (times[i] < max_times[i]) {
		times[i]++;
		dfs (comb + alfabeto[i]);
		times[i]--;
	}
}

int main() {
total = 0;
for (int i = 0 ; i < MAX ; i++) {
	cin >> max_times[i];
	total += max_times[i];
}
dfs("");
return 0;  
}

edit: btw Afonso, não sabia que tavas no 9º ano, obviamente que tens jeito para isto, não tenhas pressa (coisas de rankings de nº de problemas resolvidos e etcs). Reforço a qualidade do sistema da usaco, gastar 1 semana para resolver um problema lá (como já me aconteceu) vale mais que 100 problemas no UVA. Se fores com calma podes ganhar umas medalhas nas IOIs. Normalmente o pessoal só toma conhecimento destas coisas no 12º e já não vai a tempo.

Isto não é só válido para o Afonso, mas para todos  :D


"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
xtrm0

Sim:

Era só substitures os "R"/"r" por "" e os "L"/"l" por "U"/"u", para todas as palavras onde não houvesse um @.

Eu nao fiz esse por que não me lembrei como usar a funçao find() e replace() durante a prova.  :wallbash:


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