시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 616 | 467 | 412 | 75.458% |
블리트릭스라는 양은 더 빨리 잠을 들기 위한 전략을 세웠다.
먼저, 숫자 N을 뽑는다. 그리고 N, 2 × N, 3 × N 등을 떠올린다. 숫자를 떠올릴 때 마다, 그 숫자의 모든 자리수의 숫자들을 적어놓는데, 이미 적은 숫자는 또 적지 않는다. 0에서 9까지의 모든 숫자가 적히게 되면 잠이 든다.
블리트릭스는 N에서 시작해서 i × N 후에는 (i + 1) × N을 떠올리게 된다. 예를 들어 N = 1692 일 경우, 다음 과 같이 진행된다:
블리트릭스가 잠에 빠지는 수는 무엇인가? 영원히 잠에 들 수 없다면 INSOMNIA라고 출력하라.
첫 번째 행은 케이스의 개수, T이다. 다음 행부터는 T개의 케이스들이 나온다. 각 케이스는 블리트릭스가 고른 하나의 숫자 N으로 구성된다.
제한
각 케이스에 대해서, 케이스 번호가 x이고 y가 정답일 때, Case #x: y라고 출력해야 한다.
5 0 1 2 11 1692
Case #1: INSOMNIA Case #2: 10 Case #3: 90 Case #4: 110 Case #5: 5076
예제 입출력 1번에 대해서, 2 × 0 = 0, 3 × 0 = 0 등등으로 이어지므로, 블리트릭스는 0외에는 다른 숫자를 기록할 수 없을 것이며, 따라서 영원히 잠에 들 수 없다.
예제 입출력 2번의 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 순으로 떠올릴 것이며, 0이 가장 마지막에 기록되는 수가 될 것이다. 따라서 10이 마지막 수가 될 것이다.
예제 입출력 3번의 경우, 2, 4, 6... 등등으로 떠올릴 것이다. 숫자 9는 90 전에는 기록할 수 없다. 90을 떠올렸을 때 이미 블리트릭스는 0~8의 숫자를 적었을 것이므로, 90이 마지막 수가 될 것이다.
예제 입출력 4번은 블리트릭스가 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 을 떠올릴 것이고, 110이 마지막 수가 될 것이다.
예제 입출력 5번은 문제에서 설명한 수이다.
Contest > Google > Code Jam > Google Code Jam 2016 > Qualification Round A2번