DTDOI – spoj

05/12/2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Thông thường thì ta sẽ có cách giải QHĐ với đpt O(S*n), nhưng vì S lên đến 1e9 nên ta có cách làm như sau:
    • Giảm S bằng tờ có giá trị lớn nhất cho đến khi S đủ nhỏ để QHĐ (giảm đến mức nào thì các bạn nên tự thử, trong code mình giảm xuống 100000)
    • QHĐ

Code:

#include<bits/stdc++.h>
using namespace std;
int n,s;
int a[101];
int d[100001];
int main()
{
	cin>>n>>s;
	for (int i=1; i <= n; i++)
		cin>>a[i];
	int mx=0;
        for (int i=1; i <= n; i++)
                mx=max(mx,a[i]);
	int res=0;
	while (s >= 100001)
		{
			res++;
			s-=mx;
		}
	d[0]=0;
	for (int i=1; i <= s; i++)
		{
                        d[i]=10000000;
                        for (int j=1; j <= n; j++)
			        if (i >= a[j])
				         d[i]=min(d[i],d[i-a[j]]+1);
                }
	cout<<res+d[s];
	return 0;
}
Chủ đề: Quy hoạch động Mức độ:

VOGAME – spoj

30/11/2016 by Leave a Comment

Đề 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;
		}
}
Chủ đề: SPOJ, Toán học Mức độ: