epoch@まつやま2008の予選問題
予選期間が終わったので，とりあえず自分が書いたのを晒してみる(終わったし問題ないはず)．minunitとか問題付きのアーカイブはこちら．久しぶりのCでした．
長くなったので続きを読む．ついでに言うと，別に面白いソースではありません(minunitも削除済み)．
- 問1
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <inttypes.h> static int32_t *read_data(int32_t *, int32_t *); static int32_t resolve_problem(int32_t *, int32_t, int32_t); static int32_t num_comp(const void *, const void *); int main(int argc, char *argv[]) { int32_t answer; int32_t offset; int32_t input_num; int32_t *input_values; input_values = read_data(&input_num, &offset); if (input_values == NULL) exit(EXIT_FAILURE); answer = resolve_problem(input_values, input_num, offset); printf("%"PRId32"\n", answer); return EXIT_SUCCESS; } /* * read input data from stdin */ static int32_t * read_data(int32_t *input_num, int32_t *offset) { int32_t num; int32_t *p, *values; scanf("%"SCNd32" %"SCNd32, input_num, offset); p = values = malloc(sizeof(int32_t) * (*input_num)); if (values == NULL) return NULL; while (scanf("%"SCNd32, &num) != EOF) *p++ = num; return values; } /* * main section of this program */ static int32_t resolve_problem(int32_t *input_values, int32_t input_num, int32_t offset) { qsort(input_values, input_num, sizeof(int32_t), num_comp); return input_values[offset - 1]; } /* * helper for qsort */ static int32_t num_comp(const void *_num1, const void *_num2) { int32_t num1 = *(int32_t *)_num1; int32_t num2 = *(int32_t *)_num2; if (num1 < num2) return -1; else if (num1 > num2) return 1; else return 0; }
- 問2
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INPUT_END "END" // end of input data enum { MAX = 256 }; // max length(255) + null character(1) static char **read_data(int *); static char **realloc_table(char **, int, int); static int resolve_problem(char **, int); static int search_string(char **, int, const char *, int, int); static char *reverse_string(const char *, int); int main(int argc, char *argv[]) { int answer; int input_num; char **input_values; input_values = read_data(&input_num); if (input_values == NULL) exit(EXIT_FAILURE); answer = resolve_problem(input_values, input_num); printf("%d\n", answer); return EXIT_SUCCESS; } /* * read input data from stdin */ static char ** read_data(int *input_num) { int count = 0; char buf[MAX]; char **values; values = malloc(sizeof(char *)); if (values == NULL) return NULL; while (scanf("%s", buf) != EOF) { int len; if (!strncmp(buf, INPUT_END, sizeof(INPUT_END))) break; len = strlen(buf); if ((values = realloc_table(values, count, len)) == NULL) return NULL; strncpy(values[count], buf, len); count++; } *input_num = count; return values; } /* * memory extension for input data */ static char ** realloc_table(char **table, int size, int len) { char **new, *str; new = realloc(table, sizeof(char *) * (size + 1)); str = calloc(len + 1, sizeof(char)); if (new == NULL || str == NULL) return NULL; new[size] = str; return new; } /* * main section of this program(not implement) */ static int resolve_problem(char **input_values, int input_num) { int i; int len; int count = 0; char *str, *rev; for (i = 0; i < input_num; i++) { if (input_values[i][0] == '\0') continue; str = input_values[i]; len = strlen(str); rev = reverse_string(str, len); count += search_string(input_values, input_num, str, len, i + 1); count += search_string(input_values, input_num, rev, len, i + 1); } return count; } /* * helper for resolve_problem */ static int search_string(char **input_values, int input_num, const char *str, int len, int start) { int i; int count = 0; for (i = start; i < input_num; i++) { if (!strncmp(str, input_values[i], len)) { input_values[i][0] = '\0'; count++; } } return count; } /* * create reverse string with _src_ argument */ static char * reverse_string(const char *src, int len) { int i; static char rev[MAX]; memset(rev, 0, len + 1); for (i = 0; i < len; i++) rev[i] = src[len - i - 1]; return rev; }
- 問3
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <stdbool.h> #include <inttypes.h> enum { INC = 2, // memory size increment for realloc UPPER = 4 // initialize upper }; static int32_t *read_data(int32_t *, int32_t *); static int32_t *create_prime_table(int32_t, int32_t *); static int32_t *realloc_table(int32_t *, int32_t *); static int32_t resolve_problem(int32_t *, int32_t, int32_t *, int32_t); static bool check_prime(int32_t); int main(int argc, char *argv[]) { int32_t answer; int32_t max_value; int32_t input_num, table_size; int32_t *input_values, *prime_table; input_values = read_data(&input_num, &max_value); prime_table = create_prime_table(max_value, &table_size); if (input_values == NULL || prime_table == NULL) exit(EXIT_FAILURE); answer = resolve_problem(input_values, input_num, prime_table, table_size); printf("%"PRId32"\n", answer); return EXIT_SUCCESS; } /* * read input data from stdin */ static int32_t * read_data(int32_t *input_num, int32_t *max_value) { int32_t num; int32_t max = 0; int32_t *p, *values; scanf("%"SCNd32, input_num); p = values = malloc(sizeof(int32_t) * (*input_num)); if (values == NULL) return NULL; while (scanf("%"SCNd32, &num) != EOF) { *p++ = num; if (max < num) max = num; } *max_value = max; return values; } /* * create prime table with _max_ argument */ static int32_t * create_prime_table(int32_t max, int32_t *table_size) { int32_t i, n; int32_t limit = max / 2; // required primes are half max value int32_t upper = UPPER; int32_t stkptr = 0; int32_t *table = malloc(sizeof(int32_t) * upper); if (table == NULL) return NULL; table[stkptr++] = 2; table[stkptr++] = 3; for (n = 5; n <= limit; n += 2) { // even is not prime int32_t flag = 0; if (stkptr >= upper - 1) if ((table = realloc_table(table, &upper)) == NULL) return NULL; for (i = 1; table[i] * table[i] <= n; i++) { if (n % table[i] == 0) { flag = 1; break; } } if (!flag) table[stkptr++] = n; } *table_size = stkptr; return table; } /* * memory extension for prime table */ static int32_t * realloc_table(int32_t *table, int32_t *upper) { int32_t *new; *upper += INC; new = realloc(table, sizeof(int32_t) * (*upper)); return new; } /* * main section of this program */ static int32_t resolve_problem(int32_t *input_values, int32_t input_num, int32_t *prime_table, int32_t table_size) { int32_t i, j; int32_t count = 0; for (i = 0; i < input_num; i++) { int32_t value = input_values[i]; for (j = 0; j < table_size; j++) { int32_t div, mod; int32_t prime = prime_table[j]; if (value < prime * 2) break; div = value / prime; mod = value % prime; if (!mod && check_prime(div)) { count++; break; } } } return count; } /* * check whether _value_ argument is prime */ static bool check_prime(int32_t value) { int32_t i; bool ret = true; if (value == 2 || value == 3 || value == 5) { ret = true; goto Last; } if (value % 2 == 0) { ret = false; goto Last; } for (i = 3; i * i <= value; i += 2) { if (value % i == 0) { ret = false; goto Last; } } Last: return ret; }
