SHAHBG Spoj

Logic :

        In each iteration keep count of groups and when a new person add in chain just see that if its left and right position are empty or not if they both are empty then groups will increase by 1 if both filled then decrease count of group by 1 otherwise nothing.
(Why this approach will work well try to simulate this in your mind or on paper ;) )


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 Line[1000000];

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

int ans = 0;
while(Q--) {
int P;
scanf("%d", &P);
bool Left = false;
bool Right = false;
if(P - 1 > 0 && Line[P - 1]) Left = true;
if(P + 1 <= 20000 && Line[P + 1]) Right = true;

if(Left && Right) {
ans--;
} else if(Left || Right) {
ans += 0;
} else {
ans += 1;
}
Line[P] = true;
printf("%d\n", ans);
}
puts("Justice");
    return 0;
}


Happy Coding :)

UCV2013I Spoj

Logic :

     For this problem only a image is enough to understand logic. 
     Which is

Source: Click Here

now we can apply sine formula to find solution.

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()

{

while(true) {

double r;

double N;

scanf("%lf%lf", &r, &N);

if(r <= 0 || N <= 0) break;

printf("%.2lf\n", r/sin((acos(-1) * 0.5) / N));

}

    return 0;

}

Happy Coding :)

TIPTOP Spoj

Logic : 

           First of all we will try to solve problem using brute force solution.

           

           For Given N find all divisors count them and if count is Odd then answer will be 

           ''Yes"  otherwise "No".

           So finding divisors of a number can take Sqrt(N) time and N can be 10^18 that mean

           time complexity will be O(T*sqrt(N)) which will fail and give time limit exceeded.

           

           Now we will write number of divisors from N = 1 to 50 and then find some pattern.

           (Why 50 well you can take 1000 :P it depend on you)

           

            

     1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6

      now list all number N where count of divisors are odd(Why? Odd well there are so many even numbers so try to find relation from small set)

          N = 1 , count 1

          N = 4,  count 3

          N = 9,  count 3

          N = 16, count 5

          

           I think thats enough to find a relation or pattern , so by looking at N we can say that if count of divisors are odd then that number must be a perfect square number. 

          

           Now our problem reduced to detect that given number is perfect square number or not

           we can apply a standard method for this one which is binary search and also we can try some hack ;) 

          so here we will see only hack approach you can read about binary search and easily apply.

  

        Hack Approach :

              Suppose given number is N , find square root of N which is built in almost all programming languages.

              SQRT_OF_N = sqrt(N)  
              now we knew that if N is perfect square then if we multiply its square root we can get N again otherwise we will get smaller number than N. :D

Below you can see solution (both approaches)

#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 SQRT(long long x) {

double sq = sqrt(x);

long long sq_l = sq;

if(sq_l * sq_l == x) return true;

return false;

}

bool BS(long long x) {

long long low = 1;

long long high = 1e9;

while(high - low >= 2) {

long long mid = (low + high) >> 1;

if(mid * mid >= x) {

high = mid;

} else {

low = mid;

}

}

for(long long i = low; i <= high; ++i) {

if(i*i == x) return true;

}

return false;

}

int main()

{

int T;

scanf("%d", &T);

int t = 1;

while(T--) {

long long N;

scanf("%lld", &N);

printf("Case %d: ", t++);

if(BS(N)) {

puts("Yes");

} else {

puts("No");

}

}

    return 0;

}

Happy Coding :)

            

MKEQUAL

Logic : 

            we can make N - 1 equal easily by choosing a single element for decreasing.

             so according to first statement answer will be atleast N - 1 now if see this test case

             

             N = 4   Arr = {1, 9, 1, 9}
             answer is 4 because we can make 5 by choosing 1, 9 as pair and perform operation.

             

             that mean answer can be N also , now question is when it can be happen and why ?

             

 answer of above question is :

            

              If sum of numbers is divisible by n then all element changed to sum_element/n by 

              choosing two  index one with value greater than sum_element/n and other with

              smaller value at a time.

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 N;

scanf("%d", &N);

long long sum = 0;

for(int i = 0; i < N; ++i) {

long long data;

scanf("%lld", &data);

sum += data;

}

printf("%d\n", N - (sum%N == 0 ? 0 : 1));

}

    return 0;

}