codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/* 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. */ #include <stdio.h> #include <stdlib.h> #define N 5 // 桁を入れ替えて得られる立方数の個数 typedef struct tree { struct tree *branch[10]; struct list *p; // 線形リストへのポインタ.葉以外では無効 } Tree; typedef struct list { struct list *next; long long int num; } List; // n^3 long long int cubicnumber(int n) { return (long long int)n * n * n; } int *count(long long int num) { int *rep; int i; rep = (int *)calloc(10, sizeof(int)); for( i = 0; num != 0; i++ ) { rep[num % 10]++; num /= 10; } return rep; } Tree *allocNodeofTree(void) { Tree *rep; int i; rep = (Tree *)malloc(sizeof(Tree)); rep->p = NULL; for( i = 0; i < 10; i++ ) { rep->branch[i] = NULL; } return rep; } List *allocNodeofList(long long int num) { List *rep; rep = (List *)malloc(sizeof(List)); rep->num = num; rep->next = NULL; return rep; } long long int add(long long int num, int *digits, Tree *root) { Tree *node = root; List *p, *head; int depth; int cnt = 0; for( depth = 0; depth < 10; depth++ ) { if( node->branch[digits[depth]] == NULL ) { node->branch[digits[depth]] = allocNodeofTree(); } node = node->branch[digits[depth]]; } if( node->p == NULL ) { node->p = allocNodeofList(num); } else { head = node->p; for( p = head; p->next != NULL; p = p->next ) { cnt++; // 手繰るノードが3つあれば,numは桁を入れ替えて得られる5つ目の立方数 if( cnt == N - 2 ) { return head->num; } } p->next = allocNodeofList(num); } return -1; } int main(void) { Tree *root; int *digits; long long int n; int i; root = allocNodeofTree(); for( i = 1;; i++ ) { long long int rep; n = cubicnumber(i); digits = count(n); rep = add(n, digits, root); if( rep == -1 ) continue; printf("%lld\n", rep); break; } return 0; }
Private
[
?
]
Run code
Submit