PTIT Summer Round 4

  • Published on
    05-Oct-2015

  • View
    17

  • Download
    0

Embed Size (px)

DESCRIPTION

ACM 2014

Transcript

<ul><li><p>PTIT Summer 2014 Round 4 </p><p>Problem A: Nam chm Time limit: 1s </p><p>T ang hc v t tnh ca nam chm. Cu bit rng nam chm c 2 cc m v dng, cng cc </p><p>th y nhau, khc cc th ht nhau. </p><p>Mt ln cu sp ln lt cc nam chm theo chiu dc, nhim v ca bn l xem c bao nhiu </p><p>khi nam chm nm ri nhau. </p><p>Nam chm c biu din biu 2 k t 0 v 1. 0 l cc m, 1 l cc dng. </p><p>Input </p><p>Dng u tin l s nguyn n (1 </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem B: Cp s cng Time limit: 1s </p><p>Bn c cho mt dy s c n phn t. Nhim v ca bn l tm tt c cc s x tha mn: x xut </p><p>hin trong dy s cho v cc v tr ca x trong dy to thnh mt cp s cng. </p><p>Input </p><p>Dng u tin l s nguyn n (1 </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem C: S tuyt p Time limit: 1s </p><p>To c mt s thch c bit khi rt thch cc s c to bi 2 ch s a, b, cu gi cc s nh </p><p>vy l s p. c bit hn na, cc s p c tng cc ch s l mt s p, cu gi l s tuyt </p><p>p. </p><p>V d: To thch cc s 1 v 3, s 11, 311 l s p cn 12 th khng. </p><p>S 111 l s tuyt p, 11 th khng phi. </p><p>Gi To mun bit c bao nhiu s tuyt p c n ch s, tt nhin ch s 0 khng ng u. </p><p>Kt qu c ly d cho (10 ^ 9 + 7). </p><p>Input </p><p>Dng duy nht c 3 s nguyn a, b, n ( 1 </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem D: Chui c bit Time limit: 1s </p><p>T rt thch chi vi cc chui s. Mt chui s a[] c T gi l c bit nu: </p><p>+ a[1] = q vi q l 1 s nguyn no . </p><p>+ a[i] = a[i-1] + ((-1) ^ (i +1) )* p, vi p l 1 s nguyn no . </p><p>Gi T ang c mt chui b, cu cn tm chui con di nht ca b l chui c bit. </p><p>Mt chui con ca b l chui c to bi b khi gi nguyn th t v xa i mt s phn t no </p><p> hoc khng xa mt phn t no c. </p><p>Cc bn gip T nh! </p><p>Input </p><p>Dng u tin l s nguyn n( 1</p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem E: Truy vn Time limit: 2s </p><p>T thch vic tm chui s c bit, To th li thch x l vi cc truy vn trn mng. Cu ang </p><p>c mt dy s v phi tr li cc cu hi, trn mt on ca con gm cc phn t lin tip c </p><p>bao nhiu s m s ln xut hin ca n bng chnh n. </p><p>Cc bn cng chi vi To cho vui nh! </p><p>Input </p><p>Dng u tin gm 2 s nguyn n, m (1 </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem F: Xp hng. Time limit: 1s </p><p>Bob c ng ch giao nhim v lm bo v qun bar. Qun bar mi khai trng v m ca </p><p>min ph, v vy rt ng khch ti. Do , mi ngi phi xp hng ln lt vo trong qun </p><p>bar, v nhim v ca Bob l duy tr trt t ng li. </p><p> duy tr cn bng gii tnh trong qun bar, ng ch mong mun s chnh lch gia nam v </p><p>n khng vt qu X (X </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Gii thch test 2: </p><p>Ti v tr ngi th 5, nu ngi ny vo, s lm mt cn bng gii tnh, v vy ngi ng </p><p>th 2 (W) s c vo trc. Hng i lc ny cn li MWMMMWWMW, trong qun bar hin ti c 3 </p><p>nam v 2 n. </p><p>Lt th 6 v th 7, hai ngi tip vo bnh thng, hng i cn li MMMWWMW, trong qun bar </p><p>hin ti c 4 nam v 3 n. </p><p>Lt th 8, ngi tip (M) vo bnh thng, trong qun bar c 5 nam v 3 n. Sau lc ny </p><p>khng th cho ai vo c na, Bob s ng ca qun bar li. </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem G: Vn chuyn bnh piza Time limit: 2s. </p><p>T v To c nhn vo lm thm ti mt ca hng bnh piza. Nhim v ca T l ng gi, </p><p>xp bnh vo hp cn thn, cn nhim v ca To l vn chuyn bnh theo a ch yu cu ca </p><p>khch hng. </p><p>Nh bp lm bnh lin tc, mi ln lm mt chic bnh c kch thc khc nhau. T phi qun l </p><p>mt hng i nhng chic bnh piza. T lun sp xp danh sch nhng chic bnh ch c </p><p>mang i ny theo th t ng knh tng dn. Mi ln c yu cu ca khch hng, T s mang ra </p><p>chic bnh c kch thc bng phn t trung v trong tp hp tt c nhng chic bnh m T hin </p><p>ti ang qun l. C ngha l nu hin ti T qun l c ci bnh, nu c l, T s mang i chic </p><p>bnh c kch thc ln th (c+1)/2; trong trng hp c chn, T s ly i chic bnh c kch </p><p>thc ln th c/2+1. </p><p>Ca hng lun ghi li nhng hot ng ca mnh, gm mc thi gian mt chic bnh c ra l </p><p>v mc thi gian c mt chic bnh c chuyn i. Vi cch lm k d ca T, ca hng ny kh </p><p>au u trong vic lit k nhng chic bnh no c xut xng. Cho bit cc mc s kin </p><p>xy ra theo thi gian, cc bn hy hy gip ca hng ny lp ra danh sch nhng chic bnh </p><p>c bn i. </p><p>Input: </p><p>C 1 b test, gm nhiu dng, c th hin theo trnh t thi gian. </p><p>Mi dng c th l mt s nguyn n, hoc mt k t #. S nguyn dng n th hin ti thi </p><p>im , mt chic bnh piza c ng knh l n c lm xong v chuyn sang khu ng gi. </p><p>K t # th hin ti thi im c yu cu ca khch hng, T s mang cho To mt chic </p><p>bnh piza To vn chuyn ti a ch yu cu ca khch hng. </p><p>Output: </p><p>In ra kch thc cc chic bnh piza m To vn chuyn theo ng th t. </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Sample test: </p><p>Test 1 Test 2 </p><p>Input: </p><p> 1 </p><p>2 </p><p>3 </p><p>4 </p><p># </p><p># </p><p># </p><p># </p><p>Output: 3 </p><p>2 </p><p>4 </p><p>1 </p><p>Input: </p><p> 1 </p><p># </p><p>2 </p><p># </p><p>3 </p><p># </p><p>4 </p><p># </p><p>Output: 1 </p><p>2 </p><p>3 </p><p>4 </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem H: Hnh trnh du lch Time limit: 2s </p><p>Bob ang trong k ngh h ti b bin. Tht khng may, cc khch sn gn b bin ht phng </p><p>v anh phi trong trung tm thnh ph. Anh thu hn mt chic xe my c th vi vu khp </p><p>thnh ph bin ny. m nay, a im m anh mun ti khng phi l bi bin nh thng </p><p>ngy, m l thp truyn hnh cao nht ca thnh ph. </p><p>H thng giao thng trong thnh ph kh phc tp. C N nt giao thng v M con ng mt </p><p>chiu ni gia cc im giao thng. Khch sn ca Bob nm gn nt giao thng th nht, cn </p><p>thp truyn hnh ngay gn nt giao thng th N. i ng bui ti nn Bob rt mun trnh cc </p><p>khc cua, anh ch mun gi ga v phng u trn ng. V vy, Bob mun chn cho mnh mt </p><p>hnh trnh sao cho gc cua ln nht trong hnh trnh l nh nht. Tuy nhin, anh cng khng </p><p>mun qung ng i qu di, v xe ca anh ch xng i c ti a khong cch bng D. </p><p>Cc bn hy gip Bob chn ra hnh trnh ti u, v tnh gc cua ln nht trong hnh trnh ti u </p><p>ny. </p><p>Input : </p><p>Dng u tin gm 3 s nguyn N, M, D ln lt l s nt giao thng, s ng mt chiu v </p><p>khong cch ln nht m Bob mong mun. (N </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Sample test </p><p>Test 1 Test 2 Test 3 </p><p>Input: </p><p> 5 6 500 </p><p>-100 0 </p><p>-100 100 </p><p>0 200 </p><p>100 100 </p><p>100 0 </p><p>1 2 </p><p>1 3 </p><p>2 3 </p><p>3 4 </p><p>3 5 </p><p>4 5 </p><p>Output: 90.00000000 </p><p>Input: </p><p> 5 6 450 </p><p>-100 0 </p><p>-100 100 </p><p>0 200 </p><p>100 100 </p><p>100 0 </p><p>1 2 </p><p>1 3 </p><p>2 3 </p><p>3 4 </p><p>3 5 </p><p>4 5 </p><p>Output: 126.86989765 </p><p>Input: 5 12 440 </p><p>-100 0 </p><p>-100 100 </p><p>0 200 </p><p>100 100 </p><p>100 0 </p><p>1 2 </p><p>1 3 </p><p>3 1 </p><p>2 3 </p><p>3 2 </p><p>3 4 </p><p>4 3 </p><p>3 5 </p><p>5 3 </p><p>4 5 </p><p>5 4 </p><p>5 1 </p><p>Output: Impossible </p><p>Gii thch test 1: Hnh trnh ti u l 1-2-3-4-5. Gc cua ln nht l ti nt 3 bng 180-90 = 90 </p><p>. </p><p>Gii thch test 2: Hnh trnh ti u l 1-3-5. Gc cua ln nht ti nt 3. </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem I: Chia phn Time limit: 1s. </p><p>Sau gi hc, T cng cc bn r nhau i n xc xch. Mi ngi cng nhau gp tin. C tt c M </p><p>ngi nhng s tin m T cng cc bn c ch mua c N ci xc xch. </p><p> cho cng bng th T s chia u N chic xc xch cho tt c mi ngi. Vi mt con dao </p><p>trong tay, cc bn hy gip T tnh xem T cn ct t nht bao nhiu pht? </p><p>Input </p><p>Gm 2 s nguyn n v m (n, m </p></li><li><p>PTIT Summer 2014 Round 4 </p><p>Problem J: Nui cy vi khun Time litmit: 2s </p><p>Phng th nghim XYZ thc hin nui cy mt loi vi khun trn mt bng vung kch thc </p><p> vi cc dng v cc ct nh s t 1 ti . S c th vi khun trong mt vung ban u </p><p>l 0 v ngi ta c th tin hnh cy thm mt s c th vi khun trong mi . </p><p>C hai loi yu cu: </p><p> S : Cy thm c th vi khun vo ( ) ( ); </p><p> Ch th Q : Yu cu cho bit tng s c th vi khun trong cc ( ) nm </p><p>trong phm vi , . </p><p>Cho bit mt dy m yu cu thc hin tun t, hy tr li tt c cc yu cu loi Q. </p><p>Input </p><p> Dng 1 cha hai s nguyn dng ; </p><p> dng tip theo, mi dng cha mt yu cu theo th t thc hin. </p><p>Output: </p><p>ng vi mi ch th Q, hy in ra s lng c th vi khun tng ng tnh c. </p><p>Sample test: </p><p>Input: </p><p> 4 7 </p><p>S 2 2 2 </p><p>S 4 3 3 </p><p>Q 2 2 4 4 </p><p>S 1 2 5 </p><p>S 4 3 6 </p><p>Q 1 1 4 4 </p><p>Q 1 1 2 2 </p><p>Output: </p><p> 5 </p><p>16 </p><p>7 </p></li></ul>