#include <stdio.h>
#include <math.h>
double sizes[] = {10, 11, 11.75, 10.5, 11.3, 13.25};
int coins[] = {1, 5, 10, 50, 100, 500};
double min = 0;
int minData[6];

// prototype
void permute(int *s, int *r, int n);
void calc(int *r);

void permute(int *s, int *r, int n)
{
  int i, t;
  if (!n) {
    calc(r);
    return;
  }

  n--;
  for ( i = 0; i < 6; ++i) {
    if (s[i] != -1) {
      r[n] = s[i];
      t = s[i];
      s[i] = -1;
      permute(s, r, n);
      s[i] = t;
    }
  }


}

void calc(int *r)
{
  int i;
  double lth = 0;
  for ( i = 0; i < 6; ++i)
    printf("%4d円,", coins[r[i]]);
  // putchar('\n');
  for ( i = 0; i < 5; ++i)
    lth += 2 * sqrt(sizes[r[i]] * sizes[r[i + 1]]);
  printf(" 距離 = %f\n", lth);
  if ((min == 0) | (min > lth)) {
    min = lth;
    for ( i = 0; i < 6; ++i)
      minData[i] = r[i];
  }
}

int main(void)
{
  int s[6], r[6], i;
  for ( i = 0; i < 6; ++i) {
    s[i] = i;
  }
  permute(s, r, 6);
  printf("最短距離 = %f mm\n", min);
  printf("並び= ");
  for ( i = 0; i < 6; ++i)
    printf("%d円 ", coins[minData[i]]);
  putchar('\n');

  return 0;
}