Advertisement
Guest User

Untitled

a guest
Aug 15th, 2013
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <stdlib.h>
  5. #include <stack>
  6. #include <queue>
  7. #include <set>
  8. #include <map>
  9. #include <string>
  10. #include <algorithm>
  11. #include <iostream>
  12. using namespace std;
  13.  
  14. class BI {
  15.     vector<int> a; 
  16. public:
  17.     BI() {}
  18.     void init(char *s) {
  19.         static int p[] = { 1, 10, 100, 1000, 10000, 100000, 1000000 };
  20.         int l = strlen(s) - 1;
  21.         while (l >= 0) {
  22.             int d = 0;
  23.             for (int i = 0; i < 6; i++, l--)
  24.                 d += (l >= 0 ? s[l] - '0' : 0) * p[i];
  25.             a.push_back(d);
  26.         }          
  27.     }
  28.     void print() {
  29.         printf("%d", a[a.size() - 1]);
  30.         for (int i = a.size() - 2; i >= 0; i--)
  31.             printf("%06d", a[i]);      
  32.     }
  33.     bool operator < (const BI &x) const {
  34.         if (a.size() != x.a.size())
  35.             return a.size() < x.a.size();
  36.         for (int i = a.size() - 1; i >= 0; i--)
  37.             if (a[i] != x.a[i])
  38.                 return a[i] < x.a[i];
  39.         return 0;
  40.     }
  41.     BI operator + (const BI &x) const {
  42.         BI r;
  43.         int s = 0, o = 0;
  44.         for (int i = 0; i < max(a.size(), x.a.size()); i++) {
  45.             s = o;
  46.             if (i < a.size())
  47.                 s += a[i];
  48.             if (i < x.a.size())
  49.                 s += x.a[i];
  50.             o = s / 1000000;
  51.             r.a.push_back(s % 1000000);
  52.         }
  53.         if (o)
  54.             r.a.push_back(o);
  55.         return r;
  56.     }
  57. } bi[1010];
  58.  
  59. int n;
  60. char s[510];
  61.  
  62. int main() {
  63.     freopen("input.txt", "r", stdin);
  64.     freopen("output.txt", "w", stdout);
  65.     scanf("%d\n", &n);
  66.     for (int i = 0; i < n; i++) {
  67.         scanf("%s\n", s);
  68.         bi[i].init(s);
  69.     }
  70.     sort(&bi[0], &bi[n]);
  71.     for (int i = 0; i < n - 2; i++) {
  72.         for (int j = i + 1; j < n - 1; j++) {
  73.             BI sum = bi[i] + bi[j];
  74.             int l = j + 1, r = n - 1;
  75.             while (l + 1 < r) {
  76.                 int m = l + (r - l) / 2;
  77.                 if (bi[m] < sum)
  78.                     l = m;
  79.                 else
  80.                     r = m;
  81.             }
  82.             if (bi[l] < sum && bi[i] < bi[j] + bi[l] && bi[j] < bi[i] + bi[l]) {
  83.                 bi[i].print();
  84.                 printf(" ");
  85.                 bi[j].print();
  86.                 printf(" ");
  87.                 bi[l].print();
  88.                 return 0;
  89.             }
  90.             if (bi[r] < sum && bi[i] < bi[j] + bi[r] && bi[j] < bi[i] + bi[r]) {
  91.                 bi[i].print();
  92.                 printf(" ");
  93.                 bi[j].print();
  94.                 printf(" ");
  95.                 bi[r].print();
  96.                 return 0;
  97.             }
  98.         }
  99.     }
  100.     printf("0 0 0");
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement