#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 1000
#define PLANNING_HORIZON 365*2*24

int i,j,start_time,duration,number_of_vehicles,x,y,v1,v2,n,q,optimal_value;
int hour_bin[PLANNING_HORIZON],smallest_veh_request_bin[PLANNING_HORIZON];

struct {
  int s,e,v;
} request[MAX];

int max(int a,int b) { return a > b ? a : b; }

void main() {
  srand((unsigned) time(NULL));
  for (j=0; j<PLANNING_HORIZON; j++) {
    hour_bin[j] = 0;
    smallest_veh_request_bin[j] = 32767*32767;
  }

  printf("input x: ");
  scanf("%d",&x);
 
  printf("input y: ");
  scanf("%d",&y);

  printf("input v1: ");
  scanf("%d",&v1);

  printf("input v2: ");
  scanf("%d",&v2);

  for (i=0; i<x; i++) {
    duration = 1 + rand() % v1;
    start_time = rand() % (PLANNING_HORIZON-duration);
    number_of_vehicles = 1 + rand() % v2;

    request[i].v = number_of_vehicles;
    request[i].s = start_time;
    request[i].e = start_time+duration;

    for (j=start_time; j<start_time+duration; j++) {
      hour_bin[j] += number_of_vehicles;
      if (number_of_vehicles < smallest_veh_request_bin[j]) smallest_veh_request_bin[j] = number_of_vehicles;
    }
  }

  for (i=0; i<x; i++)
    if (request[i].s > 365*24*2 || request[i].e > 365*24*2)
      break;

  optimal_value = -1;
  for (j=0; j<PLANNING_HORIZON; j++) if (hour_bin[j] > optimal_value) optimal_value = hour_bin[j];

  int numHoursNonOptimal = 0;
  for (j=0; j<PLANNING_HORIZON; j++) if (hour_bin[j] != optimal_value) numHoursNonOptimal++;
  int slice = (numHoursNonOptimal-24*31) / y; // to ensure, minus 1 mth.....

  j=0; // start from day 0
  for (i=x; i<x+2*y; i+=2,j+=slice) {
    while (hour_bin[j] >= optimal_value / 2) {
      j++; // to ensure the generator is correct
      if (j > 365*24*2) j = 0; // back again, rollover... don't overflow
    }
    // by this point, j must be empty...
    // create two single day requests...

    // must be taken
    request[i].s = j;
    request[i].e = j+1;

    // must not be taken
    request[i+1].s = j;
    request[i+1].e = j+1;

    int difference_to_optimal = optimal_value - hour_bin[j];

    // must be taken
    request[i].v = difference_to_optimal - rand()%difference_to_optimal; // taking this will preserve optimality

    // must not be taken
    request[i+1].v = difference_to_optimal + 1 + rand()%2; // +1 or +2
  }

  n = x+2*y;
  q = x+y;

  // scramble requests... 
  for (i=0; i<n; i++) {
    int index1 = rand()%n;
    int index2 = rand()%n;
    // swap index1 with index2
    int temp;
    
    temp = request[index1].v;
    request[index1].v = request[index2].v;
    request[index2].v = temp;

    temp = request[index1].s;
    request[index1].s = request[index2].s;
    request[index2].s = temp;

    temp = request[index1].e;
    request[index1].e = request[index2].e;
    request[index2].e = temp;
  }
 
  FILE *f = fopen("testcase.txt","w");

  int totalDays,hour,totalDaysUpToMonth[12] = {0,31,59,90,120,151,181,212,243,273,304,334};

  // print to file!!!
  fprintf(f,"%d\t%d\t%d\n",n,q,optimal_value);
  for (i=0; i<n; i++) {
    fprintf(f,"%d\t",request[i].v);

    int year;
    // convert values to days...
    if (request[i].s > 365*24) {
      request[i].s -= 365*24;
      fprintf(f,"2003");
      year = 2003;
    }
    else {
      fprintf(f,"2002");
      year = 2002;
    }

    if (request[i].s != 0) {
      hour = request[i].s % 24;
      totalDays = request[i].s / 24;
    }
    else {
      hour = 0;
      totalDays = 0;
    }

    for (j=11; j>=0; j--) if (totalDays >= totalDaysUpToMonth[j]) break;
    if (request[i].s == totalDaysUpToMonth[j] && j!=0) j--; // minus 1
    fprintf(f,"%0.2d",j+1);

    totalDays -= totalDaysUpToMonth[j];
    fprintf(f,"%0.2d",totalDays);
    if (totalDays > 30)
      break;

    fprintf(f,"\t%d\t",hour);

    if (request[i].e > 365*24) {
      request[i].e -= 365*24;
      fprintf(f,"2003");
    }
    else
      fprintf(f,"2002");

    if (request[i].e != 0) {
      hour = request[i].e % 24;
      totalDays = request[i].e / 24;
    }
    else {
      hour = 0;
      totalDays = 0;
    }

    for (j=11; j>=0; j--) if (totalDays >= totalDaysUpToMonth[j]) break;
    if (request[i].e == totalDaysUpToMonth[j] && j!=0) j--; // minus 1
    fprintf(f,"%0.2d",j+1);

    totalDays -= totalDaysUpToMonth[j];
    fprintf(f,"%0.2d",totalDays);

    fprintf(f,"\t%d\n",hour);
 }
}