Jump to content

Greedy Gift Givers - programa crasha


deathseeker25
 Share

Recommended Posts

Boas,

Não sei se já conhecem o problema Greedy Gift Givers, um problema do USACO de nível bastante avançado mas que me está a dar a volta à cabeça. O código que vou apresentar não visa resolver por completo o problema, apenas visa testar o que já consegui fazer até ao momento. O resto do algoritmo implementarei a partir daí.

O problema que surgiu é que após compilar o código no DevC++, a janela do DOS abre mas aparece um erro e o programa crasha e tenho de o terminar. O que está a provocar esse erro é algo que estou a tentar descobrir há mais de uma hora mas ainda não consegui. Se me conseguirem dar uma ajuda, correndo o código no vosso SO com o DevC++ e procurar a origem do erro (não há warnings nem errors, o programa deveria funcionar caso não crashasse), avisem de imediato. Aceito também dicas de optimização, caso as queiram dar.

Aqui fica o código:

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

string splitMoney(string st)
{
               unsigned int num;
               string money;
               vector<char> v1, v2;
               for(unsigned int i=0; i<=st.size(); i++)
               {
                            if(isspace(st[i]))
                                 num = st[i];
               }
               
               for(unsigned int i=0; i<=num; i++)
                           v1.push_back(st[i]);
               for(unsigned int i=0; i<=v1.size(); i++)
                           money += v1[i];
               
               return money;
}

string splitNPeople(string st)
{
               unsigned int num;
               string NPeople;
               vector<char> v1, v2;
               for(unsigned int i=0; i<=st.size(); i++)
               {
                            if(isspace(st[i]))
                                 num = st[i];
               }
               for(unsigned int i=num; i<=st.size(); i++)
                           v2.push_back(st[i]);
               for(unsigned int i=0; i<=v2.size(); i++)
                           NPeople += v2[i];
               
               return NPeople;
}
                                             
int numElevadoA (int num, int exp) // função que faz o mesmo que a função pow mas que devolve um inteiro em vez de um double
{
    int numfinal;
    
      if ((exp == 0) && (num != 0)) // sempre que o expoente for 0 e a base não for nula...
        numfinal = 1;
      
        else 
        {
         numfinal = num;
           
           while (exp > 1) // multiplica o número por si próprio enquanto o expoente for superior a 1
           {
             numfinal *= num; 
             exp--;
           }
         }
    return numfinal;
}  

int converteStringInt(string num) // função que converte um número numa string para um inteiro
{
   
         unsigned int i = num.size()-1, n = 0;
         int resultado = 0;

    
           while (i >= 0 && n <= num.size()) // ciclo que percorre os algarismos da string do menos significativo para o mais significativo
            {
               int d; // inteiro que é utilizado na conversão de cada caracter para inteiro
               d = num[i] - '0'; // como o caracter é convertido em ASCII subtraímos-lhe o código ASCII do '0' a fim de obter o valor real do algarismo
               resultado += (d * numElevadoA(10, n)); // somamos os valores de cada algarismo multiplicado por 10^n a fim de colocar cada um na "casa" correspondente
               i--;
               n++; 
            }
          
         return resultado; 
}

                                    

int main ()
{
    int NP, count, money, dadoAUm, dadoTotal, resto, NPeople;
    vector<string> vec, Users;
    vector<int> Guito;
    string temp, guy;
    ifstream input;
    input.open("gift1.in.txt");
    while(getline(input, temp))
    {
           vec.push_back(temp);
    }
    
    //por causa do tipo dos vectores ser incompativel...
    NP = converteStringInt(vec[0]);
    
    // preenche o vector users com o nome dos utilizadores inseridos
    for(int i=1; i<=NP; i++)
                 Users.push_back(vec[i]);
    
    temp = vec[NP+2];
    for(count=1; count <= NP; count ++)
    {
        guy = vec[NP+1];
        money = converteStringInt(splitMoney(temp));
        NPeople = converteStringInt(splitNPeople(temp));
        dadoAUm = money / NPeople;
        dadoTotal = dadoAUm * NPeople;
        resto = money - dadoTotal;
        money = money - dadoTotal + resto;
        Guito.push_back(money);
        
    }
    
    ofstream output;
    output.open("gift1.out.txt");
    for(unsigned int i=0; i<=Users.size(); i++)
                 output << Users[i] << " " << Guito[i] << endl;
    
    return 0;
}
Link to comment
Share on other sites

Aqui nem estava a compilar, faltava o #include <string>

Na função converteStringInt(string num) estás a utilizar i como inteiro sem sinal, logo o que vai acontecer é que ao chegares a 0 e decrementares, i passa a ter 0xFFFFFFFF e o ciclo continua alegremente, e vai tentar mexer em num com um índice enorme, e aí estoira.

Se declarares i com sinal, esse problema fica resolvido.

PS: Tens outros problemas semelhantes em outras funções, como na splitMoney, em que também vais tentar aceder a índices fora da string, o que vai causar o mesmo erro. Devias fazer debug step by step e olhar para os valores das variáveis para veres onde é que está a rebentar e porquê.

PS2: Não devias dar aquele endereço da USACO ali em cima, neste momento estou logado como sendo tu 🙂

Desaparecido.

Link to comment
Share on other sites

Aqui nem estava a compilar, faltava o #include <string>

Na função converteStringInt(string num) estás a utilizar i como inteiro sem sinal, logo o que vai acontecer é que ao chegares a 0 e decrementares, i passa a ter 0xFFFFFFFF e o ciclo continua alegremente, e vai tentar mexer em num com um índice enorme, e aí estoira.

Se declarares i com sinal, esse problema fica resolvido.

Olha que se eu declarar i com sinal, vou estar a comprar um signed value com um unsigned value (proveniente do num.size(), que devolve um unsigned). O problema não se resolve e há o acréscimo de dar um Warning pelo facto de estar a comparar valores com sinal com valores sem sinal.

Vou então fazer debug e tentar ver o que consigo resolver.

Quanto ao endereço, já o removi.  😁 Erro meu.

Link to comment
Share on other sites

Boas

Em primeiro lugar um reparo:

Não sei se já conhecem o problema Greedy Gift Givers, um problema do USACO de nível bastante avançado mas que me está a dar a volta à cabeça.

Não sei se era mesmo isto que querias dizer (devido ao "mas"), mas se foi estás enganado.

O treino da USACO está dividido em 6 módulos, sendo que cada um deles se divide em submódulos:

1: 1.1 , 1.2 , 1.3 , 1.4 e 1.5

2: 2.1 , 2.2 , 2.3 , 2.4

3: 3.1 , 3.2 , 3.3 e 3.4

4: 4.1 , 4.2 , 4.3 e 4.4

5: 5.1 , 5.2 , 5.3 , 5.4 e 5.5

6: 6.1

De um modo geral, a dificuldade dos exercícios vai aumentando de submódulo em submódulo e esse exercício é do 1.1. Por isso, sem querer desmotivar (pelo contrário!), ainda há muito pela frente 😄

Eu tou empancado no 5.3 🙂

Podes simplificar muito a leitura de dados - não precisas de ler tudo linha-a-linha e guardar num vector:

ifstream input("gift1.in.txt");
input >> NP;
input.get();	// ler '\n' no final da linha

for (count = 0 ; count < NP ; count++)
{
	getline(input, temp);
	Users.push_back(temp);
}	
for (count=1; count <= NP; count++)
{
	input >> guy;  // nao ha problema porque os nomes só têm uma palavra, mas tb se pode fazer getline
	input >> money >> NPeople;

	dadoAUm = money / NPeople;
	dadoTotal = dadoAUm * NPeople;
	resto = money - dadoTotal;
	money = money - dadoTotal + resto;
	Guito.push_back(money);
}

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

Link to comment
Share on other sites

Boas

Em primeiro lugar um reparo:

Não sei se já conhecem o problema Greedy Gift Givers, um problema do USACO de nível bastante avançado mas que me está a dar a volta à cabeça.

Não sei se era mesmo isto que querias dizer (devido ao "mas"), mas se foi estás enganado.

Sim, enganei-me a escrever. Tenho plena noção de que estou a tentar resolver um problema de nível bastante simples, daí o "mas".  😛 Obrigado pelo reparo.

