← 返回题目列表

AtCoder · joisc2008_fraction

fraction. 分数

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

分数 (Fraction) - 原题 PDF 第 1 页
原题PDF第3页
可复制的 PDF 提取文本
Fraction: 分数


input ファイル“fraction.in”
output 標準出力
ソースファイルfraction.c/fraction.cpp
時間制限0.5 秒/ データ



  JOI のM 理事長はIOI2008 で日本の選手が活躍できるように毎日ピラミッドの写真にお祈

りをしていた.ある晩彼の夢にスフィンクスが現われてこういった.

   我に金塊を捧げよ,さすれば願いをかなえよう,ただし,金塊の重さは1kg より軽

  く,分母がM 以下の分数のうち小さいものから数えてk 番目の分数になるように

   せよ. これより軽くても重くても願いはかなえられないであろう.

 とても多忙なM 理事長は代表候補であるあなた達にこの問題を解くように指示をした.


Input. 入力ファイルfraction.in は1 行のファイルであり,分母の上限M と求める分数の

順位を表わすk が空白を区切として書かれている.ただし,M ≦30, 000, k ≦200, 000 である.


Output. 出力は,標準出力に行うこと.出力は1 行からなり, 1 つまたは2 つの整数を出力す

る.求める分数を既約分数で表したときの分子と分母を空白で区切って書くこと.ただし,解

となる分数が存在しないときは−1 を書くこと.


例1
 fraction.in 標準出力
 6 8          2 3

例2
 fraction.in 標準出力
 6 12         -1
                                          {1 1 1 1 2 1 3 2 3 4 5 }
 上の2つの例において, 分母が6 以下の分数を小さい順に並べると  6, 5, 4, 3, 5, 2, 5, 3, 4, 5, 6
の11 個である.

注意この問題では,採点用データの組ごとに採点する.組に含まれる全てのデータについて正

しく動作したときその組を正解とする.





                            分数–1/1