SPOJ

Problem Link #include <iostream> #include <cmath> using namespace std; typedef long long ll; int n, m; ll a[101], b[101], c[101], d[101]; ll calculateCoconutsProduced(ll time) { ll coconutsProduced = 0; for(int i = 0; i < n; i++) { coconutsProduced += (time - a[i] >= 0) ? (time - a[i]) / b[i] + 1 : 0; } return coconutsProduced; } ll calculateCoconutsConsumed(ll time) { ll coconutsConsumed = 0; for(int i = 0; i < m; i++) { coconutsConsumed += (time - c[i] >= 0) ? (time - c[i]) / d[i] + 1 : 0; } return coconutsConsumed; } void solve(ll s, ll e) { ll endTime = e; while(s < e) { ll mid = s + (e - s + 1) / 2; ll coconutsProduced = calculateCoconutsProduced(mid); ll coconutsConsumed = calculateCoconutsConsumed(endTime - mid); if(coconutsProduced > coconutsConsumed) { e = mid - 1; } else { s = mid; } } cout << s << endl; } int main() { ll t; cin ...

Problem Link #include <iostream> #include <cmath> using namespace std; struct node { int x, y, pm, sm, pv, sv; node(){} node(int x, int y, int pm, int sm, int pv, int sv) { this->x = x; this->y = y; this->pm = pm; this->sm = sm; this->pv = pv; this->sv = sv; } }; int n; node arr[101]; /* Find out if it is possible to have given number of servings for each ingredient with given money */ bool isServingPossible(int totalServings, int money) { int required = 0; /* check if we can have totalServings of each ingredient */ for(int i = 0; i < n; i++) { required = totalServings * arr[i].x; required -= arr[i].y; int minMoneySpent = 99999999; int limit = ceil(required / (double)arr[i].sm); for(int numSmallItem = 0; numSmallItem <= limit; numSmallItem++) { int totalSmallItem = numSmallItem * arr[i].sm; int numLargeItem = (required > totalSmallItem)? ceil((required - totalSmal...

Problem Link #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int n, f; double radius[10001]; bool isVolumePossible(double p) { int total = 0; for(int i = 0; i < n; i++) { total += (int)floor((M_PI * radius[i]) / p); } if(total >= f + 1) return true; return false; } void solve(double s, double e) { double result = 0.0; for(int i = 0; i < 60; i++) { double mid =  (e + s) / 2.0; if(isVolumePossible(mid)) { s = mid; result = mid; } else { e = mid; } } printf("%.4lf\n", result); } int main() { double maxVolume = 0; int t; cin >> t; while(t--) { cin >> n >> f; memset(radius, 0, sizeof radius); for(int i = 0; i < n; i++) { cin >> radius[i]; radius[i] *= radius[i]; } maxVolume = 4e8; solve(0.0, maxVolume); } return 0; }

Problem Link #include <iostream> #include <algorithm> using namespace std; typedef long long ll; struct Order { ll s; ll e; ll p; Order(){} Order(ll s, ll e, ll p) { this->s = s; this->e = e; this->p = p; } bool operator <(const Order &other) const { return e < other.e; } }; int findLastNonConflictingOrder(Order arr[], int index) { int start = 0; int end = index -1; int result = -1; while(start <= end) { int mid = (start + end) / 2; if(arr[index].s >= arr[mid].e) { result = mid; start = mid + 1; } else { end = mid - 1; } } return result; } void findMaxProfit(Order arr[], int n) { ll dp[n]; dp[0] = arr[0].p; ll profitInclusive, profitExclusive; for(int i = 1; i < n; i++) { profitInclusive = arr[i].p; int j = findLastNonConflictingOrder(arr, i); if(j != -1) { profitInclusive += dp[j]; } profitExclusive = dp[i - 1]...

Problem Link #include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std; void computeSubsetSum(long long arr[], long long result[], int start, int len) { for(int i = 0; i < (1 << len); i++) { for(int j = 0; j < len; j++) { if(i & (1 << j)) { result[i] += arr[start + j]; } } } } int main() { int n; long long a, b; long long arr[35]; cin >> n >> a >> b; int size_lhs = 1 << (n / 2); int size_rhs = 1 << (n - n / 2); long long lhs[size_lhs]; long long rhs[size_rhs]; memset(lhs, 0, sizeof lhs); memset(rhs, 0, sizeof rhs); for(int i = 0; i < n; i++) { cin >> arr[i]; }     /* Divide the set in 2 part n/ 2 element each        and compute sum of subsets for both the part        2^(n/2) + 2^(n / 2) < 2 ^n     */    ...

