a.c (1408B) [raw]
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAX_WIDTH 32 5 6 int main(void) { 7 /* Key takeaway: if think of the input as a matrix, we can 8 * sum the columns and count the number of entries and know 9 * that if N entries had X sum, there's X 1's and N-X 0's. 10 */ 11 int counts[MAX_WIDTH] = { 0 }; 12 int c; 13 int col = 0; 14 int n = 0; 15 while ((c = getchar()) != EOF) { 16 switch (c) { 17 case '0': 18 col++; 19 break; 20 case '1': 21 counts[col]++; 22 col++; 23 break; 24 case '\n': 25 /* reset the column */ 26 col = 0; 27 n++; 28 break; 29 default: 30 fprintf(stderr, "bad input"); 31 exit(1); 32 break; 33 } 34 } 35 36 /* convert counts into a bitmask of 1/0 based on which was max */ 37 unsigned int gamma = 0; 38 unsigned int eps = 0; 39 for (int i = 0; i < MAX_WIDTH; i++) { 40 if (counts[i] == 0) { 41 /* assume we see each at least once, so this was the end of width */ 42 break; 43 } 44 /* boost the last value to make room for more! */ 45 gamma <<= 1; 46 eps <<= 1; 47 if (counts[i] > n / 2) { 48 gamma |= 1; 49 } else { 50 eps |= 1; 51 } 52 } 53 printf("%u\n", eps * gamma); 54 return 0; 55 }