Submission #66142592

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const char* for_add[2048];
int for_add_len[2048];
const char* for_mult[2048];
int for_mult_len[2048];
int main(void) {
  int N;
  int t;
  if (scanf("%d", &N) != 1) return 1;
  for (t = 1; t <= N; t++) {
    if (t == 1) {
      for_add[t] = "1";
      for_add_len[t] = 1;
      for_mult[t] = "1";
      for_mult_len[t] = 1;
    } else if (t == 11) {
      for_add[t] = "11";
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char* for_add[2048];
int for_add_len[2048];
const char* for_mult[2048];
int for_mult_len[2048];

int main(void) {
	int N;
	int t;
	if (scanf("%d", &N) != 1) return 1;
	for (t = 1; t <= N; t++) {
		if (t == 1) {
			for_add[t] = "1";
			for_add_len[t] = 1;
			for_mult[t] = "1";
			for_mult_len[t] = 1;
		} else if (t == 11) {
			for_add[t] = "11";
			for_add_len[t] = 2;
			for_mult[t] = "11";
			for_mult_len[t] = 2;
		} else if (t == 111) {
			for_add[t] = "111";
			for_add_len[t] = 3;
			for_mult[t] = "111";
			for_mult_len[t] = 3;
		} else if (t == 1111) {
			for_add[t] = "1111";
			for_add_len[t] = 4;
			for_mult[t] = "1111";
			for_mult_len[t] = 4;
		} else {
			int add_best_a = -1, add_best_b = -1, add_best_score = 22222;
			int mult_best_a = -1, mult_best_b = -1, mult_best_score = 22222;
			int i;
			for (i = 1; i < t; i++) {
				int add_candidate = for_add_len[i] + for_add_len[t - i] + 1;
				if (add_candidate < add_best_score) {
					add_best_a = i;
					add_best_b = t - i;
					add_best_score = add_candidate;
				}
				if (t % i == 0 && i > 1) {
					int mult_candidate = for_mult_len[i] + for_mult_len[t / i] + 1;
					if (mult_candidate < mult_best_score) {
						mult_best_a = i;
						mult_best_b = t / i;
						mult_best_score = mult_candidate;
					}
				}
			}
			if (add_best_score <= mult_best_score) {
				char* res = malloc(add_best_score + 1);
				strcpy(res, for_add[add_best_a]);
				strcat(res, "+");
				strcat(res, for_add[add_best_b]);
				for_add[t] = res;
				for_add_len[t] = add_best_score;
			} else {
				char* res = malloc(mult_best_score + 1);
				strcpy(res, for_mult[mult_best_a]);
				strcat(res, "*");
				strcat(res, for_mult[mult_best_b]);
				for_add[t] = res;
				for_add_len[t] = mult_best_score;
			}
			if (add_best_score + 2 < mult_best_score) {
				char* res = malloc(add_best_score + 3);
				strcpy(res, "(");
				strcat(res, for_add[add_best_a]);
				strcat(res, "+");
				strcat(res, for_add[add_best_b]);
				strcat(res, ")");
				for_mult[t] = res;
				for_mult_len[t] = add_best_score + 2;
			} else {
				char* res = malloc(mult_best_score + 1);
				strcpy(res, for_mult[mult_best_a]);
				strcat(res, "*");
				strcat(res, for_mult[mult_best_b]);
				for_mult[t] = res;
				for_mult_len[t] = mult_best_score;
			}
		}
	}
	puts(for_add[N]);
	return 0;
}

Submission Info

Judge Result