Đề thi đề nghị môn Tin học Lớp 10 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Trường Chinh

Nội dung text: Đề thi đề nghị môn Tin học Lớp 10 Kỳ thi Olympic 23-3 Tỉnh ĐăkNông lần thứ 5 - Năm học 2017-2018 - Trường THPT Trường Chinh

1. Đáp án câu hỏi 2: ĐÁP ÁN – HƯỚNG DẪN CHẤM Test Bag.inp Bag.out ĐIỂM Test 1 0 Max Value : 0 1 0 Test 2 1 Max Value : 16 1 9 Pack 1 W = 3 Value = 16 3 16 Test 3 1 Max Value : 0 1 3 4 18 Test 4 2 Max Value : 24 1 11 Pack 2 W = 2 Value = 6 4 18 Pack 1 W = 4 Value = 18 2 6 Test 5 5 Max Value : 45 1,5 18 Pack 4 W = 8 Value = 16 4 18 Pack 3 W = 6 Value = 11 2 6 Pack 1 W = 4 Value = 18 6 11 8 16 9 6 Test 6 7 Max Value : 44 1,5 20 Pack 7 W = 7 Value = 10 7 18 Pack 4 W = 6 Value = 16 6 6 Pack 1 W = 7 Value = 18 8 4 6 16 9 6 11 11 5
2. Write(' + Value : '); Readln(V[i]); end; Write('M = '); Readln(g1,M);} close(g1); end; procedure Optimize; {Tính bảng phương án công thức truy hồi} var i, j: Integer; begin FillChar(B[0], SizeOf(B[0]), 0); for i := 1 to n do for j := 0 to M do begin B[i, j] := B[i - 1, j if (j >= W[i]) and (B[i, j] < B[i - 1, j - W[i]] + V[i]) then B[i, j] := B[i - 1, j - W[i]] + V[i]; end; end; procedure Trace; begin assign(g2,fo); rewrite(g2); Writeln(g2,'Max Value : ', B[n, M]); 7
3. Câu hỏi 3: ( 7 điểm) Mã số câu: Nhân dịp Tết sắp đến công ty XYZ quyết định tăng cường việc quảng bá sản phẩm đến người tiêu dùng. Vì thế giám đốc marketing, ông X muốn gửi đi số lượng nhân viên tối đa có thể, làm nhiệm vụ tiếp thị tại đại lý trong thành phố Trong thành phố có m con đường, n đại lý bán kẹo (đánh số từ 1 đến n). Mỗi con đường chỉ nối trực tiếp giữa 2 đại lý, và được ký hiệu bằng chỉ số của 2 đại lý mà nó nối. Đồng thời, giữa 2 đại lý bất kỳ có không quá 1 con đường nối chúng Ông X nghĩ rằng, ông ta sẽ quản lý nhân viên dễ hơn nếu xếp mỗi người tiếp thị trên những hành trình có tính chất thứ tự. Tức là những đại lý bán kẹo trên hành trình đó thỏa các điều kiện sau Có đường nối trực tiếp giữa 2 đại lý liên tiếp nhau trên hành trình Từ một đại lý bất kỳ trong hành trình có thể đi qua tất cả các đoạn đường trong hành trình đó rồi trở về nơi xuất phát mà không đi qua đoạn đường nào quá một lần Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị. Mỗi nhân viên chỉ di chuyển trên hành trình mà anh ta được phân công. Hãy tính số lượng nhân viên tối đa mà ông X có thể xếp việc, và hành trình cụ thể mà mỗi người được xếp. Dữ liệu vào: cho từ file văn bản Quangcao.inp - Dòng đầu là 2 số tự nhiên N và M (N<=2000) (M<=5000) - Trong M dòng tiếp theo, mỗi dòng ghi 2 số nguyên mô tả một đoạn đường, mỗi đoạn đường được mô tả bởi chỉ số của 2 đại lý mà nó nối. Dữ liệu ra: Ghi vào file văn bản Quangcao.out - Dòng đầu tiên ghi Q là số lượng nhân viên tối đa tìm được Example 9
4. Đáp án câu hỏi 3: ĐÁP ÁN – HƯỚNG DẪN CHẤM CÂU Quangcao.inp Quangcao.out ĐIỂM Test 3 4 3 1 1 1 2 2 4 4 5 5 7 Test 0 5 6 1 2 1 2 2 4 4 5 5 7 3 5 Test 5 8 4 1 3 1 2 2 4 4 5 5 7 3 5 3 3 6 7 2 3 Test 12 8 2 1 4 1 2 2 4 4 5 5 7 3 5 3 3 11
5. a:array[1 nmax,1 nmax] of byte; dd:array[1 nmax] of boolean; procedure docfile; var i,j:word; x,y:word; begin assign(f,fi); reset(f); readln(f,n,m); fillchar(a,sizeof(a),0); for i:=1 to m do begin readln(f,x,y); a[x,y]:=1; a[y,x]:=1; end; close(f); end; procedure DFS(i:word); var j:word; begin dd[i]:=true; for j:=1 to n do if (not dd[j]) and (a[i,j]=1) then dfs(j); end; function SPT:longint; var i:word; sl:longint; 13