VOGAME – spoj

Đề bài:

Thuật toán:

  • Mình tham khảo từ solution của anh Lê Anh Đức
    Thuật toán:
    -Nhận xét là tính chẵn lẻ của số bi đỏ ko đổi, vậy nên kết quả sẽ là số bi đỏ modulo 2.
    -Hãy thử tạo 1 test và sinh ra dãy A, các bạn sẽ nhận thấy dãy A tuần hoàn theo chu kì D+1, từ đó có thể giải quyết bài toán này. Sau đây là code của mình:

Code:

#include<bits/stdc++.h>
#define N 100001
using namespace std;
int t,n,d;
long long a[N], s[3];
int main()
{
	cin>>t;
	for (int z=1; z <= t; z++)
		{
			s[0]=s[1]=0;
			cin>>n>>d;
			for (int i=1; i <= d; i++)
				{
					cin>>a[i];
					s[a[i]]=s[a[i]]+1;
				}	
			if (n == d)
				{
					cout<<s[1]%2<<endl;
					continue;
				}
			d=d+1;
			a[d]=s[1]%2;
			s[a[d]]=s[a[d]]+1;
			int ck=n/d;
			int du=n-ck*d;
			long long kq=s[1]*ck;
			for (int i=1; i <= du; i++)
				kq=kq + a[i]%2;
			cout<<kq%2<<endl;
		}
}
Khuyên dùng

 

Speak Your Mind

*