33489번 - 수열의 점수 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 437 | 176 | 131 | 41.456% |
문제
두 정수 $x$와 $y$가 주어질 때, 무한한 길이의 정수 수열 $A$를 아래와 같이 정의한다.
- $A_1 = x$
- $A_2 = y$
- $A_{k} = A_{k-2} - A_{k-1}(k \geq 3)$
당신은 $1 \leq x \leq X;$ $1 \leq y \leq Y$를 만족하는 정수 $x$, $y$를 선택할 수 있다.
수열에서 $0$ 이하의 수가 $k$번째 항에서 처음 등장하였을 때, $k$를 수열 $A$의 점수라고 한다. $x$, $y$를 어떻게 정하더라도 상관없이 수열에 $0$ 이하의 수가 적어도 한 번 등장함을 증명할 수 있다. 수열 $A$의 점수를 최대화하는 $x$, $y$를 찾아보자.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 아래와 같이 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, 두 개의 정수 $X$, $Y$가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해, 수열 $A$의 점수를 최대화하는 $x$와 $y$를 공백으로 구분하여 출력한다.
정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.
제한
- $1\leq T \leq 10^4$
- $1\leq X, Y \leq 3 \times 10^5$
- 모든 테스트 케이스의 $X$의 합은 $10^6$을 넘지 않음
- 모든 테스트 케이스의 $Y$의 합은 $10^6$을 넘지 않음
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $X = 1$ |
| 2 | 15 | 모든 테스트 케이스의 $X\cdot Y$의 합은 $3 \times 10^7$을 넘지 않음 |
| 3 | 82 | 추가 제약 조건 없음 |
예제 입력 1
1 4 3
예제 출력 1
4 3
$x = 4$, $y = 3$인 경우 수열 $A$를 나열하면 $4, 3, 1, 2, -1, 3, \cdots$으로 $0$보다 작거나 같은 값이 처음으로 등장하는 항은 $A_5$이고, 점수는 $5$이다.
다른 어떤 $x$, $y$를 선택하더라도 이보다 점수를 더 높게 만들 수 없음을 증명할 수 있다. 따라서 $x = 4$, $y = 3$이 답이 된다.
출처
School > 한국과학영재학교 > 2025 KSA Automata Winter Contest E번
- 문제를 만든 사람: mythofys
- 문제를 검수한 사람: hjroh0315, utilforever, sooahn07, sjhi00, raehwan0418, parkky, kwoncycle, kep1er07, aaron0526, gs22059, flakepowders, eric00513, edward3378, dongwook7, davidkim0, ai4youej
채점 및 기타 정보
- 예제는 채점하지 않는다.