#include <stdio.h> #include <stdlib.h> #include <stdarg.h> #include <time.h> #include <string.h> #include <map> #include <vector> #ifdef ENABLE_LOG void printFormatted(const char* format, ...); #define LOG(TAG, ...) {\ char buffer[256];\ time_t now = time(0);\ struct tm* timeVal = gmtime(&now);\ strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", timeVal);\ printFormatted("%s| %s:%d: %s ", buffer, __FILE__, __LINE__, TAG);\ printFormatted(__VA_ARGS__);\ printFormatted("\n");\ } FILE* initLogIfNecessary() { static FILE* fp = NULL; if(fp == NULL) { fp=fopen("log.txt", "a"); if(fp == NULL) { fprintf(stderr, ("Unable to open log file.\n")); return NULL; } printFormatted("Compiled on %s %s\n", __DATE__, __TIME__); } return fp; } void printFormatted(const char * format, ... ) { FILE* logFile = initLogIfNecessary(); va_list args; va_start (args, format); vfprintf (logFile, format, args); va_end (args); fflush(logFile); } #else #define LOG(TAG, ...) #endif void helloWorldFunction() { printf("HelloWorld\n"); } #define MAX_NUM_OF_FIELDS 500000 typedef struct { unsigned long long currentHeight; int count; } fieldStruct; void fillFieldStruct(fieldStruct* fs, int growSpeed, unsigned long long currentHeight, int numFieldsGrowFaster) { //fs->growSpeed = growSpeed; fs->currentHeight = currentHeight; //fs->numFieldsGrowFaster = numFieldsGrowFaster; } void updateFieldStructInfo(std::vector<int>* fieldTypes, std::map<int,fieldStruct*> * fieldsMap, int newFieldType) { std::map<int, fieldStruct*>::iterator it = fieldsMap->find(newFieldType); LOG(__FUNCTION__, "entering function"); fieldStruct* fsPtr; if(it != fieldsMap->end()) { fsPtr = it->second; fsPtr->count ++; } else { fsPtr = (fieldStruct*)malloc(sizeof(fieldStruct)); fieldTypes->push_back(newFieldType); fsPtr->count = 1; fsPtr->currentHeight = 0; (*fieldsMap)[newFieldType] = fsPtr; } LOG(__FUNCTION__, "leving function"); } void fillMap(std::map<int,fieldStruct*> * fieldsMap, int* growSpeedArr, int numberOfFields) { int i = 0; fieldStruct fieldInfo; fieldStruct* fsPtr = NULL; std::vector<int> diffFields; for(i = 0; i < numberOfFields; i++) { int speed = growSpeedArr[i]; updateFieldStructInfo(&diffFields, fieldsMap, speed); } } unsigned long long computeSia(unsigned long long daysOfGrow, unsigned long long heightDiff, unsigned long long fieldSum, int numOfFields) { return ((fieldSum * daysOfGrow) - (numOfFields*heightDiff)); } unsigned long long computeFieldSum(int numberOfFields, int* growSpeed) { int i = 0; unsigned long long result = 0; for(i = 0; i < numberOfFields; i++) { result += growSpeed[i]; } return result; } unsigned long long processCut(unsigned long long daysOfGrow, unsigned long long finalHeight, std::map<int,fieldStruct*>* fieldInfo, int numberOfFields, int minGrowSpeed) { LOG(__FUNCTION__, "called with daysOfGrow=%llu, finalHeight=%llu, numberOfFields=%d", daysOfGrow, finalHeight, numberOfFields); int i = 0; unsigned long long sum = 0; for(std::map<int, fieldStruct*>::iterator it = fieldInfo->begin(); it != fieldInfo->end(); it++) { int speed = it->first; fieldStruct* fs = it->second; fs->currentHeight += speed * daysOfGrow; long long diff = fs->currentHeight - finalHeight; if(diff > 0) { LOG(__FUNCTION__, "diff greater equals %llu for currHeight[%d]=%llu",diff, i, fs->currentHeight); fs->currentHeight -= diff; sum += diff*fs->count; } } return sum; } #ifndef UNIT_TEST int main(int argc, char* argv[]) { int numberOfFields, numberOfCuts; int growSpeed[MAX_NUM_OF_FIELDS]; int minGrowSpeed = 10000000; unsigned long long currHeight[MAX_NUM_OF_FIELDS]; memset(currHeight, 0, sizeof(currHeight)); scanf("%d %d", &numberOfFields, &numberOfCuts); LOG(__FUNCTION__, "read numberOfFields = %d, numberOfCuts = %d", numberOfFields, numberOfCuts); int i = 0; for(i = 0; i < numberOfFields; i++) { scanf("%d", &(growSpeed[i])); LOG(__FUNCTION__, "Scanned : growSpeed[%d]=%d", i, growSpeed[i]); minGrowSpeed = minGrowSpeed > growSpeed[i] ? growSpeed[i] : minGrowSpeed; } std::map<int, fieldStruct*> fieldInfo; fillMap(&fieldInfo, growSpeed, numberOfFields); unsigned long long startingDay, startingHeight; startingDay = 0; startingHeight = 0; unsigned long long cuttingDay, finalHeight; for(i = 0; i < numberOfCuts; i++) { scanf("%llu %llu",&cuttingDay, &finalHeight); LOG(__FUNCTION__, "Scanned cuttingDay:%llu, finalHeight:%llu", cuttingDay, finalHeight); // unsigned long long result = computeSia(cuttingDay - startingDay, finalHeight - startingHeight, fieldSum, numberOfFields); unsigned long long result = processCut(cuttingDay - startingDay, finalHeight, &fieldInfo, numberOfFields, minGrowSpeed); LOG(__FUNCTION__, "Computed result = %llu", result); printf("%llu\n",result); startingDay = cuttingDay; startingHeight = finalHeight; } } #endif
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | #include <stdio.h> #include <stdlib.h> #include <stdarg.h> #include <time.h> #include <string.h> #include <map> #include <vector> #ifdef ENABLE_LOG void printFormatted(const char* format, ...); #define LOG(TAG, ...) {\ char buffer[256];\ time_t now = time(0);\ struct tm* timeVal = gmtime(&now);\ strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", timeVal);\ printFormatted("%s| %s:%d: %s ", buffer, __FILE__, __LINE__, TAG);\ printFormatted(__VA_ARGS__);\ printFormatted("\n");\ } FILE* initLogIfNecessary() { static FILE* fp = NULL; if(fp == NULL) { fp=fopen("log.txt", "a"); if(fp == NULL) { fprintf(stderr, ("Unable to open log file.\n")); return NULL; } printFormatted("Compiled on %s %s\n", __DATE__, __TIME__); } return fp; } void printFormatted(const char * format, ... ) { FILE* logFile = initLogIfNecessary(); va_list args; va_start (args, format); vfprintf (logFile, format, args); va_end (args); fflush(logFile); } #else #define LOG(TAG, ...) #endif void helloWorldFunction() { printf("HelloWorld\n"); } #define MAX_NUM_OF_FIELDS 500000 typedef struct { unsigned long long currentHeight; int count; } fieldStruct; void fillFieldStruct(fieldStruct* fs, int growSpeed, unsigned long long currentHeight, int numFieldsGrowFaster) { //fs->growSpeed = growSpeed; fs->currentHeight = currentHeight; //fs->numFieldsGrowFaster = numFieldsGrowFaster; } void updateFieldStructInfo(std::vector<int>* fieldTypes, std::map<int,fieldStruct*> * fieldsMap, int newFieldType) { std::map<int, fieldStruct*>::iterator it = fieldsMap->find(newFieldType); LOG(__FUNCTION__, "entering function"); fieldStruct* fsPtr; if(it != fieldsMap->end()) { fsPtr = it->second; fsPtr->count ++; } else { fsPtr = (fieldStruct*)malloc(sizeof(fieldStruct)); fieldTypes->push_back(newFieldType); fsPtr->count = 1; fsPtr->currentHeight = 0; (*fieldsMap)[newFieldType] = fsPtr; } LOG(__FUNCTION__, "leving function"); } void fillMap(std::map<int,fieldStruct*> * fieldsMap, int* growSpeedArr, int numberOfFields) { int i = 0; fieldStruct fieldInfo; fieldStruct* fsPtr = NULL; std::vector<int> diffFields; for(i = 0; i < numberOfFields; i++) { int speed = growSpeedArr[i]; updateFieldStructInfo(&diffFields, fieldsMap, speed); } } unsigned long long computeSia(unsigned long long daysOfGrow, unsigned long long heightDiff, unsigned long long fieldSum, int numOfFields) { return ((fieldSum * daysOfGrow) - (numOfFields*heightDiff)); } unsigned long long computeFieldSum(int numberOfFields, int* growSpeed) { int i = 0; unsigned long long result = 0; for(i = 0; i < numberOfFields; i++) { result += growSpeed[i]; } return result; } unsigned long long processCut(unsigned long long daysOfGrow, unsigned long long finalHeight, std::map<int,fieldStruct*>* fieldInfo, int numberOfFields, int minGrowSpeed) { LOG(__FUNCTION__, "called with daysOfGrow=%llu, finalHeight=%llu, numberOfFields=%d", daysOfGrow, finalHeight, numberOfFields); int i = 0; unsigned long long sum = 0; for(std::map<int, fieldStruct*>::iterator it = fieldInfo->begin(); it != fieldInfo->end(); it++) { int speed = it->first; fieldStruct* fs = it->second; fs->currentHeight += speed * daysOfGrow; long long diff = fs->currentHeight - finalHeight; if(diff > 0) { LOG(__FUNCTION__, "diff greater equals %llu for currHeight[%d]=%llu",diff, i, fs->currentHeight); fs->currentHeight -= diff; sum += diff*fs->count; } } return sum; } #ifndef UNIT_TEST int main(int argc, char* argv[]) { int numberOfFields, numberOfCuts; int growSpeed[MAX_NUM_OF_FIELDS]; int minGrowSpeed = 10000000; unsigned long long currHeight[MAX_NUM_OF_FIELDS]; memset(currHeight, 0, sizeof(currHeight)); scanf("%d %d", &numberOfFields, &numberOfCuts); LOG(__FUNCTION__, "read numberOfFields = %d, numberOfCuts = %d", numberOfFields, numberOfCuts); int i = 0; for(i = 0; i < numberOfFields; i++) { scanf("%d", &(growSpeed[i])); LOG(__FUNCTION__, "Scanned : growSpeed[%d]=%d", i, growSpeed[i]); minGrowSpeed = minGrowSpeed > growSpeed[i] ? growSpeed[i] : minGrowSpeed; } std::map<int, fieldStruct*> fieldInfo; fillMap(&fieldInfo, growSpeed, numberOfFields); unsigned long long startingDay, startingHeight; startingDay = 0; startingHeight = 0; unsigned long long cuttingDay, finalHeight; for(i = 0; i < numberOfCuts; i++) { scanf("%llu %llu",&cuttingDay, &finalHeight); LOG(__FUNCTION__, "Scanned cuttingDay:%llu, finalHeight:%llu", cuttingDay, finalHeight); // unsigned long long result = computeSia(cuttingDay - startingDay, finalHeight - startingHeight, fieldSum, numberOfFields); unsigned long long result = processCut(cuttingDay - startingDay, finalHeight, &fieldInfo, numberOfFields, minGrowSpeed); LOG(__FUNCTION__, "Computed result = %llu", result); printf("%llu\n",result); startingDay = cuttingDay; startingHeight = finalHeight; } } #endif |