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     */     computeSubsetSum(arr, lhs, 0, n / 2); computeSubsetSum(arr, rhs,

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; if(carry) { rhs[i] = carry;

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++)         {            arr[i] += arr[i - 1];         }         for(int i = 0; i < n; i++)         {             for(int j = i; j < n; j++)             {                 if(i == 0)                 {                     val = arr[j];                 }                

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] << endl;             continue;         }         if(n == 2)         {             cout << arr[1] << " " <<  arr[2] << endl;             continue;         }         int index = 0;         int sumIndex = 0;         for(int i = 1; i < maxIndex; i++)         {             int expected

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(freq, 0, sizeof freq);         memset(sad, 0, sizeof sad);         result = 0;         v.clear();         set<int> daySet;         for (int i = 0; i < D; i++) { daySet.insert(i); }         for(int i = 0; i < n; i++)         {             cin >>

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;         double den = ncr[s - 1][n - 1];         double num = 0;         /* if s = 6, m = 4, n = 4, k = 1. Here 2 people from m will go to the trip for sure.            One of them is Alice, so one more friend will picked up for sure. So we should start checking              probability of picking from 2(mc2) be

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 and it will not cause any problem .     problem may occur if pos[i - 1]< (B -T)*2 as it can me

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 = 0; i < n; i++)         {             arr[i] -= avg;         }         for(int i = 1; i < n; i++)         {             arr[i] += arr[i - 1];         }         long max = 0;         for(int i = 0; i < n; i++)         {             if(max < abs(arr[i]))             {                 max = abs(arr[i]);             }         }         cout << max << endl;     }     return 0; }

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++)         {             dpWithoutDelete[i] = max(arr[i], dpWithoutDelete[i - 1] + arr[i]);         }                 dpWithDelete[1] = max(arr[0], arr[1]);                 for(int i = 2; i < n; i++)         {             dpWithDelete[i] = max(dpWithDelete[i - 1] + arr[i], dpWithoutDelete[i - 1]);         }              

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';             S[i+3] = 'F';         }         i = 0;         while(i < len)         {             if(S[i] == '?')                 S[i] = 'A';             i++;         }         cout << S << endl;     }     re

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 < n; i++)     {         int diff = abs(a[i] - b[i]);         v.pb(mp(i, diff));     }     sort(v.begin(), v.end(), sortByDescDiff);     int index = 0;     for(index = 0; index &

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 ] ] = true ; }

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 += arr[i];         }                 for(int i = k; i < n; i++)         {             sum2 += arr[i];         }                 cout << sum2 - sum1 << endl;             }     return 0; }