SPOJ Problem ORDSUM23

SUMS OF 2 AND 3

Explanation:

This problem requires you to find out number of ways in which a number 'n' can be written as a sum of 2 and 3, and the easy part is you want all the ways, irrespective of the order of the numbers.

This can be easily done using recursion. For a given 'n', number of ways will become, ways(n) = ways(n-2) + ways(n-3). And, so on.

This can be then converted into a classic DP problem.

Below is the code for reference.

Solution:

#include<iostream>
#include<cstdio>
#define SIZE 1000001
#define LLD long long int
#define MOD 1000000007

int main(){
    LLD arr[SIZE];
    arr[0] = arr[1] = 0;
    arr[2] = arr[3] = 1;
    for(int i=4;i<SIZE;i++){
        arr[i] = (arr[i-2] + arr[i-3]) % MOD;
    }
    int t, a;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &a);
        printf("%lld\n", arr[a]);
    }
    return 0;
}

Any suggestions are welcome. 

SPOJ Problem CCHESS

COSTLY CHESS

Explanation:

The problem requires to find the minimum cost for a knight in chess to reach (c, d), if it starts from (a, b). Cost to reach from (a, b) to (c, d) is calculated as (a * c) + (b * d).

Problem requires simple implementation of BFS. Take a cost matrix of 8x8, with cost of each block set to INFINITY and the cost(a, b) = 0. Using BFS, find the minimum cost of each block which can be reached starting from (a, b).

If the cost(c, d) is still infinity, that means the block (c, d) cannot be reached from (a, b) and hence we should return -1, or else, return the cost(c, d).

Below is the code for reference.

Solution:

#include <iostream>
#include <cstdio>
#include <queue>
#define INF 1000000000
#define inRange(x, y) (x >= 0 && x < 8 && y >= 0 && y < 8)
#define calculateDistance(a, b, c, d) (a * c) + (b * d)

using namespace std;

int mat[8][8];

int findMinimumPath(int a, int b, int c, int d){
    queue<int> q;
    q.push(a);
    q.push(b);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        int y = q.front();
        q.pop();
        int a[] = {-1, -2, -2, -1, 1, 2, 2, 1}, b[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        for(int i=0;i<8;i++){
            int tmpX = x + a[i];
            int tmpY = y + b[i];
            if(inRange(tmpX, tmpY) && mat[tmpX][tmpY] > mat[x][y] + calculateDistance(x, y, tmpX, tmpY)){
                mat[tmpX][tmpY] = mat[x][y] + calculateDistance(x, y, tmpX, tmpY);
                q.push(tmpX);
                q.push(tmpY);
            }
        }
    }
    return ((mat[c][d] == INF) ? -1 : mat[c][d]);
}

void init(){
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            mat[i][j] = INF;
}

int main(){
    int a, b, c, d;
    while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF){
        init();
        mat[a][b] = 0;
        printf("%d\n", findMinimumPath(a, b, c, d));
    }
    return 0;
}

Problem NAKANJ can also be solved using the same strategy. Just need to do few computations.

Any suggestions are welcome. 

SPOJ Problem CRZYSMKR

CRAZY SMOKER

Explanation:

A simple problem which requires li'l bit of modular arithmetics and we are done.
We just need to calculate the results of (34 ^ n) % 11 and (30 * n) % 11. Add 32 to it.

Once we have the result of above calculation, we need to find the minimum number to be added to the above result so that final result becomes equal to (0 % 11). We do it by subtracting it from 11 and taking a modulo 11. Taking modulo 11 helps for the case where n = 0.

Below is the code for reference.

Solution:

#include <iostream>
#include <cstdio>
using namespace std;

long long int mulMod(long long int a, long long int b, long long int c){
    // returns (a * b) % c.
    long long int x = 0, y = a % c;
    while (b) {
        if (b & 1)
            x = (x + y) % c;
        y = (y << 1) % c;
        b >>= 1;
    }
    return (x % c);
}

long long int modPower(long long int a, long long int b, long long int c){
    // returns (a ^ b) % c.
    long long int y = 1;
    while (b) {
        if (b & 1)
            // y = (y * a) % mod;
            y = mulMod(y, a, c);
        // a = (a * a) % mod;
        a = mulMod(a, a, c);
        b >>= 1;
    }
    return y;
}

long long int calculateCigarettes(long long int n){
    return (modPower(34, n, 11) + mulMod(30, n, 11) + 32) % 11;
}

