寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #fraction - 分数 (Fraction)

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;
}