PrimeAlters
2019 Humblefool Cup Prelims · 2019-03-12 · by misof
Problem Statement
Two primes are called adjacent if they have the same number of digits and they only differ in one of them. For example, 103 and 113 are adjacent primes, as they only differ in the tens digit. The primes 113 and 131 are not adjacent: you need to change two digits of 113 to get 131.
In this problem your task is to transform one prime into another. You have to do this in a sequence of zero or more steps, and in each step you can change the prime you have into an adjacent prime.
You are given the
Notes
- The number 1 is not a prime number. The one-digit primes are only 2, 3, 5, and 7.
- You are not allowed to change the leading digit of a prime into a zero.
Constraints
- N will be between 1 and 200, inclusive.
- source and target will have N elements each.
- Each element of source and target will be between 2 and 99,999,999, inclusive.
- Each element of source and target will be a prime number.
- For each i, source[i] and target[i] will have the same number of digits.
{2, 17, 11, 98240249}
{7, 47, 47, 98240249}
Returns: "1111"
We can directly turn 2 into 7. We can also directly turn 17 into 47 by changing the tens digit from 1 to 4. We can change 11 into 47 using multiple consecutive steps. The two shortest solutions are 11 -> 17 -> 47 and 11 -> 41 -> 47. If the source and the target are equal, we don't need any steps.
{294001, 100003}
{100003, 100003}
Returns: "01"
There is no valid way to turn source[0] into target[0].
{7331, 72652729}
{8219, 28794281}
Returns: "11"
7331 -> 7351 -> 7451 -> 7411 -> 7211 -> 7219 -> 8219 72652729 -> 72652799 -> 72652999 -> 72656999 -> 92656999 -> 92696999 -> 92696939 -> 92696239 -> 92796239 -> 22796239 -> 28796239 -> 28796231 -> 28796281 -> 28794281
{2, 2, 3, 3}
{2, 3, 3, 2}
Returns: "1111"
{59908397, 99473021, 74785357, 10389803, 50890967, 60181831, 15337303, 30399739, 27313183, 55112053, 82351627, 21036721, 99103379, 80674207, 68784827, 36296699, 11720389, 60348193, 31128701, 82976143, 64069561, 59610611, 11418331, 84167417, 10539251, 99287579, 41290817, 65829527, 15364289, 65406307, 52153601, 65804257, 64889197, 88616681, 36107789, 17548757, 49137797, 41812613, 99586583, 37497403, 58210613, 81940981, 19803841, 57338851, 32838391, 79557403, 85484219, 34684501, 11646517, 77467051, 78703267, 65902841, 99000619, 80298539, 20976937, 99615731, 79593131, 53022731, 35349857, 85575403, 20038411, 48670187, 22184231, 75875411, 37772857, 49026833, 53598401, 48119957, 52101547, 53196851, 77290219, 12525463, 96914197, 88127729, 30213707, 29945561, 37661849, 76502809, 25920217, 39435173, 24678553, 96169819, 66583351, 23756371, 46067839, 78602197, 83653223, 26682653, 32495171, 80074409, 72860033, 43110299, 29658443, 55550029, 80377289, 28669393, 65990621, 95746031, 37877093, 19717553, 49095703, 16663307, 82512581, 16870493, 64672733, 14103361, 37206619, 94410103, 50513797, 24387817, 95105221, 66295367, 20864773, 61803361, 81296143, 57747853, 41053157, 35064257, 45337081, 64840129, 16519999, 79651133, 69297391, 97646443, 35958437, 20644837, 86956351, 93958817, 16773893, 25604573, 73708513, 26676977, 93460099, 26783693, 33889469, 58292257, 31107529, 32335781, 23265691, 73064093, 47477323, 18778967, 40089649, 29301091, 71407283, 82669549, 78534793, 73764217, 78792167, 85348873, 10532603, 86044139, 65200309, 39640963, 53076103, 62295377, 51000211, 40525187, 26650763, 28519259, 57107033, 91909183, 45934123, 21268927, 19321229, 71297803, 40271479, 12013189, 95527591, 54398347, 44909717, 14111051, 33886649, 46235351, 33653953, 66344513, 90439171, 73196159, 11890343, 69361711, 58818239, 12428051, 25978501, 85743607, 42269137, 70270147, 48442307, 54551551, 72082937, 66268831, 74454763, 90973559, 28524689, 21745357, 13089743, 38323631, 53543449, 43609859, 11593607, 19801123}
{91754731, 82031813, 69947519, 84632461, 99747409, 35380559, 98859689, 71417441, 99253267, 99580447, 73541203, 99735919, 84415151, 45526469, 77223481, 77914147, 96852461, 91754731, 50607307, 99724309, 50431883, 85096057, 73227589, 73227589, 35222413, 58878431, 99414499, 99747409, 50852173, 24558823, 97418443, 90715753, 35456053, 99747409, 97711247, 99747409, 84632461, 88488821, 74601367, 82143227, 48979481, 24558823, 93400733, 73227589, 24558823, 88672531, 76168171, 50246699, 20895793, 23080049, 67925189, 83127383, 44956151, 64913047, 73541203, 61129261, 82880069, 48156989, 79187191, 91754731, 75857669, 97418443, 99735919, 31144279, 55238279, 63405347, 88457669, 99735919, 48120419, 48120419, 50852173, 83381357, 82190629, 63435511, 99735919, 72567049, 85371457, 98741551, 99747409, 91754731, 99735919, 58878431, 88338269, 46844869, 55478641, 99747409, 96339931, 64469501, 84951689, 63405347, 23971159, 84221647, 67766857, 43493893, 67141091, 99747409, 99747409, 73227589, 83433821, 44586527, 31150277, 24558823, 93301249, 81487141, 78753977, 93985553, 48979481, 46151177, 75705853, 99724309, 44586527, 87689543, 84632461, 99747409, 99724309, 95158411, 22361219, 99747409, 33140819, 46151177, 24558823, 63405347, 83726659, 76157527, 73227589, 75539759, 14015173, 38584103, 87227317, 98741551, 88214387, 88338269, 19571611, 63405347, 25752731, 99747409, 48979481, 44586527, 49828829, 25752731, 82682641, 92559703, 85096057, 24558823, 87858961, 98741551, 63405347, 48156989, 62928953, 91454021, 47378147, 10509677, 49444523, 97711247, 91754731, 24558823, 20895793, 99747409, 98741551, 69055837, 89046829, 82488979, 48156989, 99747409, 84632461, 69976927, 91754731, 53768597, 24558823, 56837219, 99724309, 97660243, 84632461, 85976797, 99747409, 17461657, 82880069, 28847867, 58878431, 82880069, 46991677, 28873193, 44586527, 24558823, 48156989, 91165313, 37995653, 99747409, 93301249, 44586527, 95970089, 14015173, 84632461, 73227589, 21130111, 24558823, 24558823, 87417481, 40709209, 48156989}
Returns: "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrimeAlters with a public method string isReachable(vector<int> source, vector<int> target) · 69 test cases · 2 s / 256 MB per case