fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool f(int i,int j){return i>j;}
  6.  
  7. int main()
  8. {
  9.     int t,d;
  10.     cin>>t;
  11.     for(int i=1;i<=t;i++)
  12.     {
  13.         cin>>d;
  14.         vector<int> v(d);
  15.         for(int j=0;j<d;j++)cin>>v[j];
  16.         sort(v.begin(),v.end(),f);
  17.         if(v[0]==1)cout<<"Case #"<<i<<": "<<1<<'\n';
  18.         else{
  19.         int g=v[0],h=0;
  20.         bool b=true;
  21.         while(b)
  22.         {
  23.  
  24.                 h++;
  25.                 int temp=v[0]/2,temp2=v[0]-temp;
  26.                 v.erase(v.begin());
  27.                 int size=v.size();
  28.                 int start=0,end=v.size()-1;
  29.                 while(start<end)
  30.                 {
  31.                     int middle=(start+end)/2;
  32.                     if(v[middle]>temp)start=middle+1;
  33.                     else if(v[middle]<temp)end=middle-1;
  34.                     else break;
  35.                 }
  36.                 int sh=start;
  37.                 if(temp<v[start])
  38.                   while(temp<v[start] && start<size) start++;
  39.                 else if(temp>v[start])
  40.                 {while(temp>v[start] && start>=0)start--;
  41.                  start++;
  42.                 }
  43.                 v.insert(v.begin()+start,temp);
  44.                 start = sh;
  45.                 temp=temp2;
  46.                 if(temp<v[start])
  47.                   while(temp<v[start] && start<size) start++;
  48.                 else if(temp>v[start])
  49.                 {
  50.                     while(temp>v[start] && start>=0)start--;
  51.                     start++;
  52.                 }
  53.                 v.insert(v.begin()+start,temp);
  54.                 g=min(g,v[0]+h);
  55.                 if(v[0]==v[1])b=false;
  56.         }
  57.         cout<<"Case #"<<i<<": "<<g<<'\n';}
  58.     }
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
1
1
9
stdout
copy 
Case #1: 6
https://ideone.com/YKNeN2
language:
C++ (gcc 8.3)
created:
9 years 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!