Codeforces. 1336B Xenia and Colorful Gems

1.Problem
https://codeforces.com/contest/1336/problem/B

2.Idea
Assuming x <= y <=z.
Enumerating middle value, and find smallest and biggest value by binary_search.

3.Source

 int nr, ng, nb;  
 ll ans = 1LL << 60;  
 ll calc(ll x, ll y, ll z)  
 {  
      return (x - y)*(x - y) + (y - z)*(y - z) + (x - z)*(x - z);  
 }  
 void solve(vector<int> a, vector<int> b, vector<int> c) {  
      for (auto x : a) {  
           auto y = lower_bound(b.begin(), b.end(), x);  
           auto z = upper_bound(c.begin(), c.end(), x);  
           if (y == b.end() || z == c.begin()) { continue; }  
           z--;   
           ans = min(ans, calc(x, *y, *z));  
      }  
 }  
 int main()  
 {  
      int t; cin >> t;  
      while (t--) {  
           ans = 1LL << 62;  
           cin >> nr >> ng >> nb;  
           vector<int> r(nr), g(ng), b(nb);  
           for (int i = 0; i < nr; i++) {  
                cin >> r[i];  
           }  
           for (int i = 0; i < ng; i++) {  
                cin >> g[i];  
           }  
           for (int i = 0; i < nb; i++) {  
                cin >> b[i];  
           }  
           sort(r.begin(), r.end());  
           sort(g.begin(), g.end());  
           sort(b.begin(), b.end());  
           solve(r, g, b);  
           solve(r, b, g);  
           solve(g, r, b);  
           solve(g, b, r);  
           solve(b, g, r);  
           solve(b, r, g);  
           cout << ans << endl;  
      }  
      return 0;  
 }  

POJ.3484 Showstopper

1.Problem
http://poj.org/problem?id=3484

2.Idea
Binary Search

3.Source

 #define MAXN 1000006  
 ll x[MAXN], y[MAXN], z[MAXN];  
 int n;  
 char A[MAXN];  
 bool init() {   
      n = 0;       
      bool f = false;       
      while ((f = (gets_s(A) != NULL)) && strlen(A) > 0)   
      {   
           sscanf(A, "%lld %lld %lld", &x[n], &y[n], &z[n]);  
           n++;   
      }       
      return f || n;   
 }  
 ll C(ll m)  
 {  
      ll sum = 0;  
      for (int i = 0; i < n; i++) {  
           if (m < x[i]) continue;  
           ll t = min(m, y[i]);  
           sum += ((t - x[i]) / z[i] + 1);  
      }  
      return sum;  
 }  
 void solve()  
 {  
      if (n == 0) return;  
      ll l = 0;  
      ll r = 1LL << 32;  
      while (r - l > 1) {  
           ll m = (l + r) / 2;  
           if (C(m) & 1) {  
                r = m;  
           }  
           else {  
                l = m;  
           }  
      }  
      if (r == 1LL << 32) cout << "no corruption" << endl;  
      else cout << r << " " << C(r) - C(r - 1) << endl;  
 }  
 int main()  
 {  
      while (init()) {  
           solve();  
      }  
      return 0;  
 }  

POJ.1759 Garland

1.Problem
http://poj.org/problem?id=1759

2.Idea
Binary_Search by 0<=h[2]<=INF.
h[n+1] = 2 * h[n] - h[n-1] + 2

3.Source

 int N;  
 double A;  
 double B = 1000000000.0;  
 bool C(double x)  
 {  
      double a3, a2, a1;  
      a2 = x;  
      a1 = A;  
      for (int i=0; i < N - 2; i++) {  
           a3 = 2.0 * a2 - a1 + 2.0;  
           if (a3 < 0) return false;  
           a1 = a2;  
           a2 = a3;            
      }  
      if (a2 < B) B = a2;  
      return true;  
 }  
 void solve()  
 {  
      double r = A;  
      double l = 0.0;  
      for(int i=0;i<100;i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                r = m;  
           }  
           else {  
                l = m;  
           }  
      }  
      cout << fixed << std::setprecision(2) << B << endl;  
 }  
 int main()  
 {  
      cin >> N >> A;  
      solve();  
      return 0;  
 }  

