fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     // nextFront(s) = (s+1) + floor((s+1)/2)
  7.     static long nextFront(long s) {
  8.         long u = s + 1;
  9.         return u + (u / 2);
  10.     }
  11.  
  12.     // Which cow is at position 0 immediately after time t
  13.     static long frontCow(long t) {
  14.         if (t <= 1) return 0; // at times 0 and 1, cow 0 is in front
  15.  
  16.         while (t % 3 != 2) {
  17.             long r = t % 3;
  18.             if (r == 0) {
  19.                 // t = 3m  -> predecessor s = 2m - 1
  20.                 t = 2 * (t / 3) - 1;
  21.             } else { // r == 1
  22.                 // t = 3m+1 -> predecessor s = 2m
  23.                 t = 2 * (t / 3);
  24.             }
  25.             if (t <= 1) return 0;
  26.         }
  27.         // t = 3c - 1  => c = (t+1)/3
  28.         return (t + 1) / 3;
  29.     }
  30.  
  31.     // Position of cow c immediately after time t
  32.     static long positionOfCow(long c, long t) {
  33.         if (c == 0) {
  34.             // cow 0 front times start at 0
  35.             long s = 0;
  36.             while (s < t) {
  37.                 long ns = nextFront(s);
  38.                 if (ns > t) return ns - t;
  39.                 s = ns;
  40.             }
  41.             return 0; // s == t
  42.         }
  43.  
  44.         // before time 2c, cow c never moves
  45.         if (t < 2 * c) return c;
  46.  
  47.         long s = 3 * c - 1; // first time cow c reaches front
  48.         if (t <= s) return s - t; // moving toward first front
  49.  
  50.         // advance front times until we bracket t
  51.         while (s < t) {
  52.             long ns = nextFront(s);
  53.             if (ns > t) return ns - t;
  54.             s = ns;
  55.         }
  56.         return 0; // s == t
  57.     }
  58.  
  59.     // Cow at position x immediately after time t
  60.     static long cowAtPosition(long x, long t) {
  61.         if (x > (t / 2)) return x;      // untouched suffix
  62.         return frontCow(t + x);         // x steps later it reaches the front
  63.     }
  64.  
  65.     public static void main(String[] args) throws Exception {
  66.         FastScanner fs = new FastScanner(System.in);
  67.         int Q = fs.nextInt();
  68.         StringBuilder out = new StringBuilder();
  69.  
  70.         for (int i = 0; i < Q; i++) {
  71.             int type = fs.nextInt();
  72.             long a = fs.nextLong();
  73.             long t = fs.nextLong();
  74.  
  75.             long ans;
  76.             if (type == 1) {
  77.                 long c = a;
  78.                 ans = positionOfCow(c, t);
  79.             } else {
  80.                 long x = a;
  81.                 ans = cowAtPosition(x, t);
  82.             }
  83.             out.append(ans).append('\n');
  84.         }
  85.  
  86.         System.out.print(out.toString());
  87.     }
  88.  
  89.     // Fast input
  90.     static class FastScanner {
  91.         private final InputStream in;
  92.         private final byte[] buffer = new byte[1 << 16];
  93.         private int ptr = 0, len = 0;
  94.  
  95.         FastScanner(InputStream is) {
  96.             in = is;
  97.         }
  98.  
  99.         private int readByte() throws IOException {
  100.             if (ptr >= len) {
  101.                 len = in.read(buffer);
  102.                 ptr = 0;
  103.                 if (len <= 0) return -1;
  104.             }
  105.             return buffer[ptr++];
  106.         }
  107.  
  108.         long nextLong() throws IOException {
  109.             int c;
  110.             do {
  111.                 c = readByte();
  112.             } while (c <= ' ');
  113.  
  114.             long sign = 1;
  115.             if (c == '-') {
  116.                 sign = -1;
  117.                 c = readByte();
  118.             }
  119.  
  120.             long val = 0;
  121.             while (c > ' ') {
  122.                 val = val * 10 + (c - '0');
  123.                 c = readByte();
  124.             }
  125.             return val * sign;
  126.         }
  127.  
  128.         int nextInt() throws IOException {
  129.             return (int) nextLong();
  130.         }
  131.     }
  132. }
  133.  
Success #stdin #stdout 0.09s 54236KB
comments (?)
stdin
copy 
22 1 0 9 1 1 9 1 2 9 1 3 9 1 4 9 1 5 9 1 6 9 1 7 9 1 8 9 1 9 9 2 0 9 2 1 9 2 2 9 2 3 9 2 4 9 2 5 9 2 6 9 2 7 9 2 8 9 2 9 9 1 0 1000000000000000000 2 0 1000000000000000000
stdout
copy 
1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148
https://ideone.com/dg7yDx
language:
Java (HotSpot 12)
created:
1 day 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!