Greedy Gift Givers - programa crasha

[deathseeker25]

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;
}

[TheDark]

Já fizeste debug para ver onde acontece o erro?

[deathseeker25]

Já fizeste debug para ver onde acontece o erro?

Ao fazer o Debug aparece "An Access Violation (Segmentation Fault) raised in your program". Terá a ver com a quantidade de fors e alocação de elementos em vectores?  🙂

[TheDark]

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 🙂

[deathseeker25]

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.

[mogers]

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);
}

[deathseeker25]

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

[mogers]

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

[deathseeker25]

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

[TheDark]

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.

[mogers]

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 🙂

[deathseeker25]

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

[mogers]

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