# Gợi ý PTIT Summer Round 2

• Published on
27-Dec-2015

• View
248

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;

}