#include <stdio.h>
#include <stdlib.h>
int b1[25] , b2[25][9];
int a[9];
int b[9];
int n1 = 0;
void sub3()
{
int i , j , k , l;
int s1[9] , s2;
for(i = 0 ; i < n1 ; i++) {
l = 0;
s2 = 0;
for(j = 0 ; j < b1[i] ; j++) {
s1[j] = 0;
for(k = 0 ; k < b2[i][j] ; k++) {
s1[j] = s1[j] * 10 + b[l++];
}
if(j > 0 && s1[j] < s1[j - 1]) break;
if(j < b1[i] - 1) s2 += (s1[j] * s1[j]);
}
if(j == b1[i] && s2 == s1[b1[i] - 1] * s1[b1[i] - 1]) {
for(j = 0 ; j < b1[i] ; j++) printf("%d " , s1[j]);
printf("\n");
}
}
}
void sub2(int d)
{
int i;
if(d == 9) {
sub3();
return;
}
for(i = 0 ; i < 9 - d ; i++) {
b[d] = a[i];
a[i] = a[9 - d - 1];
sub2(d + 1);
a[i] = b[d];
}
}
void sub1(int d , int n)
{
int i;
if(n == 0) {
if(d < 3) return;
for(i = 0 ; i < d ; i++) b2[n1][i] = b[i];
b1[n1] = d;
n1++;
return;
}
for(i = 1 ; i <= n ; i++) {
if(i < b[d - 1]) continue;
b[d] = i;
sub1(d + 1 , n - i);
}
}
void init(void)
{
int i , j;
for(i = 1 ; i < 10 ; i++) {
b[0] = i;
sub1(1 , 9 - i);
}
for(i = 0 ; i < 9 ; i++) a[i] = i + 1;
}
int main(void)
{
init();
sub2(0);
return(0);
}
|
第104回（11月）Unique Solution Checkboard Puzzle
|
|
#include <stdio.h>
#include <stdlib.h>
#define OFF 0
#define ON 1
typedef struct {
int x;
int y;
} XY;
typedef struct {
int n;
XY xy[5];
} PP;
typedef struct {
XY xy[13];
int j[13];
int a[13];
int s;
} Z;
static PP p1[13] ={
5 , 0,0 , 1,0 , 2,0 , 3,0 , 2,1 ,
5 , 0,0 , -1,1 , 0,1 , 1,1 , 0,2 ,
5 , 0,0 , 1,0 , 2,0 , 3,0 , 0,1 ,
5 , 0,0 , 1,0 , 2,0 , 3,0 , 4,0 ,
5 , 0,0 , 1,0 , 2,0 , 2,1 , 2,2 ,
5 , 0,0 , 0,1 , 1,1 , 2,1 , 2,2 ,
5 , 0,0 , 1,0 , 1,1 , 2,1 , 3,1 ,
5 , 0,0 , 1,0 , 1,1 , 2,1 , 2,2 ,
5 , 0,0 , 1,0 , 2,0 , 1,1 , 1,2 ,
5 , 0,0 , 1,0 , 2,0 , 0,1 , 1,1 ,
5 , 0,0 , 0,1 , 1,1 , 2,1 , 1,2 ,
5 , 0,0 , 0,1 , 1,1 , 2,1 , 2,0 ,
4 , 0,0 , 1,0 , 2,0 , 3,0 , 0,0};
static int dxy[8][4] ={
1,0,0,1 , -1,0,0,1 , 1,0,0,-1 , -1,0,0,-1 ,
0,1,1,0 , 0,-1,1,0 , 0,1,-1,0 , 0,-1,-1,0};
XY p2[8][8][13][8][5];
int p2n[8][8][13];
int p3[8][8][13][8];
int b[8][8];
int r[13];
int nz = 0;
XY p4[13];
int p5[13];
Z *z;
int p6[2048];
int t = 0;
void disp(int i)
{
int k , l;
int x , y;
char bb[8][8];
printf("--------\n");
for(y = 0 ; y < 8 ; y++) {
for(x = 0 ; x < 8 ; x++) bb[y][x] = 'm';
}
for(k = 0 ; k < 12 ; k++) {
x = z[i].xy[k].x;
y = z[i].xy[k].y;
for(l = 0 ; l < p1[k].n ; l++) {
bb[p2[y][x][k][z[i].j[k]][l].y][p2[y][x][k][z[i].j[k]][l].x] =
'a' + k;
}
}
for(y = 0 ; y < 8 ; y++) {
for(x = 0 ; x < 8 ; x++) printf("%c" , bb[y][x]);
printf("\n");
}
t++;
}
void set()
{
int i;
int x1 , y1 , x2 , y2;
z = (Z *)realloc(z , sizeof(Z) * (nz + 1));
for(i = 0 ; i < 12 ; i++) {
x1 = p4[i].x;
y1 = p4[i].y;
x2 = p2[y1][x1][i][p5[i]][p3[y1][x1][i][p5[i]]].x;
y2 = p2[y1][x1][i][p5[i]][p3[y1][x1][i][p5[i]]].y;
if(((x2 + y2) % 2) == 0) z[nz].a[i] = 0;
else z[nz].a[i] = 1;
z[nz].xy[i].x = p4[i].x;
z[nz].xy[i].y = p4[i].y;
z[nz].j[i] = p5[i];
}
if(z[nz].a[0] == 1) {
for(i = 0 ; i < 12 ; i++) z[nz].a[i] = 1 - z[nz].a[i];
}
z[nz].s = z[nz].a[1] * 1024
+ z[nz].a[2] * 512
+ z[nz].a[3] * 256
+ z[nz].a[4] * 128
+ z[nz].a[5] * 64
+ z[nz].a[6] * 32
+ z[nz].a[7] * 16
+ z[nz].a[8] * 8
+ z[nz].a[9] * 4
+ z[nz].a[10] * 2
+ z[nz].a[11];
p6[z[nz].s]++;
nz++;
}
int cmp2(void *a , void *b)
{
int i;
for(i = 0 ; i < 12 ; i++) {
if ( ((Z *)a)->a[i] < ((Z *)b)->a[i] ) return(-1);
else if( ((Z *)a)->a[i] > ((Z *)b)->a[i] ) return(1);
}
return(0);
}
int cmp1(void *a , void *b)
{
if (((XY *)a)->y < ((XY *)b)->y) return(-1);
else if(((XY *)a)->y == ((XY *)b)->y) {
if(((XY *)a)->x < ((XY *)b)->x) return(-1);
else return(1);
}
else return(1);
}
void init()
{
int i , j , k , l;
XY min;
int n;
int x , y;
int bx , by;
for(y = 0 ; y < 8 ; y++) {
for(x = 0 ; x < 8 ; x++) {
for(i = 0 ; i < 13 ; i++) {
n = 0;
for(j = 0 ; j < 8 ; j++) {
min.x = min.y = 100;
for(k = 0 ; k < p1[i].n ; k++) {
p2[y][x][i][n][k].x = p1[i].xy[k].x * dxy[j][0] +
p1[i].xy[k].y * dxy[j][1];
p2[y][x][i][n][k].y = p1[i].xy[k].x * dxy[j][2] +
p1[i].xy[k].y * dxy[j][3];
if(p2[y][x][i][n][k].y < min.y ||
(p2[y][x][i][n][k].y == min.y &&
p2[y][x][i][n][k].x < min.x)) {
min.x = p2[y][x][i][n][k].x;
min.y = p2[y][x][i][n][k].y;
}
}
for(k = 0 ; k < p1[i].n ; k++) {
p2[y][x][i][n][k].x += (x - min.x);
if(p2[y][x][i][n][k].x < 0 || p2[y][x][i][n][k].x > 7)
break;
p2[y][x][i][n][k].y += (y - min.y);
if(p2[y][x][i][n][k].y < 0 || p2[y][x][i][n][k].y > 7)
break;
}
if(k < p1[i].n) continue;
bx = p2[y][x][i][n][0].x;
by = p2[y][x][i][n][0].y;
qsort((char *)p2[y][x][i][n] , p1[i].n , sizeof(XY) , cmp1);
for(k = 0 ; k < p1[i].n ; k++) {
if(p2[y][x][i][n][k].x == bx &&
p2[y][x][i][n][k].y == by) {
p3[y][x][i][n] = k;
break;
}
}
for(l = 0 ; l < n ; l++) {
for(k = 0 ; k < p1[i].n ; k++) {
if(p2[y][x][i][l][k].x != p2[y][x][i][n][k].x)
break;
if(p2[y][x][i][l][k].y != p2[y][x][i][n][k].y)
break;
}
if(k == p1[i].n) {
n--;
break;
}
}
n++;
p2n[y][x][i] = n;
}
}
}
}
for(y = 0 ; y < 8 ; y++) {
for(x = 0 ; x < 8 ; x++) b[y][x] = -1;
}
for(y = 0 ; y < 13 ; y++) r[y] = OFF;
for(y = 0 ; y < 2048 ; y++) p6[y] = 0;
z = (Z *)malloc(sizeof(Z));
}
int check(int x , int y , int i , int j)
{
int k;
for(k = 0 ; k < p1[i].n ; k++) {
if(b[p2[y][x][i][j][k].y][p2[y][x][i][j][k].x] != -1) return(OFF);
}
for(k = 0 ; k < p1[i].n ; k++) {
b[p2[y][x][i][j][k].y][p2[y][x][i][j][k].x] = i;
}
if((b[0][7] != -1 && b[0][0] > b[0][7]) ||
(b[7][0] != -1 && b[0][7] > b[7][0]) ||
(b[7][7] != -1 && b[0][0] > b[7][7])) {
for(k = 0 ; k < p1[i].n ; k++) {
b[p2[y][x][i][j][k].y][p2[y][x][i][j][k].x] = -1;
}
return(OFF);
}
p4[i].x = x;
p4[i].y = y;
p5[i] = j;
return(ON);
}
void toru(int x , int y , int i , int j)
{
int k;
for(k = 0 ; k < p1[i].n ; k++) {
b[p2[y][x][i][j][k].y][p2[y][x][i][j][k].x] = -1;
}
}
void sub(int x , int y)
{
int i , j;
if(x == 8) {
x = 0;
y++;
if(y == 8) {
set();
return;
}
}
if(b[y][x] != -1) {
sub(x + 1 , y);
return;
}
for(i = 0 ; i < 13 ; i++) {
if(r[i] == ON) continue;
r[i] = ON;
for(j = 0 ; j < p2n[y][x][i] ; j++) {
if(check(x , y , i , j) == ON) {
sub(x + 1 , y);
toru(x , y , i , j);
}
}
r[i] = OFF;
}
}
void sub2()
{
int i;
for(i = 0 ; i < nz ; i++) {
if(p6[z[i].s] == 1) disp(i);
}
}
int main(void)
{
init();
sub(0 , 0);
sub2();
free(z);
return(0);
}
|
第103回（10月）ノナヒューブ
|
|
#include <stdio.h>
#include <stdlib.h>
#define OFF 0
#define ON 1
typedef struct {
int x;
int y;
int z;
} XYZ;
typedef struct {
XYZ p1;
int n;
XYZ p2[3];
} P;
P p[27];
int b[3][3][3];
int b1[3][3][3];
int fxyz[6][9];
int u[12];
static int dai[12][2] = {3,4 , 2,5 , 1,7 , 6,8 , 5,7 , 2,8 , 0,4 , 3,6 ,
3,7 , 4,6 , 0,8 , 1,5};
int count = 0;
int mode;
void init()
{
int x , y , z;
int i;
for(z = 0 ; z < 3 ; z++) {
for(y = 0 ; y < 3 ; y++) {
for(x = 0 ; x < 3 ; x++) {
b[z][y][x] = -1;
}
}
}
for(x = 0 ; x < 12 ; x++) u[x] = x;
for(y = 0 ; y < 6 ; y++) {
for(x = 0 ; x < 9 ; x++) {
fxyz[y][x] = 0;
}
}
x = y = z = 0;
for(i = 0 ; i < 27 ; i++) {
p[i].p1.x = x;
p[i].p1.y = y;
p[i].p1.z = z;
p[i].n = 0;
if(x < 2) {
p[i].p2[p[i].n].x = x + 1;
p[i].p2[p[i].n].y = y;
p[i].p2[p[i].n].z = z;
p[i].n ++;
}
if(y < 2) {
p[i].p2[p[i].n].x = x;
p[i].p2[p[i].n].y = y + 1;
p[i].p2[p[i].n].z = z;
p[i].n ++;
}
if(z < 2) {
p[i].p2[p[i].n].x = x;
p[i].p2[p[i].n].y = y;
p[i].p2[p[i].n].z = z + 1;
p[i].n ++;
}
x++;
if(x == 3) {
x = 0;
y++;
if(y == 3) {
y = 0;
z++;
}
}
}
}
int okeru1(XYZ a , int dai)
{
if(a.x == 0 && fxyz[0][dai] == ON) return(OFF);
if(a.x == 2 && fxyz[1][dai] == ON) return(OFF);
if(a.y == 0 && fxyz[2][dai] == ON) return(OFF);
if(a.y == 2 && fxyz[3][dai] == ON) return(OFF);
if(a.z == 0 && fxyz[4][dai] == ON) return(OFF);
if(a.z == 2 && fxyz[5][dai] == ON) return(OFF);
return(ON);
}
int okeru2(XYZ a , int dai , int n , int t)
{
if(b[a.z][a.y][a.x] != -1) return(OFF);
if(okeru1(a , dai) == OFF) return(OFF);
if (n == 6) {
if(mode > 0 && t < b1[0][0][0]) return(OFF);
}
else if(n == 9) {
if(mode == 0 && t < b1[0][1][0]) return(OFF);
}
else if(n == 18) {
if(mode == 2 && t < b1[0][0][0]) return(OFF);
}
else if(n == 24) {
if(mode == 2 && t < b1[0][0][0]) return(OFF);
}
return(ON);
}
void oku(XYZ a , int dai , int t)
{
b[a.z][a.y][a.x] = dai;
if(a.x == 0) fxyz[0][dai] = ON;
if(a.x == 2) fxyz[1][dai] = ON;
if(a.y == 0) fxyz[2][dai] = ON;
if(a.y == 2) fxyz[3][dai] = ON;
if(a.z == 0) fxyz[4][dai] = ON;
if(a.z == 2) fxyz[5][dai] = ON;
b1[a.z][a.y][a.x] = t;
}
void toru(XYZ a , int dai)
{
b[a.z][a.y][a.x] = -1;
if(a.x == 0) fxyz[0][dai] = OFF;
if(a.x == 2) fxyz[1][dai] = OFF;
if(a.y == 0) fxyz[2][dai] = OFF;
if(a.y == 2) fxyz[3][dai] = OFF;
if(a.z == 0) fxyz[4][dai] = OFF;
if(a.z == 2) fxyz[5][dai] = OFF;
}
void oku3(XYZ a)
{
b[a.z][a.y][0] = 0;
b[a.z][a.y][1] = 1;
b[a.z][a.y][2] = 2;
fxyz[0][0] = fxyz[1][2] = ON;
if(a.y == 0) fxyz[2][0] = fxyz[2][1] = fxyz[2][2] = ON;
if(a.z == 0) fxyz[4][0] = fxyz[4][1] = fxyz[4][2] = ON;
b1[a.z][a.y][0] = b1[a.z][a.y][1] = b1[a.z][a.y][2] = 12;
}
void toru3(XYZ a)
{
b[a.z][a.y][0] = b[a.z][a.y][1] = b[a.z][a.y][2] = -1;
fxyz[0][0] = fxyz[1][2] = OFF;
if(a.y == 0) fxyz[2][0] = fxyz[2][1] = fxyz[2][2] = OFF;
if(a.z == 0) fxyz[4][0] = fxyz[4][1] = fxyz[4][2] = OFF;
}
void sub(int n , int nu)
{
int i , j , k , t;
int dai0 , dai1;
if (n == 14) {
if(b[1][1][1] != b[0][0][0] && b[1][1][1] != b[0][0][2] &&
b[1][1][1] != b[0][2][0] && b[1][1][1] != b[0][2][2]) return;
}
else if(n == 28) {
count++;
return;
}
if(b[p[n].p1.z][p[n].p1.y][p[n].p1.x] != -1) {
sub(n + 1 , nu);
return;
}
for(i = 0 ; i < nu ; i++) {
t = u[i];
u[i] = u[nu - 1];
for(k = 0 ; k < 2 ; k++) {
dai0 = dai[t][k];
if(okeru1(p[n].p1 , dai0) == OFF) continue;
dai1 = dai[t][1 - k];
for(j = 0 ; j < p[n].n ; j++) {
if(okeru2(p[n].p2[j] , dai1 , n , t) == OFF) continue;
oku(p[n].p1 , dai0 , t);
oku(p[n].p2[j] , dai1 , t);
sub(n + 1 , nu - 1);
toru(p[n].p2[j] , dai1);
toru(p[n].p1 , dai0);
}
}
u[i] = t;
}
}
int main(void)
{
static XYZ a[3] = {0,0,0 , 0,1,0 , 0,1,1};
init();
for(mode = 0 ; mode < 3 ; mode++) {
oku3(a[mode]);
sub(0 , 12);
toru3(a[mode]);
}
printf("%d\n" , count);
return(0);
}
|
第102回（9月）三角形の奇妙な一致
|
|
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int x , y , z;
int s1 , s2;
for(x = 1 ; x < 17 ; x++) {
y = x;
while(1) {
s1 = 2 * x + 2 * y - 1;
s2 = s1 * (2 * y - 1) * (2 * x - 1);
if(s1 * s1 * 16 < s2) break;
for(z = y ; z < x + y ; z++) {
s1 = x + y + z;
s2 = s1 * (-x + y + z) * (x - y + z) * (x + y - z);
s1 *= (s1 * 16);
if(s1 == s2) printf("%d %d %d\n" , x , y , z);
}
y++;
}
}
return(0);
}
|
第101回（8月）遺伝子数
|
|
#include <stdio.h>
#include <stdlib.h>
int d[9] , dd[9];
void init()
{
int i;
d[0] = 1;
dd[0] = 0;
for(i = 1 ; i < 9 ; i++) {
dd[i] = 111 * i * (i - 1);
d[i] = d[i - 1] * 10;
}
}
void sub7(int a[] , int p0 , int q0)
{
int i , t , p1 , q1;
for(i = 0 ; i < 2 ; i++) {
t = a[i];
p1 = p0 + t * d[7];
q1 = q0 + t;
if(p1 == q1 * dd[7]) printf("%d\n" , p1);
t = a[1 - i];
p1 += (t * d[8]);
q1 += t;
if(p1 == q1 * dd[8]) printf("%d\n" , p1);
}
}
void sub0(int a[] , int p0 , int q0 , int n)
{
int i , t , p1 , q1;
for(i = 0 ; i < 9 - n ; i++) {
t = a[i];
a[i] = a[8 - n];
p1 = p0 + t * d[n];
q1 = q0 + t;
if(p1 == q1 * dd[n]) printf("%d\n" , p1);
if (n < 6) sub0(a , p1 , q1 , n + 1);
else if(n == 6) sub7(a , p1 , q1);
a[i] = t;
}
}
int main(void)
{
int i , t;
static int a[9] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9};
init();
for(i = 0 ; i < 9 ; i++) {
t = a[i];
a[i] = a[8];
sub0(a , t , t , 1);
a[i] = t;
}
return(0);
}
|
第100回（7月）合同ニ分割
|
|
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;
int y;
} XY;
#define NX 8
#define NY 10
#define NXY 80 /* NX*NY /*
static int bb[NY][NX]={
-1,-1,-1,-1,30,29,-1,-1,
-1, 0,33,32,31,28,27,-1,
2, 1,-2,-2,-2,-2,26,-1,
3, 4,-2,-2,-2,-2,25,-1,
-1, 5,-2,-2,-2,-2,24,-1,
-1, 6,-2,-2,-2,-2,23,-1,
-1, 7,-2,-2,-2,-2,22,-1,
9, 8,-2,-2,-2,-2,21,20,
10,11,-2,-2,-2,-2,18,19,
-1,12,13,14,15,16,17,-1};
int count = 0;
static XY dd[] = {0,1 , 0,-1 , 1,0 , -1,0};
static XY ddd[][2] = {1,0,0,1 , 1,0,0,-1 , -1,0,0,1 , -1,0,0,-1 ,
0,1,1,0 , 0,1,-1,0 , 0,-1,1,0 , 0,-1,-1,0};
XY g[NXY];
XY g2[NXY];
int n34 = -1;
int n17;
void disp(XY a2[] , int m)
{
int i;
int x , y;
int cg[NX] , c2[NX] , sg[NY][NX] , s2[NY][NX];
for(y = 0 ; y < NY -1 ; y++) {
for(x = 0 ; x < NX -1 ; x++) sg[y][x] = s2[y][x] = 0;
}
for(i = 0 ; i < n34 ; i++) {
if(g[i].y == g[(i + 1) % n34].y) {
if(g[i].x + 1 == g[(i + 1) % n34].x) sg[g[i].y][g[i].x] = 1;
else sg[g[i].y][g[i].x - 1] = 1;
}
}
for(i = 0 ; i < m ; i++) {
if(a2[i].y == a2[(i + 1) % m].y) {
if(a2[i].x + 1 == a2[(i + 1) % m].x) s2[a2[i].y][a2[i].x] = 1;
else s2[a2[i].y][a2[i].x - 1] = 1;
}
}
for(y = 0 ; y < NY - 1 ; y++) {
for(x = 0 ; x < NX - 1 ; x++) {
if(y == 0) cg[x] = sg[y][x];
else cg[x] += sg[y][x];
if(y == 0) c2[x] = s2[y][x];
else c2[x] += s2[y][x];
if ((cg[x] % 2) == 1) {
if((c2[x] % 2) == 1) printf("A");
else printf("B");
}
else printf(" ");
}
printf("\n");
}
}
int dif(XY a1[] , int ia1 , XY a3[] , int ia3 , int m)
{
int i;
for(i = 0 ; i < m ; i++) {
if(a1[(ia1 + i) % m].x != a3[(ia3 + i) % m].x) break;
if(a1[(ia1 + i) % m].y != a3[(ia3 + i) % m].y) break;
}
if(i == m) return(1);
for(i = 0 ; i < m ; i++) {
if(a1[(ia1 + i) % m].x != a3[(ia3 - i + m) % m].x) return(0);
if(a1[(ia1 + i) % m].y != a3[(ia3 - i + m) % m].y) return(0);
}
return(1);
}
void check(XY z[] , int n , int is)
{
XY a1[NXY] , a2[NXY] , a3[NXY];
int i , j;
int ie;
int m = 0;
XY min;
int ia1 , ia3;
ie = is - n17;
min.x = min.y = 100;
for(i = ie ; i < is ; i++) {
a1[m].x = g[i].x;
a1[m++].y = g[i].y;
if(g[i].x < min.x || (g[i].x == min.x && g[i].y < min.y)) {
min.x = g[i].x;
min.y = g[i].y;
}
}
for(i = 0 ; i < n - 1 ; i++) {
a1[m].x = z[i].x;
a1[m++].y = z[i].y;
if(z[i].x < min.x || (z[i].x == min.x && z[i].y < min.y)) {
min.x = z[i].x;
min.y = z[i].y;
}
}
for(i = 0 ; i < m ; i++) {
if(a1[i].x == min.x && a1[i].y == min.y) ia1 = i;
a1[i].x -= min.x;
a1[i].y -= min.y;
}
m = 0;
for(i = 0 ; i < ie ; i++) {
a2[m].x = g[i].x;
a2[m++].y = g[i].y;
}
for(i = n - 1 ; i > 0 ; i--) {
a2[m].x = z[i].x;
a2[m++].y = z[i].y;
}
for(i = is ; i < n34 ; i++) {
a2[m].x = g[i].x;
a2[m++].y = g[i].y;
}
for(i = 0 ; i < 8 ; i++) {
min.x = min.y = 100;
for(j = 0 ; j < m ; j++) {
a3[j].x = a2[j].x * ddd[i][0].x + a2[j].y * ddd[i][0].y;
a3[j].y = a2[j].x * ddd[i][1].x + a2[j].y * ddd[i][1].y;
if(a3[j].x < min.x || (a3[j].x == min.x && a3[j].y < min.y)) {
min.x = a3[j].x;
min.y = a3[j].y;
}
}
for(j = 0 ; j < m ; j++) {
if(a3[j].x == min.x && a3[j].y == min.y) ia3 = j;
a3[j].x -= min.x;
a3[j].y -= min.y;
}
if(dif(a1 , ia1 , a3 , ia3 , m) == 1) {
disp(a2 , m);
break;
}
}
}
void sub(int b[][NX] , XY p1 , int n , XY z[] , int is)
{
int i;
XY p2;
int t;
z[n].x = p1.x;
z[n].y = p1.y;
n++;
if(b[p1.y][p1.x] == -1 && n > 1) return;
if(p1.x == g2[is - n17].x && p1.y == g2[is - n17].y) {
z[n].x = g[is - 17].x;
z[n++].y = g[is - 17].y;
check(z , n , is);
return;
}
t = b[p1.y][p1.x];
b[p1.y][p1.x] = 1;
for(i = 0 ; i < 4 ; i++) {
p2.x = p1.x + dd[i].x;
if(p2.x < 0 || p2.x >= NX) continue;
p2.y = p1.y + dd[i].y;
if(p2.y < 0 || p2.y >= NY) continue;
if(b[p2.y][p2.x] > 0) continue;
sub(b , p2 , n , z , is);
}
b[p1.y][p1.x] = t;
}
void init(int b[][NX])
{
int x , y;
int x1 , y1;
int i , j;
for(y = 0 ; y < NY ; y++) {
for(x = 0 ; x < NX ; x++) {
if(bb[y][x] == -1) b[y][x] = 1;
else if(bb[y][x] == -2) b[y][x] = 0;
else {
g[bb[y][x]].x = x;
g[bb[y][x]].y = y;
b[y][x] = -1;
if(n34 < bb[y][x]) n34 = bb[y][x];
}
}
}
n34++;
n17 = n34 / 2;
for(i = 0 ; i < n17 ; i++) {
x = g[i].x;
y = g[i].y;
g2[i].x = -10000;
for(j = 0 ; j < 4 ; j++) {
x1 = x + dd[j].x;
if(x1 < 0 || x1 == NX) continue;
y1 = y + dd[j].y;
if(y1 < 0 || y1 == NY) continue;
if(b[y1][x1] != 0) continue;
g2[i].x = x1;
g2[i].y = y1;
break;
}
}
}
int main(void)
{
int b[NY][NX];
XY z[NXY];
int is;
init(b);
for(is = n17 ; is < n34 ; is++) {
if(b[g[is].y][g[is].x] == 1) continue;
if(g2[is - n17].x == -10000) continue;
sub(b , g[is] , 0 , z , is);
}
return(0);
}
|
第99回（6月）スライドパズル９
|
|
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct {
int a1;
int te;
char a3[9];
char a4;
int is;
int ie;
} AA;
int nn;
void init(AA a[])
{
int i0 , i1 , i2 , i3 , i4 , i5 , i6 , i7;
int s0 , s1 , s2 , s3 , s4 , s5 , s6;
int z1[8] , z2[7] , z3[6] , z4[5] , z5[4] , z6[3] , z7[2];
int j;
int n = 0;
for(i0 = 0 ; i0 < 9 ; i0++) {
for(j = 0 ; j < 8 ; j++) z1[j] = j + 1 + (j >= i0);
s0 = (i0 + 1) * 10000000;
for(i1 = 0 ; i1 < 8 ; i1++) {
for(j = 0 ; j < 7 ; j++) z2[j] = z1[j + (j >= i1)];
s1 = s0 + z1[i1] * 1000000;
for(i2 = 0 ; i2 < 7 ; i2++) {
for(j = 0 ; j < 6 ; j++) z3[j] = z2[j + (j >= i2)];
s2 = s1 + z2[i2] * 100000;
for(i3 = 0 ; i3 < 6 ; i3++) {
for(j = 0 ; j < 5 ; j++) z4[j] = z3[j + (j >= i3)];
s3 = s2 + z3[i3] * 10000;
for(i4 = 0 ; i4 < 5 ; i4++) {
for(j = 0 ; j < 4 ; j++) z5[j] = z4[j + (j >= i4)];
s4 = s3 + z4[i4] * 1000;
for(i5 = 0 ; i5 < 4 ; i5++) {
for(j = 0 ; j < 3 ; j++) z6[j] = z5[j + (j >= i5)];
s5 = s4 + z5[i5] * 100;
for(i6 = 0 ; i6 < 3 ; i6++) {
for(j = 0 ; j < 2 ; j++) z7[j] = z6[j + (j >= i6)];
s6 = s5 + z6[i6] * 10;
for(i7 = 0 ; i7 < 2 ; i7++) {
a[n].a3[0] = i0 + 1;
a[n].a3[1] = z1[i1];
a[n].a3[2] = z2[i2];
a[n].a3[3] = z3[i3];
a[n].a3[4] = z4[i4];
a[n].a3[5] = z5[i5];
a[n].a3[6] = z6[i6];
a[n].a3[7] = z7[i7];
a[n].a3[8] = z7[1 - i7];
a[n].a1 = s6 + z7[i7];
a[n].is = n;
a[n].ie = n;
a[n++].te = -1;
}
}
}
}
}
}
}
}
for(i0 = 0 ; i0 < nn ; i0++) {
n = (a[i0].a1 - 12345678) / 239;
if(a[n].is > i0) a[n].is = i0;
if(a[n].ie < i0) a[n].ie = i0;
}
}
int search(AA a[] , int i1 , int s)
{
int is = 0;
int ie , im;
int n , n2;
static int v[12][9] = {
6,1,2,0,4,5,3,7,8, /* a /*
0,7,2,3,1,5,6,4,8, /* b /*
0,1,8,3,4,2,6,7,5, /* c /*
1,2,0,3,4,5,6,7,8, /* d /*
0,1,2,4,5,3,6,7,8, /* e /*
0,1,2,3,4,5,7,8,6, /* f /*
0,1,5,3,4,8,6,7,2, /* g /*
0,4,2,3,7,5,6,1,8, /* h /*
3,1,2,6,4,5,0,7,8, /* i /*
0,1,2,3,4,5,8,6,7, /* j /*
0,1,2,5,3,4,6,7,8, /* k /*
2,0,1,3,4,5,6,7,8, /* l /*
};
n2 = a[i1].a3[v[s][0]] * 10000000 + a[i1].a3[v[s][1]] * 1000000 +
a[i1].a3[v[s][2]] * 100000 + a[i1].a3[v[s][3]] * 10000 +
a[i1].a3[v[s][4]] * 1000 + a[i1].a3[v[s][5]] * 100 +
a[i1].a3[v[s][6]] * 10 + a[i1].a3[v[s][7]];
n = (n2 - 12345678) / 239;
is = a[n].is;
ie = a[n].ie;
while(1) {
im = (is + ie) / 2;
if (a[im].a1 < n2) {
if(a[ie].a1 == n2) return(ie);
is = im;
}
else if(a[im].a1 == n2) return(im);
else ie = im;
}
}
static int p[] = {8 , 7 , 6 , 11 , 10 , 9 , 2 , 1 , 0 , 5 , 4 , 3};
int sub(AA a[] , int te)
{
int i , j , k;
int count = 0;
int te1;
te1 = te + 1;
for(i = 0 ; i < nn ; i++) {
if(a[i].te != te) continue;
for(j = 0 ; j < 12 ; j++) {
if(i > 0 && (a[i].a4 == j || p[a[i].a4] == j)) continue;
k = search(a , i , j);
if(a[k].te < 0) {
a[k].te = te1;
a[k].a4 = j;
}
}
count++;
}
return(count);
}
void disp(AA a[] , int te)
{
int i;
char *buf[3];
buf[0] = (char *)malloc(te * 8 * sizeof(char));
if(buf[0] == NULL) return;
buf[1] = (char *)malloc(te * 8 * sizeof(char));
if(buf[1] == NULL) return;
buf[2] = (char *)malloc(te * 8 * sizeof(char));
if(buf[2] == NULL) return;
for(i = 0 ; i < nn ; i++) {
if(a[i].te == te) break;
}
buf[0][0] = buf[1][0] = buf[2][0] = '\0';
while(1) {
sprintf(buf[0] , "%s%c%c%c" , buf[0] ,
'0' + a[i].a3[0] , '0' + a[i].a3[1] , '0' + a[i].a3[2]);
sprintf(buf[1] , "%s%c%c%c" , buf[1] ,
'0' + a[i].a3[3] , '0' + a[i].a3[4] , '0' + a[i].a3[5]);
sprintf(buf[2] , "%s%c%c%c" , buf[2] , '0' + a[i].a3[6] ,
'0' + a[i].a3[7] , '0' + a[i].a3[8] , 'a' + a[i].a4);
if(i == 0) break;
strcat(buf[0] , " ");
strcat(buf[1] , " -> ");
sprintf(buf[2] , "%s %c " , buf[2] , 'a' + p[a[i].a4]);
i = search(a , i , p[a[i].a4]);
}
printf("%s\n" , buf[0]);
printf("%s\n" , buf[1]);
printf("%s\n" , buf[2]);
free(buf[0]);
free(buf[1]);
free(buf[2]);
}
int main(void)
{
AA *a;
int count;
int te = 0;
nn = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9;
a = (AA *)malloc(sizeof(AA) * nn);
if(a == NULL) {
fprintf(stderr , "malloc error.\n");
exit(0);
}
init(a);
a[0].te = 0;
a[0].a4 = 0;
count = sub(a , te);
while(count != 0) {
printf("%d手 %d通り\n", te , count);
te++;
count = sub(a , te);
}
disp(a , te - 1);
free(a);
return(0);
}
|
第98回（5月）絶対なるかけひき
|
|
#include <stdio.h>
#include <math.h>
#define GET(b , y , x) q[b[y - 1][x]][b[y][x - 1]][b[y - 1][x - 1]]
int q[10][10][10];
void sub(int b[][9] , int n1 , int n2 , int n3 , int n4)
{
int i;
static char *nn[] = {"０" , "１" , "２" , "３" , "４" ,
"５" , "６" , "７" , "８" , "９"};
for(i = 0 ; i < n1 ; i++) printf(" ");
for(i = 0 ; i < n2 ; i++) printf("%s" , nn[b[n3 - i][n4 + i]]);
printf("\n");
}
void disp(int b[][9])
{
int i;
for(i = 0 ; i < 9 ; i++) sub(b , 8 - i , 1 + i , i , 0);
for(i = 0 ; i < 8 ; i++) sub(b , 1 + i , 8 - i , 8 , 1 + i);
}
void init()
{
int x , y , z;
for(z = 0 ; z < 10 ; z++) {
for(y = 0 ; y < 10 ; y++) {
for(x = 0 ; x < 10 ; x++) {
q[z][y][x] = abs(z * y - x) % 10;
}
}
}
}
int main(void)
{
int b[9][9];
int p0 , p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 , p9;
int i0 , i1 , i2 , i3 , i4 , i5 , i6 , i7 , i8;
int a[10];
int j;
init();
for(j = 0 ; j < 10 ; j++) a[j] = j;
/* C /*
for(i0 = 0 ; i0 < 10 ; i0++) {
p0 = a[i0];
a[i0] = a[9];
b[0][0] = p0;
/* M /*
for(i1 = 0 ; i1 < 9 ; i1++) {
p1 = a[i1];
a[i1] = a[8];
b[0][1] = p1;
b[7][7] = p1;
/* L /*
for(i2 = 0 ; i2 < 8 ; i2++) {
p2 = a[i2];
a[i2] = a[7];
b[1][0] = p2;
b[1][1] = GET(b , 1 , 1);
/* A /*
for(i3 = 0 ; i3 < 7 ; i3++) {
p3 = a[i3];
a[i3] = a[6];
b[0][2] = p3;
b[1][2] = GET(b , 1 , 2);
b[0][4] = p3;
b[2][0] = p3;
b[2][1] = GET(b , 2 , 1);
b[2][2] = GET(b , 2 , 2);
b[6][0] = p3;
b[8][8] = p3;
/* G /*
for(i4 = 0 ; i4 < 6 ; i4++) {
p4 = a[i4];
a[i4] = a[5];
b[0][3] = p4;
b[1][3] = GET(b , 1 , 3);
b[2][3] = GET(b , 2 , 3);
b[4][0] = p4;
b[7][0] = p4;
b[6][6] = p4;
/* N /*
for(i5 = 0 ; i5 < 5 ; i5++) {
p5 = a[i5];
a[i5] = a[4];
b[3][0] = p5;
b[3][1] = GET(b , 3 , 1);
b[3][2] = GET(b , 3 , 2);
b[0][7] = p5;
b[4][4] = p5;
/* E /*
for(i6 = 0 ; i6 < 4 ; i6++) {
p6 = a[i6];
a[i6] = a[3];
if(p6 != GET(b , 3 , 3)) {
a[i6] = p6;
continue;
}
b[3][3] = p6;
for(j = 1 ; j < 4 ; j++) {
b[j][4] = GET(b , j , 4);
b[4][j] = GET(b , 4 , j);
}
if(p5 != GET(b , 4 , 4)) {
a[i6] = p6;
continue;
}
b[0][8] = p6;
b[8][0] = p6;
/* Z /*
for(i7 = 0 ; i7 < 3 ; i7++) {
p7 = a[i7];
a[i7] = a[2];
b[0][5] = p7;
for(j = 1 ; j < 5 ; j++) {
b[j][5] = GET(b , j , 5);
}
/* U /*
for(i8 = 0 ; i8 < 2 ; i8++) {
p8 = a[i8];
b[5][0] = p8;
for(j = 1 ; j < 5 ; j++) {
b[5][j] = GET(b , 5 , j);
}
/* I /*
p9 = a[1 - i8];
if(p9 != GET(b , 5 , 5)) continue;
b[5][5] = p9;
b[0][6] = p9;
for(j = 1 ; j < 6 ; j++) {
b[j][6] = GET(b , j , 6);
b[6][j] = GET(b , 6 , j);
}
if(p4 != GET(b , 6 , 6)) continue;
for(j = 1 ; j < 7 ; j++) {
b[j][7] = GET(b , j , 7);
b[7][j] = GET(b , 7 , j);
}
if(p1 != GET(b , 7 , 7)) continue;
for(j = 1 ; j < 8 ; j++) {
b[j][8] = GET(b , j , 8);
b[8][j] = GET(b , 8 , j);
}
if(p3 != GET(b , 8 , 8)) continue;
disp(b);
}
a[i7] = p7;
}
a[i6] = p6;
}
a[i5] = p5;
}
a[i4] = p4;
}
a[i3] = p3;
}
a[i2] = p2;
}
a[i1] = p1;
}
a[i0] = p0;
}
return(0);
}
|
第96回（3月）昇順素数
|
|
#include <stdio.h>
#define TASU 0
#define HIKU 1
#define KAKE 2
#define WARU 3
int *z;
int nz = 0;
typedef struct {
int enzan1; /* 直前の＋or−演算子の種類 /*
int enzan2; /* 直前の×or÷演算子の種類 /*
int bu1; /* 分子(合計値) /*
int bo1; /* 分母(合計値) /*
int bu2; /* 分子 /*
int bo2; /* 分母 /*
int num; /* 式上の数 /*
} AA;
int cmp(void *a , void *b)
{
if (*(int *)a < *(int *)b) return(-1);
else if(*(int *)a == *(int *)b) return(0);
else return(1);
}
void sub8(AA aa0)
{
int sum;
AA aa1;
aa1.bu2 = aa0.bu2;
aa1.bo2 = aa0.bo2;
if(aa0.enzan2 == KAKE) aa1.bu2 *= aa0.num;
else aa1.bo2 *= aa0.num;
if(aa0.enzan1 == TASU) aa1.bu1 = aa0.bu1 * aa1.bo2 + aa0.bo1 * aa1.bu2;
else aa1.bu1 = aa0.bu1 * aa1.bo2 - aa0.bo1 * aa1.bu2;
aa1.bo1 = aa0.bo1 * aa1.bo2;
if(aa1.bu1 <= 0) return;
if((aa1.bu1 % aa1.bo1) != 0) return;
sum = aa1.bu1 / aa1.bo1;
z = (int *)realloc(z , sizeof(int) * (nz + 1));
*(z + nz++) = sum;
}
void sub0(AA aa0 , int n)
{
int pp;
AA aa1;
if(n == 8) {
sub8(aa0);
return;
}
/* ＋の場合 /*
aa1.bu2 = aa0.bu2;
aa1.bo2 = aa0.bo2;
if(aa0.enzan2 == KAKE) aa1.bu2 *= aa0.num;
else aa1.bo2 *= aa0.num;
if(aa0.enzan1 == TASU) aa1.bu1 = aa0.bu1 * aa1.bo2 + aa0.bo1 * aa1.bu2;
else aa1.bu1 = aa0.bu1 * aa1.bo2 - aa0.bo1 * aa1.bu2;
aa1.bo1 = aa0.bo1 * aa1.bo2;
aa1.bu2 = aa1.bo2 = 1;
aa1.enzan1 = TASU;
aa1.enzan2 = KAKE;
aa1.num = n + 2;
sub0(aa1 , n + 1);
/* −の場合 /*
aa1.enzan1 = HIKU;
sub0(aa1 , n + 1);
/* ×の場合/*
aa1.enzan1 = aa0.enzan1;
aa1.bu1 = aa0.bu1;
aa1.bo1 = aa0.bo1;
aa1.bu2 = aa0.bu2;
aa1.bo2 = aa0.bo2;
if(aa0.enzan2 == KAKE) aa1.bu2 *= aa0.num;
else aa1.bo2 *= aa0.num;
aa1.enzan2 = KAKE;
sub0(aa1 , n + 1);
/* ÷の場合 /*
aa1.enzan2 = WARU;
sub0(aa1 , n + 1);
/* nothingの場合 /*
aa0.num = aa0.num * 10 + n + 2;
sub0(aa0 , n + 1);
}
int main(void)
{
int i;
int a , maxz;
int count;
int maxcount = -1;
AA aa0;
z = (int *)malloc(sizeof(int));
aa0.bu1 = 0;
aa0.bo1 = 1;
aa0.enzan1 = TASU;
aa0.enzan2 = KAKE;
aa0.bu2 = 1;
aa0.bo2 = 1;
aa0.num = 1;
sub0(aa0 , 0);
qsort((char *)z , nz , sizeof(int) , cmp);
a = *z;
count = 0;
for(i = 0 ; i < nz ; i++) {
if(a != *(z + i)) {
if(count > maxcount) {
maxcount = count;
maxz = a;
}
count = 0;
a = *(z + i);
}
count++;
}
free(z);
printf("N=%d 式の数=%d\n" , maxz , maxcount);
return(0);
}
|
第95回（2月）大町平方数
|
|
#include <stdio.h>
#include <stdlib.h>
#define OFF 0
#define ON 1
int check(int i , int mode)
{
int s0 , s3;
int d0 , d1 , d2 , d3 , d4 , d5 , d6 , d7 , d8 , d9;
int d;
int rf[10];
int k;
int t;
for(k = 0 ; k < 10 ; k++) rf[k] = OFF;
s0 = i * (i % 1000);
s3 = i * (i / 1000);
d0 = s0 % 10;
rf[d0] = ON;
d1 = (s0 / 10) % 10;
t = d1 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d2 = (s0 / 100) % 10;
t = d2 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d3 = (s0 / 1000) % 10 + s3 % 10 + d2 / 10;
t = d3 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d4 = s0 / 10000 + (s3 / 10) % 10 + d3 / 10;
t = d4 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d5 = (s3 / 100) % 10 + d4 / 10;
t = d5 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d6 = (s3 / 1000) % 10 + d5 / 10;
t = d6 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d7 = s3 / 10000 + d6 / 10;
t = d7 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d8 = d7 / 10;
t = d8 % 10;
if(rf[t] == ON) return(OFF);
rf[t] = ON;
d9 = d8 / 10;
if(rf[d9] == ON) return(OFF);
if(mode == ON) printf("%d%d%d%d%d%d%d%d%d%d\n" ,
d9 % 10 , d8 % 10 , d7 % 10 , d6 % 10 , d5 % 10 ,
d4 % 10 , d3 % 10 , d2 % 10 , d1 % 10 , d0 % 10);
return(ON);
}
int main(void)
{
int i;
int i0 = -1 , i1 = 0 , i2 = 0 , i3 = 0 , i4 = 1;
for(i = 10000 ; i < 100000 ; i++) {
i0++;
if(i0 == 10) {
i0 = 0;
i1++;
if(i1 == 10) {
i1 = 0;
i2++;
if(i2 == 10) {
i2 = 0;
i3++;
if(i3 == 10) {
i3 = 0;
i4++;
}
}
}
}
if(i4 > i0) continue;
if(i0 == i4 && i1 == i3) continue;
if(check(i , OFF) == OFF) continue;
if(check(i0 * 10000 + i1 * 1000 + i2 * 100 + i3 * 10 + i4 , OFF) == OFF)
continue;
printf("%d * %d = " , i , i);
check(i , ON);
printf("%d%d%d%d%d * %d%d%d%d%d = " ,
i0 , i1 , i2 , i3 , i4 , i0 , i1 , i2 , i3 , i4);
check(i0 * 10000 + i1 * 1000 + i2 * 100 + i3 * 10 + i4 , ON);
}
return(0);
}
| | | | | | | | | |