Official

B - Pizza Editorial by en_translator


For simplicity, instead of rotating the pizza, let’s consider rotating the cut (or the knife to make cuts).
After a cut is made a knife, “rotating the pizza clockwise by \(D\) degrees and making another cut” is equivalent to “rotating the direction of the knife counterclockwise by \(D\) degrees and making another cut.”
By this rephrasing, the cuts to be made can be described as follows.

  • The \(1\)-st cut is made by the knife in the direction rotated from the initial direction counterclockwise by \(0\) degrees.
  • The \(2\)-nd cut is made by the knife in the direction rotated from the initial direction counterclockwise by \(A_1\) degrees.
  • The \(3\)-nd cut is made by the knife in the direction rotated from the initial direction counterclockwise by \((A_1+A_2) \% 360\) degrees (where \(a\%b\) denotes the remainder of \(a\) divided by \(b\)).
  • The \(2\)-nd cut is made by the knife in the direction rotated from the initial direction counterclockwise by \((A_1+A_2+A_3) \% 360\) degrees.
  • \(\dots\)

Based on this procedure, find the following information: “is there a cut in the direction rotated from the initial direction counterclockwise by \(k\) degrees (where \(k\) is an integer between \(0\) (inclusive) and \(360\) (exclusive))?” This can be obtained with a loop and an array.
Then, find the size of each piece of pizza. For example, if the azimuth angle of the cuts are \(0,120,180\), then the center angle of each slice will be \(120-0=120\) degree, \(180-120=60\) degree, and \(360-180=180\) degree (note that a cut in the direction of \(0\) degree can be regarded as that of \(360\) degree too).
Of course, there is always a cut in the direction where the first cut was made (that is, in the direction rotated from the initial direction counterclockwise by \(0\) degrees). Therefore, the implementation can be reduced by taking the origin here.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<bool> fl(360,false);
  fl[0]=true;
  int p=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    p+=a;p%=360;
    fl[p]=true;
  }
  int res=0,cur=0;
  for(int i=0;i<=360;i++){
    if(fl[i%360]){
      res=max(res,cur);
      cur=0;
    }
    cur++;
  }
  cout << res << '\n';
}

posted:
last update: