Skip to content

Instantly share code, notes, and snippets.

@Mr-Kumar-Abhishek
Created October 13, 2016 17:28
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Mr-Kumar-Abhishek/365719b374306c9ac4ce0197a0090a90 to your computer and use it in GitHub Desktop.
Gridland metro algorithm
#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