from __future__ import print_function import numpy as np from pprint import pprint from ortools.linear_solver import pywraplp def mip_ortools(a): solver = pywraplp.Solver('mip_program', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) infinity = solver.infinity() x = [solver.IntVar(0.0, infinity, f'x_{i}') for i in range(5)] for i in range(5): solver.Add(sum(x[(i+j)%5] for j in range(3)) <= a[i]) solver.Maximize(sum(x)) status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print('OPTIMAL') print('Solution:') print('Objective value =', solver.Objective().Value()) for i in range(5): print(f'x_{i} =', x[i].solution_value()) else: print('The problem does not have an optimal solution.') print(list(map(lambda w: w.solution_value(), x))) return int(solver.Objective().Value()) import pulp import sys def mip_pulp(a): problem = pulp.LpProblem("prob", pulp.LpMaximize) x = [pulp.LpVariable(f'x_{i}', 0, sys.maxsize, pulp.LpInteger) for i in range(5)] problem += (sum(x), "Objective") for i in range(5): problem += (sum(x[(i+j)%5] for j in range(3)) <= a[i], f'Constraint_{i}') print(problem) res = problem.solve() print(f"Status = {pulp.LpStatus[res]}") print(f"Objective = {pulp.value(problem.objective)}") for i in range(5): print(f'x_{i} = {pulp.value(x[i])}') return pulp.value(problem.objective) from scipy.optimize import linprog def lp(a): c = np.ones(5) A = np.array([[1 if (j-i+5)%5 <= 2 else 0 for j in range(5)] for i in range(5)]) b = np.array(a) pprint(c) print(A) pprint(b) res = linprog(-c, A, b) print(res) return int(-res.fun + 0.001) if __name__ == '__main__': # input: # 1048577 1048579 1048576 1048577 1048577 a = list(map(int, input().split())) while True: # a = np.random.randint(0, 4, 5) + 2**20 ans_mip_ortools = mip_ortools(a) ans_mip_pulp = mip_pulp(a) ans_lp = lp(a) eps = 1e-1 if np.abs(ans_mip_ortools - ans_lp) > eps or np.abs(ans_mip_pulp - ans_lp) > eps: print("MIP != LP") pprint(ans_mip_ortools) # 1747627 pprint(ans_mip_pulp) # 1747628 pprint(ans_lp) # 1747628 pprint(a) exit() # else: # print("OK") break