Pre Acm Ptit Round 1

  • Published on
    19-Nov-2015

  • View
    41

  • Download
    10

Embed Size (px)

DESCRIPTION

ACM 2014

Transcript

<ul><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem A: Cc cp giai tha </p><p>Time limit: 1s </p><p>Axe chi mt tr chi vi Lina. </p><p>H nh ngha hm F(x) vi s x nguyn dng l tch giai tha cc ch s ca x. V d </p><p>F(135) = 1! * 3! * 5! = 720. </p><p>u tin, h chn mt s a c n ch s v c t nht mt ch s ln hn 1, c th c ch s </p><p>khng u. Sau h tm mt s nguyn dng x ln nht tha mn: </p><p>1. X khng cha ch s 0 hoc 1 </p><p>2. F(x) = F(a) </p><p>Hy gip Axe v Lina tm ra c s . </p><p>Input: </p><p>Dng u tin cha s b test T ( T &lt; 100 ). </p><p>Mi test gm mt dng cha s n v s a (1 </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem B: Rubik i siu th </p><p>Time limit: 1s </p><p>Rubik i siu th mua n mn v vo trong xe y ri mang ra quy thanh ton. Bit mt </p><p>hng th i c gi l C_i v ngi thu ngn cn thi gian T_i c th xc nhn mt hng ny. </p><p>Nhng Rubik l thnh n trm nn anh ta sp xp th t cc mt hng cho ngi thu ngn </p><p>xc nhn theo ca mnh, khi ngi thu ngn bn lm th tc l Rubik s c th n trm 1 </p><p>mn t chnh xe ca mnh v mt 1 giy. </p><p>Bn hy tnh xem s tin ti thiu m Rubik phi tr l bao nhiu? </p><p>Input: </p><p>Dng u tin cha s mt hng n (1 </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem C: Tr chi tr tu </p><p>Time limit: 5s </p><p>Tide v Kunkka thch thc nhau v mt tr chi. H vit tt c cc s nguyn dng t 1 n </p><p>n. Ti lt ca mi ngi, ngi s chn mt s nguyn trong cc s h va vit ra, nu </p><p>chn s x th cc s l ly tha (nguyn dng) ca x s khng c chn cho cc lt tip </p><p>theo. </p><p>Tt c u chi vi chin thut ti u, vy nu Tide chn trc th bn hy cho bit ai s l </p><p>ngi chin thng? </p><p>Ngi thua cuc l ngi m n lt ca mnh khng cn s no chn. </p><p>Input: </p><p>Dng u tin cha s b test T (1</p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem D: Du hnh gia cc v sao </p><p>Time limit: 1s </p><p>Sau chuyn du hnh gia cc v sao nhm Cooper tm c hnh tinh Edmunds ph hp vi </p><p>s sng thin h Blabla, anh gi thng tin v cho con ngi Ngn H qua l su. V di </p><p>chuyn sang thin h Blabla tn kh nhiu ti nguyn nn cn tp hp tt c ngi dn trn </p><p>mt trm bt k. </p><p>C n trm ang trn qu o ca n hnh tinh hay thin th khc nhau ln cn trong h mt </p><p>tri, mi hnh tinh c d_i c dn ang sinh sng, v c n-1 khng gian 5 chiu di chuyn </p><p>trc tip gia hai trm v ch c mt cch duy nht di chuyn gia hai trm bt k. Mi </p><p>khng gian nh vy ni hai trm u v v, di chuyn 1 ngi t trm ny sang trm kia cn </p><p>mt lng ti nguyn l w. </p><p>May thay cc nh khoa hc nghin cu ra mt cch chuyn ng i trn qua mt khng </p><p>gian nhiu chiu hn, vi cch vic di chuyn gia hai trm gn nh khng tn ti </p><p>nguyn, nhng c mt rc ri l s nhiu trong khng gian trn nn ch c th chuyn ti a k </p><p>khng gian c sang khng gian mi. </p><p>Cc nh lnh o ang tm mt cch di chuyn sao cho tn t ti nguyn nht, bn hy gip </p><p>h. </p><p>Input </p><p>Dng u tin cha s b test, mi b test cu trc nh sau: </p><p> Dng u tin cha hai s nguyn n v k (1 n 1000, 0 k n 1). </p><p> Dng th hai cha n s t nhin, di l s dn ang sng trn trm th i (1 d_i </p><p>100000). </p><p> n-1 dng cn li, dng th i cha ba s nguyn dng ui, vi v wi (1 u_i, v_i n, 1 </p><p> w_i 100000). </p><p>Output </p><p>In ra kt qu mi test trn mt dng. </p><p>Example </p><p>Input: Output: </p><p>1 </p><p>5 3 </p><p>8 5 1 8 7 </p><p>1 3 8 </p><p>2 3 9 </p><p>3 5 7 </p><p>3 4 8 </p><p>45 </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem E: Sn xut kem </p><p>Time limit: 1s </p><p>Nh my Blabla ang sn xut kem Bla. Kem c bm vo mt khay hnh ch nht kch </p><p>thc m x n nh ri a vo my lnh. My phun kem l mt cnh tay c hai u phun kem </p><p>t trn hai khc nhau. V hai u phun trn cng tay r bt nn cc bc di chuyn ca </p><p>chng ng b ha vi nhau, nu my th nht di chuyn theo mt vec t, th tay th hai </p><p>cng c di chuyn theo vect y. Ban u cc trn khay khng cha kem. </p><p>Tay r bt di chuyn theo quy lut sau: </p><p> C 2 my phun u t trn 2 khc nhau v u hot ng. </p><p> My phun di chuyn qua no th y c phun kem. </p><p> Tay r bt di chuyn song song vi cc cnh ca khay. </p><p> Cc my phun khng c di chuyn ra bn ngoi khay. </p><p>Blab l nhn vin k thut ca nh my Blabla, anh c giao nhim v vit chng trnh </p><p>tnh s khng c phun kem, cc bn hy gip anh y. </p><p>Input </p><p>Dng u tin cha s b test T (khng qu 150 test), T dng sau mi dng cha 1 b test </p><p>cha 6 s nguyn dng ln lt m, n, x1, y1, x2, y2. </p><p>Trong m, n ln lt l s ct v s hng ca khay, (x1, y1) l ta ca my phun th </p><p>nht (x1, y1 l v tr ct, hng), (x2, y2) l ta ca my phun th hai (x2, y2 l v tr ct, </p><p>hng). Cc ct c nh du t tri sang phi, cc hng c nh du t trn xung di. </p><p>Gii hn: 2 n, m 10^9, 1 x1, x2 m, 1 y1, y2 n. </p><p>Output </p><p>Vi mi b test in ra kt qu trn 1 dng. </p><p>Example </p><p>Input: Output: </p><p>2 </p><p>4 4 1 1 3 3 </p><p>4 3 1 1 2 2 </p><p>8 </p><p>2 </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem F: Cipher </p><p>Time limit: 1s </p><p>0xb0b0 team l 1 i ca PTIT ang tham gia cuc thi CTF(Capture The Flag). tm </p><p>c Flag ca mt cu hi, bn phi tri qua rt nhiu th thch. i ang tin hnh gii </p><p>quyt 1 bi Cipher. Sau 1 hi thi c rt quyt lit, 0xb0b0 team i n kt lun: </p><p>Secret key (kha b mt) c th ly c bng cch ct kha Public key (cng khai) </p><p>thnh 2 phn. Kha cng khai l 1 s t nhin rt ln, c th c ti 1 triu ch s. </p><p>0xb0b0 team mun tm mt cch sao cho c th ct publickey thnh 2 s nguyn dng </p><p>x v y sao cho x chia ht cho a v y chia ht cho b (vi a v b l 2 s cho trc). C x v y </p><p>u khng c c ch s 0 u. </p><p>Hy gip 0xb0b0 team tm cch ct public key. </p><p>Input </p><p>Dng th nht cha public key 1 s nguyn dng (khng cha ch s 0 u) c </p><p>di t 1 n 10^6 ch s. </p><p>Dng tip theo bao gm 2 s nguyn dng cch nhau bi 1 du cch a, b </p><p>(1a,b10^8). </p><p>Output </p><p>Dng u tin in "YES" nu c cch ct c public key. Trong trng hp ny, in 2 dng </p><p>tip theo l 2 s x, y sao cho x b nht c th. </p><p>Trng hp cn li, tc l khng tn ti cch ct, in "NO" v khng in g thm. </p><p>Example </p><p>Test 1 Test 2 Test 3 </p><p>Input: </p><p>116401024 </p><p>97 1024 </p><p>Output: </p><p>YES </p><p>11640 </p><p>1024 </p><p>Input: </p><p>284254589153928171911281811000 </p><p>1009 1000 </p><p>Output: </p><p>YES </p><p>2842545891539 </p><p>28171911281811000 </p><p>Input: </p><p>120 </p><p>12 1 </p><p>Output: </p><p>NO </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem G: Xp hng </p><p>Time limit: 1s </p><p>Trong gi n tra ti Hc vin Cng ngh Bu chnh Vin thng, c n sinh vin ang xp </p><p>hang ly . </p><p>Cm thy chn v phi ng i mt mnh, v vy mi sinh vin vit ra m sinh vin ca </p><p>mnh ng ngay trc v ngay sau ca mnh. Nu khng c ai ng trc hoc khng c </p><p>ai ng sau th vit ra 0. </p><p>t nhin, xe ch nc si i qua, tt c sinh vin phi trnh. Khi h tr li, h khng </p><p>nh v tr ca mnh m ch nh m sinh vin ca ngi n trc v ngi ng sau. </p><p>Hy gip cc sinh vin PTIT tm li v tr ca mnh!!!! </p><p>Input </p><p>Dng u tin gm s t nhin n (2n210^5) s lng sinh vin. </p><p>n dng tip theo, dng th i gm cp s t nhin ai, bi (0ai,bi10^6), vi ai l m sinh </p><p>vin ca ngi ng trc, bi l m sinh vin ca ngi ng sau 1 sinh vin no . </p><p>Nu khng c ai ng trc hoc khng c ai ng sau nhp 0. </p><p>M sinh vin ca mi sinh vin l khc nhau. </p><p> Output </p><p>Trn 1 dng, in ra n s x1,x2,...,xn, danh sch ca cc sinh vin theo th t ban u. </p><p>Example </p><p>Input: Output: 4 </p><p>92 31 </p><p>0 7 </p><p>31 0 </p><p>7 141 </p><p>92 7 31 141 </p><p>Gii thch test bi: </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem H: S ma thut </p><p>Time limit: 1s </p><p>Mt s ma thut l s m c ghp bi cc s 1, 14, 144. S ma thut khng nht thit </p><p>phi c ghp bi c 3 s trn. Cc bn gip kim tra gip xem mt s c l s ma </p><p>thut khng nh! </p><p>Input </p><p>Mt dng duy nht cha s n (1 </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem I: Ch s cui cng </p><p>Time limit: 1s </p><p>Thy T rt thch th vi nhng con s, c gio giao cho T mt bi tp v rt gn cc </p><p>con s. Php rt gn c thc hin nh sau: t mt s ban u, s mi c to thnh </p><p>bng cch cng cc ch s ca s ban u vi nhau. Sau T phi thc hin tip tc vi </p><p>con s va mi thu c. </p><p>Qu trnh rt gn kt thc khi s thu c ch c duy nht 1 ch s. </p><p>Cc bn hy cng T i tm ch s cui cng ca php rt gn! </p><p>Input </p><p>Dng u tin gm s lng test T (T </p></li><li><p>PRE ACM PTIT 2015 ROUND 1 </p><p>Problem J: m s ng i </p><p>Cho mt ma trn N x M, trong c K b chn khng c php i qua. Bn ch c php </p><p>i sang phi hoc i xung di. </p><p>Nhim v ca bn l tm cc ng i t (1, 1) ti (N, M). </p><p>Input: </p><p>Dng u tin gm s test T (T </p></li></ul>