Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Aug 3rd, 2012  |  syntax: C++  |  size: 2.92 KB  |  hits: 16  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. //#pragma comment(linker, "/STACK:16777216")
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7. int a[10001];
  8. int b[10001];
  9. bool used[10001];
  10. int d[2*10001];
  11. int ololo[2*10001];
  12. int ololo2[2*10001];
  13. int ololo3[2*10001];
  14.  
  15. void fill(int a [], int n)
  16. {
  17.     for (int i = 0; i<n;i++)
  18.     {
  19.         a[i] = 0;
  20.     }
  21. }
  22.  
  23.  void qSort(int A [],int b[], int low, int high) {
  24.               int i = low;
  25.               int j = high;
  26.               int x = A[(low+high)/2];
  27.               do {
  28.                   while(A[i] < x) ++i;
  29.                   while(A[j] > x) --j;
  30.                   if(i <= j){
  31.                       int temp = A[i];
  32.                       A[i] = A[j];
  33.                       A[j] = temp;
  34.                       temp = b[i];
  35.                       b[i] = b[j];
  36.                       b[j] = temp;
  37.                       i++; j--;
  38.  
  39.                   }
  40.               } while(i <= j);
  41.          
  42.               if(low < j) qSort(A,b, low, j);
  43.               if(i < high) qSort(A,b,i, high);
  44.           }
  45.          
  46. int min (int a, int b)
  47. {
  48.         if (a<b) return a;
  49.         return b;
  50. }
  51.  
  52. int main () {
  53.     int n = 0;
  54.     scanf("%d",&n);
  55.     for (int i = 0; i < n; i++)
  56.     {
  57.         scanf("%d",&a[i]);
  58.        
  59.     }
  60.     if (n==1)
  61.     {
  62.         cout<<1<<endl;
  63.         cout<<a[0];
  64.         return 0;
  65.     }
  66.     int sum = 0;
  67.     for (int i = 0; i <n; i++)
  68.     {
  69.         if (a[i]%n==0){
  70.             cout<<1<<endl;
  71.             cout<<a[i];
  72.             return 0;
  73.         }
  74.         b[i] = a[i] % n;
  75.         sum+=b[i];
  76.     }
  77.     int k = sum % n;
  78.         qSort(b,a,0,n-1);
  79.  
  80.     fill(d,k+n+1);
  81.     d[0] = 1;
  82.     fill(ololo,k+n+1);
  83.     fill(ololo2,k+n+1);
  84.     fill(ololo3,k+n+1);
  85.                 int fuuuu = 0;
  86.                 for (int i = 0; i <n; i++){
  87.                         fuuuu = min(fuuuu+b[i],n);
  88.                         for (int j = fuuuu; j>=b[i]; j--){
  89.             if (d[j-b[i]]==1 && ololo[j]==0){
  90.                 d[j] = d[j-b[i]];
  91.                 ololo[j] = a[i];
  92.                 ololo2[j] = b[i];
  93.                 ololo3[j] = i;
  94.             }
  95.             else d[j] = max(d[j],d[j-b[i]]);
  96.         }
  97.     }
  98.     if (d[k]==0){
  99.                 fill(d,n);
  100.                 d[0] = 1;
  101.                 fill(ololo,n);
  102.                 fill(ololo2,n);
  103.                 fill(ololo3,n);
  104.                                 int fuuu = 0;
  105.                                 for (int i = 0; i <n; i++){
  106.                                         fuuu = min(fuuu+b[i],n+k);
  107.                                         for (int j = fuuu; j>=b[i]; j--){
  108.                                        
  109.                         if (d[j-b[i]]==1 && ololo[j]==0){
  110.                             d[j] = d[j-b[i]];
  111.                             ololo[j] = a[i];
  112.                             ololo2[j] = b[i];
  113.                             ololo3[j] = i;
  114.                         }
  115.                         else d[j] = max(d[j],d[j-b[i]]);
  116.                     }
  117.                 }
  118.                 k = n+k;
  119.             }
  120.     int fuuu = 0;
  121.     while(k!=0){
  122.         used[ololo3[k]] = true;
  123.         fuuu++;
  124.         k-=ololo2[k];
  125.     }
  126.     printf("%d\n",(n-fuuu));
  127.      
  128.     for (int i = 0; i < n; i++){
  129.         if (!used[i]){
  130.             printf("%d\n",a[i]);
  131.         }
  132.     }
  133.  
  134.     return 0;
  135. }
create a new version of this paste RAW Paste Data