16203번 - 까다로운 수 찾기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 35 | 22 | 11 | 78.571% |
문제
알버트는 학교에서 정수, 숫자, 뺄셈을 배웠다. 그래서 심심할 때마다 혼자 즐길 수 있도록 "까다로운 수"라는 게임을 만들었다.
이 게임을 하려면 먼저, 0 이상 9 이하 숫자 A를 골라야 한다. 그 이후 K번째 작은 "A-까다로운 수"를 찾아야 하는데, 양의 정수 X가 아래와 같은 조건을 만족하면 "A-까다로운 수"라고 한다.
- X가 한 자릿수면 "A-까다로운 수"이다.
- X가 두 자리 이상이면서, X를 구성하는 숫자 중 인접한 숫자의 차이가 A 미만인 경우가 없으면 "A-까다로운 수"이다.
예를 들어, A = 0인 경우 모든 양의 정수는 "A-까다로운 수"이다.
A = 1인 경우, 첫 30개의 "A-까다로운 수"는 다음과 같다.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...
A와 K가 주어졌을 때, K번째로 작은 "A-까다로운 수"를 구하는 프로그램을 작성하시오. 단, 답이 매우 큰 수가 될 수 있기 때문에, 109+7로 나눈 나머지를 출력한다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 100). 다음 T줄에 걸쳐서 각 줄에 K와 A가 주어진다. 두 정수는 공백으로 구분되어져 있다. (1 ≤ K ≤ 1018, 0 ≤ A ≤ 9)
출력
각 테스트 케이스마다 K번째 작은 "A-까다로운 수"를 109+7로 나눈 나머지를 한 줄에 하나씩 출력한다.
예제 입력 1
8 5 0 5 1 30 1 12 2 20 5 21 5 30 8 1000 8
예제 출력 1
5 5 32 15 50 60 9190 80902435
- 네 번째 테스트 케이스: A = 2 일 때 10, 11, 12 는 "2-까다로운 수"가 아니다.
- 마지막 테스트 케이스: 1000번째 "8-까다로운 수"는 808080908091이고, 이 값을 109+7로 나눈 나머지는 80902435 이다.
출처
- 문제를 만든 사람: haden
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호