fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. /* The solution planes 7 weeks in advanced.
  5.  * Because the first pill day determines which days pills are taken, there can
  6.  * never be more than 6 distinct weeks(at least one day punched), and the 7th
  7.  * is needed only to ensure a cycle can be detected.
  8.  * 
  9.  * The following functions operate on an array days over 7 weeks.
  10.  * First eliminate all punctured days so we don't have to check the letters.
  11.  * Second compute the next pill repeatedly until the range is finished.
  12.  * Third compare weeks (7 day sections) by pill sequence to find a cycle.
  13.  * Four print weeks one line at a time.
  14.  */
  15. const int needed_days = 49;
  16. int* D = new int[49];
  17.  
  18. //eliminates (set to -1) every instance of a punctured weekday
  19. void eliminate(int i){
  20.     do{
  21.         D[i]=-1;
  22.         i+=7;
  23.     }while(i<needed_days);
  24. }
  25.  
  26. //find next pill day from a given index and step, returns new index
  27. int next(int i, int p){
  28.     while(D[i+p]==-1) p--;
  29.     if(i+p>=0) D[i+p]=1; //when P=2 and Sundays punched, i+p=-1 once
  30.     return i+p;
  31. }
  32.  
  33. //compare two weeks by week-index.
  34. int equals(int i, int j){
  35.     i*=7; j*=7;
  36.     for(int k=7; k--;)
  37.         if(D[i+k]!=D[j+k]) return 0;
  38.     return 1;
  39. }
  40.  
  41. //print week by week-index, include arrow if arrow is 1.
  42. void print(int i, int arrow){
  43.     if(arrow) cout<<">";
  44.     else      cout<<" ";
  45.     i*=7;
  46.     for(int k=0; k<7; k++)
  47.         if(D[i+k]==1) cout<<" X";
  48.         else          cout<<" ·";
  49.     cout<<"\n";
  50. }
  51.  
  52.  
  53. int main() {
  54.     //Parse input P and eliminate punctured weekdays.
  55.     int P; char C;
  56.     cin>>P;
  57.     while(cin>>C){
  58.         switch(C){
  59.             case 'N': eliminate(0); break;
  60.             case 'M': eliminate(1); break;
  61.             case 'T': eliminate(2); break;
  62.             case 'W': eliminate(3); break;
  63.             case 'R': eliminate(4); break;
  64.             case 'F': eliminate(5); break;
  65.             case 'S': eliminate(6); break;
  66.         }
  67.     }
  68.     //plan out all days
  69.     int i=-2; //last friday
  70.     while(i<needed_days){
  71.         i = next(i,P);
  72.     }
  73.     //compare weeks to find cycles
  74.     int first = -1; int last = 0;
  75.     while(first==-1){
  76.         last++;
  77.         for(int i=last; i--;){
  78.             if(equals(last,i))
  79.             first=i;
  80.         }
  81.     }
  82.     //print weeks
  83.     for(int i=0; i<last; i++)
  84.         print(i,i==first);
  85. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
6NTFS
stdout
copy 
  · · · · X · ·
> · · · X · · ·
  · X · · X · ·
https://ideone.com/FgU4Yl
Periodic Pillbox Problem
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!