tax_game_bruteforce_range.c

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

#define MAX 100
#define MIN 1
#define ORD_SIZE 50

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[ORD_SIZE][MAX] = {};
int final_order_idx = 0;

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) {
    if (ans == final_ans) {
      if (final_order_idx < ORD_SIZE) {
        memcpy(final_order[final_order_idx++], order, sizeof(int) * depth);
      }
    } else if (ans < final_ans) {
      final_order_idx = 0;
      memcpy(final_order[final_order_idx++], 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));
      //printf("idx: %d, fac: %d, used: %d\n", idx, factor, new_used);
      recursive(depth+1, new_used, ans, order);
      ans -= factor;
      NUM[idx] = 1;
      NUM[factor] = 1;
      order[depth] = 0;
    }
  }
  return;
}

void init() {
  // Initialize (Set NUM to unused)
  for (int idx = 1; idx <= test_num; ++idx) {
    NUM[idx] = 1;
    for (int idxx = 0; idxx < ORD_SIZE; ++idxx) {
      final_order[idxx][idx] = 0;
    }
  }
  final_ans = INT_MAX;
  final_order_idx = 0;

  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\n", final_ans);

  for (int idxx = 0; idxx < final_order_idx; ++idxx) {
    fprintf(stdout, "Order: ");
    for (size_t idx = 0; final_order[idxx][idx] != 0; ++idx) {
      fprintf(stdout, "%d ", final_order[idxx][idx]);
    }
    fprintf(stdout, "\tAns: %d\n", final_ans);
  }
}

int main() {
  fprintf(stdout, "Begin from? (%d ~ %d) ", MIN, MAX);
  int begin, end;
  fscanf(stdin, "%d", &begin);
  fprintf(stdout, "End to? (%d ~ %d) ", MIN, MAX);
  fscanf(stdin, "%d", &end);

  if (begin > end) {
    fprintf(stdout, "Begin(%d) is bigger than End(%d)\n", begin, end);
    return 0;
  }
  if (begin > MAX || begin < MIN || end > MAX || end < MIN) {
    fprintf(stdout, "Begin(%d) or End(%d) number is out of range! (%d ~ %d)\n", begin, end, MIN, MAX);
    return 0;
  }

  for (int i = begin; i <= end; ++i) {
    fprintf(stdout, "===========================================\n");
    test_num = i;
    fprintf(stdout, "n = %d\n", i);
    init();
    fprintf(stdout, "===========================================\n");
    fflush(stdout);
  }

  return 0;
}