Spoj FANCY

LOGIC:

For this problem we will try a mathematical approach first analyze given examples that how we can apply mathematical formulas for given input.

N = 12345
there is only one way to represent this string which is One 1, One 2, One 3, One 4, One 5

N = 11112
there are 8 way to represent this string which are :
        One 1, One 1, One 1, One 1, One 2
        One 1, One 1, Two 1, One 2
        One 1, Three 1, One 2
        Four 1, One 2
        One 1, Two 1, One 1, One 2
        Three 1, One 1, One 2
        Two 1, One 1, One 1, One 2
        Two 1, Two 1, One 2
in above example we can see that 2 occurred 1 time so  there is only 1 arrangement for 2,
now analyze for 1 , 1 occurred 4 time so we can represent it in 8 ways , now question is why?
as we know we can decompose 4 in 8 ways like:
       1 + 1 + 1 + 1
       1 + 1 + 2
       1 + 2 + 1
       1 + 3
       4
       2 + 1 + 1
       2 + 2
       3 + 1
       so here problem is in how many ways we can split K where K is some number here K = 4
Well this standard problem and you can find solution using two methods 1. Pattern recognition 2. Combinatorics

1. Pattern recognition :-
               N = 1      Ways  -> 1
               N = 2      Ways  -> 2
               N = 3      Ways  -> 4
               N = 4      Ways  -> 8
            we can find Ways using pen paper and by looking pattern we can say that it can be 
            2 ^ (N - 1)     ::where  ^ is power sign
            but this is trial and error method and no proof of its correctness 

2. Combinatorics:-  
              N = 1    Ways   ->   0 C 0 = 1
              N = 2    Ways   ->   1 C 0 + 1 C 1 = 2
              N = 3    Ways   ->   2 C 0 + 2 C 1 + 2 C 2 = 4
              N = 4    Ways   ->   3 C 0 + 3 C 1 + 3 C 2 + 3 C 3 = 8
              :: Where nCr mean ways to choose r items from n items  n! / (r! n-r!)   where '!' 
             mean factorial
             so for some N it will be (N - 1) C 0 + (N - 1) C 1 + ..... + (N - 1) C (N - 1) and we know                    that it is equal to 2 ^ (N - 1) (Need proof then google it ;) ) 
             Well why we choose N - 1 is homework for readers :D


Now we can find ways for single element which occurring continuously K time which is 2 ^ (K - 1)
but in our problem we have many elements which are occurring.
so suppose N = a1 a2 ....aK1 b1 b2 b3 ... bK2 c1 c2 c3 ... cK3
then first of all we will find 2 ^(K1 - 1) , 2 ^ (K2 - 1), 2 ^ (K3 - 1) independently all ways in which we can arrange and then we will multiply them because order will not change
so answer will be 2 ^ (K1 - 1) * 2 ^(K2 - 1) * 2^(K3 - 1).

Below you can see code also   

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
char Str[50];
scanf("%s", Str);
int len = strlen(Str);
int cnt = 0;
int ans = 1;
for(int i = 0; i < len; ++i) {
if(i == 0) {
cnt = 1;
} else {
if(Str[i] == Str[i - 1]) {
cnt++;
} else {
ans *= (1 << (cnt - 1));
cnt = 1;
}
}
}
if(cnt > 0)
ans *= (1 << (cnt - 1));
printf("%d\n", ans);
}
    return 0;
}


Happy Coding :)
       

Spoj PUCMM210

LOGIC:

As we already have our strategy first try to write brute force solution if you are unable to figure out optimized solution.
Here brute force solution will look like:

Function(N) {
          For i = 1 to N {
                F_value_at_i  += (i * i * i)
                S_value_at_i  += (S_value_at_i_minus_1 + F_value_at_i)
                Take mode if required
         }
         return S_value_at_N
}

so we can always call Function(N) for each test case so time complexity will be O(N * T)
and it can be huge because N is at most 10^6 and T is at most 10^5 so it will be timeout.

If we look at Function we can say that we are doing repeated work so to remove repetition we will precompute and keep in cache. (Basic of DP(Dynamic Programming) :) )

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

