yukicoder No.643 Two Operations No.2
問題
No.643 Two Operations No.2 - yukicoder
解説
この解説は多分悪い例として見ていただくのが良いと思います。
考察のできる人は、公式解説通りに考えられるのでしょう。でも僕にはそんな思いつきはありませんでした。ならマシンパワーに頼るしかない、ということで、全探索解でACしました。これも競技プログラミングです。
操作1,2を様々な順番で実行して行って、x==yとなるような最小手順を探してみます。
問題はこの手順をどれくらいの深さまで見るかですが、適当に手元で実行すると、30回では時間がかかりすぎたので、20回にしました。
ans=10000と初期化しておいて、x==yになればctとの最小値を取ります。最終的にans==10000であれば、x==yにならなかったので-1を出力です。
今回は偶然答えが3以下になるような問題だったので、全探索が通って嬉しいですね。
#include <iostream> using namespace std; int ans=100000; void dfs(int x,int y,int ct){ //cout<<x<<y<<endl; if(ct>20){ //20回操作を試して見たら終了 return; } if(x==y){ ans=min(ans,ct); return ; } dfs(y,x,ct+1); //操作1 dfs(x+y,x-y,ct+1); //操作2 return; } int main (){ int x,y; cin>>x>>y; dfs(x,y,0); if(ans!=100000)cout<<ans<<endl; else cout<<-1<<endl; return 0; }