Guard the Weakest Fortress Side
National Olympiad — Regional round (2024 season)
Submission name: krepost.cpp
Problem summary
Distribute N soldiers among the M corner towers of a polygon. A side is initially defended by the soldiers in its two endpoint towers. Maximize the minimum number defending any side. Solve two independent cases.
Input
Two lines, each containing N M.
Output
One optimum weakest-side defense count per case.
Constraints
1 ≤ N ≤ 10^16; 3 ≤ M ≤ 10^16.
Worked example
An independently prepared example for this explanation.
Input
59 9 10 4
Output
13 5
Solution analysis
- Every soldier contributes to the defense of exactly two sides. Thus the sum of all side defenses is 2N, and the weakest side cannot exceed floor(2N/M).
- This bound is attainable. For a target r, when r is even put r/2 soldiers at every tower. When r is odd alternate floor(r/2) and ceil(r/2); for an odd number of towers, place the extra high value so the closing edge joins two high towers. This uses ceil(Mr/2) soldiers.
- Set r=floor(2N/M). Then ceil(Mr/2)≤N, so the described construction fits the available soldiers; any leftovers can only help. For 59 soldiers and 9 sides, the answer is floor(118/9)=13.
Why it works
The total-defense bound proves no larger answer is possible. The alternating construction realizes every target r with ceil(Mr/2) soldiers, which suffices for the bound’s value. Therefore floor(2N/M) is optimal.
Watch out. Read exactly two cases, without an initial case count. Use 64-bit integers: N and M exceed int.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
for (int test = 0; test < 2; test++) {
long long soldiers, sides;
cin >> soldiers >> sides;
// Every soldier contributes to exactly two side defenses.
cout << 2 * soldiers / sides << '\n';
}
}