Created
June 22, 2019 06:02
-
-
Save namthatman/9779721532585596542e8ea48bd751b5 to your computer and use it in GitHub Desktop.
This file contains hidden or 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 <assert.h> | |
| #include <limits.h> | |
| #include <math.h> | |
| #include <stdbool.h> | |
| #include <stddef.h> | |
| #include <stdint.h> | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| char* readline(); | |
| char** split_string(char*); | |
| int compare (const void * a, const void * b) | |
| { | |
| return ( *(int*)a - *(int*)b ); | |
| } | |
| // Complete the maximumToys function below. | |
| int maximumToys(int prices_count, int* prices, int k) { | |
| qsort(prices, prices_count, sizeof(int), compare); | |
| int i = 0; | |
| while (k > 0) { | |
| k = k - prices[i]; | |
| i++; | |
| } | |
| return i-1; | |
| } | |
| int main() | |
| { | |
| FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); | |
| char** nk = split_string(readline()); | |
| char* n_endptr; | |
| char* n_str = nk[0]; | |
| int n = strtol(n_str, &n_endptr, 10); | |
| if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); } | |
| char* k_endptr; | |
| char* k_str = nk[1]; | |
| int k = strtol(k_str, &k_endptr, 10); | |
| if (k_endptr == k_str || *k_endptr != '\0') { exit(EXIT_FAILURE); } | |
| char** prices_temp = split_string(readline()); | |
| int* prices = malloc(n * sizeof(int)); | |
| for (int i = 0; i < n; i++) { | |
| char* prices_item_endptr; | |
| char* prices_item_str = *(prices_temp + i); | |
| int prices_item = strtol(prices_item_str, &prices_item_endptr, 10); | |
| if (prices_item_endptr == prices_item_str || *prices_item_endptr != '\0') { exit(EXIT_FAILURE); } | |
| *(prices + i) = prices_item; | |
| } | |
| int prices_count = n; | |
| int result = maximumToys(prices_count, prices, k); | |
| fprintf(fptr, "%d\n", result); | |
| fclose(fptr); | |
| return 0; | |
| } | |
| char* readline() { | |
| size_t alloc_length = 1024; | |
| size_t data_length = 0; | |
| char* data = malloc(alloc_length); | |
| while (true) { | |
| char* cursor = data + data_length; | |
| char* line = fgets(cursor, alloc_length - data_length, stdin); | |
| if (!line) { break; } | |
| data_length += strlen(cursor); | |
| if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } | |
| size_t new_length = alloc_length << 1; | |
| data = realloc(data, new_length); | |
| if (!data) { break; } | |
| alloc_length = new_length; | |
| } | |
| if (data[data_length - 1] == '\n') { | |
| data[data_length - 1] = '\0'; | |
| } | |
| data = realloc(data, data_length); | |
| return data; | |
| } | |
| char** split_string(char* str) { | |
| char** splits = NULL; | |
| char* token = strtok(str, " "); | |
| int spaces = 0; | |
| while (token) { | |
| splits = realloc(splits, sizeof(char*) * ++spaces); | |
| if (!splits) { | |
| return splits; | |
| } | |
| splits[spaces - 1] = token; | |
| token = strtok(NULL, " "); | |
| } | |
| return splits; | |
| } |
This file contains hidden or 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
| Mark and Jane are very happy after having their first child. Their son loves toys, so Mark wants to buy some. There are a number of different toys lying in front of him, tagged with their prices. Mark has only a certain amount to spend, and he wants to maximize the number of toys he buys with this money. | |
| Given a list of prices and an amount to spend, what is the maximum number of toys Mark can buy? For example, if prices = [1,2,3,4] and Mark has k = 7 to spend, he can buy items [1,2,3] for 6, or [3,4] for 7 units of currency. He would choose the first group of 3 items. | |
| Function Description | |
| Complete the function maximumToys in the editor below. It should return an integer representing the maximum number of toys Mark can purchase. | |
| maximumToys has the following parameter(s): | |
| prices: an array of integers representing toy prices | |
| k: an integer, Mark's budget |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment