2017年の院試合E題守望者の脱出

目次:
2017年院試合A題Neptune'Pudding
2017年院試合B題N個数求和
2017年院試合C題treat
2017年の院試合D問題の簡単な暗号化
2017年の院試合E題守望者の脱出
2017年院試合F題数独ゲーム
2017年院試合G題忠誠
2017年院試合H問題最大異和
タイトル:
Description:悪魔ハンターのユディアンは野心的で、彼女は暗夜の精霊を裏切って、海底に深く隠れているナガ族を率いて反乱を企んでいる.見張りはユディアンとの戦いで包囲殺され、荒れ果てた島に閉じ込められた.見張り人を殺すために、ユディアンはこの荒島に呪いをかけ始め、この島はすぐに沈む.その時になると、島のすべての人が遭難します.見張り人のランニングスピードは17 m/sで、このようなスピードでは島から逃げられない.幸いなことに、守望者は点滅法術を持ち、1 s以内に60 m移動できるが、点滅法術を使うたびに魔法値10点を消費する.守望者の魔法値回復速度は4時/sで、その場で休憩している場合にのみ回復します.今まで见守ってきた魔法の初期値M、彼がいた初期位置と岛の出口の间の距离S、岛が沈没した时间T.あなたの任務は、見張り人が最短時間で島を脱出する方法を計算し、脱出できない場合は、見張り人が残りの時間で歩ける最も遠い距離を出力するプログラムを書くことです.注意:見張り人はランニング、点滅または休憩活動はいずれも秒(s)単位であり、各活動の持続時間は正数秒である.距離の単位はメートル(m)です.Input:最初の行は1つの整数tで、tグループのデータを表し、次のt行で、各行はスペースで区切られた3つの非負の整数M、S、Tを含む.Output:データのセットごとに2行出力し、1行目の文字列「Yes」または「No」(大文字と小文字を区別).つまり、見張り人が荒島から脱出できるかどうか.2行目には整数が含まれている.1行目「Yes」(大文字と小文字を区別)は見張り人が荒島から脱出する最短時間を表し、1行目「No」(大文字と小文字を区別)は見張り人が歩ける最遠距離を表す.SampleInput:139200 4 SampleOutput:No 197
スレッド:

#include 
#include 

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	int m, s, t, times;
	cin>>times;
	while(times--){
		cin >> m >> s >> t;
		int m_n=m, s_n=0, t_n=0;
		while (t_n < t&&s_n < s){
			if (m_n >= 10)
				m_n -= 10, s_n += 60,++t_n;
			else if (m_n>=6){
				if (s - s_n <= 17||t-t_n==1)
					++t_n, s_n += 17;
				else
					m_n -= 6, s_n += 60, t_n += 2;
			}else if (m_n >= 2){
				if (t - t_n <= 2)
					s_n += 17, ++t_n;
				else if (s - s_n <= 34)
					++t_n, s_n += 17;
				else
					m_n -= 2, s_n += 60, t_n += 3;
			}else{
				if (t - t_n <= 6)
					s_n += 17, ++t_n;
				else if (s - s_n <= 102)
					++t_n, s_n += 17;
				else
					t_n += 7, s_n += 120;
			}
		}
		cout << ((s_n >= s) ? ("Yes") : ("No")) << endl << ((s_n >= s) ? t_n : s_n)<<endl;
	}
	return 0;
}

問題はm,s,tの範囲を書いていないので、3つの数がintの範囲内の任意の数であることを考えています.つまり、私が提出したのはO(1)のアルゴリズムで、原理はO(1)の時間内に問題を2つのサブ問題に変換することであり、この2つのパラメータはいずれも小さな定数より小さい.この方法は、POJ 1915 Knight Movesの方法と同じである.私のコード:

#include
using namespace std;

int time2(int m,int s)
{
	if(s<=0)return 0;
	if(m>=10)return time2(m-10,s-60)+1;
	int k=time2(m+4,s)+1;
	if(k>(s+16)/17)k=(s+16)/17;	
	return k;
}
int time(int m,int s)
{
	int k=m/10;
	m-=k*10;
	if(s<=k*60)return (s+59)/60;
	if(k)return time(m,s-k*60)+k;
	k=s/120-1;
	if(k>0)return time(m,s-k*120)+k*7;
	return time2(m,s);
}

int len(int m,int t)
{
	if(t==0)return 0;
	int k=m/10;
	m-=k*10;
	if(t<k)return t*60;
	if(k)return len(m,t-k)+k*60;
	k=t/7-1;
	if(k>0)return len(m,t-k*7)+k*120;
	k=len(m+4,t-1);
	if(k<t*17)k=t*17;
	return k;
}

int main()
{
	int T,m,s,t,ans;
	cin>>T;
	while(T--)
	{
		cin>>m>>s>>t;
		ans=time(m,s);
		if(ans<=t)cout<<"Yes
"<<ans<<endl;
		else cout<<"No
"<<len(m,t)<<endl;
	}
	return 0;
}

実は関数timeとtime 2は分離する必要はありませんが、デッドサイクルをよりよく防ぐために、やはり別々に書いたので、直接time 2のコードをtimeの中でtime 2を呼び出す場所にコピーしても正しいはずです.