/home/toolbox/public_html/solutions/105/10527/judged.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 /*
6 * Author: Matthew Eastman <meastman@cct.lsu.edu>
7 * Date: 2006-10-10
8 * Purpose: Contest practice
9 * Problem: 10527 - Persistent Numbers <http://isaac.lsu.edu/udv/v105/10527.html>
10 */
11
12 #define BUFFER_SIZE 1005
13 #define FALSE 0
14 #define TRUE 1
15
16 char buffer[BUFFER_SIZE];
17 int digits;
18 int divis[8];
19 int primes[] = { 2, 3, 5, 7 };
20 int weirdarray[] = { 5, 4, 6, 2, 3, 1 }; /* for division by 7 */
21
22 int digitSum()
23 {
24 int i;
25 int total = 0;
26
27 for (i = 0; i < digits; i++)
28 {
29 total += buffer[i];
30 }
31
32 return total;
33 }
34
35 /* divide _buffer_ by _num_ */
36 void divide(int num)
37 {
38 int i;
39 int temp = 0;
40
41 for (i = 0; i < digits; i++)
42 {
43 temp = temp * 10 + buffer[i];
44 buffer[i] = temp / num;
45 temp -= (buffer[i] * num);
46 }
47 }
48
49 /* check to see if the number in _buffer_ is divisible by _num_ */
50 int divisible(int num)
51 {
52 int i;
53 int temp = 0;
54 int divisible = FALSE;
55
56 for (i = 0; i < digits; i++)
57 {
58 temp = (temp * 10 + buffer[i]) % num;
59 }
60
61 if (0 == temp)
62 divisible = TRUE;
63
64 return divisible;
65 }
66
67 int primeFactor()
68 {
69 int i;
70
71 memset(divis, 0, sizeof(divis));
72
73 for (i = 0; i < 4; i++)
74 {
75 while (divisible(primes[i]))
76 {
77 divis[primes[i]]++;
78 divide(primes[i]);
79 }
80 }
81
82 /* if we ended up with 1, we successfully factored it */
83 if ((1 == digitSum()) && (1 == buffer[digits - 1]))
84 return TRUE;
85
86 return FALSE;
87 }
88
89 int getInput()
90 {
91 int i;
92
93 fgets(buffer, sizeof(buffer), stdin);
94 if ('-' == buffer[0])
95 return FALSE;
96
97 for (i = 0; '\n' != buffer[i]; i++)
98 buffer[i] -= '0';
99 digits = i;
100
101 return TRUE;
102 }
103
104 void solve()
105 {
106 int i;
107
108 /* single-digit numbers are easy; just add 10 */
109 if (1 == digits)
110 {
111 printf("1%d\n", buffer[0]);
112 return;
113 }
114
115 /* if the prime factorization wasn't all single-digits, bail */
116 if (! primeFactor())
117 {
118 printf("There is no such number.\n");
119 return;
120 }
121
122 /* fill in the answer backwards, starting with the big numbers */
123 i = BUFFER_SIZE;
124 buffer[--i] = '\0';
125
126 while (2 <= divis[3]) /* 3*3 = 9 */
127 {
128 buffer[--i] = '9';
129 divis[3] -= 2;
130 }
131 while (3 <= divis[2]) /* 2*2*2 = 8 */
132 {
133 buffer[--i] = '8';
134 divis[2] -= 3;
135 }
136 while (1 <= divis[7]) /* 7 = 7 */
137 {
138 buffer[--i] = '7';
139 divis[7]--;
140 }
141 while ((1 <= divis[2]) && (1 <= divis[3])) /* 2*3 = 6 */
142 {
143 buffer[--i] = '6';
144 divis[2]--;
145 divis[3]--;
146 }
147 while (1 <= divis[5]) /* 5 = 5 */
148 {
149 buffer[--i] = '5';
150 divis[5]--;
151 }
152 while (2 <= divis[2]) /* 2*2 = 4 */
153 {
154 buffer[--i] = '4';
155 divis[2] -= 2;
156 }
157 while (1 <= divis[3]) /* 3 = 3 */
158 {
159 buffer[--i] = '3';
160 divis[3]--;
161 }
162 while (1 <= divis[2]) /* 2 = 2 */
163 {
164 buffer[--i] = '2';
165 divis[2]--;
166 }
167
168 printf("%s\n", &buffer[i]);
169 }
170
171 int main()
172 {
173 while (getInput())
174 {
175 solve();
176 }
177
178 return EXIT_SUCCESS;
179 }
180
181