Problem 794: Seventeen Points
View on Project EulerProject Euler Problem 794 Solution
EulerSolve provides an optimized solution for Project Euler Problem 794, Seventeen Points, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary We seek the minimum possible value of \(x_1+\cdots+x_{17}\) for points added one at a time inside the unit interval. After the \(m\)-th insertion, the current set of \(m\) points must occupy the \(m\) half-open subintervals $$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$$ exactly once. So the first stage uses one bin, the second stage must place two points into the two halves, the third stage must place three points into the thirds, and so on up to \(m=17\). The implementations compute the optimal sum exactly, prove that \(17\) stages are feasible, and also verify that the same condition fails at \(18\). Mathematical Approach The key simplification is to represent uncertainty by rational intervals instead of individual real numbers. Every future decision only cuts intervals by equal-partition boundaries, so the whole search can be done with integer arithmetic. Step 1: Put Every Boundary on One Common Grid Let $$d=\operatorname{lcm}(1,2,\dots,17).$$ Because every \(m\le 17\) divides \(d\), every boundary \(k/m\) can be written exactly as an integer multiple of \(1/d\)....
Detailed mathematical approach
Problem Summary
We seek the minimum possible value of \(x_1+\cdots+x_{17}\) for points added one at a time inside the unit interval. After the \(m\)-th insertion, the current set of \(m\) points must occupy the \(m\) half-open subintervals
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$$
exactly once. So the first stage uses one bin, the second stage must place two points into the two halves, the third stage must place three points into the thirds, and so on up to \(m=17\). The implementations compute the optimal sum exactly, prove that \(17\) stages are feasible, and also verify that the same condition fails at \(18\).
Mathematical Approach
The key simplification is to represent uncertainty by rational intervals instead of individual real numbers. Every future decision only cuts intervals by equal-partition boundaries, so the whole search can be done with integer arithmetic.
Step 1: Put Every Boundary on One Common Grid
Let
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Because every \(m\le 17\) divides \(d\), every boundary \(k/m\) can be written exactly as an integer multiple of \(1/d\). Instead of storing a point \(x\), we store an interval
$$I=[l,u)\subseteq[0,d),$$
which means that the real point may lie anywhere in
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
Initially nothing is known, so the first state is just one interval:
$$[0,d).$$
Step 2: Describe the Transition from \(n\) Points to \(n+1\) Points
Assume a state with \(n\) current intervals already encodes all constraints from stages \(1\) through \(n\). For the next stage set
$$m=n+1.$$
The unit interval is now partitioned into \(m\) equal bins, which on the common denominator grid become
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
Each existing interval \(I_i\) must be assigned to one distinct bin with nonempty intersection. If bin \(B_{\pi(i)}\) is chosen, the interval is refined to
$$I_i'=I_i\cap B_{\pi(i)}.$$
Exactly one bin is left unused, and that unused bin becomes the interval of the newly inserted point. If no injective assignment exists, that branch of the search is impossible.
Step 3: View Feasibility as a Matching Problem
For a fixed stage \(m\), form a bipartite graph whose left side is the current intervals and whose right side is the \(m\) bins. Connect \(I_i\) to \(B_k\) whenever
$$I_i\cap B_k\ne\varnothing.$$
A valid transition is exactly an injective matching of the \(n\) current intervals into the \(m\) bins, leaving one unmatched bin for the new point. This is the Hall-type combinatorial core of the problem. The implementations do not invoke a separate matching library; instead they search directly through these assignments and prune as soon as a state becomes impossible.
Step 4: Canonical States Remove Label Symmetry
Once only the set of surviving intervals matters, the names of the points no longer matter. After every transition, the intervals are sorted by their endpoints. Two different histories that produce the same sorted interval list therefore represent exactly the same future problem.
This turns the search into dynamic programming on canonical states. A state is fully described by its sorted half-open intervals, and every repeated state can reuse the previously computed result instead of exploring the whole subtree again.
Step 5: The Objective Is the Sum of Left Endpoints
When the search reaches \(17\) intervals, each interval \(I_i=[l_i,u_i)\) contains all admissible final positions of one point. Since the target quantity is the sum of coordinates and every interval includes its left endpoint, the minimum achievable sum inside that terminal state is
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
Choosing any point farther to the right can only increase the total. So the global optimization problem reduces to minimizing the integer numerator
$$F=\sum_{i=1}^{17} l_i,$$
and converting to the real answer only once, at the end, by dividing by \(d\).
Worked Example: The \(4\)-Point Check
The implementations include a small exact checkpoint at target \(4\). Then
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
One optimal chain of states is
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
At the fourth stage the quarter bins are \([0,3)\), \([3,6)\), \([6,9)\), and \([9,12)\). An optimal refinement is
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
The unused bin is \([3,6)\). Therefore the four final left endpoints are \(0,3,6,9\), so
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
This is exactly the verification embedded in the implementations.
How the Code Works
The C++, Python, and Java implementations all follow the same plan. They first build the common denominator \(d\), then represent every state as a sorted list of half-open intervals with integer endpoints. From a state with \(n\) intervals, the implementation creates the \(n+1\) equal bins for the next stage and computes every nonempty interval-bin intersection.
If some interval has no compatible bin, the state is rejected immediately. Otherwise the search tries injective assignments, always considering first the interval with the fewest available bins, because that ordering cuts the branching factor sharply. One memoized search answers the yes-or-no question “can this state still be completed?”, and another memoized search returns the minimum possible numerator \(F\) reachable from that state.
The final decimal output is produced by exact integer rounding of \(F/d\) to twelve digits after the decimal point. The implementations also perform three internal consistency checks: the \(4\)-point value is \(3/2\), the \(6\)-point dynamic program agrees with a brute-force search, and feasibility is true for \(17\) but false for \(18\).
Complexity Analysis
For a state containing \(n\) intervals, constructing the next-stage bins and all interval-bin intersections costs \(O(n^2)\), because there are \(n\) intervals and \(n+1\) bins. The difficult part is the search over injective assignments, whose worst-case size is combinatorial, so the theoretical upper bound is exponential in the target size.
In practice, three features make the problem tractable for \(17\): interval intersections shrink the options quickly, branching starts with the most constrained interval, and canonical-state memoization merges many different histories into the same subproblem. Therefore the real running time is governed by the number of distinct canonical interval states that are visited, while memory is proportional to the number of cached states times the interval data stored for each one.
Footnotes and References
- Problem page: Project Euler 794 - Seventeen Points
- Least common multiple: Wikipedia - Least common multiple
- Hall's marriage theorem: Wikipedia - Hall's marriage theorem
- Bipartite graph: Wikipedia - Bipartite graph
- Dynamic programming: Wikipedia - Dynamic programming
Problem 794 source code
C++
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <numeric>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#include <iostream>
using i64 = std::int64_t;
using i128 = __int128_t;
struct Interval {
int l;
int u;
};
struct Option {
int bin;
int l;
int u;
};
struct VecHash {
std::size_t operator()(const std::vector<int>& v) const noexcept {
std::size_t h = 1469598103934665603ULL;
for (int x : v) {
h ^= static_cast<std::size_t>(x + 0x9e3779b9);
h *= 1099511628211ULL;
}
return h;
}
};
static bool interval_less(const Interval& a, const Interval& b) {
if (a.l != b.l) {
return a.l < b.l;
}
return a.u < b.u;
}
static int lcm_upto(int n) {
i64 d = 1;
for (int i = 1; i <= n; ++i) {
d = std::lcm(d, static_cast<i64>(i));
}
return static_cast<int>(d);
}
class Solver {
public:
explicit Solver(int target) : target_(target), d_(lcm_upto(target)) {}
int denom() const {
return d_;
}
i64 solve_min() {
std::vector<Interval> init{{0, d_}};
return solve_min_state(init);
}
bool can_choose_all() {
std::vector<Interval> init{{0, d_}};
return feasible_state(init);
}
private:
int target_;
int d_;
std::unordered_map<std::vector<int>, i64, VecHash> memo_min_;
std::unordered_map<std::vector<int>, bool, VecHash> memo_feasible_;
std::vector<int> pack(const std::vector<Interval>& intervals) const {
std::vector<int> key;
key.reserve(intervals.size() * 2);
for (const auto& in : intervals) {
key.push_back(in.l);
key.push_back(in.u);
}
return key;
}
i64 solve_min_state(const std::vector<Interval>& intervals) {
const std::vector<int> key = pack(intervals);
auto it = memo_min_.find(key);
if (it != memo_min_.end()) {
return it->second;
}
const int n = static_cast<int>(intervals.size());
if (n == target_) {
i64 sum = 0;
for (const auto& in : intervals) {
sum += in.l;
}
memo_min_.emplace(key, sum);
return sum;
}
const int m = n + 1;
std::vector<std::pair<int, int>> bins(m);
for (int k = 0; k < m; ++k) {
bins[k] = {k * d_ / m, (k + 1) * d_ / m};
}
std::vector<std::vector<Option>> options(n);
for (int i = 0; i < n; ++i) {
for (int k = 0; k < m; ++k) {
const int nl = std::max(intervals[i].l, bins[k].first);
const int nu = std::min(intervals[i].u, bins[k].second);
if (nl < nu) {
options[i].push_back({k, nl, nu});
}
}
if (options[i].empty()) {
static constexpr i64 INF = (1LL << 60);
memo_min_.emplace(key, INF);
return INF;
}
}
std::vector<int> order(n);
for (int i = 0; i < n; ++i) {
order[i] = i;
}
std::sort(order.begin(), order.end(), [&](int a, int b) {
return options[a].size() < options[b].size();
});
std::vector<char> used(m, 0);
std::vector<Interval> assigned(n);
i64 best = (1LL << 60);
std::function<void(int)> dfs = [&](int pos) {
if (pos == n) {
int hole = -1;
for (int k = 0; k < m; ++k) {
if (!used[k]) {
hole = k;
break;
}
}
if (hole < 0) {
return;
}
std::vector<Interval> child = assigned;
child.push_back({bins[hole].first, bins[hole].second});
std::sort(child.begin(), child.end(), interval_less);
const i64 cand = solve_min_state(child);
if (cand < best) {
best = cand;
}
return;
}
const int i = order[pos];
for (const auto& op : options[i]) {
if (used[op.bin]) {
continue;
}
used[op.bin] = 1;
assigned[i] = {op.l, op.u};
dfs(pos + 1);
used[op.bin] = 0;
}
};
dfs(0);
memo_min_.emplace(key, best);
return best;
}
bool feasible_state(const std::vector<Interval>& intervals) {
const std::vector<int> key = pack(intervals);
auto it = memo_feasible_.find(key);
if (it != memo_feasible_.end()) {
return it->second;
}
const int n = static_cast<int>(intervals.size());
if (n == target_) {
memo_feasible_.emplace(key, true);
return true;
}
const int m = n + 1;
std::vector<std::pair<int, int>> bins(m);
for (int k = 0; k < m; ++k) {
bins[k] = {k * d_ / m, (k + 1) * d_ / m};
}
std::vector<std::vector<Option>> options(n);
for (int i = 0; i < n; ++i) {
for (int k = 0; k < m; ++k) {
const int nl = std::max(intervals[i].l, bins[k].first);
const int nu = std::min(intervals[i].u, bins[k].second);
if (nl < nu) {
options[i].push_back({k, nl, nu});
}
}
if (options[i].empty()) {
memo_feasible_.emplace(key, false);
return false;
}
}
std::vector<int> order(n);
for (int i = 0; i < n; ++i) {
order[i] = i;
}
std::sort(order.begin(), order.end(), [&](int a, int b) {
return options[a].size() < options[b].size();
});
std::vector<char> used(m, 0);
std::vector<Interval> assigned(n);
bool ok = false;
std::function<void(int)> dfs = [&](int pos) {
if (ok) {
return;
}
if (pos == n) {
int hole = -1;
for (int k = 0; k < m; ++k) {
if (!used[k]) {
hole = k;
break;
}
}
if (hole < 0) {
return;
}
std::vector<Interval> child = assigned;
child.push_back({bins[hole].first, bins[hole].second});
std::sort(child.begin(), child.end(), interval_less);
if (feasible_state(child)) {
ok = true;
}
return;
}
const int i = order[pos];
for (const auto& op : options[i]) {
if (used[op.bin]) {
continue;
}
used[op.bin] = 1;
assigned[i] = {op.l, op.u};
dfs(pos + 1);
used[op.bin] = 0;
if (ok) {
return;
}
}
};
dfs(0);
memo_feasible_.emplace(key, ok);
return ok;
}
};
static i64 brute_min(int target) {
const int d = lcm_upto(target);
std::function<i64(const std::vector<Interval>&)> dfs = [&](const std::vector<Interval>& intervals) -> i64 {
const int n = static_cast<int>(intervals.size());
if (n == target) {
i64 sum = 0;
for (const auto& in : intervals) {
sum += in.l;
}
return sum;
}
const int m = n + 1;
std::vector<std::pair<int, int>> bins(m);
for (int k = 0; k < m; ++k) {
bins[k] = {k * d / m, (k + 1) * d / m};
}
std::vector<std::vector<Option>> options(n);
for (int i = 0; i < n; ++i) {
for (int k = 0; k < m; ++k) {
const int nl = std::max(intervals[i].l, bins[k].first);
const int nu = std::min(intervals[i].u, bins[k].second);
if (nl < nu) {
options[i].push_back({k, nl, nu});
}
}
if (options[i].empty()) {
return (1LL << 60);
}
}
std::vector<char> used(m, 0);
std::vector<Interval> assigned(n);
i64 best = (1LL << 60);
std::function<void(int)> assign = [&](int idx) {
if (idx == n) {
int hole = -1;
for (int k = 0; k < m; ++k) {
if (!used[k]) {
hole = k;
break;
}
}
if (hole < 0) {
return;
}
std::vector<Interval> child = assigned;
child.push_back({bins[hole].first, bins[hole].second});
std::sort(child.begin(), child.end(), interval_less);
best = std::min(best, dfs(child));
return;
}
for (const auto& op : options[idx]) {
if (used[op.bin]) {
continue;
}
used[op.bin] = 1;
assigned[idx] = {op.l, op.u};
assign(idx + 1);
used[op.bin] = 0;
}
};
assign(0);
return best;
};
std::vector<Interval> init{{0, d}};
return dfs(init);
}
static std::string to_string_i128(i128 x) {
if (x == 0) {
return "0";
}
std::string s;
while (x > 0) {
const int digit = static_cast<int>(x % 10);
s.push_back(static_cast<char>('0' + digit));
x /= 10;
}
std::reverse(s.begin(), s.end());
return s;
}
static std::string format_rounded_12(i64 numerator, i64 denominator) {
static constexpr i128 SCALE = 1'000'000'000'000LL;
const i128 num = static_cast<i128>(numerator);
const i128 den = static_cast<i128>(denominator);
const i128 rounded = (num * SCALE * 2 + den) / (den * 2);
const i128 integer_part = rounded / SCALE;
const i128 frac_part = rounded % SCALE;
std::string frac = to_string_i128(frac_part);
if (frac.size() < 12) {
frac = std::string(12 - frac.size(), '0') + frac;
}
return to_string_i128(integer_part) + "." + frac;
}
int main() {
{
Solver check4(4);
const i64 f4 = check4.solve_min();
assert(2 * f4 == 3LL * check4.denom());
}
{
Solver fast6(6);
const i64 dp6 = fast6.solve_min();
const i64 brute6 = brute_min(6);
assert(dp6 == brute6);
}
{
Solver feasible17(17);
assert(feasible17.can_choose_all());
Solver feasible18(18);
assert(!feasible18.can_choose_all());
}
Solver solver17(17);
const i64 num = solver17.solve_min();
std::cout << format_rounded_12(num, solver17.denom()) << '\n';
return 0;
}
Python
import math
from functools import lru_cache
def interval_less(a, b):
if a[0] != b[0]:
return a[0] < b[0]
return a[1] < b[1]
def lcm_upto(n):
d = 1
for i in range(1, n + 1):
d = math.lcm(d, i)
return d
class Solver:
def __init__(self, target):
self.target = target
self.d = lcm_upto(target)
self.memo_min = {}
self.memo_feasible = {}
def pack(self, intervals):
return tuple((in_l, in_u) for in_l, in_u in intervals)
def solve_min_state(self, intervals):
key = self.pack(intervals)
if key in self.memo_min:
return self.memo_min[key]
n = len(intervals)
if n == self.target:
s = sum(in_l for in_l, _ in intervals)
self.memo_min[key] = s
return s
m = n + 1
bins = [(k * self.d // m, (k + 1) * self.d // m) for k in range(m)]
options = [[] for _ in range(n)]
for i in range(n):
for k in range(m):
nl = max(intervals[i][0], bins[k][0])
nu = min(intervals[i][1], bins[k][1])
if nl < nu:
options[i].append((k, nl, nu))
if not options[i]:
inf = 1 << 60
self.memo_min[key] = inf
return inf
order = list(range(n))
order.sort(key=lambda i: len(options[i]))
used = [False] * m
assigned = [(0, 0)] * n
best = [1 << 60]
def dfs(pos):
if pos == n:
hole = -1
for k in range(m):
if not used[k]:
hole = k
break
if hole < 0:
return
child = list(assigned)
child.append((bins[hole][0], bins[hole][1]))
child.sort(key=lambda x: (x[0], x[1]))
cand = self.solve_min_state(child)
if cand < best[0]:
best[0] = cand
return
i = order[pos]
for op_bin, op_l, op_u in options[i]:
if used[op_bin]:
continue
used[op_bin] = True
assigned[i] = (op_l, op_u)
dfs(pos + 1)
used[op_bin] = False
dfs(0)
self.memo_min[key] = best[0]
return best[0]
def solve_min(self):
init = [(0, self.d)]
return self.solve_min_state(init)
def feasible_state(self, intervals):
key = self.pack(intervals)
if key in self.memo_feasible:
return self.memo_feasible[key]
n = len(intervals)
if n == self.target:
self.memo_feasible[key] = True
return True
m = n + 1
bins = [(k * self.d // m, (k + 1) * self.d // m) for k in range(m)]
options = [[] for _ in range(n)]
for i in range(n):
for k in range(m):
nl = max(intervals[i][0], bins[k][0])
nu = min(intervals[i][1], bins[k][1])
if nl < nu:
options[i].append((k, nl, nu))
if not options[i]:
self.memo_feasible[key] = False
return False
order = list(range(n))
order.sort(key=lambda i: len(options[i]))
used = [False] * m
assigned = [(0, 0)] * n
ok = [False]
def dfs(pos):
if ok[0]:
return
if pos == n:
hole = -1
for k in range(m):
if not used[k]:
hole = k
break
if hole < 0:
return
child = list(assigned)
child.append((bins[hole][0], bins[hole][1]))
child.sort(key=lambda x: (x[0], x[1]))
if self.feasible_state(child):
ok[0] = True
return
i = order[pos]
for op_bin, op_l, op_u in options[i]:
if used[op_bin]:
continue
used[op_bin] = True
assigned[i] = (op_l, op_u)
dfs(pos + 1)
used[op_bin] = False
if ok[0]:
return
dfs(0)
self.memo_feasible[key] = ok[0]
return ok[0]
def can_choose_all(self):
init = [(0, self.d)]
return self.feasible_state(init)
def format_rounded_12(num, den):
scale = 1000000000000
rounded = (num * scale * 2 + den) // (den * 2)
integer_part = rounded // scale
frac_part = rounded % scale
frac_str = str(frac_part).zfill(12)
return f"{integer_part}.{frac_str}"
def solve():
solver = Solver(17)
num = solver.solve_min()
return format_rounded_12(num, solver.d)
if __name__ == "__main__":
print(solve())
Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
public class Euler794 {
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
static long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
static int lcmUpto(int n) {
long d = 1;
for (int i = 1; i <= n; ++i) {
d = lcm(d, i);
}
return (int) d;
}
static class Interval implements Comparable<Interval> {
int l, u;
Interval(int l, int u) {
this.l = l;
this.u = u;
}
@Override
public int compareTo(Interval other) {
if (this.l != other.l) {
return Integer.compare(this.l, other.l);
}
return Integer.compare(this.u, other.u);
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Interval interval = (Interval) o;
return l == interval.l && u == interval.u;
}
@Override
public int hashCode() {
return 31 * l + u;
}
}
static class Option {
int bin, l, u;
Option(int bin, int l, int u) {
this.bin = bin;
this.l = l;
this.u = u;
}
}
static class Solver {
int target;
int d;
HashMap<ArrayList<Interval>, Long> memoMin;
HashMap<ArrayList<Interval>, Boolean> memoFeasible;
Solver(int target) {
this.target = target;
this.d = lcmUpto(target);
this.memoMin = new HashMap<>();
this.memoFeasible = new HashMap<>();
}
long solveMin() {
ArrayList<Interval> init = new ArrayList<>();
init.add(new Interval(0, d));
return solveMinState(init);
}
boolean canChooseAll() {
ArrayList<Interval> init = new ArrayList<>();
init.add(new Interval(0, d));
return feasibleState(init);
}
long solveMinState(ArrayList<Interval> intervals) {
if (memoMin.containsKey(intervals)) {
return memoMin.get(intervals);
}
int n = intervals.size();
if (n == target) {
long sum = 0;
for (Interval in : intervals) {
sum += in.l;
}
memoMin.put(new ArrayList<>(intervals), sum);
return sum;
}
int m = n + 1;
int[][] bins = new int[m][2];
for (int k = 0; k < m; ++k) {
bins[k][0] = k * d / m;
bins[k][1] = (k + 1) * d / m;
}
ArrayList<ArrayList<Option>> options = new ArrayList<>(n);
for (int i = 0; i < n; ++i) {
ArrayList<Option> ops = new ArrayList<>();
for (int k = 0; k < m; ++k) {
int nl = Math.max(intervals.get(i).l, bins[k][0]);
int nu = Math.min(intervals.get(i).u, bins[k][1]);
if (nl < nu) {
ops.add(new Option(k, nl, nu));
}
}
if (ops.isEmpty()) {
long INF = 1L << 60;
memoMin.put(new ArrayList<>(intervals), INF);
return INF;
}
options.add(ops);
}
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++)
order[i] = i;
Arrays.sort(order, Comparator.comparingInt(a -> options.get(a).size()));
boolean[] used = new boolean[m];
Interval[] assigned = new Interval[n];
long[] best = { 1L << 60 };
dfsMin(0, n, m, order, options, used, assigned, bins, best);
memoMin.put(new ArrayList<>(intervals), best[0]);
return best[0];
}
void dfsMin(int pos, int n, int m, Integer[] order, ArrayList<ArrayList<Option>> options,
boolean[] used, Interval[] assigned, int[][] bins, long[] best) {
if (pos == n) {
int hole = -1;
for (int k = 0; k < m; ++k) {
if (!used[k]) {
hole = k;
break;
}
}
if (hole < 0)
return;
ArrayList<Interval> child = new ArrayList<>(Arrays.asList(assigned));
child.add(new Interval(bins[hole][0], bins[hole][1]));
Collections.sort(child);
long cand = solveMinState(child);
if (cand < best[0]) {
best[0] = cand;
}
return;
}
int i = order[pos];
for (Option op : options.get(i)) {
if (used[op.bin])
continue;
used[op.bin] = true;
assigned[i] = new Interval(op.l, op.u);
dfsMin(pos + 1, n, m, order, options, used, assigned, bins, best);
used[op.bin] = false;
}
}
boolean feasibleState(ArrayList<Interval> intervals) {
if (memoFeasible.containsKey(intervals)) {
return memoFeasible.get(intervals);
}
int n = intervals.size();
if (n == target) {
memoFeasible.put(new ArrayList<>(intervals), true);
return true;
}
int m = n + 1;
int[][] bins = new int[m][2];
for (int k = 0; k < m; ++k) {
bins[k][0] = k * d / m;
bins[k][1] = (k + 1) * d / m;
}
ArrayList<ArrayList<Option>> options = new ArrayList<>(n);
for (int i = 0; i < n; ++i) {
ArrayList<Option> ops = new ArrayList<>();
for (int k = 0; k < m; ++k) {
int nl = Math.max(intervals.get(i).l, bins[k][0]);
int nu = Math.min(intervals.get(i).u, bins[k][1]);
if (nl < nu) {
ops.add(new Option(k, nl, nu));
}
}
if (ops.isEmpty()) {
memoFeasible.put(new ArrayList<>(intervals), false);
return false;
}
options.add(ops);
}
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++)
order[i] = i;
Arrays.sort(order, Comparator.comparingInt(a -> options.get(a).size()));
boolean[] used = new boolean[m];
Interval[] assigned = new Interval[n];
boolean[] ok = { false };
dfsFeasible(0, n, m, order, options, used, assigned, bins, ok);
memoFeasible.put(new ArrayList<>(intervals), ok[0]);
return ok[0];
}
void dfsFeasible(int pos, int n, int m, Integer[] order, ArrayList<ArrayList<Option>> options,
boolean[] used, Interval[] assigned, int[][] bins, boolean[] ok) {
if (ok[0])
return;
if (pos == n) {
int hole = -1;
for (int k = 0; k < m; ++k) {
if (!used[k]) {
hole = k;
break;
}
}
if (hole < 0)
return;
ArrayList<Interval> child = new ArrayList<>(Arrays.asList(assigned));
child.add(new Interval(bins[hole][0], bins[hole][1]));
Collections.sort(child);
if (feasibleState(child)) {
ok[0] = true;
}
return;
}
int i = order[pos];
for (Option op : options.get(i)) {
if (used[op.bin])
continue;
used[op.bin] = true;
assigned[i] = new Interval(op.l, op.u);
dfsFeasible(pos + 1, n, m, order, options, used, assigned, bins, ok);
used[op.bin] = false;
if (ok[0])
return;
}
}
}
static String formatRounded12(long numerator, int denominator) {
BigInteger SCALE = BigInteger.valueOf(1000000000000L);
BigInteger num = BigInteger.valueOf(numerator);
BigInteger den = BigInteger.valueOf(denominator);
BigInteger rounded = num.multiply(SCALE).multiply(BigInteger.TWO).add(den)
.divide(den.multiply(BigInteger.TWO));
BigInteger integerPart = rounded.divide(SCALE);
BigInteger fracPart = rounded.remainder(SCALE);
String frac = fracPart.toString();
while (frac.length() < 12) {
frac = "0" + frac;
}
return integerPart.toString() + "." + frac;
}
public static String solve() {
Solver solver17 = new Solver(17);
long num = solver17.solveMin();
return formatRounded12(num, solver17.d);
}
public static void main(String[] args) {
System.out.println(solve());
}
}