/************************************************
Programmer : Muhammad Azri bin Jasni @ Abdul Rani
Program : project euler problem 13.cpp
Link : http://projecteuler.net/problem=13
Description: Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
Note : I want to know how to install new library into Dev-C++ 4.9.9.2
*************************************************
At first, I thought of a manual addition for each digits. As we can see, 50 digits
go outside the boundary of normal int or even long long[16/32 bits]. So, that\'s what I thought.
I create string array strNumbers[] first because it is such a hassle to write it for each digits.
Made a little loop that
-check each char using substr()
-change it to c-string using .c_str() and
-convert to int using atoi()
-store into the array number[][]
Remember how we do manual addition? We just add up the first digits. If its more than 9, the
excess digits at front will be brought to the next digit summation. I actually don\'t remember
correct mathematical term for that. Just look into the example. You can skip this part if you know already.
///////Example: Skip if you want
19
+11
---
30
---
So yeah, 9+1 = 10. But only 0 being used, while the 1 being brought forward.
In programming, we can do this by using modulus division with 10.
See... 10 divide 10 equals 1 with 0 remainder. If 19 divide 10 results in 1 with remainder of 9.
So, put the remainder first, while the real result being brought forward. That\'s our manual sum algorithm.
Of course, need to remember we do it from right-to-left like reading manga.
///////End example
The storage was into a int array result[] from right to left. This result array should be larger than 50.
But, according to little experiment with paper and pen, even if every numbers here are digits 9 (largest possible combination),
the answers should be around 2 or 3 bits more(52/53), that\'s it. I might be wrong, because at first I used 50 rows of numbers. D:
Change to 100 rows, and there my effort doesn\'t go to waste. YAY. What really interesting is the answer exactly 50 digits.
Oh, we only need the first 10 digits. Because I initalize the array to zeros, I can ignore first zeros,
then check for actual 10 first digits. Gotta display \'em all! ["pika!"]
Phew. Now, I need internet connection to actually post this online. Btw, we can also made summation of chunks of 10 bit digits,
but I won\'t do it. It reduce the total processes, thus reduce time, but I don\'t really check for performance and am lazy.
EDIT: It\'s wrong. =_=;
*/
/*
http://suchideas.com/journal/2007/07/installing-gmp-on-windows/
*/
/*BigInt: http://www.cplusplus.com/forum/lounge/32041/*/
#include <iostream>
#include <string>
using namespace std;
int main()
{
/*Local declaration*/
const int row = 100, column = 50;
string strNumber[] = //the lazy first storage
{
"37107287533902102798797998220837590246510135740250",
"46376937677490009712648124896970078050417018260538",
"74324986199524741059474233309513058123726617309629",
"91942213363574161572522430563301811072406154908250",
"23067588207539346171171980310421047513778063246676",
"89261670696623633820136378418383684178734361726757",
"28112879812849979408065481931592621691275889832738",
"44274228917432520321923589422876796487670272189318",
"47451445736001306439091167216856844588711603153276",
"70386486105843025439939619828917593665686757934951",
"62176457141856560629502157223196586755079324193331",
"64906352462741904929101432445813822663347944758178",
"92575867718337217661963751590579239728245598838407",
"58203565325359399008402633568948830189458628227828",
"80181199384826282014278194139940567587151170094390",
"35398664372827112653829987240784473053190104293586",
"86515506006295864861532075273371959191420517255829",
"71693888707715466499115593487603532921714970056938",
"54370070576826684624621495650076471787294438377604",
"53282654108756828443191190634694037855217779295145",
"36123272525000296071075082563815656710885258350721",
"45876576172410976447339110607218265236877223636045",
"17423706905851860660448207621209813287860733969412",
"81142660418086830619328460811191061556940512689692",
"51934325451728388641918047049293215058642563049483",
"62467221648435076201727918039944693004732956340691",
"15732444386908125794514089057706229429197107928209",
"55037687525678773091862540744969844508330393682126",
"18336384825330154686196124348767681297534375946515",
"80386287592878490201521685554828717201219257766954",
"78182833757993103614740356856449095527097864797581",
"16726320100436897842553539920931837441497806860984",
"48403098129077791799088218795327364475675590848030",
"87086987551392711854517078544161852424320693150332",
"59959406895756536782107074926966537676326235447210",
"69793950679652694742597709739166693763042633987085",
"41052684708299085211399427365734116182760315001271",
"65378607361501080857009149939512557028198746004375",
"35829035317434717326932123578154982629742552737307",
"94953759765105305946966067683156574377167401875275",
"88902802571733229619176668713819931811048770190271",
"25267680276078003013678680992525463401061632866526",
"36270218540497705585629946580636237993140746255962",
"24074486908231174977792365466257246923322810917141",
"91430288197103288597806669760892938638285025333403",
"34413065578016127815921815005561868836468420090470",
"23053081172816430487623791969842487255036638784583",
"11487696932154902810424020138335124462181441773470",
"63783299490636259666498587618221225225512486764533",
"67720186971698544312419572409913959008952310058822",
"95548255300263520781532296796249481641953868218774",
"76085327132285723110424803456124867697064507995236",
"37774242535411291684276865538926205024910326572967",
"23701913275725675285653248258265463092207058596522",
"29798860272258331913126375147341994889534765745501",
"18495701454879288984856827726077713721403798879715",
"38298203783031473527721580348144513491373226651381",
"34829543829199918180278916522431027392251122869539",
"40957953066405232632538044100059654939159879593635",
"29746152185502371307642255121183693803580388584903",
"41698116222072977186158236678424689157993532961922",
"62467957194401269043877107275048102390895523597457",
"23189706772547915061505504953922979530901129967519",
"86188088225875314529584099251203829009407770775672",
"11306739708304724483816533873502340845647058077308",
"82959174767140363198008187129011875491310547126581",
"97623331044818386269515456334926366572897563400500",
"42846280183517070527831839425882145521227251250327",
"55121603546981200581762165212827652751691296897789",
"32238195734329339946437501907836945765883352399886",
"75506164965184775180738168837861091527357929701337",
"62177842752192623401942399639168044983993173312731",
"32924185707147349566916674687634660915035914677504",
"99518671430235219628894890102423325116913619626622",
"73267460800591547471830798392868535206946944540724",
"76841822524674417161514036427982273348055556214818",
"97142617910342598647204516893989422179826088076852",
"87783646182799346313767754307809363333018982642090",
"10848802521674670883215120185883543223812876952786",
"71329612474782464538636993009049310363619763878039",
"62184073572399794223406235393808339651327408011116",
"66627891981488087797941876876144230030984490851411",
"60661826293682836764744779239180335110989069790714",
"85786944089552990653640447425576083659976645795096",
"66024396409905389607120198219976047599490197230297",
"64913982680032973156037120041377903785566085089252",
"16730939319872750275468906903707539413042652315011",
"94809377245048795150954100921645863754710598436791",
"78639167021187492431995700641917969777599028300699",
"15368713711936614952811305876380278410754449733078",
"40789923115535562561142322423255033685442488917353",
"44889911501440648020369068063960672322193204149535",
"41503128880339536053299340368006977710650566631954",
"81234880673210146739058568557934581403627822703280",
"82616570773948327592232845941706525094512325230608",
"22918802058777319719839450180888072429661980811197",
"77158542502016545090413245809786882778948721859617",
"72107838435069186155435662884062257473692284509516",
"20849603980134001723930671666823555245252804609722",
"53503534226472524250874054075591789781264330331690"
};
int number[row][column];//the real storage array
for (int i=0;i<row;i++)
{
for (int j=0;j<column;j++)
{
number[i][j]=atoi( strNumber[i].substr(j,1).c_str() );
}
}
const int resultSize = 54;//result array size
int result[resultSize]={}, counter = resultSize-1;//the result storage and counter for moving about, this count may actually not required
long sumCounter = 0;
/*END Local declaration*/
for (int j=column-1;j>=0;j--,counter--)
{
for (int i=0;i<row-1;i++)
{
sumCounter = sumCounter + number[i][j] + number[i+1][j];
result[counter]= sumCounter%10;
sumCounter = sumCounter/10;
}
}
/*
//If you want to display the whole result including zeros
for (int i =0; i<resultSize;i++)
{
cout << result[i];
} cout << endl;
//
*/
int count = 0;//check only first 10 digit
bool firstCounter = true; //counter to make sure it is the leading zeros.
for (int j=0;j<resultSize,count<10;j++)
{
if (result[j]==0 && firstCounter)//skip zeros
continue;
else
{
if (firstCounter)
firstCounter = false;//This is required to debug error of removing results zeros
//althought the answer still correct without this, right algorithm still important
cout << result[j];
count++;
}
}
cout << endl;
/*These lines below are the cross-platform alternative to getch()*/
//cin.ignore(1110,\'\\n\'); //needed only when have input to remove our "ENTER" = \'\\n\'
cin.get();
return 0;
}