Skip to content

Instantly share code, notes, and snippets.

@calee0219
Last active November 19, 2019 13:00
Show Gist options
  • Save calee0219/d9d35ef83cbaf9a75fec271e634cfd44 to your computer and use it in GitHub Desktop.
Save calee0219/d9d35ef83cbaf9a75fec271e634cfd44 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100
#define MIN 1
int PRIME[MAX] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int NUM[MAX] = {};
int test_num;
int final_ans;
int final_order[MAX] = {};
int find_max_factor(int x) {
int prime_idx = 0;
while (PRIME[prime_idx] <= x) {
if (x % PRIME[prime_idx]) {
prime_idx++;
} else {
int max_fac = x / PRIME[prime_idx];
if (NUM[max_fac]) {
return max_fac;
} else {
prime_idx++;
}
}
}
if (NUM[1]) {
return 1;
}
return x;
}
int min(int a, int b) {
return a < b ? a : b;
}
void recursive(int depth, int used, int ans, int order[]) {
if (used == 0) {
//printf("ans: %d\norder:", ans);
/*
for(size_t idx = 0; order[idx] != 0; ++idx) {
printf("%d ", order[idx]);
}
printf("\n");
*/
if (ans < final_ans) {
memcpy(final_order, order, sizeof(int) * depth);
final_ans = ans;
}
//exit(0);
return;
}
//printf("depth: %d, used: %d\n", depth, used);
for (int idx = test_num; idx > 0; --idx) {
if (!NUM[idx]){
continue;
} else {
int factor = find_max_factor(idx);
if (ans + factor >= final_ans) {
continue;
}
order[depth] = idx;
NUM[factor] = 0;
NUM[idx] = 0;
ans += factor;
int new_used = used - 1 - (!(factor == idx));
recursive(depth+1, new_used, ans, order);
ans -= factor;
NUM[idx] = 1;
NUM[factor] = 1;
order[depth] = 0;
}
}
return;
}
int main() {
fprintf(stdout, "What number do you want to test? (%d ~ %d) ", MIN, MAX);
fscanf(stdin, "%d", &test_num);
if (test_num > MAX || test_num < MIN) {
fprintf(stdout, "Input(%d) number is out of range! (%d ~ %d)", test_num, MIN, MAX);
return 0;
}
// Initialize (Set NUM to unused)
for (int idx = 1; idx <= test_num; ++idx) {
NUM[idx] = 1;
final_order[idx] = 0;
}
final_ans = INT_MAX;
time_t before = time(NULL);
int order[MAX] = {};
recursive(0, test_num, 0, order);
fprintf(stdout, "Used time: %ld sec\n", time(NULL) - before);
final_ans = test_num * (test_num+1) / 2 - final_ans;
fprintf(stdout, "Ans: %d\norder: ", final_ans);
for(size_t idx = 0; final_order[idx] != 0; ++idx) {
fprintf(stdout, "%d ", final_order[idx]);
}
fprintf(stdout, "\n");
return 0;
}
@calee0219
Copy link
Author

╭─calee@workstation ~/junior/mine
╰─➤ echo 1 | ./a.out 1 ↵
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 1
order: 1
╭─calee@workstation ~/junior/mine
╰─➤ echo 2 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 1
order: 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 3 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 3
order: 3 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 4 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 3
order: 4 3
╭─calee@workstation ~/junior/mine
╰─➤ echo 5 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 6
order: 5 4 3
╭─calee@workstation ~/junior/mine
╰─➤ echo 6 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 6
order: 6 5 4
╭─calee@workstation ~/junior/mine
╰─➤ echo 7 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 11
order: 7 6 5 4
╭─calee@workstation ~/junior/mine
╰─➤ echo 8 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 15
order: 8 7 6 5 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 9 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 21
order: 9 8 7 6 5 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 10 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 21
order: 10 9 8 7 6 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 11 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 28
order: 11 10 9 8 7 6 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 12 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 28
order: 12 11 10 9 8 7 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 13 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 3 sec
Ans: 39
order: 13 12 11 10 9 8 7 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 14 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 20 sec
Ans: 39
order: 14 13 12 11 10 9 8 2

@calee0219
Copy link
Author

╭─calee@workstation ~/junior/mine
╰─➤ echo 15 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 192 sec
Ans: 49
order: 15 14 13 12 11 10 9 8 2

@calee0219
Copy link
Author

╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 20
Used time: 0 sec
Ans: 92
order: 20 19 18 17 16 15 14 13 12 11 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 21
Used time: 3 sec
Ans: 106
order: 21 20 19 18 17 16 15 14 13 12 11 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 22
Used time: 1 sec
Ans: 106
order: 22 21 20 19 18 17 16 15 14 13 12 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 23
Used time: 15 sec
Ans: 125
order: 23 22 21 20 19 18 17 16 15 14 13 12 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 24
Used time: 14 sec
Ans: 131
order: 24 23 22 21 20 19 18 17 16 15 14 13 6 4
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 25
Used time: 124 sec
Ans: 146
order: 25 24 23 22 21 20 19 18 17 16 15 14 13 6 4

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment