【アルゴリズム問題】yukicoder no.14 最小公倍数ソート (level ☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.14 最小公倍数ソート (level ☆☆)

2014-08-15 00:08
    最小公倍数を習ったばかりのLarryは、最小公倍数ソートというのを思いついた。

    ここで「最小公倍数ソート」とは、
    N個の整数(重複を含む)が与えられ、それぞれai(1<=i<=N)とする。
    a1を固定し、a2〜aNをそれぞれa1に対して最小公倍数を取り、最小公倍数が小さい順に並べ変えるソートのことであるとする。
    (最小公倍数の最小が複数ある場合は、元の数が少ない方が優先される)

    Larryは、
    この時出来た配列を新たにa1..aNの名前をつけなおして操作を続ける。次にa2を固定し(a1も固定したまま)、a3〜aNを「最小公倍数ソート」していく。
    次にa3を固定し...と続けていった時にaNまで行った時になる数列を求めてください。

    多分、うまい方法というより実装問題のはずです。

    入力
    N
    a1 a2 ..ai... aN

    1行目は整数の数を表すN(1<=N<=1000)が与えれる。
    2行目は各整数の値ai(1<=i<=N, 1<=ai<=10000)を半角スペース区切りとして与えられる。


    追加点 -Wanted-
    1<=N<=10000
    を満たす条件が回答できれば
    +40pt
    (僕が解けませんでした)

    ideoneでTLEしなければよいです。(5秒以内)

    出力
    a1からaNまで続けていった時の数列を半角スペース区切りで出力してください。

    sample1
    5
    1 2 3 4 5

    ans1
    1 2 4 3 5

    まず1番目の1を固定し、それ以降で最小公倍数ソートすると
    1 2 3 4 5
    次に2番目の2を固定し、それ以降で最小公倍数ソートすると
    1 2 4 3 5
    次に3番目の3を固定し、・・を続けると答えのようになる。

    sample2
    5
    4 8 1 2 4

    ans2
    4 1 2 4 8

    同じ数が出てくる可能性もあります、ソート時に同じ最小公倍数だったら、元の数が少ない方を優先します。

    sample3
    10
    9 9 3 7 5 9 1 5 2 1

    ans3
    9 1 1 2 3 9 9 5 5 7

    q

    https://gist.githubusercontent.com/yuki2006/6b77349719ffbbe157ce/raw/fb249bbe86780ea47a7c3a1ea54efb4b1caa1599/yukicoder14.txt

    q - large

    https://gist.githubusercontent.com/yuki2006/6b77349719ffbbe157ce/raw/35cfe4520aa3971bbb1955b8ead6076bb871fdc2/yukicoder14_large.txt




    1st.くろとんさん C++
    http://ideone.com/BU3HUO
    (largeクリア)
    2nd.なおさん C++
    http://ideone.com/fLgw44
    (largeクリア)

    3rd. scacheさん Java
    http://ideone.com/dSVQjm

    4th.ヨザさん python
    http://ideone.com/eqSaUA

    5th.ヒロソフさん C
    http://ideone.com/hukaXy

    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。