Untitled

Array game
Có 1 trò chơi với dãy gồm N số như sau:
Mỗi bước đi bạn phải chia mảng thành 2 phần không rỗng sao cho tổng các phần tử bên trái bằng tổng phần tử bên phải. Nếu chia được bạn sẽ được 1 điểm, nếu không chia được trò chơi kết thúc.
Sau mỗi lần chia thành công, bạn phải bỏ 1 trong 2 phần đã chia và tiếp tục trò chơi với phần còn lại.
Cho 1 dãy, hỏi số điểm nhiều nhất mà bạn có thể thu được là bao nhiêu?
Input
Dòng đầu tiên là số lượng test case T (T <= 20).
Dòng đầu tiên của mỗi test case là N (N <= 20,000) là số lượng phần tử của dãy. Dòng tiếp theo là N phần tử của dãy đó.
 
Output
Mỗi test case in ra số điểm nhiều nhất mà có thể thu được
 
Sample
Input
3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1
Output
0
2
3


// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include <stdio.h>
#include <iostream>

using namespace std;
int N;
unsigned long long arr[200000];
unsigned long long cnt;
unsigned long long Sum;

unsigned long long findMid(unsigned long long left, unsigned long long right, unsigned long long sum) {
	unsigned long long half= sum/2;
	unsigned long long tempSum=0;
	
	unsigned long long mid;
	for (mid=left; tempSum<half; ++mid) {
		tempSum+=arr[mid];
		
	}
	--mid;
	if(tempSum==half) {
		return mid;
	} else {
		return -1;
	}
}

void backtrack(unsigned long long left, unsigned long long right, unsigned long long sum, unsigned long long score) {
	if (left==right || sum%2==1) {
		if(score>cnt) {
			cnt=score;
		}
		return;
	}
	
	unsigned long long mid;
	mid = findMid(left,right,sum);
	if(mid==-1) {
		if(score>cnt) {
			cnt=score;
		}
		return;
	}
	backtrack(left, mid,sum/2,score+1);
	backtrack(mid+1, right,sum/2,score+1);
}
int main(int argc, char** argv)
{
	int tc, T;
	
	// The freopen function below opens input.txt file in read only mode, and afterward,
	// the program will read from input.txt file instead of standard(keyboard) input.
	// To test your program, you may save input data in input.txt file,
	// and use freopen function to read from the file when using cin function.
	// You may remove the comment symbols(//) in the below statement and use it.
	// Use #include<cstdio> or #include<stdio.h> to use the function in your program.
	// But before submission, you must remove the freopen function or rewrite comment symbols(//).

	freopen("input.txt", "r", stdin);

	cin >> T;
	for(tc = 1; tc <=T; tc++)
	{
		/**********************************
		*  Implement your algorithm here. *
		***********************************/
		cin >> N;
		Sum=0;
		cnt=0;
		for (unsigned long long i=0;i<N;i++) {
			cin >> arr[i];
			Sum+=arr[i];
		}
		// Print the answer to standard output(screen).
		if (Sum == 0) {
			cnt = N - 1;
		} else {
			backtrack(0,N-1,Sum,0);
		}

		cout << cnt << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}