Сумма значений на улице и в наборе может быть разделена на 3:
- n + n + n = 3n
- (n-1) + n+ (n + 1) = 3n
Итак, если вы сложите все числа в решенной раздаче, вы получите число вида 3N + 2M, где M - значение плиткив паре.Остаток от деления на три (total % 3) для каждого значения M:
total % 3 = 0 -> M = {3,6,9}
total % 3 = 1 -> M = {2,5,8}
total % 3 = 2 -> M = {1,4,7}
Таким образом, вместо того, чтобы проверять девять возможных пар, вам нужно всего лишь попробовать три на основе простогодополнение.Для каждой возможной пары удалите две плитки с этим значением и перейдите к следующему шагу алгоритма, чтобы определить, возможно ли это.
Как только вы это получите, начните с самого низкого значения.Если с этим значением меньше трех плиток, это означает, что они обязательно являются первым элементом улицы, поэтому удалите эту улицу (если вы не можете этого сделать, потому что плитки n + 1 или n + 2 отсутствуют, это означает, что руканедопустимо) и перейдите к следующему наименьшему значению.
Если есть хотя бы три плитки с наименьшим значением, удалите их как набор (если вы спросите "что, если они были частью улицы?"«учтите, что если бы они были, то есть также три фрагмента n + 1 и три фрагмента n + 2, которые также можно превратить в наборы), и продолжим.
Если вы дойдете до пустой руки, эта рука действительна.
Например, для вашей недействительной руки итоговая сумма равна 60, что означает M = {3,6,9}:
Remove the 3: 112244556789
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there is only one
Remove the 9: impossible, there is only one
В вашем втором примере 12345555678999 сумма равна78, что означает M = {3,6,9}:
Remove the 3: impossible, there is only one
Remove the 6: impossible, there is only one
Remove the 9: 123455556789
- Start with 1: there is only one, so remove a street
-> 455556789
- Start with 4: there is only one, so remove a street
-> 555789
- Start with 5: there are three, so remove a set
-> 789
- Start with 7: there is only one, so remove a street
-> empty : hand is valid, removals were [99] [123] [456] [555] [789]
Ваш третий пример 11223378888999 также имеет в общей сложности 78, что вызывает возврат:
Remove the 3: 11227888899
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there are none
Remove the 9: 112233788889
- Start with 1: there are less than three, so remove streets
-> 788889
- Start with 7: there is only one, so remove a street
-> 888
- Start with 8: there are three, so remove a set
-> empty, hand is valid, removals were : [99] [123] [123] [789] [888]