Kỳ thi chọn học sinh giỏi lớp 12 cấp tỉnh năm học 2005 – 2006 môn thi: tin học, vòng 1 thời gian: 150 phút (không kể thời gian giao đề)

SỞ GIÁO DỤC – ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH THỪA THIÊN HUẾ NĂM HỌC 2005 – 2006 Đề chính thức Môn thi: TIN HỌC, vòng 1 Số báo danh: Thời gian: 150 phút (không kể thời gian giao đề) HỌC SINH LẬP TRÌNH GIẢI HAI BÀI TOÁN SAU: (đề thi có 3 trang) Tổng quan về các file: Tên bài Tên file nguồn Tên file văn bản chứa dữ liệu vào, ra Vào Ra Bài toán cổ TOANCO.PAS TOANCO.INP TOANCO.OUT Kim tự tháp TUTHAP.PAS TUTHAP.INP TUTHAP.OUT BÀI 1: BÀI TOÁN CỔ. Tương truyền rằng, ngày xưa có một mưu sĩ thấy dân chúng quá nghèo khổ nên ông ta đã đến thách đố đánh cờ cùng nhà vua nhằm lấy thóc trong kho đem phân phát cho dân nghèo. Nhà vua ra điều kiện nếu đánh thua nhà vua thì mưu sĩ sẽ bị chém đầu, ngược lại mưu sĩ sẽ được trọng thưởng bằng vật chất. Nếu đánh thắng cờ với nhà vua, mưu sĩ chỉ xin một điều đó là trong mỗi ô cờ gồm 8x8 ô thì lần lượt bỏ vào ô thứ 1: 1 hạt thóc, ô thứ 2: 1x2 hạt thóc, ô thứ 3: 1x2x3 hạt thóc, cho đến ô cuối cùng. Nhà vua nghe qua rất khoái chí và đồng ý ngay. Sau lần đấu cờ đó nhà vua đã mất rất nhiều kho lương thực cho dân nghèo. Do bản tính hiếu thắng của nhà vua, ông vẫn tiếp tục thách đấu với những tay cao thủ cờ khác trong thiên hạ nhưng bây giờ rút kinh nghiệm ông chỉ xuất trong kho ra bây giờ không phải là thóc nữa mà là vàng. Nguyên tắc để nhận được vàng sau khi đánh thắng nhà vua như sau: Mỗi ô trong bàn cờ có một số. Con số này được gán vào như sau: - Ô số 1: 1 - Ô số 2: 1x2 = 2 - Ô số 3: 1x2x3 = 6 - Ô số 10 1x2x3x.x10 = 3 628 800 - Ô số 21 1x2x3x.x21 = 51 090 942 171 709 440 000 Số vàng nhận được chính là con số khác không đầu tiên kể từ hàng đơn vị lên phía trước của ô mà đối thủ sẽ chọn. Ví dụ, chọn ô số 10 thì sẽ được 8 lạng vàng, ô số 21 sẽ được 4 lạng vàng, Đối thủ chỉ được chọn mỗi lần một ô để nhận vàng. Không được phép chọn các ô bé hơn 6. Bàn cờ dùng thi đấu là bàn cờ 8x8, nhưng bàn cờ để chọn vàng là NxN (1 ≤ N ≤10 000), các ô được đánh số liên tục từ 1đến N. Yêu cầu: Em hãy viết chương trình để giúp đấu thủ nọ nhận được vàng theo các yêu cầu nói trên. Dữ liệu vào: có nhiều dòng liên tiếp nhau, trên mỗi dòng chứa một số nguyên không âm, đó là thứ tự ô mà đấu thủ đó chọn. Dữ liệu ra: có số dòng bằng số dòng tương ứng với dữ liệu vào. Trên mỗi dòng có nội dung: chữ số đầu tiên là ô số mà đấu thủ nọ chọn, tiếp theo là một mũi tên “->” và cuối cùng là chữ số khác không cuối cùng của ô số đó (theo các nguyên tắc trên). Ví dụ: Dữ liệu vào Dữ liệu ra 26 26 -> 4 125 125 -> 8 3125 3125 -> 2 9999 9999 -> 8 BÀI 2: KIM TỰ THÁP. Các nhà khoa học lịch sử muốn tìm một khu đất để xây dựng một kiến trúc mang hình kim tự tháp. Với ý tưởng là ngôi vườn mà công trình kiến trúc được xây dựng cũng phải có hình tam giác. Chính quyền địa phương nhiều nơi đã tìm kiếm rất vất vả, cuối cùng cũng chọn ra được một số khu vườn như thế. Dưới đây là một trong các khu vườn có hình dáng cần tìm: Tuy nhiên trên các khuôn viên lại có một số công trình, cây cối, đã có trước đây cần phải duy trì. Họ phải lại bắt đầu tính toán để tìm ra được một ô đất cũng có hình tam giác mà diện tích của nó là lớn nhất. Hình vẽ trên cho ta thấy các ô có màu đen chính là các công trình đã có; các ô trắng là đất trống và đường viền đậm là khu vực được đánh dấu để xây dựng. Yêu cầu: Hãy lập trình tìm ra khu đất có diện tích lớn nhất theo yêu cầu của các nhà khoa học đã đưa ra. Dữ liệu vào: gồm nhiều dòng: dòng đầu tiên là n, n là độ rộng của tam giác (1 ≤ n ≤ 100). n dòng tiếp theo chứa các ký tự {#, -} đại diện các hàng của tam giác. Ký tự ‘#’ là màu đen và ‘-’ màu trắng. Trong mỗi tam giác, số ký tự ‘#’ và ‘-’ là lẻ và giảm dần từ 2n – 1 xuống 1. Dữ liệu ra: chỉ một dòng chứa một số nguyên là kết quả tìm ra khu đất lớn nhất cần xây dựng có nội dung “Dien tich lon nhat:” tiếp theo là diện tích tìm được. Nếu không tìm ra cũng trả lời “KHONG TIM RA” Ví dụ, với hình trên ta có dữ liệu vào, ra như sau: Dữ liệu vào Dữ liệu ra 5 #-##----# -----#- ---#- -#- - Dien tich lon nhat: 9 Giám thị không giải thích gì thêm. ĐÁP ÁN, HƯỚNG DẪN CHẤM MÔN TIN HỌC (VÒNG 1) KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH NĂM HỌC 2005 – 2006 I.Đáp án, hướng dãn chấm. BÀI 1: BÀI TOÁN CỔ. 12điểm Có 24 test, mỗi test cho 0.5 điểm. Tất cả thực hiện cùng lúc trong một thời điểm test, thời gian thực thi không quá 30 giây INP OUT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 5 6 7 8 9 10 14 15 24 25 26 124 125 624 625 3124 3125 9999 100 200 501 5001 7029 7501 5 -> 2 6 -> 2 7 -> 4 8 -> 2 9 -> 8 10 -> 8 14 -> 2 15 -> 8 24 -> 6 25 -> 4 26 -> 4 124 -> 4 125 -> 8 624 -> 6 625 -> 6 3124 -> 4 3125 -> 2 9999 -> 8 100 -> 4 200 -> 2 501 -> 4 5001 -> 2 7029 -> 4 7501 -> 6 BÀI 2: KIM TỰ THÁP. 8 điểm Có 16 test, mỗi test cho 0.5 điểm. Thực hiện mỗi lúc một test, thời gian thực thi không quá 30 giây 1 - 1 # 2 #-- # 3 ----- --# - 3 -#-#- --- # 5 --------- ------- ----- --- - 10 --#--#--#---#---#-- ---------#------- --#-##----#---- ---------#--- #-#------#- --#-#-#-- ------# --#-- --- - 20 ----------------#------#-#------#--#--- #------#------##-#--#------------##-- -#--------#--##--------##-#---#-#-- ##-------#--#---#------#------##- #-#-------#-------#---------#-- -----#------------#--------#- --##----#-----------------# --#-------#--------#--##- -##---#------#-#---#--- --#-------###-------- ---#---#----------- -------#-#--#-##- -------#------- ---#------##- -#-----##-- -------#- #-#---- ----- -#- - 30 -----#---##---#-----#---------#----------#----#---##------- ----------#--#----------------#-----#-----#--#----------- ---#------#--------#-----#----#-----#----#----#-------# --#------#-#--#-----#-----#-----------##--#---#------ ------#------##----#-----###------#-----------#---- -------##-#--------------------#---------------## #-##--------#---##----#------###-##----##------ --------##-##--#---------#--###--##---------- --------------##---------##-----#--------#- ---#---#----------------#-###--------#--- -##---------#--##-#---#--#-#-#--#------ -#####-----#--#-----#---#---#---#---- -----------##-----##--#---#-------- --------------#---#---#-------#-- ----#-----#----#-----#---#-#--# ---##-----#--#------#--#----# -----------#-#--##--------- -------------#--------#-# -------#--------#-----# --#-##-#----------#-- --#--#----#-##--#-# --##--#--#-#----- -------#------# -------#----- ------#--#- ----#-#-- --#--## #---- --# # 40 #----------#---------------##------#-#--#---------------##--##---#-#-#------#-- -----#------------#--------#-#-#----#--------#-#-------------##-####--#------ #----#------#------##--#------#-----#-#-----------#--#-#-------#-#--------- ---#---##-#--##--#-#------##-#-----##---#--#--#--#-#-#--##--#-##---#----# -----#---##----#----------------#------------------#----------------#-- ------------------##-----#--#-##----#--####---##-----#--##------##--# ---#------#-----#----------#-----#--#--#-#------#----#----#----#--- ---##-------------------#-----#-#--#----#-#-----##-------#----#-- -##---------#---------#----#----##----------------#------------ ---#--------##------###--------#--#--#-#---#-------#-------#- -#---##--#--#---#-------#------#------####---#---#----#---- ----#-----#---------------##---#----##-----#------------- #---#-------------##---##------#----#--------#-#------- #--#------#--#--##----##--#------------#------#--#--- --#-#---#--#----##---#--------#--#-------##-----#-- #----#-----#------#----##--#----##----#--------#- ---##-------------------------------#----#----# #----------#-----#---#-##-#---#------####---# -#-#-----#--##--#------#--#--------------#- ----------------------##-#--------------- -#----##-##------#-#------#-#---------- ------------#---#--#-----#--#---##--# #-----##-#--------#-----#--------#- ----#---------#-#-----#----#-#--- ---------####------------#--#-# ----##-------#--------------- ------#------------#------# -------##----------##--#- ----------#----------## --#--##---------#--#- -#-##------------#- ##----------#-#-# #---#-----#---# --#-###------ -#--#-#-#-- ---#--#-- -#--##- ---#- --- - 100 ---------------------------------------------------------------------------------------------------------------------------#-------#-----------#------------------------------------------------------- --------------------------------------------------------------#-------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------#----------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------#-----------------------------------------#-#---------------------------------------------------------------------#---------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------#--------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------#-------------------------------------------------------------------------------------------------------------------------------------------#----------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -----#------------#------------------------------------------------#---------------------------------------------------------------------#---------#--------------------------------- ------------------------------#---------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------#-------------------------------------------------#----------------------------------------------------------------- -------------------------------------------------------------------------------------------#----------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------#----------------#---------------------------- ------------------------------------------------------------------------#----------------------------------------------------------#--------------------------------------- -------------------------------------------------------#----------------------------------------------------------------------------------------------------------------- -----------------------------------------------------------#--------------------------------------------------------------------------------------------------------#-- ----------------------------------------------------------------------------------------#-------------------------------#-------------------------------------------- #-------------------------------------------------------------#---------------------------------------------------------------------------------------------------- ----------#---------------------------------------#-------------------------------#------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------#-------------------------#-- ----------------------------------------------------------------------------------------------------------------------------------------------------------- -#---------------------------------------------------#----------------------------#-----------------#---------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------#--------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------#------------------------------------------------------------------------- ------------------------------------------------------------------------#------------------------------------------------------------------------ -------------------------------------------------------------------------------------------#--------------------------------------------------- ------------------------------------------------------------------------------------#----#--------#------------------------------------------ --------------------------------------#-----------------------------------------------------------#-------------------------------------#-- ----------------------------------------------------------------------------------------------------------------------------------------- ----------------#----------------------------------------------------------------------------------------------------------------#----- -----------------------------------------------------------#------------------------#------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------- ------------------#-----------------------------------------------------------------------------------------------------#-------- ----------------------------------------------------------------#--------------------------#----------------------------------- --------------------#---------------------------------------------------------------------------------------------------#---- ---------------------------------#----------------------------------------------------------------------------------------- ---------------#--------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------- -------------------------------------------#------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------#----------------#------------------------ -----------------------------------------------------------------------------------------------------#--------- --------------------------------------------------------------------#---------------------------------------- ----------------------------------------------------------------------------------------------------------- --------------------#--#-------#-------------------------------------#----------------------------------- ------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------#------------------- --------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------- -----------#---------------------------------------------------------------#------------------- -------------------------------------------------------#------------------------------------- ------------------------------------------------------------------------------------------- -----------------#------------#---------------#------------------------------------------ ------------------#-----------------#--------------#-----------------------#----------- --------------------------------------------------------------------#---------------- ----------------------------------------------------------------------------------- ---------------------------------------#----------------------------------------- ---------------------------------------------------------------#--------------- ------#---------------------------------------------------------------------- --------------------------------------------------------------------------- ------------------------------------------------------------------------- ----------------------------------------------------------------------- -----------------------#--------------------------------------------- ------------------------------------------------------------------- ----------------------------------------------------------------- --------------#--------------#----------#---------------------- --------------------------------------------#---------------- ----------------------------------------------------------- --------------------------------------------------------- ---#--------------------------------------------------- ----------------------------------------------------- --------------------------------------------------- -----------------#------------------#------------ ------#---------------------------------------- --------------------------------------------- ------------------------------------------- ----------------------------------------- --------------------------------------- -----------------------------#------- ---------#------------------------- --------------------------------- ------------------------------- ----------------------------- --------------------------- ------------------------- ----------#------------ --------------------- ------------------- ----------------- --------------- ------------- ----------- --------- ------- ----- --- - 100 --------------#-----------------------------------#-------------------#------------#---------------------------#-----------#---------------#--#------#--------#----------#--#--#-----#--------#-------# ---------------------------------------------------------#------#-------#-----------------------------------------------------------------------------#--------#---#--------------------------------- ---------------##--------------------------------------------------------------------------------------#-----------------------------------------------------------------------------------#---#--# ------------------------------------------------------#---#--#------#-----------------#-----------#-#------------------------------------------#--------------#-------#-----------------#-------- ---------------------------------#----------------------#-------------#----------#---------------------------------------------------------------------------#---------------------#---#------- -----------------#---#------------#--------------------#-#-----------------#----------------#---------#-----------------#------------#-----#-------#------#---------------------------------- ---------#----------#--------------------------#--------------#---#-#-#-----------------------------------------------------#-------#-------#---------------------------------##-----#----- -----------------------------#------#------------------------------#-----------------------------------------------#-#-------------------#------#------#----------#-#-#----------------#- #-----#-----------------#---------------------------#----------------------------------------------------------------------------------------#----------------------------------------- -------------------------#------------------------------------#-----------------------------------------------#---------------------------------------------------------------------- ------------------------------#-----------------------------------------#--------------------#----------------#------------------------------------------#------------#--------#--- ----#----------------------------#--------#--#-----------------------------------------------------------#------------------------------------------#---------------------------- ----------#----------------------------------#-----------#----------#-------#-----------------------------------#-------------#--------------#--------------------------------- --------#---#-------------------------------#------#-#-#-------------------------------#----------------------#--------#-----------------------------#-----------#----------# ------#-------------------------------------#-#---------------------------------------------------------------------------------------------------------------------------- #---------------------------------------#----------------------------------------#-----#-------------------#------------------------------------------------------------- -----------------------------------------------##--------------------------------------------------#---#--------------------------------------#------------------------ -------------------------------------------------#------#------#--------------------------------------------------#-----------------------------##------------------- ----------------------#-----------------#---#-----#-----#--------#---#----#-------------------------------#-----------------------#-------------------------------- -----------------#-------------------#------------------------#-------------------------------------------------------------------------------------------------- ----------#--#------#-----#----------------------#----#----------------------------------------------#--------------------------------------------------------- ------------------------------------#-----------------#-------------------------------#---------------------------------------------------------#------------ --#----------------------------------#--------------------------#----------------------------------#--#-#---#------------------#-------#---#-------------#- --------------------#-#------------------#------------#---------------------------------------------------#----#----------------------------------------- ------------------------------------------#---------------------#---------------------------#--#-----#------------------------------#------------------ -----------------------------------------------#---------------------#----------------------------------#--------------#-#--------------------------- ---------------------------------#--------------------------------#-------------------------------------#----------#-----#------------------------- -----------------#------------#-------------------------------------------#---------------------------------------------------------------------- ----------------------------------------------------------------#--------------#--------#---------#--------------------------#---#------------- -------------------------------#-----#------------------------------#------------------------#--#--#----------------------------------------# ---#---#--------------------------------------------------------#--------------------------------------------------#----------------#-----# -------------#-----------#--------------------------------#------------------------------------------------------------------------------ ----------#-#--------------------------------------------------------------#---------------------------------------------------#------- -----------------------------#---------------#------------------------------------------------#------------------#-----------------#- #---#----------------------#------------#----#------------------------------------#--------------------------------#--------------- -------------#--------------------------------------------------------------#---#--------------------#--------------------------- ------------#-------#-----#----------------------#----------------------------------------------------------------------------- -------#----------------------------