Hotels

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf=1e9;

int r[111];
int m[111];

int has(map<int, int> d, int t){
	for (auto it=d.begin();it!=d.end();it++){
		int lp=(*it).F+(t-(*it).S-1);
		
		auto nit=it;
		nit++;
		
		int up=(*nit).F-(t-(*nit).S-1);
		
		lp=max(lp, (*it).F-1);
		up=min(up, (*nit).F+1);
		if (lp+1<up){
			return lp+1;
		}
	}
	return inf;
}

void solve(){
	int f,e;
	cin>>f>>e;
	map<int, vector<int> > es;
	map<int, int> d;
	for (int i=0;i<e;i++){
		cin>>r[i]>>m[i];
		for (int j=0;;j++){
			int x=j*m[i]+r[i];
			if (x>=f) break;
			es[x].push_back(i);
		}
	}
	priority_queue<pair<int, int> > dij;
	dij.push({0, 0});
	while (!dij.empty()){
		auto t=dij.top();
		dij.pop();
		int x=t.S;
		int dd=-t.F;
		assert(x==0||es.count(x));
		if (d.count(x)) continue;
		d[x]=dd;
		for (int ev:es[x]){
			if (x+m[ev]<f){
				dij.push({-dd, x+m[ev]});
			}
			if (x-m[ev]>=0){
				dij.push({-dd, x-m[ev]});
			}
		}
		auto it=es.upper_bound(x);
		if (it!=es.end()){
			int nx=(*it).F;
			assert(nx>x);
			dij.push({-(dd+(nx-x)), nx});
		}
		if (it!=es.begin()) {
			it--;
			if (it!=es.begin()){
				it--;
				int nx=(*it).F;
				assert(nx<x);
				dij.push({-(dd+(x-nx)), nx});
			}
		}
	}
	if (d.count(f-1)==0){
		d[f-1]=f-1;
	}
	int mi=0;
	int ma=f;
	pair<int, int> ans={0, 0};
	while (mi<=ma){
		int mid=(mi+ma)/2;
		int h=has(d, mid);
		if (h<inf){
			ans={mid, h};
			mi=mid+1;
		}
		else{
			ma=mid-1;
		}
	}
	cout<<ans.F<<" "<<ans.S<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED