Odd Bouquets for Seven Dwarfs
National Olympiad — Municipal round (2009 season)
Submission name: princess.cpp
Problem summary
Collect 1+2+…+a flowers. Give each of seven dwarfs the same odd positive number of flowers, leaving as few flowers as possible for Snow White.
Input
The number a of meadows.
Output
Flowers per dwarf and flowers left over.
Constraints
5 ≤ a ≤ 15.
Worked example
Input and output for the worked example discussed below.
Input
7
Output
3 7
Solution analysis
- The total collected is the triangular number a(a+1)/2. If each dwarf receives x flowers, the seven bouquets use 7x flowers and leave total−7x.
- Minimizing the remainder is equivalent to maximizing x subject to x being odd and 7x≤total. Start at floor(total/7); if it is even, subtract one. The stated lower bound ensures a positive odd choice exists.
- For a=7, total=28 and floor(28/7)=4. Four is even, so each dwarf gets 3, leaving 28−21=7. For a=5, total=15, each gets 1 and 8 remain.
Why it works
Every feasible bouquet size is at most floor(total/7). This bound itself, or one less if it is even, is the largest feasible odd integer. Since the remainder decreases strictly as bouquet size increases, that choice is optimal.
Watch out. The seven bouquets must be equal and odd, not merely have an odd total. Do not distribute the leftover among only some dwarfs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
int meadows;
cin>>meadows;
int total=meadows*(meadows+1)/2;
int bouquet=total/7;
// Round down to the largest odd feasible bouquet size.
if(bouquet%2==0){
bouquet--;
}
cout<<bouquet<<' '<<total-7*bouquet<<'\n';
}