SPOJ Problem BOMARBLE

D - Playing with Marbles

Explanation:

A simple DP problem. I would suggest to work with pen and paper before reading the explanation.

For ith pentagon, we add three edges to the (i-1)th pentagon and for each edge added, we put i marbles. In total, we add (3 * i) marbles. Now remains 1 marble, which needs to be added to the intersection of two edges. Thus, finally we add (3 * i) + 1 to number of marbles in (i-1)th pentagon.

Example is shown for two pentagons.

• New edges added are shown in green.
• 3 * i marbles are shown in blue.
• 1 marble at the intersection is shown in red.

two pentagons

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define SIZE 1001

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

int main(){
 
    vector<LLD> num_of_marbles(SIZE);
    int n;

    // initialize number of marbles for first pentagon.
    num_of_marbles[1] = 5;

    // compute the no. of marbles from second pentagon to thousandth pentagon
    // by adding (3 * i) + 1 to num_of_marbles[i-1].
    for (int i=2;i<SIZE;i++)
        num_of_marbles[i] = num_of_marbles[i-1] + (3 * i) + 1;

    while(true){
        cin >> n;
        if(!n)
            break;
        cout << num_of_marbles[n] << endl;
    }

    return 0;
}

Any suggestions are welcome.