RiseOJ – 소 세기

설명

언제나 그렇듯이, 농부 존의 소들은 그의 가장 큰 목초지에 흩어져 있다. 이 목초지는 정사각형 "칸"들로 이루어진 커다란 2차원 격자(거대한 체스판을 떠올려 보자)로 생각할 수 있다.

목초지에 소들이 분포한 패턴은 상당히 흥미롭다. $x\ge 0$ , $y\ge 0$ 인 모든 칸 $$(x,y)$$ 에 대해, 모든 정수 $k\ge 0$ 에 대해 $\left\lfloor \frac{x}{3^k}\right\rfloor$ 와 $\left\lfloor
\frac{y}{3^k}\right\rfloor $를\ 3으로\ 나눈\ 나머지의\ 홀짝성이\ 같으면$ (x,y) $에\ 소가\ 존재한다. 다시\ 말해, 두\ 나머지가\ 모두\ 홀수($ 1 $)이거나, 모두\ 짝수($ 0 $$ 또는 $$ 2 $)여야\ 한다. 예를\ 들어$ 0\le x,y<9$를 만족하는 칸 중 소가 있는 칸은 아래 그림에서 1로 표시되어 있다.

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

FJ는 목초지의 특정 영역에 소가 몇 마리 있는지 궁금하다. 그는 $$Q$$ 개의 질의를 하며, 각 질의는 세 정수 $$x_i,y_i,d_i$$ 로 이루어진다. 각 질의에 대해 FJ는 $$(x_i,y_i)$$ 부터 $$(x_i+d_i,y_i+d_i)$$ 까지의 대각선 범위에 있는 칸들(양 끝점 포함)에 소가 몇 마리 있는지 알고 싶어 한다.

문제 제공: Benjamin Qi

제약

채점 방식

테스트 케이스 2는 각 질의에 대해 $d_i\le 100$ 을 만족한다.
테스트 케이스 3-6은 각 질의에 대해 $x+d=3^{30}-1$ 이고 $$y=0$$ 을 만족한다.
테스트 케이스 7-12는 추가 제약이 없다.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 질의의 개수 $$Q$$ ( $1\le Q\le 10^4$ )가 주어진다.

다음 $$Q$$ 개의 줄에는 각각 세 정수 $$d_i$$ , $$x_i$$ , $$y_i$$ ( $0\le x_i,y_i,d_i\le 10^{18}$ )가 주어진다.

출력 형식

각 질의마다 한 줄씩, 총 $$Q$$ 개의 줄을 출력한다.

예제 1

입력

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

출력

11
0
4
3
1
2
2
1000000000000000001

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > February > Gold

올림피아드 > USACO > 2020-2021 > February > Gold

태그

JudgeUSACO

소 세기

평가 및 의견

풀이 제출