/************************************************************** * * Sample solution for the Moving Piano problem in contest 2002 * * Author: A. Björklund * Description: The system of linear constraints is satisfiable * if and only if there is no interval within which the enclosed * jobs are larger than the amount of working power. * **************************************************************/ #include #define FINE (0) #define WEEKEND_WORK (1) #define SERIOUS_TROUBLE (2) // Week-end arithmetics #define NON_WED(j) (((j) % 7)<5); #define MAX_DAYS (100) typedef struct { int size; unsigned int con[MAX_DAYS][MAX_DAYS]; unsigned int interv[MAX_DAYS][MAX_DAYS]; } tInter; tInter Weeks; void clear_con(tInter *theCon) { int i,j; for (i=0;isize;i++) for (j=0;jsize;j++) { theCon->con[i][j] = 0; theCon->interv[i][j] = 0; } } void cumsum_interv(tInter *theCon) { int i,j,sum; for (i=0;isize;i++) { sum = theCon->interv[i][i]; for (j=i-1;j>=0;j--) { sum += theCon->interv[j][i]; theCon->interv[j][i] = sum; } } } void calc_cons(tInter *theCon) { int i,j; for (i=0;isize;i++) theCon->con[i][i] = theCon->interv[i][i]; for (i=1;isize;i++) for (j=0;jsize-i;j++) { theCon->con[j][j+i] = theCon->con[j][j+i-1] + theCon->interv[j][j+i]; } } int solve_cons(tInter *theWeeks,int p) { int i,j; int workingdays, weekend = 0; int nwed,pwed; for (i=0;isize;i++) { workingdays = 0; for (j=i;j>=0;j--) { workingdays += NON_WED(j); // Check if non weekend day if (workingdays*p < theWeeks->con[j][i]) { weekend = 1; if ((i-j+1)*p < theWeeks->con[j][i]) { return SERIOUS_TROUBLE; } } } } if (weekend) { return WEEKEND_WORK; } else { return FINE; } } int main() { int i,j,m,p,n,b,e,num; Weeks.size = MAX_DAYS; scanf("%d",&n); for (i=0;i