Choose Weekly Training Days
Autumn Tournament (2012)
Submission name: timetable.cpp
Problem summary
Choose a fixed nonempty set of weekdays on which training occurs every week. Sessions are held strictly after 15 September and strictly before the tournament date. The total must lie in [X,Y]. Print any valid weekday set or 0 if none exists.
Input
The weekday of 15 September; tournament day and English month name; X Y.
Output
The number of chosen weekdays followed by their names in Monday-to-Sunday order, or 0.
Constraints
Tournament date is 23 September through 20 December; 1 ≤ X ≤ Y ≤ 200.
Worked example
Original statement sample.
Input
Tuesday 8 October 9 15
Output
3 Monday Tuesday Wednesday
Solution analysis
- First count how many times each of the seven weekdays occurs strictly between the two dates. Convert the tournament to a day offset from 15 September and loop over offsets 1 through offset−1. Add each offset to the given starting weekday modulo seven.
- Every weekly schedule is one subset of the seven weekdays, so there are only 2^7−1=127 nonempty possibilities. For each mask, sum the occurrence counts of its selected weekdays. If the sum is between X and Y, output that mask’s weekdays in calendar order.
- In the sample, the open interval runs from 16 September through 7 October. Monday and Tuesday occur three times each and Wednesday four times. Selecting those days gives ten sessions, within [9,15]. Different valid schedules are equally acceptable.
Why it works
A selected weekday contributes exactly its counted occurrences in the permitted interval. Enumeration includes every possible fixed weekly schedule, and its count test is exactly the required total-session condition. Thus every printed schedule is valid, and failure of all masks proves impossibility.
Watch out. Exclude both endpoint dates, not their weekdays throughout the season. September and November have 30 days. The output count is the number of selected weekdays, not the number of sessions. Constructive outputs need not match the sample schedule.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
const array<string,7>names={
"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
string opening;
string month;
int day;
int minimum;
int maximum;
cin>>opening>>day>>month>>minimum>>maximum;
int firstWeekday=0;
while(names[firstWeekday]!=opening){
firstWeekday++;
}
int distance=day-15;
if(month=="October"){
distance=15+day;
}
else if(month=="November"){
distance=46+day;
}
else if(month=="December"){
distance=76+day;
}
array<int,7>occurrences{};
// Neither the opening date nor the tournament date is a training day.
for(int offset=1;offset<distance;offset++){
occurrences[(firstWeekday+offset)%7]++;
}
for(int mask=1;mask<(1<<7);mask++){
int total=0;
int chosen=0;
for(int weekday=0;weekday<7;weekday++){
if((mask&(1<<weekday))!=0){
total+=occurrences[weekday];
chosen++;
}
}
if(minimum<=total&&total<=maximum){
cout<<chosen<<'\n';
for(int weekday=0;weekday<7;weekday++){
if((mask&(1<<weekday))!=0){
cout<<names[weekday]<<'\n';
}
}
return 0;
}
}
cout<<0<<'\n';
}