Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < iostream >
#include < vector >
#include < set >
#include < algorithm >

using namespace std;

int w,h,total;
vector<pair<int,int> > v,ans;
set<int> note;

int calc_color(int x){
  if(x<0 || x >= total) return -1;
  for(int i=0;i<v.size();i++){
    if(x < v[i].second) return v[i].first;
    x -= v[i].second;
  }
  return -1;
}

#define abs(x) ((x)<0?(-(x)):(x))

void calc(){
  ans.clear();
  ans.push_back(make_pair(0,0));
  int bef_pos = -1;
  for(set<int>::iterator p = note.begin();p!=note.end();p++){
    int t = *p;
    int cur_color = calc_color(t);
    int around[8];
    int cur_diff = 0;
    for(int i=0;i<8;i++) around[i] = -1;
    if(t % w != 0){
      around[0] = calc_color(t-w-1);
      around[1] = calc_color(t  -1);
      around[2] = calc_color(t+w-1);
    }
    around[3] = calc_color(t-w );
    around[4] = calc_color(t+w );
    if(t % w != w-1){
      around[5] = calc_color(t-w+1);
      around[6] = calc_color(t  +1);
      around[7] = calc_color(t+w+1);
    }
    for(int i=0;i<8;i++){
      if(around[i]==-1) continue;
      cur_diff = max(cur_diff,abs(around[i]-cur_color));
    }
    if(ans[ans.size()-1].first == cur_diff){
      ans[ans.size()-1].second += (t-bef_pos);
    }else{
      ans.push_back(make_pair(cur_diff,t-bef_pos));
    }
    bef_pos = t;
  }
}

int main(void){
  while(true){
    cin >> w;
    cout << w << endl;
    if(w==0) break;
    v.clear();
    total = 0;
    while(true){
      int a,b;
      cin >> a >> b;
      if(a==0 && b == 0) break;
      v.push_back(make_pair(a,b));
      total += b;
    }
    h = total/w;
    int cur_pos = 0;
    note.clear();
    for(int i=0;i<v.size();i++){
      for(int j=-w;j<=w;j+=w)
        for(int k=-2;k<=1;k++)
          note.insert(cur_pos + j + k);
      cur_pos += v[i].second;
    }
    note.insert(total-w);
    note.insert(total-w-1);
    note.insert(total  -1);
    set<int>::iterator sp = note.begin();
    while(*sp < 0){
      note.erase(sp);
      sp = note.begin();
    }
    sp = note.end();sp--;
    while(*sp >= total){
      note.erase(sp);
      sp = note.end();sp--;
    }
    calc();
    
    for(int i=0;i<ans.size();i++)
      if(ans[i].second != 0)
        cout << ans[i].first << " "<<ans[i].second << endl;
    cout << "0 0"<<endl;
  }
  
  return 0;
}