%2021. 12. 1. 22:47에 작성된 글입니다%
2595번: 배수
N은 30,000이하의 자연수이다.
www.acmicpc.net
05KOI 지역본선 고등부 5번이랜다... 뻘짓을 좀 하긴 했는데 여튼 푸는 데만 거의 3시간을 갖다 박았으니 아직 KOI 지역 수준에도 못 미치는 것이다. 안타깝다.
문제를 푸는 데 중요한 사실은, 조건을 만족하는 출력은 모두 숫자의 종류의 수(이하 cnt(x)로 씀)가 1 혹은 2라는 것이다. 증명은 모르겠다.
1인 경우에는 당연히 1111, 33333333, 77777 따위의 수가 될 것이고, 2는 3333300000000, 44444440, 20220222220, 2882828, 5555555550 뭐 이런 식의 형태이다.
1. 수에 10의 배수가 있다면 cnt(출력)은 무조건 2다. 10의 배수인 수에 무슨 짓을 해도 맨 뒤의 0을 없앨 수 없기 때문.
2. 수에 16의 배수나 25의 배수가 있다면 무조건 2다.
임의의 자연수 n에다 임의의 자연수를 잘 곱해서 1로만 이루어진 수를 만들 수 있다고 하자. 8n이나 5n은? 각각 8로만 이루어진 수, 5로만 이루어진 수를 만들 수 있다. 16n이나 25n은???
얘네는 일단 무조건 안 된다. 17777777776이나 27777777777777775 따위의 형태가 나올 텐데, 이러면 cnt 값이 3이니까 아웃이다.
이제 N을 대충 가공해서 만들어 낸 xxxxxxxxxx...xxx에 처리를 잘 해서 답을 낼 수 있다. 이게 케이스 1.
핵심은 케이스 2고, 자릿수마다 bfs를 때리는데 대충 경우의 수 잘 컷해서 구현하면 된다.
%+2022-02-14: 이후 'notorious coincidence' 날먹하려다가 실패하고 나서 안 사실인데, 2595에서는 AC맞는 코드가 7784에서는 TLE가 날 수 있다. 아니 애초에 테케 수도 범위도 다른데 뭐지...%