首先有一個 \(O(n^2)\) 的 DP：設(shè) \(f_{i,j}\) 表示前 \(i\) 分鐘，當(dāng)前朝上的面煎了 \(j\) 分鐘的最小翻面次數(shù)。于是有方程：

其中第二種轉(zhuǎn)移是翻面的，即僅當(dāng) \(\exist k,i\in[l_k,r_k]\) 時可以轉(zhuǎn)移。

那么如果 \(i\) 不在可以翻面的區(qū)間里，直接移過來就行了。于是只考慮可翻面的區(qū)間。設(shè) \(f_{i,j}\) 表示前 \(r_i\) 分鐘，朝上的面煎了 \(j\) 分鐘的最小翻面次數(shù)。

考慮當(dāng)在同一區(qū)間內(nèi)如果翻面次數(shù) \(\ge 2\)，那一不如只翻 \(1\) 次或 \(2\) 次。于是只需考慮這兩個轉(zhuǎn)移。

• 翻 \(1\) 次

  枚舉當(dāng)前朝下的面在這個區(qū)間內(nèi)煎的時間 \(k\)。當(dāng)前朝下的面顯然總共煎了 \(r_i-j\) 分鐘，那么在這個區(qū)間開始前它就煎了 \(r_i-j-k\) 分鐘。而這個區(qū)間前這一面正好就是朝上的。于是 \(f_{i,j}=\min(f_{i-1,r_i-j-k})\)。

• 翻 \(2\) 次

  枚舉當(dāng)前朝上的面在這個區(qū)間內(nèi)煎的時間 \(k\)。在這個區(qū)間前這一面也是朝上的，煎了 \(j-k\) 分鐘。于是 \(f_{i,j}=min(f_{i-1,j-k})\)。

用單調(diào)隊列優(yōu)化這兩個轉(zhuǎn)移即可。時間復(fù)雜度 \(O(nk)\)。

#include<bits/stdc++.h>
#define ll long long
#define il inline

using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,duil[maxn];
int f[105][maxn];
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
//	cout<<cplx::usdmem();
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	memset(f[0],0x3f,sizeof f[0]);
	f[0][0]=0;
	for(int i=1,l,r,hd,tl;i<=m;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=f[i-1][j];
		}
		cin>>l>>r;
		hd=1,tl=0;
		for(int j=0;j<=min(r,n);j++){
			while(hd<=tl&&f[i-1][duil[tl]]>f[i-1][j]){
				tl--;
			}
			duil[++tl]=j;
			while(hd<=tl&&duil[hd]<j-(r-l)){
				hd++;
			}
			f[i][j]=min(f[i][j],f[i-1][duil[hd]]+2);
		}
		hd=1,tl=0;
		for(int j=r;~j;j--){
			while(hd<=tl&&f[i-1][duil[tl]]>f[i-1][r-j]){
				tl--;
			}
			duil[++tl]=r-j;
			while(hd<=tl&&duil[hd]<l-j){
				hd++;
			}
			f[i][j]=min(f[i][j],f[i-1][duil[hd]]+1);
		}
	}
//	for(int i=0;i<=m;i++){
//		for(int j=0;j<=n;j++){
//			cout<<f[i][j]<<" ";
//		}
//		puts("");
//	}
	printf(f[m][n]>=inf?"Hungry":"Full\n%d",f[m][n]);
	return 0;
}
}
int main(){return asbt::main();}
/*
10 1
0 20
*/