#include<iostream>
using namespace std;
#define maxsize 20  //硬币的数目
class fenzhi {
public:
  int falsecoin(int low, int high);
  void showresult();
  int num;
  int coin[maxsize];
  int result;
};
int fenzhi::falsecoin(int low, int high)
{
  int sum1=0;
  int sum2=0;
  int sum3=0;
  if (low + 1 == high)  //只有两枚硬币
  {
  if (coin[low] < coin[high])
  {
    result = low + 1;
    return result;
  }
  else
  {
    result = high + 1;
    return result;
  }
  } 
  //分治算法
  if((high-low+1)%2==0)  //n是偶数
  { 
  for (int i = low; i <= low+(high-low)/2; i++)
  {
    sum1 += coin[i];//前半段和
  }
  for (int j = low + (high - low) / 2+1; j <= high; j++)
  {
    sum2 += coin[j];//后半段和
  }
  if (sum1 > sum2)
  {
    result = falsecoin(low + (high - low) / 2 + 1, high); //递推后半段
    return result;
  }
  else if(sum1 < sum2)
  {
    result = falsecoin(low, low + (high - low) / 2); //递推前半段
    return result;
  }
  }
  else  //n是奇数
  {
  for (int i = low;i<=low+(high-low)/2-1;i++)
  {
    sum1 += coin[i];   //中位数的前半段和
  }
  for (int j = low + (high - low) / 2+1; j <= high; j++)
  {
    sum2 += coin[j];   //中位数的后半段和
  }
  sum3 = coin[low + (high - low) / 2];   //中位数
  if (sum1 > sum2)      //前半段和大于后半段和
  {
    result = falsecoin(low + (high - low) / 2 + 1, high);//递推后半段
    return result;
  }
  else if (sum1 < sum2)   //前半段和小于后半段和
  {
    result = falsecoin(low, low + (high - low) / 2 - 1);//递推前半段
    return result;
  }
  if (sum1 + sum3 == sum2 + sum3)    //前半段和加中位数等于后半段和加中位数，所以中位数为目标寻找值
  {
    result = low + (high - low) / 2+1;
    return result;
  }
  }
}
void fenzhi::showresult()
{
  cout << "假币所在的位置：" << this->result << endl;
}
void text()
{
  fenzhi fz;
  cout << "输入硬币的总数目：" << endl;
  cin >> fz.num;
  cout << "请输入硬币的真假（1真/0假）：" << endl;
  for (int i = 0; i < fz.num; i++)
  {
  cin >> fz.coin[i];
  }
  fz.falsecoin(0, fz.num - 1);
  fz.showresult();
}
int main()
{
  text();
}