Problem Link #include <iostream> #include <algorithm> #include <string.h> #include <cmath> using namespace std; const int N = 1e4; int rhs[N]; int lhs[N]; int convertToTernary(long long x, int arr[], int index) {   if(x == 0)   return index;   int remainder = x % 3;   arr[index] = remainder;   x = x / 3;   return convertToTernary(x, arr, index + 1); } long convertToDecimal(int arr[], int len) { long result = 0; long power = 1; int i = 0; while(i < len) { result += arr[i] * power; power *= 3; i++; } return result; } void solve(int arr[],  int len, long maxSum) { int i = 0; int carry = 0; int rlen = 0; while(i < len) { arr[i] += carry; carry = arr[i] / 3; arr[i] = arr[i] % 3; if(arr[i] == 0 || arr[i] == 1) { lhs[i] = 0; } else { lhs[i] = 1; carry = 1; } rhs[i] = (arr[i] + lhs[i]) % 3; i++; } rlen = len; ...

Problem Link #include <iostream> #include <vector> #include <algorithm> using namespace std; long arr[2002]; int binarySearch(int start, int end, int x){ while(end > start){ int mid = (start + end) / 2; if(arr[mid] > x){ end = mid; } else{ start = mid + 1; } } return end; } int main(){ int n, b; long result = 0; while(true){ cin >> n; if(n == 0) break; for(int i = 0; i < n; i++){ cin >> arr[i]; } sort(arr, arr + n); result = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(arr[i] + arr[j] < arr[n - 1]){   /* Find the first element which is greater than sum of two element */ b = binarySearch(i, n - 1, arr[i] + arr[j]); result += (n - b); } } } cout << result << endl; } return 0; }

Problem Link #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int arr[105]; int n, a, b, c, d, e, f, g; vector<long> lhs; // lhs stores result of a * b + c vector<long> rhs; // rhs stores result of d * (e + f) cin >> n; for(int i = 0; i < n; i++){ cin >> arr[i]; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ a = arr[i]; b = arr[j]; c = arr[k]; d = arr[i]; e = arr[j]; f = arr[k]; lhs.push_back((a * b) + c); if(d != 0){ rhs.push_back(d * (e + f)); } } } } sort(lhs.begin(), lhs.end()); sort(rhs.begin(), rhs.end()); vector<long>::iterator it, l1, l2, u1, u2; it = lhs.begin(); long result = 0; while(it != lhs.end()){ l1 = lower_bound(lhs.begin(), lhs.end(), *it); u1 = upper_bound(lhs.begin(), lhs.end(), *it); l2 = lower_b...

Problem Link #include <iostream> using namespace std; int printIntermediateSteps(int s, int t, int i){ if(s > t){ return 0; } if(s == t){ return 1; } int mid = (s + t) / 2; if(i <= mid){ cout << s << " " << mid << endl; return printIntermediateSteps(s, mid, i) + 1; } else{ cout << (mid + 1) << " " << t << endl; return printIntermediateSteps(mid + 1, t, i) + 1; } } int main(){ int t, s, T, i, depth; cin >> T; while(T--){ cin >> s >> t >> i; if(i < s || i > t){ cout << "-1"; continue; } depth = 1; cout << s << " " << t << endl; depth = printIntermediateSteps(s, t, i); cout << depth << endl; } return 0; }

Problem Link #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define sf(i) scanf("%d",&i) #define pf(i) printf("%d ", i) using namespace std; const int N = 10000; int main() {     int t, n, k1, k2, k3;     int arr[N + 1];     int sum[2015];     int index;     long s, val;     sf(t);     while(t--)     {         sf(n), sf(k1), sf(k2), sf(k3);         priority_queue<long, vector<long>, greater<long>> pq;         index = 0;         s = 0;         for(int i = 0; i < n; i++)         {             sf(arr[i]);         }         for(int i = 1; i < n; i++)         { ...

Problem Link #include <iostream> #include <set> #include <cstring> #include <algorithm> using namespace std; #define ll long long const int N = 32768; int main() {     int n, t;     long long arr[N + 1];         cin >> t;     while(t--)     {         cin >> n;         multiset<ll> s;         long long sum[N + 1];         long long element[N + 1];         int maxIndex = 1 << n;         for(int i = 0; i < maxIndex; i++)         {             cin >> arr[i];         }         sort(arr, arr + maxIndex);         if(n == 1)         {             cout << arr[1] ...

Problem Link #include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <set> using namespace std; const int N = 1e5; struct node {     int trainer;     int day;     int sadness;     node()     {     }     node(int t, int d, int s)     {         trainer = t;         day = d;         sadness = s;     } }; bool comparator(node a, node b) {     return a.sadness > b.sadness; } int main() {     long long result;     int test, n, D, d, t, s;     int freq[N + 1], sad[N + 1];     vector<node> v;     node temp;     cin >> test;     while(test--)     {         cin >> n >> D;         memset(fr...

Problem Link #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N = 1001; double ncr[N][N]; void calNCR() {     for(int i = 0; i < N; i++)     {         for(int j = 0; j < N; j++)             ncr[i][j] = 0;     }     for(int i = 0; i < N; i++)     {         ncr[i][0] = ncr[i][i] = 1.0;         for(int j = 1; j < i; j++)         {             ncr[i][j] = ncr[i - 1][j - 1] + ncr[i - 1][j];         }     } } int main() {     int t, s, n, m, k;     calNCR();     cin >> t;     for(int j = 0; j < t; j++)     {         cin >> s >> n >> m >> k;        ...

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 ...