ProjectEuler Problem 13

Sep 16, 2010 at 10:12am
I've written algorythm to solve this problem, but i cant recognize, why i keep getting wrong answer...

Here is the problem:
http://projecteuler.net/index.php?section=problems&id=13
"Work out the first ten digits of the sum of the following one-hundred 50-digit numbers."

Here is code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#define wszystkie 100
#define cyfry 50
#define rezerwa 5

int main()
{
    char liczba[cyfry];
    char wynik[cyfry+rezerwa];        
    for(short int i=0 ; i < cyfry+rezerwa ; i++) wynik[i]=0;
    
    for(short int i=1 ; i <= wszystkie ; i++)        
    {
        std::cin>>liczba;
        
        for(short int i=0 ; i < cyfry+rezerwa ; i++)
        {
            if(i < cyfry) wynik[i] = wynik[i] + liczba[i]- 48;
            
            while(wynik[i] >= 10)
            {
                wynik[i+1] += wynik[i]/10;
                wynik[i] = wynik[i]%10;
            }
        }
    }
    
    for(short int i = cyfry+rezerwa-1 ; i >= cyfry+rezerwa-20 ; i--)    
    {
        int dupa = wynik[i];
        std::cout<<dupa<<" ";
    }
    
    std::cout<<"\n";
    return 0;
}

Sorry for polish names of variables.


I'm running this with standard input from file, which contains 100 50-digits numbers each in one line...

Please, help me find a mistake in the code. Thank you.
Sep 16, 2010 at 12:21pm
closed account (EzwRko23)
I get:

5537376230

with:

 
(io.Source fromFile "euler13.txt" getLines).map(BigInt(_)).sum.toString.substring(0, 10)


Have you tested if your code adds numbers correctly? E.g. try it for some simple numbers first and check manually where the error is.

BTW: This can be simplified:
1
2
3
4
5
 while(wynik[i] >= 10)
            {
                wynik[i+1] += wynik[i]/10;
                wynik[i] = wynik[i]%10;
            }


To:
1
2
3
4
5
 if (wynik[i] >= 10)
            {
                wynik[i+1] += 1;
                wynik[i] -= 10;
            }



BTW2: Don't you read the digits in the wrong order? (reversed)? The algorithm assumes wynik[0] is the least significant position, while in the file, the first character is the most significant.
Last edited on Sep 16, 2010 at 12:32pm
Sep 16, 2010 at 12:40pm
You were right.
It was adding digits of these numbers in reversed order.
I've correct it. Thanks.
Sep 16, 2010 at 1:30pm
closed account (EzwRko23)
Nie ma za co. :)
Topic archived. No new replies allowed.