#define MXN 1000000
#define MOD 1000000003
long long F[MXN + 2];
long long Sum[MXN + 2];

int main()
{
Sum[0] = F[0] = 0;
for(int i = 1; i <= MXN; ++i) {
long long temp = i;
temp *= i;
if(temp >= MOD) 
temp %= MOD;
temp *= i;
if(temp >= MOD)
temp %= MOD;
F[i] = F[i - 1] + temp;
if(F[i] >= MOD)
F[i] %= MOD;

Sum[i] = Sum[i - 1] + F[i];
if(Sum[i] >= MOD)
Sum[i] %= MOD;
}

int T;
scanf("%d", &T);

while(T--) {
int N;
scanf("%d", &N);
printf("%lld\n", Sum[N]);
}

    return 0;
}



Happy Coding :)

Spoj MAY99_3

Logic:

So when we start to solve a problem first approach should always be brute force solution if we have no idea about problem's optimized solution, so for this problem brute force solution will be a recursion function where we try all possible cases and if we get our expected solution then return YES otherwise go on.
Now here question is when we will stop or what will be our termination condition well in this problem if we reach again same condition then we stop.

pseudocode of recursive function:-

Function(Water_in_JugA, Water_in_JugB) {
              //We can fill any jug completely 
              Answer = Function(Fill_Full_JugA, Water_in_JugB)
              Answer = Answer or Function(Water_in_JugA, Fill_Full_JugB)
             
              //We can empty any jug entirely 
             Answer = Answer or Function(0, Water_in_JugB)
             Answer = Answer or Function(Water_in_JugA, 0)

            //Transfer as much water from Jug A to Jug B, till Jug A gets empty or Jug B is completely filled or vice versa
            
            Answer = Answer or Function(Fill_JugA_until_JugA_Full_or_JugB_empty, Water_in_JugB - how much water we use to fill JugA)
            Answer = Answer or Function(Water_in_JugA - how much water we use to fill JugB, Fill_JugB_until_JugB_Full_or_JugA_empty) 
  
}

Now someone will say hey it will take O(Limit_of_JugA * Limit_of_JugB)
and that mean it will be O(10^16) because at most Limit_of_JugA can be 10^8
and yes he is right.
Now again question arise that then how we can solve it well our solution is in brute force solution
try some cases using above function and analyze it.

................ (analyzing :P)

 so when we analyze our brute force solution most critical point here is third one transfer water from A/B to B/A which can be write down as F(A, B) -> F(min(A + B, A), B - min(A, A + B)) and using other two points we can always fill one of our jug so now if we can find domain of elements we can get in our brute force solution then we can insure that we can get solution or not.
look this sequence if you find any relation

try some examples for F(A, B) -> F(min(A + B, A), B - min(A, A + B))

F(2, 5) -> F(2, 3) -> F(2, 1)

F(5, 2) -> not a valid state

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0)

so if you see sequence closely you get it solution right.
someone will say no its okay for more we will try to examine our equation

F(A, B) -> F(min(A + B, A), B - min(A, A + B))
as we know if A > B then there will be no more steps but we can swap B, A right
now again why? (read problem again and convenience yourself that we can :D )

so we can right that A < B
F(A, B) -> F(min(A + B, A), B - min(A, A + B))
and if A > B then
F(B, A) -> F(min(A + B, B), A - min(B, A + B))

now again try examples
F(2, 5) -> F(2, 3) -> F(2, 1) -> F(1, 2) -> F(1, 1) -> F(1, 0) -> F(0, 1)

F(5 , 2) -> F(2, 5) same sequence

F(3, 9) -> F(3, 6) -> F(3, 3) -> F(3, 0) -> F(0, 3)

now again we analyze this sequence we can say that F(A, B) -> F(A , KA - B) or vice versa
that mean we can get expected water in any jug if it is equal to any factor of their Limit's gcd
for more details on GCD  read  wikipage. :D

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
int x;
int y;
int z;
scanf("%d%d%d", &x, &y, &z);
if(max(x, y) < z) {
puts("NO");
} else if (z % __gcd(x, y) == 0){
puts("YES");
} else {
puts("NO");
}
}
    return 0;
}


