Gợi ý PTIT Summer Round 2

  • Published on
    27-Dec-2015

  • View
    248

  • Download
    0

Embed Size (px)

Transcript

  • Mt vi gi PTIT Summer round 2

    Bi A: Tm s. Gi s n = k1*(k1 + 1)/2 + k2*(k2+1)/2 v 1

  • Cch th hai: s dng thut ton KMP.

    Trong thut ton KMP, hm next[i] = j s cho ta bit S[1 .. j] = S[i j+1 .. i].

    Bi E: Tp hp. Mt bi ton sinh thng thng. Gii hn k nh (k

  • Vi im P(0, b) bt k nm trn trc Oy, ta lun tm c aL sao cho ng thng y = aL+b

    chia a gic bn tri thnh hai hnh bng nhau. Tm aL bng cch s dng cht nh phn cho n

    khi din tch 2 phn b ct bi ng thng l bng nhau. Tng t cho vi aR.

    Ta cn tm im P sao cho 2 ng thng ny trng nhau, tc aL = aR.

    Khi b tng (im P dch ln trn), aL tng. Vi hnh bn phi, khi b tng th aR gim. Xt hm s

    a(b) = aL(b) aR(b) l mt hm s ng bin theo b. Khi b tin ra dng v cng, aL(b) aR(b)

    > 0, khi b tin ti m v cng, aL(b) aR(b) < 0. Do , phng trnh a(b) = 0 lun c nghim

    v l duy nht. Da vo tnh cht ng bin ca hm a(b), ta s cht nh phn tm b.

    Thut ton nh sau:

    lowB = -infi, highB = infi, midB;

    while(lowB aR) highB = midB;

    }