#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
int N;
vector<int> A;
typedef int vert;
typedef int cost;
typedef pair<cost,vert> edge;
typedef vector<edge> edges;
vector<int> dijkstra_like( vert S, int T, int I )
{
set<int> ans;
for(int i=1; i<=I; ++i) ans.insert(i);
priority_queue< edge, edges, greater<edge> > Q;
Q.push( edge(0, S) );
// set<vert> vis;
vector<bool> vis(1<<24);
while( !Q.empty() )
{
edge ce=Q.top(); Q.pop();
int t = ce.first;
vert v = ce.second;
if( vis[v] )
continue;
vis[v]=true;
int sw = v&511;
int a[] = {(v>>9)&31, (v>>14)&31, (v>>19)&31};
ans.erase(sw);
for(int i=0; i<(1<<N+1); ++i)
{
int sw2 = sw;
int a2[] = {a[0], a[1], a[2]};
int nzMin = 9999;
for(int j=0; j<N; ++j) {
if( (i&(1<<j)) )
a2[j] = A[j]-a2[j];
if( a2[j] )
nzMin = min(nzMin, a2[j]);
}
if( (i&(1<<N)) ) sw2 = 0;
if( nzMin==9999 ) continue;
if( t+nzMin > T )
continue;
for(int j=0; j<N; ++j)
if( a2[j] )
a2[j] -= nzMin;
sw2 += nzMin;
vert u = sw2 | (a2[0]<<9) | (a2[1]<<14) | (a2[2]<<19);
if( !vis[u] ) {
Q.push( edge(t+nzMin,u) );
}
}
}
return vector<int>(ans.begin(), ans.end());
}
class SandTimers
{
public:
vector <int> badIntervals(vector <int> timers, int maxInterval, int maxTime)
{
N = timers.size();
A = timers;
return dijkstra_like( vert(), maxTime, maxInterval );
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const vector <int> &Expected, const vector <int> &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } return 0;}
template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
int timers_[] = { 5, 7 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 10;
int maxTime = 10;
int RetVal_[] = {1, 6, 8 };
vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<1>) {
int timers_[] = { 2, 10, 20 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 30;
int maxTime = 40;
int RetVal_[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 };
vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<2>) {
int timers_[] = { 2, 5, 9 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 360;
int maxTime = 360;
vector <int> RetVal;
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<3>) {
int timers_[] = { 4 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 23;
int maxTime = 47;
int RetVal_[] = {1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23 };
vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<4>) {
int timers_[] = { 20, 13 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 30;
int maxTime = 30;
int RetVal_[] = {1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 28, 29, 30 };
vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<5>) {
int timers_[] = { 20, 17, 13 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 25;
int maxTime = 30;
int RetVal_[] = {18, 19 };
vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
int Test_(Case_<6>) {
int timers_[] = { 20, 20, 19 };
vector <int> timers(timers_, timers_+sizeof(timers_)/sizeof(*timers_));
int maxInterval = 360;
int maxTime = 360;
vector <int> RetVal;
return verify_case(RetVal, SandTimers().badIntervals(timers, maxInterval, maxTime)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE