tło
Ex zwiększenie ustalonej kolejności kolejnością określa się jako sekwencję zestawów całkowitą który spełnia następujące:
- Każdy jest niepustym podzbiorem .
- Dla , , tj. dwa kolejne zestawy nie mają wspólnych elementów.
- Dla średnia (wartość średnia) jest ściśle mniejsza niż .
Wyzwanie
Biorąc pod uwagę dodatnią liczbę całkowitą N
, wyprowadza długość najdłuższej, rosnącej sekwencji sekwencji N
.
Przypadki testowe
Są one oparte na wynikach Project Euler użytkownika thundre .
1 => 1 // {1}
2 => 2 // {1} {2}
3 => 3 // {1} {2} {3}
4 => 5 // {1} {2} {1,4} {3} {4}
5 => 7 // {1} {2} {1,4} {3} {2,5} {4} {5}
6 => 10 // {1} {2} {1,4} {3} {1,4,5} {2,3,6} {4} {3,6} {5} {6}
7 => 15 // {1} {2} {1,4} {3} {1,2,7} {3,4} {1,2,5,7} {4} {1,3,6,7} {4,5} {1,6,7} {5} {4,7} {6} {7}
8 => 21
9 => 29
10 => 39
11 => 49
12 => 63
13 => 79
14 => 99
15 => 121
16 => 145
17 => 171
18 => 203
19 => 237
20 => 277
21 => 321
22 => 369
23 => 419
24 => 477
25 => 537
Zasady
Obowiązują standardowe zasady gry w golfa . Najkrótsze prawidłowe przesłanie w bajtach wygrywa.
Hojność
Problem ten był omawiany tutaj na forum projektu Euler około 4 lata temu, ale nie udało nam się opracować sprawdzalnego algorytmu czasu wielomianowego (pod względem N
). Dlatego przyznam +200 nagród za pierwsze zgłoszenie, które to osiągnie, lub udowodnię jego niemożliwość.