Quanto á forma como eu li os dados, de facto, comparando com a forma como nesse excerto os leste, está bastante suja e complicada. Acho que vou optar pela forma que sugeriste, visto que facilita não só a leitura do código como simplifica também a concepção do programa. Por vezes excedo-me um pouco no uso de vectores, começo a usá-los por tudo e por nada, o que complica a legibilidade e o meu próprio raciocínio, enquanto escrevo o código.

Já está, portanto, a funcionar com esse excerto que sugeriste. A partir de agora vou começar a ler os dados de input dessa forma.  🙂

Vou completar o programa e posteriormente coloco aqui o código-fonte.  😄

Link to comment
Share on other sites

Que idade tens? Vieste para a faculdade não foi ? Não sei se estou a confundir... começa a participar nos concursos universitarios 🙂

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

Link to comment
Share on other sites

Que idade tens? Vieste para a faculdade não foi ? Não sei se estou a confundir... começa a participar nos concursos universitarios 🙂

Tenho 18 anos, ando na FEUP e acho que sei quem és. Participei na prova de treino na passada quarta-feira (sou o tipo que tinha equipa mas que ninguém da equipa esteve presente pelo que me juntei com outros na mesma situação que eu).

Link to comment
Share on other sites

Olha que se eu declarar i com sinal, vou estar a comprar um signed value com um unsigned value (proveniente do num.size(), que devolve um unsigned). O problema não se resolve e há o acréscimo de dar um Warning pelo facto de estar a comparar valores com sinal com valores sem sinal.

O problema resolve-se e sabes que nunca terás uma string com 2 milhões de caracteres, logo não vão existir overflows (ao contrário daquele decremento, que provoca um underflow), e podes neste caso ignorar esse warning. Mas só porque sabes à partida que não vais ter problemas devido ao tamanho das strings.

Porque dizes que não resolve? Só pelo warning? Podes livrar-te dele fazendo cast do valor de retorno do método size para signed.

Desaparecido.

Link to comment
Share on other sites

Tenho 18 anos, ando na FEUP e acho que sei quem és. Participei na prova de treino na passada quarta-feira (sou o tipo que tinha equipa mas que ninguém da equipa esteve presente pelo que me juntei com outros na mesma situação que eu).

Ah.. já sei quem és 😄 És da turma de programação do Michel?

Qual é o nome da tua equipa? A prova era bastante complicada, não foi o ideal para quem estava a participar pela primeira vez...

edit: já vi que sim. eu sou o monitor da tua turma 😛 força na usaco 🙂

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

Link to comment
Share on other sites

Ah.. já sei quem és 🙂 És da turma de programação do Michel?

Qual é o nome da tua equipa? A prova era bastante complicada, não foi o ideal para quem estava a participar pela primeira vez...

Sim, sou da turma dele e sou o companheiro de grupo do Michel.  🙂

A prova era complicada de facto, muito mais para quem nunca tinha sequer tentar fazer exercícios daquele género. A verdade é que pelo facto de não ter conseguido resolver um único exercício fiquei com apetite para treinar esse tipo de exercícios de modo a que na próxima vez consiga fazer mais qualquer coisa.

Participar nesse género de concursos dá-nos experiência como programadores, dá-nos experiência no trabalho em equipa, mas acima de tudo faz com que percebamos que somos realmente muito fracos, que pouco ou nada sabemos. E isso motivou-me para começar a por mãos ao trabalho e resolver problemas do género.  😛

P.S.: A minha equipa é a Equinox.  😛

P.S.2: Sim, eu descobri que fazias parte do fórum porque quando acedeste ao teu e-mail vi lá um e-mail que eu próprio tinha enviado relativo à  revista PROGRAMAR e o nick mogers. E associei de imediato.  😄

Link to comment
Share on other sites

A verdade é que pelo facto de não ter conseguido resolver um único exercício fiquei com apetite para treinar esse tipo de exercícios de modo a que na próxima vez consiga fazer mais qualquer coisa.

É esse o espirito 🙂

Caso não tenhas reparado, está aberto um pós-prova onde podemos tentar resolver os exercícios da prova.

Tou a tentar fazer um programa para participar num concurso na 4ª feira, até lá não posso tentar resolver os problemas :\

Btw, na minha opinião, o E é o problema mais fácil, seguido do B. Agora sei resolver o A, não é muito fácil de chegar a solução. O C e o D não sei como resolver dentro do tempo limite...

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

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.