https://codeforces.com/contest/1561/problem/B
시간 2초, 메모리 512MB
input :
- t (1 ≤ t ≤ 103)
- a b (0 ≤ a, b ≤ 105, a + b > 0)
output :
-
For each test case print two lines.
각 테스트 케이스에서 두 줄을 출력하시오. -
In the first line, print a single integer m (1 ≤ m ≤ a + b + 1) — the number of values of k such that exactly k breaks could happen during the match.
첫 번째 줄에는 경기를 할 때 브레이크가 발생할 수 있는 경기 상황의 수 m을 출력하시오. -
In the second line, print m distinct integers k1, k2, ..., km (0 ≤ k1 < k2 < … < km ≤ a + b) — the sought values of k in increasing order.
두 번째 줄에는 각 경기 상황에서 발생하는 브레이크의 횟수를 오름차순으로 출력하시오.
조건 :
-
Players serve in turns: after a game where Alice is serving follows a game where Borys is serving, and vice versa.
서브는 돌아가면서 넣게 됩니다. Alice가 서브를 하면 그 다음 경기는 Borys가 그 다음은 Alice가 ... -
If a game is won by the serving player, it's said that this player holds serve. If a game is won by the receiving player, it's said that this player breaks serve.
서브를 넣은 선수가 게임을 이기게 되면 이를hold라 부릅니다. 서브를 받는 선수가 게임을 이기게 되면 이를break라 부릅니다. -
It is unknown who served first and who won which games.
어느 선수가 서브를 넣을지는 정해져 있지 않습니다. -
Find all values of k such that exactly k breaks could happen during the match between Alice and Borys in total.
Alice와 Borys가 경기를 하는 도중에 발생할 수 있는 모든 break의 경우의 수를 구하시오.
우선 서브를 누가 넣을 지는 정해져 있지 않다.
그렇기 때문에 총 경기의 수가 홀수라면
A B A B A
B A B A B
두 가지의 경우가 발생한다. 근데 맨 처음 입력을 받을 때 1 5, 5 1 이렇게 입력이 들어올 때 어차피 브레이크가 발생하는 경우의 수는 동일하다.
입력이 1 2 가 들어올 때
Borys의 기준에서 승패를 나열해 보자.
A B A
B A B
break를 가장 최소화 하려면 우선 자기의 서브를 지켜야 한다. 그래서 최대한 자기의 서브는 지키고 남는 나머지의 경우에 브레이크가 발생한다.
승 패 승 -> 3, 0의 브레이크가 발생한다.
그 다음의 경우 어떤 경우가 있을까? 순서를 바꿀 수 있다. 근데 순서를 바꾸게 되면 브레이크의 경우는 2개씩 차이가 나게 된다. 이전에는 브레이크가 아니였던 것을 브레이크가 발생하도록 했기 때문이다.
그러면 우리는 최소, 최대의 경우를 들고 있기 때문에 하나의 경우에는 2개 줄어드는 것이고 하나의 경우는 2개 늘어나는 것이다.
그래서 반복문을 이용해서 찾을 수 있다.
3번 발생하던 브레이크는 2번의 지점을 교체해서 1번 브레이크가 발생하게 할 수 있고
0번의 경우에는 2번 브레이크가 발생하게 할 수 있다.
import sys, math
for _ in range(int(sys.stdin.readline())):
a, b = map(int, sys.stdin.readline().split())
if a > b:
a, b = b, a
small, big = math.floor((a + b) / 2), math.ceil((a + b) / 2)
start, end = b - big, a + big
left, right = [i for i in range(start, end, 2)], [i for i in range(end, start - 1, -2)]
ans = list(set(left + right))
ans.sort()
print(len(ans))
print(*ans)end의 형태는 a + b - start로 만들어서 제출했는데 저런 형태로 만들 수 있길래 바꿨다.
수식을 중요시하는 거 같다.