Happy Coding :)

Spoj IEEEBGAM

Logic:

Problem is not written very well so many people didn't get that simple problem's problem. ;)
So basically problem is that you have N boxes , N White and N black Balls and you need to put all 2N balls in boxes where after putting them all boxes contains at least one ball and you need to find an arrangement where if you pick a box and a ball probability should be maximum for that ball's color is white.
Whenever you think about probability problems just remember that
Px = satisfied samples / Total Samples  ::where Px mean probability of x occur in Total samples
Now here we can see that if one factor is constant and other are change eg. satisfied samples increase or Total samples decreased then our probability will increase.
So Suppose we pick an arrangement where in N - 1 boxes we put 1 white ball  now we have 1 white ball and N black balls put them in last box and find probability of this arrangement
 = 1/1 + 1/1 + 1/1 + ... + N - 1 times + 1/(N + 1)
 = N / (N + 1)
and we can see that this is maximum probability in any arrangement we can get.
if you still in confuse try some examples and try to convince yourself(Most important part in Coding world :) )


Below Code you can see also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
int N;
scanf("%d", &N);
double wh = N;
double ans = wh / (wh + 1);
printf("%.8f\n", ans);
}
    return 0;
}



Happy Coding :)

Spoj ELEVTRBL

You can read problem here

Logic:

First of all we will try brute force solution because we can do this better than anyone. ;)
So brute force solution will be simple recursion function where on each floor we have 2 choices
1. Go Up if we can
2. Go Down if we can
so our code will look like

Function(step) {
          IF step + UpJump <= HighestFloor:
               Function(step + UpJump)
         
          IF step - Down > 0:
               Function(step - Down)
}

Now here question is how we can halt this recursion so this question is easy if we already visited this floor that mean we traverse a loop and come back again so no need to go further, here we can use Vis array for this information that we already visited or not.
Now here again we will get in stuck because of memory issue first think why we will stuck here and then think solution also. :P


Below code you can see also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

int Limit;
int Start;
int Goal;
int Up;
int Down;

bool Vis[1000006];
int Dis[1000006];

void bfs(int vertex, int depth) {
Vis[vertex] = true;
Dis[vertex] = depth;
queue<int> Q;
Q.push(vertex);
while(!Q.empty()) {
vertex = Q.front();
Q.pop();
if(vertex == Goal) return;
if(vertex + Up <= Limit && !Vis[vertex + Up]) {
Q.push(vertex + Up);
Dis[vertex + Up] = Dis[vertex] + 1;
Vis[vertex + Up] = true;
}
if(vertex - Down > 0 && !Vis[vertex - Down]) {
Q.push(vertex - Down);
Dis[vertex - Down ] = Dis[vertex] + 1;
Vis[vertex - Down ] = true;
}
}
}

int main()
{
scanf("%d%d%d%d%d", &Limit, &Start, &Goal, &Up, &Down);
bfs(Start, 0);
if(Vis[Goal]) {
printf("%d\n", Dis[Goal]);
} else {
printf("use the stairs\n");
}
    return 0;
}

Spoj SPCQ

LOGIC:

You should need to convince yourself that after some iterations surely you will get your answer.
Now here question is why?
Answer of this question is that there can be maximum 18-19 digits that mean maximum number
can be '9' 18-19 times so sum of this will be 9 * 19 = 171 maximum, so we can be sure that if  we
start increase a number from Number + 1,  Number + 2, .... Number + 171 so at most 171 iteration will be required to get answer :)
     
Below you can see code also


#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

bool SUM_OF_DIG(unsigned long long num) {
unsigned long long temp = num;
int sum = 0;
while(num > 0) {
sum += (num%10);
num /= 10;
}
return (temp%sum == 0);
}

int main()
{
int T;
scanf("%d", &T);

while(T--) {
unsigned long long N;
scanf("%llu", &N);
for(; ; ) {
if(SUM_OF_DIG(N)) {
printf("%llu\n", N);
break;
}
N++;
}
}
    return 0;
}


happy coding :)