11432 - Busy Programmer

[f74956227]

Is this a DP program? i use a backtracking method but it is too slow... can someone give me some hints ?plz

[Robert Gerbicz]

Is this a DP program? i use a backtracking method but it is too slow... can someone give me some hints ?plz

Yes, this is dp.
You can also send a precomputed table, that fits in 40kb code size.

[andmej]

I'm trying to define a state for this problem. I'm letting dp be the number of possible schedules using the first i days where the last day is MICRO, and without violating any constraint. (The answer will be 2 * dp[2d], since for every schedule ending at MICRO I can construct the "negation" swapping MICRO for GOO and viceversa.).

I'm having problems filling the table though, because I can't find how to determine if some schedule has used one of the tasks d or more days or if it has used one task the last d-1 days.

Any help?
Thanks.

[baodog]

Hi, I keep get wa. Is this i/o correct?

Code: Select all

0 0
1 0
1 1
3 2
3 1
3 0
3 3
4 0
4 1
4 2
4 3
4 4
3 10
33 33
33 12
33 0
33 1
-1 -1

Code: Select all

Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 10
Case 5: 2
Case 6: 0
Case 7: 12
Case 8: 0
Case 9: 2
Case 10: 22
Case 11: 38
Case 12: 40
Case 13: 12
Case 14: 3665248281885181068
Case 15: 3660530221414286026
Case 16: 0
Case 17: 275644373642

[mf]

I get this output:

Code: Select all

Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 10
Case 5: 2
Case 6: 0
Case 7: 12
Case 8: 0
Case 9: 2
Case 10: 24
Case 11: 38
Case 12: 40
Case 13: 12
Case 14: 3665248281885181068
Case 15: 3658824518409873670
Case 16: 0
Case 17: 2

[rushel]

edited my outputs: me and mf replied almost at same time.

[baodog]

Thanks! Got ac.

[f74956227]

I still can't find the recursive relationship...ORZ

[sclo]

I still can't find the recursive relationship...ORZ

Hint: figure out what this line does:

Code: Select all

for(int i=1; i<=d; i++) if(n-i>=0) ret+=f(m,n-i,d,!k);

I'm not saying what are m,n,d, or k, you have to figure it out.

[H_Hima]

Hi.
Excelent alright.
I used this method in the contest. (backtracking & memorizing and this is my code.
but my answer for case:
33 12
is
3658729080464717380

but I got correct answer for case. 33 33 ?
the above case can be fetch in part of 33 33 solution.
this is my code please help me in my wrong.

Code: Select all

#include<iostream>
#include<fstream>
using namespace std;

unsigned long long res[40][80][40];
bool sws[40][80][40];
int D,G;
bool sw;

unsigned long long fun(int num,int space) {
	if(sws[num][space][G])
		return res[num][space][G];
	int i,j;
	unsigned long long re=0;
	if(num==0)
		re=1;
	else if(num>space)
		re=0;
	else if(num==space) {
		re=0;
		if(num<=G)
			re=1;
	}
	else {
		j=space-num;
		for(i=0;i<G&&i<num;i++) {
			re+=fun(j,space-i-1);
		}
	}
	sws[num][space][G]=true;
	res[num][space][G]=re;
	return re;
}

int main() {
	//ifstream cin("test.in");
	//ofstream cout("test.out");
	int i,j,k,num,space,t=1;
	unsigned long long re;
	for(i=0;i<40;i++)
		for(j=0;j<80;j++)
			for(G=0;G<40;G++)			
				sws[i][j][G]=false;
	cin>>D>>G;
	while(D>=0&&G>=0) {
		num=D;
		space=2*D;
		if(D==0)
			cout<<"Case "<<t++<<": "<<1<<endl;
		else if(G==0) {
			cout<<"Case "<<t++<<": "<<0<<endl;
		}
		else if(G==1)
			cout<<"Case "<<t++<<": "<<2<<endl;
		else {
			for(i=0,re=0;i<num&&i<G;i++)
				re+=fun(num-1,space-i-2);
			re*=2;
			cout<<"Case "<<t++<<": "<<re<<endl;
		}
		cin>>D>>G;
	}
}

thanks alot.

[sad2kind]

In case D=4 G=2 , I can't find only 22 schedules.

• aabbaabb
  aabbabab
  aababbab
  aabababb
  abbaabab
  abbabaab
  abaabbab
  abaababb
  ababbaab
  ababaabb
  abababab

What is the last one?

[rio]

he can not be away from any project for more than G consecutive days. (of course unless a project is already complete.)

aabaabbb
-----
Rio

[sad2kind]

orz.. Thanks! I got AC