fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define RIVER_LENGTH 10000
  4.  
  5. int main() {
  6.     int num_cases;
  7.     scanf("%d", &num_cases);
  8.     int cases[num_cases];
  9.     int N;
  10.     int s1[RIVER_LENGTH] = {1};
  11.     int s3[RIVER_LENGTH] = {3};
  12.     int s9[RIVER_LENGTH] = {9};
  13.     int i;
  14.     int temp;
  15.  
  16.     for (i = 1; i < RIVER_LENGTH; i++) {
  17.         s1[i] = temp = s1[i-1];
  18.         while (temp) {
  19.             s1[i] += temp % 10;
  20.             temp /= 10;
  21.         }
  22.     }
  23.  
  24.     for (i = 1; i < RIVER_LENGTH; i++) {
  25.         s3[i] = temp = s3[i-1];
  26.         while (temp) {
  27.             s3[i] += temp % 10;
  28.             temp /= 10;
  29.         }
  30.     }
  31.  
  32.     for (i = 1; i < RIVER_LENGTH; i++) {
  33.         s9[i] = temp = s9[i-1];
  34.         while (temp) {
  35.             s9[i] += temp % 10;
  36.             temp /= 10;
  37.         }
  38.     }
  39.  
  40.     int start;
  41.     int end;
  42.     int pivot;
  43.  
  44.     for (i=1; i <= num_cases; i++) {
  45.         scanf("%d", &cases[i]);
  46.     }
  47.  
  48.     for (i=1; i <= num_cases; i++) {
  49.         printf("Case #%d\n\n", i);
  50.         N = cases[i];
  51.  
  52.         while (1) {
  53.  
  54.             temp = N;
  55.             while (temp) {
  56.                 N += temp % 10;
  57.                 temp /= 10;
  58.             }
  59.  
  60.             start = 0;
  61.             end = RIVER_LENGTH;
  62.             pivot = 1;
  63.  
  64.             while (end != start && pivot != RIVER_LENGTH - 1) {
  65.                 pivot = start + ((end - start) >> 1);
  66.                 if (s1[pivot] == N) {
  67.                     printf("first meets river 1 at %d\n\n", N);
  68.                     goto case_done;
  69.                 } else if (N < s1[pivot]){
  70.                     end = pivot;
  71.                 } else {
  72.                     start = pivot+1;
  73.                 }
  74.             }
  75.  
  76.             start = 0;
  77.             end = RIVER_LENGTH;
  78.             pivot = 1;
  79.  
  80.             while (end != start && pivot != RIVER_LENGTH - 1) {
  81.                 pivot = start + ((end - start) >> 1);
  82.                 if (s3[pivot] == N) {
  83.                     printf("first meets river 3 at %d\n\n", N);
  84.                     goto case_done;
  85.                 } else if (N < s3[pivot]){
  86.                     end = pivot;
  87.                 } else {
  88.                     start = pivot+1;
  89.                 }
  90.             }
  91.  
  92.             start = 0;
  93.             end = RIVER_LENGTH;
  94.             pivot = 1;
  95.  
  96.             while (end != start && pivot != RIVER_LENGTH - 1) {
  97.                 pivot = start + ((end - start) >> 1);
  98.                 if (s9[pivot] == N) {
  99.                     printf("first meets river 9 at %d\n\n", N);
  100.                     goto case_done;
  101.                 } else if (N < s9[pivot]){
  102.                     end = pivot;
  103.                 } else {
  104.                     start = pivot+1;
  105.                 }
  106.             }
  107.         }
  108.  
  109.         case_done:;
  110.  
  111.     }
  112. }
Time limit exceeded #stdin #stdout 5s 2160KB
comments (?)
stdin
copy 
86
12345
0
stdout
copy 
Standard output is empty
https://ideone.com/mHCeef
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!