CodeIQ「中学入試から：数列の和」解答コード

cn_suretu.c

#include <stdio.h>

typedef unsigned long long ull;

typedef struct {
	ull syoko, kosa;
} sequence_info_t;

/* seq_strを読み取り、整数でsequenceに格納する。その要素数を返す。 */
unsigned  read_sequence(const char *seq_str,ull sequence[]) {
	ull current_value=0;
	int read_num=0;
	for (;;) {
		if(*seq_str == ',' || *seq_str == '\0') {
			sequence[read_num++] = current_value;
			current_value = 0;
			if (*seq_str == '\0') break;
		} else {
			current_value = current_value * 10 + *seq_str - '0';
		}
		seq_str++;
	}
	return read_num;
}

/* 数列の第index項の値を得る */
ull get_sequence_value(int si_num,const sequence_info_t si[], int index) {
	return si[index % si_num].syoko + si[index % si_num].kosa * (index / si_num);
}

/* 非負整数を文字列に変換する */
void ull_to_str(char *out, ull num) {
	char buffer[64];
	char *p = buffer;
	do {
		*(p++) = (num % 10) + '0';
	} while ((num /= 10) > 0);
	do {
		*(out++) = *(--p);
	} while (p != buffer);
	*out = '\0';
}

/* 二つの文字列が同一かを判定する(同一なら非0、同一でないなら0を返す) */
int is_same_strings(const char *s1, const char *s2) {
	while (*s1 != '\0' || *s2 != '\0') {
		if (*(s1++) != *(s2++)) return 0;
	}
	return 1;
}

int main(void) {
	char id[32];
	char seq_str[1024];
	int b, c;
	char expected_answer[64];
	while (scanf("%s%s%d%d%s", id, seq_str, &b, &c, expected_answer) == 5) {
		char real_answer[64];
		ull sequence[1000];
		int seq_length;
		sequence_info_t si[1000];
		int si_num;
		int i;
		int accepted = 0;
		seq_length = read_sequence(seq_str, sequence);
		/* 問題の数列は複数の等差数列を混ぜたものと推測し、
		 * 等差数列の数とそれぞれの初項および公差を求める */
		for (si_num = 1; si_num <= seq_length / 2; si_num++) {
			/* 初項と公差を求める */
			for (i = 0; i < si_num; i++) {
				si[i].syoko = sequence[i];
				si[i].kosa = sequence[i + si_num] - sequence[i];
			}
			/* 数列と合っているか確かめる */
			accepted = 1;
			for (i = 0; i < seq_length; i++) {
				if (get_sequence_value(si_num, si, i) != sequence[i]) {
					accepted = 0;
					break;
				}
			}
			if (accepted) break;
		}
		if (accepted) {
			/* 数列の生成規則が見つかった */
			ull sum = 0;
			for ( i = b - 1; i < c; i++) {
				/* 愚直に和を求める */
				sum += get_sequence_value(si_num, si, i);
			}
			/* 和を文字列に変換する */
			ull_to_str(real_answer, sum);
			/* 答えが一致するかを確かめる */
			if (!is_same_strings(expected_answer, real_answer)) {
				fprintf(stderr, "%s,", id);
				printf("%s : expected %s, got %s\n", id, expected_answer, real_answer);
			}
		} else {
			printf("%s : ERROR unsupported sequence\n", id);
			continue;
		}
	}
	putc('\n', stderr);
	return 0;
}