POJ.3685 Matrix

1.Problem
http://poj.org/problem?id=3685

2.Idea
Binary Search + Binary Search

3.Source

 #define MAX_N 50010  
 ll N, M;  
 ll getVal(ll i, ll j)  
 {  
      return i*i + 100000 * i + j * j - 100000 * j + i * j;  
 }  
 bool C(ll x)  
 {  
      ll cnt = 0;  
      for (ll j = 1LL; j <= N; j++) {  
           ll l = 0;  
           ll r = N + 1;  
           while (r - l > 1) {  
                ll m = (l + r) / 2;  
                if (getVal(m, j) < x) {  
                     l = m;  
                }  
                else {  
                     r = m;  
                }  
           }  
           cnt += l;  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      ll r = MAX_N * MAX_N * 3 + MAX_N * 100000 * 2;  
      ll l = -r;  
      while(r - l > 1) {  
           ll m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%lld\n", l);  
 }  
 int main()  
 {  
      int t;  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%lld%lld", &N, &M);  
           solve();  
      }  
      return 0;  
 }  

POJ.3579 Median

1.Problem
http://poj.org/problem?id=3579

2.Idea
Binary Search + Lower_Bound

3.Source

 int N;  
 ll M;  
 int x[100005];  
 bool C(int f)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           cnt += lower_bound(x + i + 1, x + N, x[i] + f) - (x + (i + 1));  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      sort(x, x + N);  
      M = (ll)N * (N - 1) / 2;  
      if (M % 2) M = M / 2 + 1;  
      else   M = M / 2;  
      int l = 0;  
      int r = 1000000010;  
      while(r - l > 1) {  
           int m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%d\n", l);  
 }  
 int main()  
 {  
      while (scanf("%d", &N) > 0) {  
           for (int i = 0; i < N; i++) scanf("%d", &x[i]);  
           solve();  
      }  
      return 0;  
 }  

POJ.3111 K Best

1.Problem
http://poj.org/problem?id=3111

2.Idea
Binary Search

3.Source

 int N, K;  
 int v[100005];  
 int w[100005];  
 pair<double, int> y[100005];  
 bool C(double x)  
 {  
      for (int i = 0; i < N; i++) {  
           y[i] = make_pair((double)v[i] - x * (double)w[i], i + 1);  
      }  
      sort(y, y + N);  
      double sum = 0.0;  
      for (int i = N - K; i < N; i++) sum += y[i].first;  
      return sum >= 0;  
 }  
 void solve()  
 {  
      double l = 0.0, r = 100000000.0;  
      for (int i = 0; i < 50; i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      C(l);  
      for (int i = N - K; i < N; i++) {  
           printf("%d ", y[i].second);  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &K);  
      for (int i = 0; i < N; i++) scanf("%d%d", &v[i], &w[i]);  
      solve();  
      return 0;  
 }  

POJ.2976 Dropping tests

1.Problem
http://poj.org/problem?id=2976

2.Idea
Binary Search

3.Source

 int N, K;  
 int a[1003];  
 int b[1003];  
 double y[1003];  
 bool C(double x)  
 {  
      for (int i = 0; i < N; i++) {  
           y[i] = (double)a[i] - x * (double)b[i];  
      }  
      sort(y, y + N);  
      double sum = 0.0;  
      for (int i = K; i < N; i++) sum += y[i];  
      return sum >= 0;  
 }  
 void solve()  
 {  
      double l = 0.0, r = 1.0;  
      for (int i = 0; i < 100; i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      cout << (int)(100.0 * l + 0.5) << endl;  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &K) > 0) {  
           if (N + K == 0) break;  
           for (int i = 0; i < N; i++) cin >> a[i];  
           for (int i = 0; i < N; i++) cin >> b[i];  
           solve();  
      }  
      return 0;  
 }  

POJ.3104 Drying

1.Problem
http://poj.org/problem?id=3104

2.Idea
Binary Search

3.Source

 ll N, K;  
 ll a[100005];  
 ll MaxL = 0;  
 bool C(ll d)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           if (a[i] > d) {  
                cnt += ceil((a[i] - d) * 1.0 / (K - 1));  
           }  
      }  
      return cnt <= d;  
 }  
 void solve()  
 {  
      if (K == 1) {  
           printf("%d\n", MaxL);  
           return;  
      }  
      ll lb = 0, ub = MaxL;  
      while (ub - lb > 1) {  
           //cout << lb << " " << ub << endl;  
           ll mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {   
           scanf("%d", &a[i]);  
           MaxL = max(MaxL, a[i]);  
      }  
      cin >> K;  
      solve();  
      return 0;  
 }  

POJ.3273 Monthly Expense

1.Problem
http://poj.org/problem?id=3273

2.Idea
Binary Search

3.Source

 int N, M;  
 int x[100005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int sum = 0;  
      for (int i = 0; i < N; i++) {  
           if (x[i] > d) return false;  
           else if(sum + x[i] > d){  
                cnt++;  
                sum = x[i];  
           }  
           else {  
                sum += x[i];  
           }  
      }  
      if (cnt < M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      ll lb = 0, ub = 12345678900;  
      while (ub - lb > 1) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) cin >> x[i];  
      solve();  
      return 0;  
 }  

POJ.3258 River Hopscotch

1.Problem
http://poj.org/problem?id=3258

2.Idea
Binary Search

3.Source

 int L, N, M;  
 int x[50005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int last = 0;  
      for (int i = 1; i <= N + 1; i++) {  
           if (x[i] - x[last] < d) {  
                cnt++;  
           }  
           else {  
                last = i;  
           }  
      }  
      if (cnt <= M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      sort(x, x + N + 2);  
      int ans;  
      int lb = 0, ub = L;  
      while (lb <= ub) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) {  
                ans = mid;  
                lb = mid + 1;  
           }  
           else ub = mid - 1;  
      }  
      printf("%d\n", ans);  
 }  
 int main()  
 {  
      cin >> L >> N >> M;  
      for (int i = 1; i <= N; i++) cin >> x[i];  
      x[N + 1] = L;  
      solve();  
      return 0;  
 }  

