Created
October 13, 2016 17:28
Star
You must be signed in to star a gist
Gridland metro algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <string.h> | |
#include <math.h> | |
#include <stdlib.h> | |
void get_meta(long int* meta_data){ | |
// getting the meta data of the problem | |
for (long int i = 0; i < 3; i++){ | |
scanf("%ld", &meta_data[i]); | |
} | |
} | |
int main() { | |
/* Enter your code here. Read input from STDIN. Print output to STDOUT */ | |
long int* meta_data = malloc(sizeof(long int) * 3); | |
get_meta(meta_data); | |
long int total_grids = meta_data[0] * meta_data[1]; | |
long int max_col_data = meta_data[1]; // used for checking | |
long int track_num = meta_data[2]; | |
// initializing array for tracks min and max points | |
long int track_array[track_num][2]; | |
// fill the min col with default max data and max col with default min data | |
for (long int i = 0; i < track_num; i++){ | |
track_array[i][0] = 2000000000; | |
track_array[i][1] = 0; | |
} | |
// filling the min col with the minimum available data and max col with maximum availabe data | |
for (long int i = 0; i < track_num; i++){ | |
get_meta(meta_data); | |
if(track_array[meta_data[0]-1][0] > meta_data[1]){ | |
track_array[meta_data[0]-1][0] = meta_data[1]; | |
} | |
if(track_array[meta_data[0]-1][1] < meta_data[2]){ | |
track_array[meta_data[0]-1][1] = meta_data[2]; | |
} | |
} | |
// fix min values for calculation | |
for(long int i = 0; i < track_num; i++){ | |
if(track_array[i][0] > max_col_data){ | |
track_array[i][0] = 0; | |
} | |
} | |
// calculate lamp posts | |
long int sum = 0; | |
for(long int i = 0; i < track_num; i++){ | |
sum = sum + ((track_array[i][1] - track_array[i][0]) + 1); | |
} | |
long int lamp_posts = total_grids - sum; | |
printf("%ld", lamp_posts); //check output | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment