#C
C
#C
C
#C
Very simple, it just looks that long because I unrolled all the 3 rivers. It first generates the 3 rivers up to RIVER_LENGTH (which I hope is big enough), and then for each step on N it does a binary search on all three streams to see if it is in any of them. This works because the streams are already sorted, so we can do the contains check in log(n) time.
#include <stdio.h>
#define RIVER_LENGTH 10000
int main() {
int num_cases;
scanf("%d", &num_cases);
int cases[num_cases];
int N;
int s1[RIVER_LENGTH] = {1};
int s3[RIVER_LENGTH] = {3};
int s9[RIVER_LENGTH] = {9};
int i;
int temp;
for (i = 1; i < RIVER_LENGTH; i++) {
s1[i] = temp = s1[i-1];
while (temp) {
s1[i] += temp % 10;
temp /= 10;
}
}
for (i = 1; i < RIVER_LENGTH; i++) {
s3[i] = temp = s3[i-1];
while (temp) {
s3[i] += temp % 10;
temp /= 10;
}
}
for (i = 1; i < RIVER_LENGTH; i++) {
s9[i] = temp = s9[i-1];
while (temp) {
s9[i] += temp % 10;
temp /= 10;
}
}
int start;
int end;
int pivot;
for (i=1; i <= num_cases; i++) {
scanf("%d", &cases[i]);
}
for (i=1; i <= num_cases; i++) {
printf("Case #%d\n\n", i);
N = cases[i];
while (1) {
temp = N;
while (temp) {
N += temp % 10;
temp /= 10;
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s1[pivot] == N) {
printf("first meets river 1 at %d\n\n", N);
goto case_done;
} else if (N < s1[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s3[pivot] == N) {
printf("first meets river 3 at %d\n\n", N);
goto case_done;
} else if (N < s3[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s9[pivot] == N) {
printf("first meets river 9 at %d\n\n", N);
goto case_done;
} else if (N < s9[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
}
case_done:;
}
}
It takes a number for the number of cases first, instead of using 0 to delimit the end of the inputs, because you know, C. This is just for convenience and doesn't really affect anything, so I hope its okay.