我是菜鸟，从零开始刷题。这道题搞了两天，做的基本思想是找下一个差值可能变化的点，提交了3次，第一次因为没有为许多重复行进行优化，还是一行一行进行判断，导致超时了，第二次是一个小bug，多亏看到别人的测试数据才查出问题。最后内存200多K，时间16MS，判断下一个拐点的代码写得很乱，有空了再优化一下

#include <iostream>
using namespace std;

int width;
int rows;
int value[1000];
int start[1001];
int pairCount;

//get value from position using binary search
int getVal(int pos) {
	if (pos < 0 || pos > start[pairCount]) {
		return 0;
	}
	int begin = 0;
	int end = pairCount;
	int i;
	while(1) {
		i = (begin + end) / 2;
		if (start[i] <= pos && start[i+1] > pos) {
			return value[i];
		}
		else if (start[i] > pos) {
			end = i - 1;
		}
		else {
			begin = i +1;
		}
	}
}

//get pair index from position
int getIndex(int pos) {
	if (pos < 0 || pos > start[pairCount]) {
		return 0;
	}
	int begin = 0;
	int end = pairCount;
	int i;
	while(1) {
		i = (begin + end) / 2;
		if (start[i] <= pos && start[i+1] > pos) {
			return i;
		}
		else if (start[i] > pos) {
			end = i - 1;
		}
		else {
			begin = i +1;
		}
	}
}

//next checkpoint, before which difference remains the same
int nextCheck(int pos) {
	int y = pos / width;
	int x = pos % width;
	int ret = pos + (width - pos % width);//next row
	//jump multiple rows
	if (pos > width && y < rows - 2 && getIndex((y + 3) * width - 1) == getIndex(pos - width - 1)) {
		return (start[getIndex(pos) + 1] / width - 2) * width;
	}
	//next pair
	ret = ret > start[getIndex(pos) + 1] ? start[getIndex(pos) + 1] - 1 : ret;
	ret = pos == start[getIndex(pos)] ? pos + 1 : ret;
	//up left
	if (y > 0 && x > 0) {
		ret = ret > start[getIndex(pos - width - 1) + 1] + width - 1 ? 
			start[getIndex(pos - width - 1) + 1] + width - 1 : ret;
	}
	//up
	else if(y > 0) {
		ret = ret > start[getIndex(pos - width) + 1] + width - 1 ? 
			start[getIndex(pos - width) + 1] + width - 1 : ret;
	}
	//down-left
	if (y < rows - 1 && x > 0) {
		ret = ret > start[getIndex(pos + width - 1) + 1] - width - 1 ? 
			start[getIndex(pos + width - 1) + 1] - width - 1 : ret;
	}
	//down
	else if(y < rows - 1) {
		ret = ret > start[getIndex(pos + width) + 1] - width - 1 ? 
			start[getIndex(pos + width) + 1] - width - 1 : ret;
	}
	//make sure next point >= pos+1
	ret = ret <= pos ? pos + 1 : ret;
	return ret;
}

int diff(int pos) {
	int y = pos / width;
	int x = pos % width;
	int ret = 0;
	//right
	if (x < width - 1) {
		ret = abs(getVal(pos) - getVal(pos+1));
	}
	//left
	if (x > 0) {
		ret = ret >= abs(getVal(pos) - getVal(pos-1)) ? ret : abs(getVal(pos) - getVal(pos-1));
	}
	//down
	if (y < rows - 1) {
		ret = ret >= abs(getVal(pos) - getVal(pos+width)) ? ret : abs(getVal(pos) - getVal(pos+width));
	}
	//up
	if (y > 0) {
		ret = ret >= abs(getVal(pos) - getVal(pos-width)) ? ret : abs(getVal(pos) - getVal(pos-width));
	}
	//down-right
	if (x < width-1 && y < rows - 1) {
		ret = ret >= abs(getVal(pos) - getVal(pos+width+1)) ? ret : abs(getVal(pos) - getVal(pos+width+1));
	}
	//down-left
	if (x > 0 && y < rows - 1) {
		ret = ret >= abs(getVal(pos) - getVal(pos+width-1)) ? ret : abs(getVal(pos) - getVal(pos+width-1));
	}
	//up-right
	if (x < width-1 && y > 0) {
		ret = ret >= abs(getVal(pos) - getVal(pos-width+1)) ? ret : abs(getVal(pos) - getVal(pos-width+1));
	}
	//up-left
	if (x > 0 && y > 0) {
		ret = ret >= abs(getVal(pos) - getVal(pos-width-1)) ? ret : abs(getVal(pos) - getVal(pos-width-1));
	}
	return ret;
}


int main() {
	
	int length;	

	while (1) {
		cin >> width;
		if (width <= 0) {
			break;
		}
		pairCount = 0;
		start[0] = 0;
		//get pair input
		while (1) {
			int val;
			cin >> val >> length;
			if (val == 0 && length == 0) {
				if (start[pairCount] % width == 0) {
					break;
				}
				else {
					cerr << "Not complete" << endl;
					return 1;
				}
			}
			value[pairCount] = val;
			start[pairCount+1] = start[pairCount] + length;
			pairCount++;			
		}
		rows = start[pairCount] / width;
		//process pairs
		int curIndex = 0;
		int curPos = 0;
		int curLength = 1;
		int curDiff = diff(curPos);
		int nextPos;
		int nextDiff;
		cout << width << endl;
		//stop condition: current position == total length
		while (1) {
			nextPos = nextCheck(curPos);
			if (nextPos >= start[pairCount]) {
				curLength += start[pairCount] -1 - curPos;
				cout << curDiff << " " << curLength << endl;
				break;
			}
			nextDiff = diff(nextPos);
			if (nextDiff == curDiff) {
				curLength += nextPos - curPos;
			}
			else {
				cout << curDiff << " " << curLength + nextPos - curPos -1 << endl;
				curDiff = nextDiff;
				curLength = 1;
			}
			curPos = nextPos;
		}
		cout << "0 0" << endl;
	}
	cout << 0 << endl;
}