Gợi ý PTIT Summer Round 4

  • Published on
    03-Jun-2018

  • View
    217

  • Download
    0

Embed Size (px)

Transcript

  • 8/12/2019 Gi PTIT Summer Round 4

    1/2

    Mt vi gi PTIT Summer Round 4

    Bi A: Nam chm

    Kt qubng sln c 2 nam chm lin tip y nhau cng thm 1.

    Bi B: Cp scngVi mi slu li tp hp cc vtr xut hin ca n ri kim tra dy sny c l cp scnghay khng?

    Bi C: Stuyt p1 stuyt p ta chcn quan tm xem tng ca cc sc l sp khng, vy ta chcn bit cbao nhiu sa v bao nhiu sb xem c thto ra stuyt p khng, ri tnh cc hon vcthc sinh ra.

    Vi i chsa, v (n-i) chsb, scc stuyt p c to ra bng!

    !( )!

    n n

    i i n i

    .

    tnh c gi trbiu thc ny, c 2 cch nh sau:

    Cch 1: Phn tch thnh tha snguyn tv lu sm vo mng vi n!, i! v (n-i)!. Sau khigin c i th cng vic cn li chl nhn cc tha snguyn tvi nhau.

    Cch 2: Dng mod nghch o (mod inverse). S 1a c gi l mod inverse ca a modulo

    BASE nu nh 1. 1 moda a BASE . Vi iu kin gcd a, n 1 , mod inverse ca a c

    tnh bng

    ( ) 1 modna n trong ( )n l phi hm Euler ca n. Trong trng hp ny, n =

    BASE 1000000007 l mt snguyn tnn A( S) 2n B E .

    Bi D: Chui c bitC nhiu cch gii quyt, mt trong s l:

    chui c bit sc nhiu nht l 2 gi trv cc gi trny xen knhau.

    Hng gii quyt gi F[i][j] l chui c sinh ra bi si v j. j l scui ca dy. Ri rc hathc hin cho mng.

    Kt qu: max(F[i][j]) vi mi i, j.

    Bi E: Truy vnCc gi trx tha mn c sln xut hin t nht x ln nhiu nht l khong 450 s.

    Xl tch ly vi tt ccc gi trny.

  • 8/12/2019 Gi PTIT Summer Round 4

    2/2

    Bi F: Xp hngSdng mt hng i (queue) m tbi ton.

    C thlm n gin hn nh sau: vi a l chnh lch gii hn gii tnh cho php.

    FOR(i,1,n){

    if(abs(nam[i]-nu[i]) > a+1) {

    return i-2;

    }

    }

    if(abs(nam[n]-nu[n] = a+1)) return n-1;

    else return n;

    Bi G: Vn chuyn bnh pizaCu trc dliu.

    Cn duy tr 2 tp hp A v B cha cc bnh theo thtkch thc bnh tng dn. Nu slngbnh l chn th sphn tca A v B l bng nhau, nu lth A t hn B mt phn t.

    Thao tc ly bnh sl phn tu tin ca tp hp B. Mi ln bsung thm 1 phn t, cn cpnht li c2 tp hp trn sao cho duy tr ng tht.

    Bi H: Hnh trnh du lchCht nhphn + ng i ngn nht.

    Trng hp vi gc cua gii hn bng 180 m vn khng thi c, y l trng hpimpossible.

    Cht nhphn tm gc cua nhnht sao cho tn ti ng i tnt 1 ti nt N sao cho mi gccua u khng vt qu gc gii hn ny. nh du ng i bng mng 2 chiu, F[i][j] lng i ngn nht ti nh j, c nh lin trc l i.

    Bi I: Chia phnA funny problem.

    p sca bi ton bng mgcd(n, m). Phn chng minh dnh cho bn c.

    Bi J: Nui cy vi khun

    Vi gii hn n