Tin 11 - Đề thi chọn HSG cấp cụm Ba Đình - Tây Hồ

huutoan00

Học sinh tiến bộ
Thành viên
19 Tháng hai 2012
181
67
181
24
Your UnderWorld
www.facebook.com
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Câu 1: Ước số
Cho trước số nguyên dương n.
Yêu cầu: Tìm số lượng các ước nguyên dương của n.
vd:
inp:12
out:6
gt: có 6 ước 1,2,3,4,6,12.

Câu 2: Chi tiết máy
Tại phân xưởng có tổng số nguyên liệu là s (đơn vị khối lượng). Quy trình sản xuất chi tiết máy như sau:
(1) Từ nguyên liệu, ngta tạo ra các phôi, mỗi phôi có khối lượng k (đơn vị khối lượng).
(2) Từ mỗi phôi, người ta tạo ra các chi tiết máy, mỗi chi tiết máy có khối lượng m
Sau đó các phần nguyên liệu dư khi sản xuất phôi và chi tiết mày sẽ được thu lại để tiếp tục sản xuất theo quy trình trên.
Yêu cầu: tìm số chi tiết máy nhiều nhất có thể sản xuất được.
vd:
inp: s,k,m=13 5 3
out:3
gt:
13 nguyên liệu, tạo dc 2 phôi, làm dc 2 chi tiết.
dư 7 nguyên liệu, tạo dc 1 phôi, làm dc 1 chi tiết.
dư 4 nguyên liệu
=> có 3 chi tiết được làm

Câu 3: Tích lớn nhất
Cho trước n số nguyên bất kì a1, a2, a3, ..., an.
Yêu cầu: tìm 2 số trong n số đã cho có tích lớn nhất.
2<=n<=10^4
|ai|<=10^4
vd:
inp: n=4; -2 -7 -15 2
out:105
gt: (-7)*(-15)=105

Câu 4: Xâu đối xứng
S là xâu đối xứng nếu viết các ký tự của S teho ký tự ngược lại ta nhận được chính xâu S
Cho xâu X.
Yêu cầu: Tìm cách viết thêm ít kí tự nhất vào cuối xâu X để nhận dc xâu đối xứng S.
length(x)<=100
vd:
inp: ABB
out:
1 ABBA
gt:
thêm 1 kí tự 'A' vào cuối xâu 'ABB' để được xâu 'ABBA' đối xứng
 

H.Đ.O.M.G

Học sinh chăm học
Thành viên
27 Tháng hai 2017
12
8
71
25
đề này thi vs bạn dư sức nhỉ ??? mình đọc câu 1 là thấy hơi bị thất vong ==
 
  • Like
Reactions: huutoan00

Nguyễn Thánh Tiền

Mr Favoirite 2012
Thành viên
2 Tháng mười 2010
1,931
782
324
Hà Nội
cO VUA
câu 4 thử test này chưa chú

abab

đề không giới hạn số liệu có cần sử lí số lớn không 2 chú

Thân
 

huutoan00

Học sinh tiến bộ
Thành viên
19 Tháng hai 2012
181
67
181
24
Your UnderWorld
www.facebook.com
câu 4 thử test này chưa chú

abab

đề không giới hạn số liệu có cần sử lí số lớn không 2 chú

Thân
đề có giới hạn số liệu và nó cũng chỉ nằm trên int với longint thôi ạ, còn xâu thì chỉ đến 100, cho nên về số liệu thì có thể thoải mái
e thử 1 xâu giống dạng đấy và cho ra 'ababa'

inp: n=4; 10 -7 -15 11
out:110
test này thử chưa
cái này dùng 2 vòng lặp lòng nhau, nên nếu có vấn đề thì cũng chỉ là về thời gian chạy và tối ưu của thuật toán thôi
 

Nguyễn Thánh Tiền

Mr Favoirite 2012
Thành viên
2 Tháng mười 2010
1,931
782
324
Hà Nội
cO VUA
đề có giới hạn số liệu và nó cũng chỉ nằm trên int với longint thôi ạ, còn xâu thì chỉ đến 100, cho nên về số liệu thì có thể thoải mái
e thử 1 xâu giống dạng đấy và cho ra 'ababa'


cái này dùng 2 vòng lặp lòng nhau, nên nếu có vấn đề thì cũng chỉ là về thời gian chạy và tối ưu của thuật toán thôi
1 vòng for đc ko nhỉ tìm max âm , max dương , nhì âm , nhì dương rồi so sánh
 

huutoan00

Học sinh tiến bộ
Thành viên
19 Tháng hai 2012
181
67
181
24
Your UnderWorld
www.facebook.com
đề dễ thế :v câu cuối làm bằng quy hoạch động cho nhanh cần gì phức tạp
đề yêu cầu tính tối ưu cơ,
vd như bài 1 chỉ dc xét đến căn n mới dc hết điểm
bài 3 cần chia ra làm 2 mảng âm dương tìm cho nhanh
bài 4 thì có 2 cách:
C1: thêm từng kí tự từ đầu vào cuối, cho tới khi xâu đối xứng (xét với length+x)
C2: xét đoạn đối xứng dài nhất ở cuối xâu (xét với length-x)
=> C2 nhanh hơn vì xét ít hơn => dc điểm cao hơn
 

nguyenhoanghai9d@gmail.com

Học sinh
Thành viên
10 Tháng mười hai 2015
13
3
21
đề yêu cầu tính tối ưu cơ,
vd như bài 1 chỉ dc xét đến căn n mới dc hết điểm
bài 3 cần chia ra làm 2 mảng âm dương tìm cho nhanh
bài 4 thì có 2 cách:
C1: thêm từng kí tự từ đầu vào cuối, cho tới khi xâu đối xứng (xét với length+x)
C2: xét đoạn đối xứng dài nhất ở cuối xâu (xét với length-x)
=> C2 nhanh hơn vì xét ít hơn => dc điểm cao hơn

Bài 4 : Gọi F[i,j] là số phép biến đổi ít nhất cần thêm vào đoạn i..j để đoạn i,,j trở thành một palindrome. Ta có công thức:
- F[i, i]=0;
- Nếu s = s[j] thì F[i,j]=F[i+1,j-1]
- Nếu s <> s[j] thì F[i,j]=min( F[i,j-1],F[i+1,j]
 
Top Bottom