2008年 日本情報オリンピック春合宿OJから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#fraction - 分数 (Fraction)
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day3_22.pdf
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #fraction - 分数 (Fraction) https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day3_22.pdf 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int m,k; cin>>m>>k; map<pair<int,int>,pair<int,int>> mp; pair<int,int> pii={0,1}; mp[pii]={1,1}; for(int i=0;i<k;i++){ while(1){ auto a=mp[pii]; if(pii.second+a.second>m){ break; } pair<int,int> mid={pii.first+a.first,pii.second+a.second}; mp[pii]=mid; mp[mid]=a; } pii=mp[pii]; if(pii.first==1 && pii.second==1){ cout<<-1<<endl; return 0; } } cout<<pii.first<<" "<<pii.second<<endl; return 0; }