Đề thi Olympic Tin học sinh viên lần thứ 31 khối Siêu cúp (Năm 2022)

Đề thi Olympic Tin học sinh viên lần thứ 31 khối Siêu cúp (Năm 2022) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: K địa điểm gần nhất; trò chơi trên xâu; tìm xâu đẹp; chữ số đẹp;... Mời các bạn cùng tham khảo chi tiết nội dung đề thi!
Nội dung trích xuất từ tài liệu:
Đề thi Olympic Tin học sinh viên lần thứ 31 khối Siêu cúp (Năm 2022) ThÌi gian làm bài: 240 phút Ngày thi: 07-12-2022 TNG QUAN ó THIBài 1. K ‡a i∫m g¶n nhßt — KNPOINTS (100 i∫m) . . . . . . . . . . . . . . . . . . . 2Bài 2. Trò chÏi trên xâu — SGAME (100 i∫m) . . . . . . . . . . . . . . . . . . . 4Bài 3. Tìm xâu µp — BSTR (100 i∫m) . . . . . . . . . . . . . . . . . . . 6Bài 4. Ch˙ sË µp — BDIGIT (100 i∫m) . . . . . . . . . . . . . . . . . . . 8 Trang 1 trên 8Bài 1. K ‡a i∫m g¶n nhßt — KNPOINTSThành phË HÁ Chí Minh là thành phË s¶m ußt nhßt Viªt Nam vÓi rßt nhi∑u nh˙ng ‡a i∫m d‡ch vˆkhác nhau. Ngân hàng SGHBANK nh™n thßy các cây ATM cıa ngân hàng trên các con ˜Ìng vành aixung quanh thành phË hiªn ho§t Îng không hiªu qu£ nên d¸ ki∏n bË trí l§i v‡ trí các cây ATM này.Ngân hàng ti∏n hành d¸ án kh£o sát các ‡a i∫m d‡ch vˆ thi∏t y∏u trên các tuy∏n ˜Ìng vành ai ó,nÏi th˜Ìng xuyên t™p trung nhi∑u ng˜Ìi qua l§i. Tuy nhiên ph˜Ïng án kh£o sát b¨ng nhân công tr¸c ti∏plà không kh£ thi nên ngân hàng yêu c¶u tÍ tin hÂc áp dˆng các công nghª trí tuª nhân t§o hiªn bi∏t vàohÈ trÒ kh£o sát. Sau mÎt thÌi gian nghiên c˘u, tÍ tin hÂc quy∏t ‡nh s˚ dˆng ph¶n m∑m HMAP ∫ truyvßn nh˙ng ‡a i∫m c¶n thi∏t cho d¸ án.HMAP là mÎt ph¶n m∑m phân tích d˙ liªu chuyên dˆng, l˜u tr˙ thông tin tÂa Î toàn bÎ ‡a i∫m d‡chvˆ thi∏t y∏u trong thành phË, trong ó có N ‡a i∫m vòng quanh các tuy∏n ˜Ìng vành ai. TÂa Î các ‡a i∫m d‡ch vˆ ˜Òc HMAP quy chu©n v∑ hª trˆc tÂa Î ∑-các Oxy. Do vßn ∑ b£o m™t nên HMAPkhông dπ dàng công khai thông tin các ‡a i∫m này. HMAP cho phép ng˜Ìi dùng th¸c hiªn các thaotác, mÈi l¶n chÂn mÎt v‡ trí tÂa Î (x, y) và l¸a chÂn tìm ki∏m trên các tuy∏n ˜Ìng vành ai. VÓi mÈithao tác này, HMAP tr£ v∑ K ‡a i∫m khác nhau có tÍng kho£ng cách ∏n tÂa Î (x, y) là nh‰ nhßttrong sË N ‡a i∫m trên các tuy∏n ˜Ìng vành ai.L˜u ˛:- Các ‡a i∫m tr£ v∑  các thao tác chÂn khác nhau có th∫ trùng nhau, và- N∏u có nhi∑u l¸a chÂn cho K i∫m tr£ v∑, HMAP s≥ tr£ v∑ ng®u nhiên K i∫m tho£ mãn có tÍngkho£ng cách ∏n (x, y) là nh‰ nhßt.Yêu c¶u: B§n hãy giúp tÍ tin hÂc cıa ngân hàng tìm ph˜Ïng án t˜Ïng tác vÓi HMAP ∫ nh™n ˜Òc tÂa Î cıa toàn bÎ N ‡a i∫m trên vÓi sË l˜Òng thao tác ít nhßt có th∫.T˜Ïng tác • Dòng ¶u tiên trong luÁng vào chu©n ch˘a ba sË nguyên d˜Ïng N , K và T l¶n l˜Òt là sË l˜Òng ‡a i∫m d‡ch vˆ, sË l˜Òng ‡a i∫m tr£ v∑ sau mÈi thao tác ng˜Ìi dùng và lo§i subtask cıa bài toán (N  105 ; K  min(N, 100); 1  T  2). • B§n ˜Òc ∞t mÈi câu h‰i b¨ng cách in ra luÁng ra chu©n theo ‡nh d§ng QUERY x y (x, y là các sË nguyên có tr‡ tuyªt Ëi không v˜Òt quá 109 ). Sau khi ∞t câu h‰i, b§n có th∫ Âc vào k∏t qu£ t¯ luÁng vào chu©n gÁm K c∞p sË nguyên x1 , y1 , x2 , y2 , . . . , xK , yK là v‡ trí cıa K ‡a i∫m khác nhau g¶n vÓi (x, y) nhßt. Tr‡ tuyªt Ëi mÈi giá tr‡ to§ Î tr£ v∑ không v˜Òt quá 106 . • B§n c¶n tr£ lÌi câu h‰i b¨ng cách in ra luÁng ra chu©n nh˜ sau: – Dòng ¶u tiên ˜a ra ANSWER – MÈi dòng trong sË N dòng ti∏p theo ghi hai sË x, y mô t£ tÂa Î mÎt ‡a i∫m b§n tìm ˜Òc. Hai sË liên ti∏p trên cùng mÎt dòng cách nhau bi dßu cách.L˜u ˛: Sau mÈi l¶n in ra, b§n c¶n ©y d˙ liªu ra luÁng chu©n (fflush(stdout) ho∞c cout Ví dˆ stdin stdout 3 2 1 QUERY 0 0 1 0 3 0 QUERY 1 0 3 0 1 0 QUERY 3 0 4 0 3 0 ANSWER 1 0 3 0 4 0 4 3 2 QUERY 1 0 1 1 2 0 1 -1 QUERY 2 1 1 1 2 0 1 -1 QUERY 0 0 0 0 1 1 1 -1 ANSWER 0 0 1 1 2 0 1 -1Chßm i∫m: Ëi vÓi mÈi test, gÂi sË câu h‰i cıa b§n là C, ban giám kh£o có mÎt giá tr‡ J vÓi test ó: • B§n s≥ b‡ 0 i∫m n∏u: – TÂa Î các i∫m ˜a ra không chính xác. – T˜Ïng tác sai quy cách. – Ch§y sinh lÈi ho∞c quá thÌi gian. – SË câu h‰i quá 10 ⇥ J. • Ng˜Òc l§i, – N∏u C  J, b§n ˜Òc 100% sË i∫m cıa test ó. – N∏u C > J, b§n s≥ ˜Òc ( C ) ⇥ 100% sË i∫m cıa test ó. JH§n ch∏ • Subtask 1 (50% sË i∫m): T = 1 và toàn bÎ N i∫m ∑u có tung Î y = 0. • Subtask 2 (50% sË i∫m): T = 2 và toàn bÎ N i∫m ∑u n¨m trên mÎt a giác lÁi. Trang 3 trên 8Bài 2. Trò chÏi trên xâu — SGAMECùng n≠m gi˙ k lˆc hai l¶n vô ‡ch Siêu Cúp Olympic Tin hÂc, Quang và H§nh muËn l˜u gi˙ k niªm µp b¨ng cách cùng nhau thi∏t k∏ mÎt trò chÏi t˜Ïng tác gi˙a hai ng˜Ìi.Trò chÏi b≠t ¶u vÓi mÎt xâu nh‡ phân Î dài N . Hai ng˜Ìi s≥ chÏi luân phiên,  mÈi l˜Òt, ng˜Ìi chÏi s≥ ˜Òc th¸c hiªn mÎt trong hai thao tác sau ây: • Thao tác 1: ChÂn mÎt v‡ trí có kí t¸ 0 và bi∏n kí t¸ 0 ó thành kí t¸ 1. • Thao tác 2: ChÂn mÎt v‡ trí có kí t¸ 1 và bi∏n kí t¸ 1 ó thành kí t¸ 0. Ti∏p theo, tìm kí t¸ 0 g¶n nhßt phía bên trái (n∏u có) cıa v‡ trí ˜Òc chÂn và bi∏n nó thành 1, tìm kí t¸ 0 g¶n nhßt phía bên ph£i (n∏u có) cıa v‡ trí ˜Òc chÂn và bi∏n nó thành 1.MÎt n˜Óc i gÂi là hÒp lª n∏u nh˜ xâu nh‡ phân mÓi t§o thành ...