• 【アルゴリズム問題】yukicoder no.30 たこやき工場 (by なおさん)(level ☆☆)

    2014-09-25 23:20


    太郎君はとある工場を建てようとしています。
    効率よく生産するためには、材料を計画的に購入しなければなりません。

    この工場では、最終的に製造したい製品を 製品番号N とし、
    製品番号1 ~ N-1 の中間素材となる製品を取り扱います。

    製品番号1 ~ N-1 の製品は、外部から購入するか
    またはこの工場で製造するかのどちらかにより手に入るものとします。
    また、最終製品Nも含め、製造することが出来る製品は、
    外部から購入せずに必ず製造するものとします。

    入力に、各製品番号(1~N)の製造方法
    (材料の製品番号・個数と、その材料から1個製造できる製品番号)
    が与えられるので、
    製品iの製造方法が複数書かれている場合は、それらすべての材料が必要である。

    最終製品Nを1個作るために、外部から購入する必要のある最小の個数を
    1~N-1番の 製品番号ごとにそれぞれ1行で出力してください。
    行の末尾には改行を出力してください。

    製品Nを製造するための製造方法は必ず与えられます。


    【入力】
    N
    M
    P1 Q1 R1
    P2 Q2 R2
    ...
    PM QM RM


    【制約】
    2 <= N <= 100 : 製品の種類数
    1 <= M <= 1500 : 製造方法の数
    1 <= Pi < N : 材料の製品番号
    1 <= Qi <= 100 : 材料の個数
    1 <= Ri <= N : 製造する製品番号

    1 <= i <= M
    i ≠ j ならば (Pi,Ri) ≠ (Pj,Rj)
    すべてのRiについて、
    Riの材料(および材料の材料、…)としてRi自身を必要とすることはありません。

    【出力】
    S_1 : 製品番号1 の購入数
    S_2 : 製品番号2 の購入数
    ...
    S_N-1 : 製品番号N-1 の購入数
    : 0 <= S_i <= 4294967295 (2^32-1), 1 <= i < N

    となるようにN-1行出力してください。

    【sample1】
    2
    1
    1 5 2

    【ans1】
    5




    ⇒ 製造方法の数は1つだけで、最終製品(番号2)を作るためには、
    中間素材(番号1)の材料が5個必要です。
    番号1は製造できないので、これを5個購入すると出力すれば正解です。


    【sample2】
    4
    3
    1 1 2
    2 3 4
    3 1 4

    【ans2】
    3
    0
    1





    ⇒ 最終製品(番号4)を作るためには、製品2が3個と、製品3が1個必要になります。
    製品2は製品1から製造できるので、最終的に 製品1が3個と製品3が1個必要となります。
    購入しない製品は0を出力する必要があります。


    【sample3】
    9
    10
    1 11 2
    7 12 8
    8 13 1
    2 14 9
    8 15 9
    8 16 4
    3 17 4
    4 18 5
    5 19 9
    2 20 4

    【ans3】
    0
    0
    5814
    0
    0
    0
    11827308
    0





    提出はこちら
    http://yukicoder.me/problems/a14e51c14f78a730
  • 広告
  • 【アルゴリズム問題】yukicoder no.29 パワーアップ (level ☆)

    2014-09-24 00:20

    Quinは、RPGをしている。
    そのRPGでは、アイテムは10種類(それぞれ番号付けされている)あり、「同じアイテム」を2つ揃えるか、「任意のアイテム」を4つ揃えるとパワーアップする仕組みがある。
    そして敵を倒したら、何かアイテムを3つもらうことができる。
    (同じアイテムがもらえることもある。)
    このとき、持てるアイテムの上限はないとする。

    N回敵を倒すと考えたとき、その時のパワーアップする最大の回数を求めてください。



    【入力】
    N
    a1 b1 c1
    a2 b2 c2
    ・・・・
    aN bN cN

    1行目に敵を倒す回数を表すN (1<=N<=100)が与えられる。
    2行目以降はi(1<=i<=N)回目で敵を倒した時のもらえる3つのアイテムの番号ai,bi,ci(1<=ai,bi,ci<=10)が半角空白区切りで与えられる。

    【出力】
    最大のパワーアップする回数を文字列で出力してください。出力の末尾には改行をいれること。

    【sample1】
    5
    1 2 3
    4 5 6
    7 8 9
    10 1 2
    3 4 5

    【ans1】
    6

    アイテム1,2,3,4,5が2つ揃ったので パワーアップを5回できる。
    さらにアイテム 6,7,8,9を使い、更にパワーアップするでき、合計6回パワーアップすることができる。

    【sample2】
    3
    1 1 1
    1 1 1
    1 1 1

    【ans2】
    4

    【sample3】

    3
    1 2 3
    5 4 1
    1 9 2

    【ans3】
    3

    回答はこちらに
    http://133.242.139.202/snowpack/yukicoder29/

  • 【アルゴリズム問題】yukicoder no.28 末尾最適化 (by くろとんさん) (level ☆☆☆☆)

    2014-09-22 00:25

    x[0] = seed

    x[n] = 1 + (x[n-1] ^ 2 + x[n-1] * 12345) % 100000009 (1<=n<=N)

    ※) %は剰余演算とする


    上の定義から作られるN+1個の要素を持つ数列xの中からK個数字を選びそれらを掛け合わせTとおく。

    TをB進数に変換した時末尾の0の数が最小となるTでは末尾の0の数はいくつになるか答えよ。


    例)

    B=18、Tが10進数で「612」ならTは18進数で「1g0」なので末尾の0の数は1個

    B=3、Tが10進数で「36」ならTは3進数で「1100」なので末尾の0の数は2個

    【Input】

    Q
    seed1 N1 K1 B1
    seed2 N2 K2 B2
    ...
    seedQ NQ KQ BQ
    ・1行目は Q(1<=Q<=1000)が与えられる。

    ・2行目からのQ行では seed(1<=seed<=100000009), N(1<=N<=10000), K(1<=K<=N+1), B(2<=B<=36) の組が与えられる。

    【Output】

    Q個の組ごとに末尾の0の数の最小を計算しそれぞれ出力せよ。ただし末尾に改行をつけること。


    【sample1】

    4
    98808561 8 6 18
    61316635 15 11 4
    37650646 100 86 20
    98630457 1000 647 2

    【ans1】

    1
    2
    6
    142


    1st. laycrs さん C++
    http://133.242.139.202/snowpack/yukicoder28/aAAqWExX

    2nd. なおさん C++
    http://133.242.139.202/snowpack/yukicoder28/ZDYEUWvf/

    3rd. scacheさん Java
    http://133.242.139.202/snowpack/yukicoder28/bIyeKa4T/