차이
시간 제한2초메모리 제한512 MB
A1에서 시작해 다음에 더할 가장 작은 차이를 골라 수열을 만들고, m이 수열의 값 또는 두 값의 차이로 처음 나오는 위치 n을 찾습니다.
문제
최소 차이 수열(SDS)은 다음과 같이 만든 양의 정수 수열이다. A1 = r ≥ 1이다. n > 1일 때 An = An−1 + d이며, d는 수열의 값이나 이미 수열에 있는 두 값의 차이로 아직 등장하지 않은 가장 작은 양의 정수이다. 예를 들어 A1 = 1이면 지금까지 수열에 없는 가장 작은 수가 2이므로 A2 = A1 + 2 = 3이다. 마찬가지로 A3 = 7인데, 1, 2, 3은 이미 수열의 값이거나 두 값의 차이로 사용되었기 때문이다. 계속하면 1, 2, 3, 4, 6, 7이 사용되었으므로 다음으로 가장 작은 차이는 5이고, 따라서 A4 = 12이다. 이 SDS의 다음 몇 항은 20, 30, 44, 59, 75, 96, ...이다. 양의 정수 m이 주어지면, m이 SDS의 값으로 처음 등장하는지, SDS에 있는 두 값의 차이로 처음 등장하는지 판별해야 한다. 위 SDS에서 12, 5, 9, 11은 4단계에서 처음 등장한다.
입력
입력은 한 줄로 주어지며, 두 양의 정수 A1 m (1 ≤ r ≤ 100, 1 ≤ m ≤ 200 000 000)이 포함된다.
출력
수열 A1, ..., An이 m을 값으로 포함하거나 두 값의 차이로 포함하는 가장 작은 n을 출력한다. 모든 답은 10 000 이하이다.