POJ.1064 Cable master

1.Problem
http://poj.org/problem?id=1064

2.Idea
Binary Search

3.Source

 int N, K;  
 double L[10004];  
 bool C(double x)  
 {  
      int num = 0;  
      for (int i = 0; i < N; i++) {  
           num += (int)(L[i] / x);  
      }  
      return num >= K;  
 }  
 void solve()  
 {  
      double lb = 0, ub = INF;  
      for (int i = 0; i < 100; i++) {  
           double mid = (lb + ub) / 2;  
           if (C(mid)) lb = mid;  
           else ub = mid;  
      }  
      printf("%.2f\n", floor(ub * 100) / 100);  
 }  
 int main()  
 {  
      cin >> N >> K;  
      for (int i = 0; i < N; i++) cin >> L[i];  
      solve();  
      return 0;  
 }  

POJ.2456 Aggressive cows

1.Problem
http://poj.org/problem?id=2456

2.Idea
Binary Search

3.Source

 int N, M;  
 double x[100005];  
 bool C(int d)  
 {  
      int last = 0;  
      for (int i = 1; i < M; i++) {  
           int crt = last + 1;  
           while (crt < N && x[crt] - x[last] < d) {  
                crt++;  
           }  
           if (crt == N) return false;  
           last = crt;  
      }  
      return true;  
 }  
 void solve()  
 {  
      sort(x, x + N);  
      int lb = 0, ub = INF;  
      while (ub - lb > 1) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) lb = mid;  
           else ub = mid;  
      }  
      printf("%d\n", lb);  
 }  
 int main()  
 {  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) cin >> x[i];  
      solve();  
      return 0;  
 }