BOJ 1494 - 절댓값 수열

BOJ 1494 - 절댓값 수열

Div2 C 문제에 동일한 아이디어가 나왔고, 저 글에서풀이를 대신한다.

다만 이 문제에선 실제로 $s_i$ 의 값을 추적해줘야 하는데, 이것도 사실 그렇게 어렵지 않다.

int f(int a, int b) {  
   if (a == 0) return 0;  
   if (b == 0) return 1;  
   if (a == b) return 2;  
   if (a > b) {  
      int q = a / b;  
      int r = a % b;  
  
      if (q % 2 == 1) {  
         return f(b, r) + q + q / 2;  
      } else {  
         return f(r, b) + q + q / 2;  
      }  
  
   } else {  
      return f(b, abs(b - a)) + 1;  
   }  
}  
  
int f2(int a, int b, int n) {  
   if (n == 0) return a;  
   if (n == 1) return b;  
   if (n == 2) return abs(b - a);  
   if (a >= b) {  
      int q = a / b;  
      int r = a % b;  
  
      int skip = q + q / 2;  
      if (n >= skip) {  
         if (q % 2 == 1) return f2(b, r, n - skip);  
         else return f2(r, b, n - skip);  
      } else {  
         // 0   1   2    3    4    5     6  
         // a,  b, a-b, a-2b, b, a-3b, a-4b  
         if (n % 3 == 1) return b;  
         if (n % 3 == 0) return a - b * (n / 3 * 2);  
         if (n % 3 == 2) return a - b * (n / 3 * 2 + 1);  
      }  
  
   } else {  
      return f2(b, abs(b - a), n - 1);  
   }  
}  
  
void solve() {  
   int a, b, n;  
   cin >> a >> b >> n;  
   vi g(3);  
   int first_zero = f(a, b);  
   int e = gcd(a, b);  
   while (n--) {  
      int i;  
      cin >> i;  
      if (i >= first_zero) {  
         if (i % 3 == first_zero % 3) cout << 0 << endl;  
         else cout << e << endl;  
      } else {  
         cout << f2(a, b, i) << endl;  
      }  
   }  
}