SPOJ

Problem Link /* explanation     lets solve the problem only for 2 chicken.     s[i] = speed of chicken i     pos[i] = position of chicken i     if s[i] > s[i - 1] then no problem, just check whether both can reach b within time or not.     if s[i] < s[i - 1] then there is a chance that i can slow down i - 1.     lets say s[i] = 1 m/sec and s[i - 1] = 2 m/sec and time limit is T and point to reach is B.     for s[i] pos[i] can be at max B - T. if pos is greater than B-T it can not reach within Tsec.     and for s[i - 1] pos[i - 1] can be at max (B-T)*2. if pos[i - 1] > (B-T)*2 it can not reach within Tsec.     at T sec i will be at B and i - 1 will also be at B. at T - 1 i will be at B-T-1 and i-1 will be at B-T-2 and so on. as we can see i -1 will always be behind i. so there will not be any collision.     if i is pos[i] < B-T then i can reach B before T sec ...

Problem Link Ref Link #include <iostream> #include <cmath> using namespace std; int main() {     int n;     int arr[9001];     long sum;     while(cin >> n)     {         sum = 0;         if(n == -1)         {             break;         }         for(int i = 0; i < n; i++)         {             cin >> arr[i];             sum += arr[i];         }         long avg = sum / n;         if(avg * n != sum)         {             cout << "-1\n";             continue;         }         for(int i ...

Problem Link #include <iostream> #include <algorithm> using namespace std; const int N = 1e5; void read(int s, int e, long arr[]) { for(int i = s; i < e;  i++) { cin >> arr[i]; } } int main() { int t, n, k, m; long result; long diff[N + 1], completed[N + 1], planned[N + 1], white[N + 1], black[N + 1], arr[2 * N + 1]; cin >> t; while(t--) { cin >> n >> k >> m; result = 0; read(0, n, planned); read(0, n, completed); read(0, k, arr); read(k, k + m, arr); for(int i= 0; i < n; i++) { diff[i] = planned[i] - completed[i]; } int index = k + m; sort(diff, diff + n, greater<long>()); sort(arr, arr + index, greater<long>()); int i = 0; int j = 0; while(i < index && j < n) { if(arr[i] <= diff[j]) { result += diff[j] - arr[i]; i++; j++; } else { i++; } } while(j < n) ...

Problem Link #include <iostream> #include <cstring> using namespace std; const int N = 100000; long long dpWithDelete[N + 1], dpWithoutDelete[N + 1]; int main() {     int t, n;     long long arr[N + 1];     long long maxVal;     cin >> t;     while(t--)     {         cin >> n;         for(int i = 0; i < n; i++)         {             cin >> arr[i];         }         memset(dpWithDelete, 0, sizeof dpWithDelete);         memset(dpWithoutDelete, 0, sizeof dpWithoutDelete);         dpWithDelete[0] = dpWithoutDelete[0] = arr[0];         maxVal = arr[0];                 for(int i = 1; i < n; i++)         {     ...

Problem Link #include <iostream> #include <cstdio> #include <cstring> using namespace std; int main() {     int t, index;     char S[2014];     cin >> t;     while(t--)     {         scanf("%s", S);         int len = strlen(S);         int i;         for(i = len - 4; i >= 0; i--)         {             if(!(S[i]=='C' || S[i]=='?')) continue;             if(!(S[i+1]=='H' || S[i+1]=='?')) continue;             if(!(S[i+2]=='E' || S[i+2]=='?')) continue;             if(!(S[i+3]=='F' || S[i+3]=='?')) continue;             S[i] = 'C';             S[i+1] = 'H';             S[i+2] = 'E...

Problem Link #include <iostream> #include <vector> #include <algorithm> using namespace std; #define pb push_back #define pi pair<int, int> #define mp make_pair bool sortByDescDiff(const pair<int, int> &p1, const pair<int, int> &p2) {     return p1.second > p2.second; } int main() {     int n, x, y;     int a[100001], b[100001];     long result = 0;     // stores absolute difference between tip gained by a and b     //first element in pair is order number and second is difference in tip     vector<pi> v;     cin >> n >> x >> y;     for(int i = 0; i < n; i++)     {         cin >> a[i];     }     for(int i = 0; i < n; i++)     {         cin >> b[i];     }     for(int i = 0; i ...

Problem Link #include <iostream> #include <cstring> #include <algorithm>   using namespace std;   int main ( ) { int t, n, m, res, victim; int c [ 401 ] ; int lastUse [ 401 ] ; int seenBefore [ 401 ] ; bool present [ 401 ] ;   cin >> t; while ( t-- ) { cin >> n >> m; memset ( present, false , sizeof present ) ; memset ( seenBefore, 0 , sizeof seenBefore ) ;   for ( int i = 0 ; i < m; i++ ) { cin >> c [ i ] ; lastUse [ c [ i ] ] = i; }   int order = 0 ; res = 0 ; while ( ( res < n || present [ c [ order ] ] ) && order < m ) { if ( !present [ c [ order ] ] ) { res++; present [ c [ order ] ] = t...

Problem Link #include <iostream> #include <algorithm> using namespace std; int arr[101]; int main() {     int t, n, k;     long sum1, sum2, res;         cin >> t;     while(t--)     {         cin >> n >> k;         for(int i = 0; i < n; i++)         {             cin >> arr[i];         }                 if(k > n / 2)         {             k = n - k;         }                 sort(arr, arr + n);         sum1 = sum2 = 0;                 for(int i = 0; i < k; i++)         {             sum1 ...

Problem Link #include <iostream> #include <algorithm> using namespace std; #define LL long long const int N = 100000; int main() {     LL n , d;     LL arr[N + 1];     int p = 0;     cin >> n >> d;     for(int i = 0; i < n; i++)     {         cin >> arr[i];     }     sort(arr, arr + n);     for(int i = 0; i < n - 1;)     {         if(arr[i + 1] - arr[i] <= d)         {             p++;             i += 2;         }         else             i++;     }     cout << p << endl;     return 0; }

Problem Link #include <iostream> #include <cstring> #include <cstdio> using namespace std; #define LL long long #define sf(i) scanf("%d", &i) #define sl(i) scanf("%ld", &i) const LL N =  5000000; const LL MOD = 1000000007; bool isPrime[N + 1]; LL prime[N + 1]; LL dp[N + 1]; void sieve() { memset(isPrime, true, sizeof isPrime); for(LL i = 2; i * i <= N; i++) { if(isPrime[i]) { for(LL j = i * i; j <= N; j += i) { isPrime[j] = false; } } } isPrime[1] = false; prime[0] = 0; for(LL i = 1; i <= N; i++) { prime[i] = (prime[i-1] + (isPrime[i] ? 1 : 0)); } } void init() { dp[1] = 1LL; for(LL i = 2; i <= N; i++) { dp[i] = ((dp[i - 1] % MOD) * (1 + prime[i])) % MOD; } } int main() { int t; LL n; sieve(); init(); sf(t); while(t--) { sl(n); printf("%lld\n", dp[n]); } return 0; }

Problem Link #include <iostream> #include <cstring> #include <cstdio> using namespace std; #define LL long long #define sf(i) scanf("%d", &i) #define pf(i) printf("%d ", i); const int N = 1000000; const int M = 100000; int leastPrime[N + 1]; bool prime[N + 1]; int arr[M + 1]; int seg[3 * M]; void sieve() {     memset(prime, true, sizeof prime);    for(int i = 0; i <= N; i++)    {        leastPrime[i] = N;    }     for(int i = 2; i * i <= N; i++)     {         if(prime[i])         {             for(int j = i * i; j <= N; j += i)             {                 prime[j] = false;                 leastPrime[j] = min(i, leastPrime[j]);           ...

Problem Link #include <iostream> #include <cstring> using namespace std; const int N = 100000; int div1[N + 1]; int dp[N + 1][6]; void sieve() {     memset(div1, 0, sizeof div1);     for(int i = 2; i <= N; i++)     {         if(div1[i] == 0)         {             for(int j = i; j <= N; j += i)             {                 div1[j]++;             }         }     } // precompute number of k-prime before i     for(int i = 2; i <= N; i++)     {         for(int k = 1; k <= 5; k++)         {             dp[i][k] = dp[i - 1][k] + (div1[i] == k?1:0);         }     } } int main() {   ...

Problem Link #include <iostream> #include <cstring> #include <cmath> #include <vector> using namespace std; #define LL long long const int N = 1000010; bool prime[N + 1]; vector<int> v; void sieve() { for(int i = 2; i <= N; i++) { prime[i] = true; } for(int i = 2; i * i <= N; i++) { if(prime[i]) { for(int j = i * i; j <= N; j += i) { prime[j] = false; } } } v.push_back(2); for(int i = 3; i <= N; i += 2) { if(prime[i]) { v.push_back(i); } } } LL getNumDiv(LL num) {     /* if prime factor of n is p1^k1 p2 ^ k2 then prime factor of n^2 would be         (p1^k1 p2 ^ k2)^2 = p1^(2k1) p2^(2k2)         so number of divisors of n^2 would be (2 * k1 + 1) * (2 * k2 + 1) ...         if n is a prime number number then number of divisors of n^2 would be 3.     */ LL res = 1; for(int i = 0;...

Problem Link #include <iostream> #include <vector> #include <cstring> using namespace std; #define LL long long int LL lucas(LL n,LL r,LL p) { LL ans=1,ncr[p][p]; memset(ncr, 0, sizeof ncr); for (int i = 0; i < p; ++i) { ncr[i][0]=1; } for (int i = 1; i < p; ++i) { for (int j = 1; j <= i; ++j) { ncr[i][j]=(ncr[i-1][j] + ncr[i-1][j-1])%p; } } while(n && r) { ans=(ans * ncr[n%p][r%p])%p; n/=p; r/=p; } return ans; } LL fastExpo(LL a, LL b, LL P) {   LL res = 1;   if(b==0) return 1; if(b==1) return a;   while (b) {     if (b & 1) {       res = (res * a) % P;     }     a = (a * a) % P;     b = b >> 1;   }   return res; } int main() { int t; cin>>t; while(t--) { long long int n,r,m,tm,ans=0; cin>>n>>r>>m; tm=m; for (int i = 2; i <= 50; ++i...

Ref Link1 Ref Link2 #include <bits/stdc++.h> using namespace std; #define ULL unsigned long long ULL mod = 1000000007; void mul(ULL a[][2] , ULL b[][2]) {     ULL result[2][2];     memset(result , 0 , sizeof result);     for(int row = 0; row < 2; row++)     {         for(int col = 0; col < 2; col++)         {             for(int k = 0; k < 2; k++)             {                 result[row][col] = (result[row][col] + (a[row][k] * b[k][col]) % mod) % mod;             }         }     }     for(int row = 0; row < 2; row++)     {         for(int col = 0; col < 2; col++)         {             a[row][col] = result[row][...

Ref Link #include <iostream> using namespace std; #define LL long long LL fastExpo(LL a, LL b, LL mod) {     LL x = 1;     LL y = a;     while(b > 0)     {         if(b & 1)         {             x = (x * y) % mod;         }         y = (y * y) % mod;         b = b >> 1;     }     return x; } int main() {     int t;     LL n, p, i, temp;     LL result = - 1;     cin >> t;     while(t--)     {         cin >> n >> p;         result = -1;         temp = 1;         if(n >= p)         {             cout << "0\n";     ...