ArithSeq
SRM 224 · 2004-12-22 · by vorthys
Problem Statement
An arithmetic sequence of length n is a sequence of n numbers in which the difference between each pair of adjacent numbers is some constant delta. For example, the sequence 1,6,11,16 is an arithmetic sequence of length 4 with delta=5. Now, consider the infinite set
{ 1, 3, 4, 7, 8, 9, ... }
This set is of particular interest to mathematicians because it contains arbitrarily long arithmetic sequences for any delta, yet it contains no infinitely long arithmetic sequences. The set is contructed by keeping or dropping successive groups of positive integers according to the following pattern: keep one (1), drop one (2), keep two (3,4), drop two (5,6), keep three (7,8,9), drop three (10,11,12), and so on.
Given n and delta, your task is to find the earliest arithmetic sequence contained in the set that has the given length and delta. In other words, you should find the smallest number A such that all integers of the form A+i*delta are in the set, for all i between 0 and n-1, inclusive. You should return A.
Constraints
- n is between 2 and 30, inclusive.
- delta is between 1 and 100000000, inclusive.
3 3 Returns: 1
The sequence is 1, 4, 7.
5 12 Returns: 9
6 12 Returns: 3661
30 4130 Returns: 1001001
30 100000000 Returns: 670380219057
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ArithSeq with a public method long long minStart(int n, int delta) · 74 test cases · 2 s / 256 MB per case