1.c (3763B)
1 #include <stdio.h> 2 #include <assert.h> 3 #include <string.h> 4 #include <stdbool.h> 5 #include <stdlib.h> 6 7 char *reverse(char *s){ 8 char *rev = malloc(strlen(s)); 9 int j = 0; 10 for (int i = strlen(s)-1; i >= 0; i--){ 11 rev[j] = s[i]; 12 j++; 13 } 14 rev[j] = 0; 15 16 return rev; 17 } 18 19 bool ispal(int n){ 20 char *strnum = malloc(128); 21 snprintf(strnum, 128, "%d", n); 22 char *rev = reverse(strnum); 23 24 if (strcmp(rev, strnum) == 0) { // is the same both ways round 25 free(strnum); 26 free(rev); 27 return true; 28 } 29 free(strnum); 30 free(rev); 31 return false; 32 } 33 34 int findhighestsumof2(int sums[][2], int sumcount){ 35 int highest = sums[0][0]; 36 int highestIndex = 0; 37 38 for (int i = 0; i < sumcount; i++) { 39 if (sums[i][0] > highest) { 40 highest= sums[i][0]; 41 highestIndex = i; 42 } 43 if (sums[i][1] > highest) { 44 highest = sums[i][1]; 45 highestIndex = i; 46 } 47 } 48 49 return highestIndex; 50 } 51 52 int findlowesetsumof2(int sums[][2], int sumcount){ 53 if (sumcount == 0) return -1; // no sums 54 int lowest = sums[0][0]; 55 int lowestIndex = 0; 56 bool needscheck = false; 57 58 for (int i = 0; i < sumcount; i++) { 59 if (sums[i][0] < lowest) { 60 lowest = sums[i][0]; 61 lowestIndex = i; 62 needscheck = false; 63 } 64 if (sums[i][1] < lowest) { 65 lowest = sums[i][1]; 66 lowestIndex = i; 67 needscheck = false; 68 } 69 if (sums[i][0] == lowest || sums[i][1] == lowest) needscheck == true; 70 } 71 if (needscheck) return findhighestsumof2(sums, sumcount); 72 return lowestIndex; 73 } 74 75 int findhighestsumof3(int sums[][3], int sumcount){ 76 int highest = sums[0][0]; 77 int highestIndex = 0; 78 79 for (int i = 0; i < sumcount; i++) { 80 if (sums[i][0] > highest) { 81 highest= sums[i][0]; 82 highestIndex = i; 83 } 84 if (sums[i][1] > highest) { 85 highest = sums[i][1]; 86 highestIndex = i; 87 } 88 if (sums[i][2] > highest) { 89 highest = sums[i][2]; 90 highestIndex = i; 91 } 92 } 93 return highestIndex; 94 } 95 96 int findlowesetsumof3(int sums[][3], int sumcount){ 97 if (sumcount == 0) return -1; // no sums 98 // 99 int lowest = sums[0][0]; 100 int lowestIndex = 0; 101 bool needscheck = false; 102 103 for (int i = 0; i < sumcount; i++) { 104 if (sums[i][0] < lowest) { 105 lowest = sums[i][0]; 106 lowestIndex = i; 107 needscheck = false; 108 } 109 if (sums[i][1] < lowest) { 110 lowest = sums[i][1]; 111 lowestIndex = i; 112 needscheck = false; 113 } 114 if (sums[i][2] < lowest) { 115 lowest = sums[i][2]; 116 lowestIndex = i; 117 needscheck = false; 118 } 119 if (sums[i][0] == lowest || sums[i][1] == lowest || sums[i][0] == lowest) needscheck == true; 120 } 121 if (needscheck) return findhighestsumof3(sums, sumcount); 122 return lowestIndex; 123 } 124 125 126 int main(int argc, char **argv){ 127 int input; 128 if (argc == 1) { 129 assert(scanf("%d", &input) != 0); 130 } else input = atoi(argv[1]); 131 132 if (ispal(input)) { // if 1 number is enough 133 printf("%d\n", input); 134 return 1; 135 } 136 137 int sums[input*2][2]; 138 int sumcount = 0; 139 for (int i = 1; i < input/2+1; i++){ // if 2 is enough 140 for (int j = input; j > (input/2) - 1; j--){ 141 if ((i + j) == input) { 142 if (ispal(i) & ispal(j)){ 143 sums[sumcount][0] = i; 144 sums[sumcount][1] = j; 145 sumcount++; 146 } 147 } 148 } 149 } 150 151 int index = findlowesetsumof2(sums, sumcount); 152 if (index != -1) { 153 printf("%d %d\n", sums[index][0], sums[index][1]); 154 return 2; 155 } 156 157 int triples[input*3][3]; 158 int triplecount = 0; 159 for (int i = 0; i < input; i++){ // if 3 is enough 160 for (int j = 0; j < input; j++){ 161 for (int k = 0; k < input; k++){ 162 if ((i + j + k) == input) { 163 if (ispal(i) & ispal(j) & ispal(k)){ 164 triples[triplecount][0] = i; 165 triples[triplecount][1] = j; 166 triples[triplecount][2] = k; 167 triplecount++; 168 } 169 } 170 } 171 } 172 } 173 174 index = findlowesetsumof3(triples, triplecount); 175 if (index != -1) { 176 printf("%d %d %d\n", triples[index][0], triples[index][1], triples[index][2]); 177 return 3; 178 } 179 }