/home/toolbox/public_html/solutions/108/10825/b.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (TRUE)
14 #define DEBUG1 if (TRUE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2012-08-07:
19 * Purpose: fun
20 * Problem: 10825 - Anagram and Multiplication
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 */
26
27 int digits[400];
28 int M;
29 int N;
30 long long int llN;
31 int start[7] = {0, 0, 0, 100, 1000, 10000, 100000};
32
33 int n1[7];
34 int n2[7];
35 long long int v1;
36 long long int v2;
37 long long int h1;
38 long long int h2;
39
40 unsigned int addDigits(int num)
41 {
42 /* FUNCTION addDigits */
43 int i;
44 int j;
45 unsigned int sum = 0;
46
47 for (i=0; N>i; i++)
48 {
49 /* for */
50 digits[i] = 0;
51 } /* for */
52
53 for (i=num; 0<i; i = i / N)
54 {
55 /* for */
56 digits[i % N]++;
57 } /* for */
58
59 for (i=(N-1); 0<=i; i--)
60 {
61 /* for i */
62 for (j=digits[i]; 0<j; j--)
63 {
64 /* for j */
65 sum = sum * N + i;
66 } /* for j */
67 } /* for i */
68 return sum;
69 } /* FUNCTION addDigits */
70
71 long long int breakOut(long long int num, int *ary[])
72 {
73 /* FUNCTION breakOut */
74 int i;
75 long long int tmp;
76 long long int tot;
77 long long int dgt;
78
79 tot = 0;
80 tmp = num;
81 for(i=1; i<7; i++)
82 {
83 /* for each digit */
84 dgt = tmp % 10;
85 ary[i] = (int) dgt;
86 if (0 < tmp)
87 {
88 /* found a digit */
89 tot = tot * llN + ary[i];
90 tmp = tmp / 10;
91 } /* found a digit */
92 } /* for each digit */
93 return tot;
94 } /* FUNCTION breakOut */
95
96 long long int calcHash(int *ary[])
97 {
98 /* FUNCTION calcHash */
99 int i;
100 int j;
101 long long int sum;
102
103 for (i=0; i<N; i++)
104 {
105 digits[i] = 0;
106 }
107 for (i=1; i<=M; i++)
108 {
109 digits[ary[i]]++;
110 }
111 for (i=(N-1); 0<=i; i--)
112 {
113 /* for i */
114 for (j=digits[i]; 0<j; j--)
115 {
116 /* for j */
117 sum = sum * N + i;
118 } /* for j */
119 } /* for i */
120 return sum;
121 } /* FUNCTION calcHash */
122
123
124 void init()
125 {
126 /* FUNCTION init */
127 } /* FUNCTION init */
128
129 void dump()
130 {
131 /* FUNCTION dump */
132 } /* FUNCTION dump */
133
134 int getInput()
135 {
136 /* FUNCTION getInput */
137 int dataReadFlag;
138
139 scanf(" %d %d ", &M, &N);
140 llN = N;
141
142 dataReadFlag = (0 != M);
143 return (dataReadFlag);
144 } /* FUNCTION getInput */
145
146 void process()
147 {
148 /* FUNCTION process */
149 int num;
150 long long int upperLimit;
151 int hashMatch;
152 int solutionNotFound = TRUE;
153 int i;
154
155 v1 = start[M];
156 v1 = breakOut(v1, n1);
157 h1 = calcHash(n1);
158 upperLimit =v1 * N / M + 1;
159 DEBUG1 /* debug1 */
160 {
161 printf("n1: %lld ==>", v1);
162 for (i=1; i<=M; i++)
163 {
164 printf(" %d", n1[i]);
165 }
166 printf(" hash=%lld\n", h1);
167 } /* debug1 */
168 while ((v1 < upperLimit) && (solutionNotFound))
169 {
170 /* while */
171 hashMatch = TRUE;
172 for (i=2; (i<=M) && (hashMatch); i++)
173 {
174 /* for - check each multiple */
175 v2 = breakout(i * v1, n2);
176 DEBUG1 /* debug1 */
177 {
178 printf("n2: %lld ==>", v2);
179 for (i=1; i<=M; i++)
180 {
181 printf(" %d", n2[i]);
182 }
183 printf(" hash=%lld\n", h2);
184 } /* debug1 */
185 hashMatch = (h1 == h2);
186 } /* for - check each multiple */
187 if (! hashMatch)
188 {
189 /* no solution yet */
190 solutionNotFound = ! hashMatch;
191 v1++;
192 v1 = breakOut(v1, n1);
193 h1 = calcHash(n1);
194 {
195 /* no solution yet */
196 } /* while */
197 if (solutionNotFound)
198 {
199 /* no solution */
200 printf("Not found.\n");
201 } /* no solution */
202 else
203 {
204 /* solution found */
205 printf("Solution: %d\n", num);
206 } /* solution found */
207 } /* FUNCTION process */
208
209 int main ()
210 {
211 /* main */
212 int moreToDo;
213
214 /* init(); */
215 moreToDo = getInput();
216 while (moreToDo)
217 {
218 /* while */
219 process();
220 moreToDo = getInput();
221 } /* while */
222
223 return EXIT_SUCCESS;
224 } /* main */
225