Menu Close

The maximum number of good sleeping times….[Cprogm]FTC

Tina had a pretty weird sleeping schedule. There are h hours in a day. Tina will sleep exactly n times.

The i -th time he will sleep exactly after ai hours from the time he woke up. You can assume that Tina woke up exactly at the beginning of this story (the initial time is 0 ). Each time Tina sleeps exactly one day (in other words, h hours).


Tina thinks that the i -th sleeping time is good if he starts to sleep between hours l and r inclusive.
Tina can control himself and before the i -th time can choose between two options: go to sleep after ai hours or after ai−1 hours.


Your task is to say the maximum number of good sleeping times Tina can obtain if he acts optimally.

#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))
int main(){
  int n, h, l, r, *dp[2], re = 0, i, j, k;
  scanf("%d %d %d %d", &n, &h, &l, &r);
  for(i = 0; i < 2; i++) {
  dp[i] = malloc(h*sizeof(int));
  for(j = 0; j < h; j++)
  dp[i][j] = -1;
  }
  dp[1][0] = 0;
  for(i = 0; i < n; i++) {
  int *t = dp[0], a;
  dp[0] = dp[1];
  dp[1] = t;
  for(j = 0; j < h; j++)
  dp[1][j] = -1;
  scanf("%d", &a);
  for(j = 0; j < h; j++)
  if(dp[0][j] != -1)
  for(k = 0; k < 2; k++) {
  int t = dp[0][j], u = (j + a - k)%h;
  if(u >= l && u <= r)
  t++;
  dp[1][u] = max(dp[1][u], t);
  }
  }
  for(i = 0; i < h; i++)
  re = max(re, dp[1][i]);
  printf("\n%d\n\n", re);
return 0;
}


INPUT_1:
2  24  14  16
17  2

OUTPUT:
1


INPUT_2:
5  3  0  0 
1  1  1  1  1

OUTPUT:
5


ILLUSTRATION

Executed using gcc