fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<long long>g;
  4. long long a[100005],n,t,kh,cnt,o,w,cntt,tong,res;
  5. bool ch[100005];
  6. long long check(long long k)
  7. {
  8. 	res=1e9;
  9.     for(int i=0;i<g.size();i++)
  10.     {
  11.         for(int j=1;j<=k-1;j++)
  12.         {
  13.             if(a[j]!=w&&a[j+1]!=w)
  14.             {
  15.                 a[j+1]+=a[j];
  16.                 a[i]=1e9;
  17.                 cnt++;
  18.             }
  19.             w=max(w,a[j+1]);
  20.         }
  21.         if(cnt==g[i]) res=min(res,g[i]);
  22.     }
  23.     return res;
  24. }
  25. void checkk(long long k)
  26. {
  27.     cntt=0;
  28.     for(int i=1;i<=k;i++)
  29.     {
  30.          if(k%i==0){
  31.             g.push_back(i);
  32.             cntt++;
  33.          }
  34.     }
  35. }
  36. int main()
  37. {
  38.     cin>>t;
  39.     while(t--)
  40.     {
  41.         cin>>n;
  42.         w=0;
  43.         o=a[1];
  44.         tong=0;
  45.         for(int i=1;i<=n;i++)
  46.         {
  47.             cin>>a[i];
  48.             w=max(w,a[i]);
  49.             tong+=a[i];
  50.         }
  51.         o=a[1];
  52.           for(int i=1;i<=n;i++)
  53.         {
  54.             if(a[i]!=o)
  55.             {
  56.                 kh++;
  57.                 o=a[i];
  58.             }
  59.         }
  60.         if(kh==0) cout<<0<<endl;
  61.         else{
  62.             checkk(tong);
  63.             if(cntt==2) cout<<n-1<<endl;
  64.             else cout<<check(n)<<endl;
  65.         }
  66.     }
  67. }
  68.  
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
stdout
copy 
1000000000
2
1000000000
https://ideone.com/7W78VT
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!