int main() {
    int t;
    long long int n;
    scanf("%d", &t);
    while(t--){
        scanf("%lld", &n);
        printf("%lld\n", (11 - calculateCigarettes(n)) % 11);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem TMSUM

THE MAXIMIZE SUM

Explanation:

Given 'n' number of elements in a set, you need to find the subsets of the set containing maximum of two elements and minimum of one. Once, we have the subsets, we need to find the product of the elements in the subset containing two elements. And, then adding all the found products to the elements of set with size one. Following the process, we need to find the maximum sum at the end and then print. The problem requires li'l bit of recursion which later gets converted into a very simple DP problem. You can find the explanation below.

Now, since we are supposed to find the maximum sum, thus, we can say that the product of two numbers should be maximum (as we are adding the product of two numbers for a 2-element set to get the sum). For that, we need to multiply together, the largest numbers and hence, we can get maximum product. Thus, we can come to a conclusion that, sorting is required here. Once sorted, we have two options now, either we form a 2-element set or 1-element set containing this element.

Let's say, for example.

Set, S = {1, 3, 2}
Once, we have sorted this, we get S' = {1, 2, 3}.

Now, taking every element into consideration, we can have following possible subset combinations.

1. {1}, {2}, {3}
2. {1}, {2, 3}
3. {1, 2}, {3}

Calculating results for above possible combination, we get,

1. 6
2. 7
3. 5

And, as said above, we need to find the product of largest numbers to get the maximum sum, and thus, we can see, we get the maximum sum for case 2, where we find the product of two largest numbers.

Now, let's try to come up with the recursion formula.

Case 1.
Consider, we take ith element ai into a 1-element set, so the sum till ith index, say Si, will be, Si = Si-1 + ai, where Si-1 is the maximum sum till index (i-1).

Case 2.
Consider, we take ith element ai into a 2-element set, so the sum till ith index, say Si, will be, Si = Si-2 + (ai * ai-1), where Si-2 is the maximum sum till index (i-2).

So, the final formula becomes,

Si = max(Si-1 + ai, Si-2 + (ai * ai-1))

Below is the code for reference.

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>

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

using namespace std;

int main(){
 
    int t, n, arr[100];
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);
        if(n == 1){
            printf("%d\n", arr[0]);
            continue;
        }
        if(n == 2){
            printf("%d\n", max(arr[0] * arr[1], arr[0] + arr[1]));
            continue;
        }
        sort(arr, arr + n);
        int sum[100];
        sum[0] = arr[0];
        sum[1] = max(arr[0] * arr[1], arr[0] + arr[1]);
        for(int i=2;i<n;i++)
            sum[i] = max(sum[i-1] + arr[i], sum[i-2] + (arr[i-1] * arr[i]));
        printf("%d\n", sum[n-1]);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem ESYRCRTN

EASY RECURSION

Explanation:

Problem requires to find out the sum of F(1) + F(2) + ... + F(n). Before you go for the solution, I would suggest you to find out the values from 1 to 12, and you will have the result.

Solution:

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long int LLD;

int main(){
    LLD t, n;
    int arr[] = {1, 4, 6, 5, 2, 0};
    scanf("%lld", &t);
    while(t--){
        scanf("%lld", &n);
        printf("%d\n", arr[(n-1) % 6]);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem DOL

LARGEST ODD DIVISOR

Explanation:

Simple problem. Requires just pen and paper to come up with a solution, or not even that. Coming to the point though. For an odd number 'N', answer will be 'N'. Now, for an even integer, we simply need to keep on dividing by 2 until the quotient is even, and thus, removing the even factors from the number.

Solution:

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long int LLD;

LLD findLargestOddDivisor(LLD n){
    while(n % 2 == 0){
        n >>= 1;
    }
    return n;
}

int main() {
    LLD t, n, cas=0;
    scanf("%lld", &t);
    while(t--){
        scanf("%lld", &n);
        printf("Case %lld: %lld\n", ++cas, findLargestOddDivisor(n));
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem OLOLO

ONOTOLE NEEDS YOUR HELP

Explanation:

One of the simplest problem on SPOJ. You just need to find XOR of all the numbers and you have the number which appeared only once.

Solution:

#include<cstdio>
int main(){
    int n,t,a=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        a ^= n;
    }
    printf("%d",a);
    return 0;
}

Any suggestions are welcome.