PTIT Summer Round 5

  • Published on
    17-Jan-2016

  • View
    23

  • Download
    0

Embed Size (px)

DESCRIPTION

ACM 2014

Transcript

<ul><li><p>PTIT Summer 2014 Round 5 </p><p>Problem A: Chic v may mn Time limit: 1s </p><p>Mt s may mn l s c to ra bi 2 s 4 v 7. V d, 47, 44 l s may mn, cn 13 th khng </p><p>phi. </p><p>To l mt ngi rt thch cc chic v xe la, mi chic v u c s ghi trn v tt c cc s </p><p>u c chn ch s. To gi mt chic v l chic v may mn nu s ghi trn v l s may </p><p>mn v tng cc ch s na u bng tng cc ch s na cui. </p><p>Cc bn xem h To chic v m cu c l chic v may mn khng nh. </p><p>Input </p><p>Dng u tin l s nguyn dng n (2 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem B: Sp xp Time limit: 1s </p><p>Bn c mt mng a[] gm n phn t, nh s t 1 ti n, mi phn t c gi tr -1 hoc 1. </p><p>Bn cn phi tr li m truy vn. Truy vn th i dng L[i], R[i] (1 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem C: S tuyt p Time limit: 1s </p><p>T ang hc v c chung ln nht, cu bit cch tm c chung ln nht ca 2 s nhng c v </p><p> l chuyn n gin v gy nhm chn, thy vy, c gio giao cho T mt nhim v khc phc </p><p>tp hn mt cht, tm c chung ln nht ca 2 s nhng gi tr ca c chung ln nht nm </p><p>trong mt khong cho trc. </p><p>Input </p><p>Dng u tin gm 2 s nguyn a, b (1 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem D: Mua bo Time limit: 1s </p><p>To, T i mua v nh mt t bo c. To bt cht ngha ra mt tr, cu ct tiu ca t </p><p>bo ra (mt xu gm cc ch ci thng lin tip) xa mt s k t c t m cu mong </p><p>mun. Tuy nhin khng phi lc no cng c c iu ny, cu nh phi mua thm cc t bo </p><p>nh vy ghp cc tiu li lin tip vi nhau ri li xa th xem c c khng. </p><p>Cu lin T th tm xem cn t nht bao nhiu t bo c c t m To mun. T gii </p><p>c th To i mua, khng th T phi l ngi i mua, m khng bit cn phi mua bao </p><p>nhiu t th T cng phi mt nhiu tin c lng mua tha ra. T mt b ph ri, cc bn </p><p>tnh gip cho T nh! </p><p>Input </p><p>Dng u tin l tiu ca t bo. C di khng qu 10^4. </p><p>Dng th hai l t m To mun c. C di khng qu 10^6. </p><p>Cc xu khc rng. </p><p>Output </p><p>Nu c th ghp cc t bo c t to mun in ra s t bo cn thit. </p><p>Nu khng th ghp c, in ra -1. </p><p>Example </p><p>Test 1 Test 2 </p><p>Input: </p><p> abc </p><p>xyz </p><p>Output: -1 </p><p>Input: </p><p> abcd </p><p>dabc </p><p>Output: 2 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem E: Chia ht Time limit: 1s </p><p>Bn c cho n truy vn dng x[i], y[i]. </p><p>Vi mi truy vn bn cn tr li cho cu hi c bao nhiu s l c s ca x[i], m khng l c </p><p>s ca bt k cc s x[i y[i]], x[i y[i] + 1], .. x[i-1]. </p><p>Nu y[i] = 0 bn ch cn a ra bao nhiu s l c s ca x[i]. </p><p>Input </p><p>Dng u tin l s nguyn n(1 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem F: Trang tr bn c Time limit: 1s </p><p>T ang mun lm mt ci bn c vua mi cho ring mnh. Sau khi c anh trai lm cho mt </p><p>tm g phng v nhn, T bt u sn mu cho bn c ca mnh. Bn c ca T gm c RxC , </p><p>mi c chiu cao bng A v chiu rng bng B, chng c t mu en, trng xen k. </p><p>Nhim v ca cc bn l hy m t bn c ca T. </p><p>Input : </p><p>Dng u tin gm 2 s nguyn R v C. </p><p>Dng th 2 gm 2 s nguyn A v B (A, B, R, C </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem G: Trm kim sot sn bay Time limit: 1s. </p><p>Ti sn bay Ni Bi, mt hnh khch gm M ngi chun b tham gia chuyn bay. V s lng </p><p>khch qu ln nn im kim sot ca sn bay c tng ln thnh N im. Ti im kim </p><p>sot th i, cn mt T_i (s) c th kim tra xong mt ngi (tnh c thi gian i b t a im </p><p>xp hng ti im kim tra ny). </p><p>Cc hnh khch sp xp theo mt hng i. Ln lt tng ngi vo mt. Hnh khch u </p><p>hng i c php i vo mt trm kim sot no nu nh trm kim sot ang trng. </p><p>Tuy nhin, ngi cng c quyn ng ch i mt trm kim sot khc trng i ti </p><p>trm , v c th gim thiu chi ph thi gian cho c on (xem v d 1). </p><p>Cc bn hy tnh ton xem thi gian nh nht c th on hnh khch kim tra xong hnh l </p><p>l bao nhiu? </p><p>Input: </p><p>Dng u tin gm 2 s nguyn N v M, ln lt l s quy gi v s v khch (N </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem H: H thng in Time limit: 1s </p><p>Khu vc nh T b mt in di ngy khc phc s c ng dy 500 kV. Cc k s bo rng </p><p>khu vc ny c khi mt in n c thng tri. V vy, cc h dn y s dng my pht </p><p>in. Khng phi h gia nh no cng c, v vy, h kt ni vi nhau to thnh h thng </p><p>li in ring. R rng nhng gia nh no cng xa ngun pht th in s cng yu. </p><p>T mun bit xem trong khu vc ca mnh, gia nh no in s yu nht? </p><p> yu ca in ti h gia nh X c tnh bng 0 nu h l h pht in, nu h X c kt </p><p>ni in vi h Y m h Y gn my pht hn, yu ti h X = yu ti h Y + 1. Nu h X </p><p>khng c in th c yu bng v cng (infinity). </p><p>Input : </p><p>Dng u tin gm 3 s nguyn N, M, H ln lt l s h gia nh, M l s h gia nh c my </p><p>pht in, H l s kt ni 2 chiu. (N, M </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem I: n ng Time limit: 1s. </p><p>Mt bui ti n, To r T sang nh chi. Tuy nhin, T rt s ma nn ch dm i nhng on </p><p>ng c nh sng. Nh T ta (L, 0) cn nh To ta (R, 0). Trn ng i c n chic </p><p>n cao p, tuy nhin, nhng chic n ny ch c gc chiu l a_i. H thng n cao p ny </p><p>c nh To u t kinh ph, v vy, To c th d dng iu khin chng bng mt h thng </p><p>iu khin t xa. </p><p>T yu cu To hy iu chnh h thng n sao cho on ng m T i n nh To lun c </p><p>chiu sng. </p><p>Nhim v ca cc bn l hy tnh xem qung ng xa nht m T c th i c l bao nhiu? </p><p>Input: </p><p>Dng u tin gm 3 s nguyn n, L, R (1 </p></li><li><p>PTIT Summer 2014 Round 5 </p><p>Problem J: Truy vn Time litmit: 2s </p><p>Cho mt dy s ( ) v cc loi truy vn sau: </p><p> 1 : ( ) gn cc phn t th n th trong dy bng ; </p><p> 2 : ( ) cng phn t th cho , th cho ,... , th cho ( ) ; </p><p> 3 : chn vo trc phn t th ca dy hin thi; </p><p> 4 : ( ) Tnh tng t phn t th n phn t th . </p><p>Input </p><p> Dng u ghi hai s nguyn v s truy vn . </p><p> Dng tip theo m t dy s. Mi s khng vt qu . </p><p> dng tip theo m t cc truy vn theo nh dng nh trong bi. Trong mi truy vn, </p><p> . </p><p>Output: </p><p>In ra kt qu cho tng truy vn loi 4. </p><p>Sample test: </p><p>Input: </p><p> 5 5 </p><p>1 2 3 4 5 </p><p>1 5 5 0 </p><p>4 4 5 </p><p>4 5 5 </p><p>2 1 5 1 </p><p>4 1 5 </p><p>Output: </p><p> 4 </p><p>0 </p><p>25 </p></li></ul>