Artificial Intelligence softs: 2014

Thứ Sáu, 19 tháng 12, 2014

Hỏi - Đáp về HSG 10

Các em nếu cần hỏi gì về bài toán học sinh giỏi 10 thì viết dưới đây.
Thầy.

Thứ Ba, 29 tháng 7, 2014

TKB2014

Với phương châm không ngừng cải tiến, phần mềm xếp thời khóa biểu liên tục được cập nhật những tính năng mới, TKB2014 là phiên bản mới nhất, mạnh nhất của chúng tôi.

Nhằm tránh cho người dùng truyền thống khỏi bỡ ngỡ nên chúng tôi vẫn giữ lại giao diện của phiên bản 2013, những thay đổi chỉ trong lõi phần mềm, tất cả dữ liệu của các phiên bản trước (2009, 2011, 2013) đều tương thích.

TKB2014 đem lại những tính năng thú vị:

Hướng tối ưu TKB giáo viên: giảm buổi dạy, giảm tiết trống, giảm giáo án, cân bằng số tiết dạy, tránh tiết dạy,...
Hướng tối ưu TKB học sinh: cân bằng số môn học, giảm số môn học, cân bằng số tiết học tự nhiên - xã hội trên mỗi buổi,...
Thuận lợi cho quản lý:

Xếp TKB trường THPT, THCS, Tiểu học. Đã hỗ trợ triệt để cho trường Tiểu học.
Xếp 2 ca trên cùng 1 TKB.
Ba công cụ di chuyển mạnh mẽ, trong đó có xuất phát đích trong cùng một buổi.
Bốn hệ điều hành thông dụng: Windows XP, Vista, 7 và 8 cho 32bit và 64bit.
Xuất 5 định dạng TKB khác nhau (toàn trường, giáo viên, lớp,...)

....

Chỉ với một chi phí nhỏ, các bạn có thể sử dụng toàn bộ những tính năng mạnh mẽ đó. Tuy nhiên phần mềm sẽ chỉ bị khóa 2 chức năng: di chuyển xuất phát - đích trong TKBGV và xuất TKB nếu bạn dùng miễn phí.

Mọi góp ý, thắc mắc, hay cần hỗ trợ khi các bạn gặp khó khăn trong quá trình xếp thời khóa biểu có thể trao đổi với tác giả thông qua công cụ trực quan Teamviewer hay ngay dưới bài viết này.

Nếu các bạn có cài đặt lại máy (Windows) thì nhớ mã chương trình (hình chìa khóa) và cài lại chương trình TKB, sau đó điền lại mã chương trình đó, mã này vẫn không thay đổi, các bạn cứ an tâm.

Các bạn đang dùng phần mềm TKB, nếu trong hợp đồng hay được tặng vẫn còn thời hạn sử dụng thì hãy cập nhật phiên bản này (ngày 24/08/2014), chúng tôi đã sửa những lỗi quan trọng và cung cấp khả năng di chuyển mới, thêm màu sắc cho TKB,... mà không thu thêm phí. Khi cập nhật thì không bị mất dữ liệu cũng như mã chương trình trước đây. Ngoài ra, mong các bạn thông báo cho các bạn khác biết thông tin đó.

Xin cảm ơn.

Link download TKB2014 (cập nhật ngày 26/08/2014) hoặc link download từ googledrive
Link download Teamviewer

Video hướng dẫn nhập phân công chuyên môn trường trung học:
link download từ mediafire
link download từ googledrive

Video hướng dẫn xếp TKB trường trung học:
link download từ mediafire
link download từ googledrive

Link download TKB2011

Chủ Nhật, 30 tháng 3, 2014

Đề - Đáp án Tin học 10 - Bài 3 - Olympic 30/4/2012 - Đoạn hoán vị

Cho dãy số A gồm N số nguyên dương a1, a2,.., aN, mỗi phần tử chỉ xuất hiện đúng 1 lần. (1<=N, ai<=10^5).
YC: Hãy tìm đoạn dài nhất gồm các phần tử trong dãy trên tạo thành một hoán vị các phần tử của tập {1, 2,..., K} (1<=K<=N). Nếu không tìm dc thì trả về 0, ngược lại trả về vị trí bắt đầu imax và độ dài dmax.
Ví dụ:

PASWAP.INP	PASWAP.OUT
7 10 9 3 4 1 2 8	3 4

Lời giải O(N^3)
procedure try;
var i,j
begin
for i...
for j...
if isOK(i,j) then update; //O(N)
Hai vòng lặp for có dpt O(N^2), kiểm tra xem đoạn a[i],.. a[j] có thỏa mãn hoán vị có dpt O(N). Đpt tổng thể là O(N^3).

Lời giải O(N^2)
Bằng cách kết hợp cấp số cộng, tổng tích lũy, chi phí kiểm tra isOK(i,j) chỉ còn O(1).

Lời giải O(NlogN)
Kết hợp Binary Search.

Thứ Sáu, 28 tháng 3, 2014

Đề - Đáp án Tin học 10 - Bài 2 - Olympic 30/4/2012 - Xây dựng hệ thống lưới điện

Công ty truyền tải điện ABC đang thực hiện dự án cung cấp cho một số xã vùng cao của một huyện miền núi. Dự án đã thực hiện được giai đoạn 1, cty đã xây dựng dc N trạm biến áp đặt tại N địa điểm trên địa bàn. Các trạm biến áp này dc đánh số từ 1 đến N (2 <=N<=600). Hiện nay cty tiếp tục thực hiện giai đoạn 2 là cần nối N-1 đường dây điện giữa các trạm biến áp này sao cho khi một trạm biến áp bất kỳ dc nối với lưới điện quốc gia thì tất cả các trạm đều dc cung cấp điện. Hiện tại giữa các trạm biến áp này đã có M (N<=M<=2000) con đường bộ để từ trạm biến áp này có thể đi đến bất kỳ trạm biến áp khác và các hộ dân đều đang sống trên con đường này. Để nối đường dây giữa 2 trạm khác nhau, trạm thứ i với trạm thứ j thì có thể cung cấp dc điện sinh hoạt cho C[i,j] (0<=C[i,j]<=1000) hộ gia đình sống dọc theo con đường này.
Yêu cầu: Tính cách nối dây để cung cấp điện sinh hoạt cho nhiều hộ nhất.
Ví dụ:

ELECTRIC.INP	ELECTRIC.OUT
3 3 1 2 9 1 3 6 2 3 7	16

Lời giải:
C[i,j]:=-C[i,j]. Áp dụng Kruskal.

Đề - Đáp án Tin học 10 - Bài 1 - Olympic 30/4/2012 - Robot nhặt vàng

Cho hình chữ nhật NxM ô vuông, mỗi ô vuông ghi một số nguyên có giá trị không vượt quá 100 thể hiện số lượng vàng robot nhặt được vào ô đó. Một robot đứng tại góc trái trên muốn di chuyển xuống góc phải dưới của hcn. Mỗi bước robot di chuyển sang ô bên phải hoặc ô dưới ô đang đứng.
YC: Tìm con đường robot đi sao nhặt được số lượng vàng nhiều nhất.
DL vào: ROBOT.INP
- Dòng đầu chứa N và M (1<=N, M <=1000)
- N dòng sau, mỗi dòng có M số thể hiện số lượng vàng.
Kết quà: ROBOT.OUT, ghi tổng số lượng vàng nhặt được.
Ví dụ:

ROBOT.INP	ROBOT.OUT
3 4 1 1 1 1 5 2 2 100 9 4 2 1	111

Lời giải:

Phương pháp qui hoạch động đơn giản như sau:

F[i,j] = Max(F[i-1,j], F[i,j-1])+a[i,j], i:[1,N], j:[1,M]

Out: F[N,M]

Độ phức tạp O(NxM)

Thứ Hai, 24 tháng 3, 2014

Đề - Đáp án bài 1 - HSG QG 2014

1.1. CON ĐƯỜNG TÙNG -TRÚC (Bài 1 – Đề thi HSG Quốc gia 2014)

Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ i ở vị trí có khoảng cách đến vị trí bắt đầu của con đường là d_i (i = 1, 2, ..., n). Với kinh phí có hạn, Ban quản lý muốn chọn một đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.

Yêu cầu: Cho a, b và vị trí của n cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đoạn đường đó có ít nhất a cây tùng và b cây trúc.

Dữ liệu vào: MINROAD.INP

- Dòng đầu chứa 3 số nguyên dương n, a, b (a + b ≤ n)

- Dòng thứ i trong n dòng tiếp theo mỗi dòng chứa hai số nguyên dương d_i (d_i ≤ 10^9) trong đó d_i là khoảng cách của cây tính từ vị trí bắt đầu của con đường, k_i = 1 nếu cây thứ i là cây tùng, k_i = 2 nếu là cây trúc.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra: MINROAD.OUT

Ghi ra một số nguyên là độ dài đoạn đường ngắn nhất tìm được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.

Giới hạn:

d_i ≤ 10^9.

30% số test có n ≤ 300.

30% số test khác có n ≤ 3 000.

40 % số test còn lại có n ≤ 300 000.

Ví dụ:

MINROAD.INP	MINROAD.OUT
7 2 2 20 2 30 1 25 1 35 1 60 2 65 2 10 1	35

Lời giải O(N^3)

Vector nghiệm (x1,x2)

QuickSort(D); //O(NlogN)

isOK(x1, x2); //1 vòng lặp đếm số cây, O(N)

Try; //2 vòng lặp liệt kê, O(N^2)

Độ phức tạp tổng thể:

Số lần thử O(N^2) * Chi phí kiểm tra O(N) = O(N^3)

Lời giải O(N^2)

QuickSort(D); //O(NlogN)

SumK1[i], SumK2[i], "i Î[1,n] //O(N)

isOK(x1, x2); //O(1)

Try; //2 vòng lặp liệt kê, O(N^2)

Độ phức tạp tổng thể:

Số lần thử O(N^2) * Chi phí kiểm tra O(1) = O(N^2)

Lời giải O(NlogN)

Thủ tục Try chỉ cần 1 vòng lặp x2, chi phí của isOK(x2) là O(logN).

Độ phức tạp tổng thể:

Số lần thử O(N) * Chi phí kiểm tra O(logN) = O(NlogN)

Chủ Nhật, 16 tháng 3, 2014

Đề thi-Đáp án Tin 10 - Bài 3- Olympic 30-4-2013

Bài 3: Đoạn đường đẹp nhất (Đề thi Tin học 10 – Olympic 30/4/2013)

Trong thời gian vừa qua, người dân ở hành tinh Alpha đã vui mừng chào đó sự xuất hiện của con đường mới XYZ. Được đầu tư rất nhiều nguồn vốn, con đường này được coi là con đường đẹp nhất hành tinh. Những tòa nhà chỉ ở một bên đường với độ cao khác nhau. Theo các giáo sư, đoạn đường đẹp nhất là đoạn đường ở đó độ cao trung bình của các tòa nhà bằng K. Cụ thể, có N tòa nhà nằm cạnh nhau ở một bên của con đường. Tòa nhà thứ i tính từ đầu đường có độ cao là A_i.

Yêu cầu: Hãy tìm đoạn đường dài nhất chứa các tòa nhà liên tiếp sao cho chúng có độ cao trung bình là K.

Dữ liệu vào: cho trong ROAD.INP:

- Dòng 1: ghi hai số nguyên N và K (1≤ N ≤ 10⁵; 0 ≤ K ≤ 10⁹).

- N dòng tiếp theo, dòng thứ i ghi số nguyên A_i (0 ≤ A_i ≤ 10⁹).

Kết quả ra: ghi vào ROAD.OUT:

Nếu không tìm được đoạn nào có các tòa nhà có độ cao trung bình là K thì ghi ra một số 0 duy nhất. Ngược lại, ghi ra hai số u, v với ý nghĩa: u là vị trí bắt đầu của đoạn đường và v là độ dài đoạn đường. Nếu có nhiều đáp án thì ghi ra đáp án có u nhỏ nhất.

Ví dụ:

ROAD.INP	ROAD.OUT
4 5 2 4 5 6	2 3

ĐÁP ÁN - HƯỚNG DẪN GIẢI

Cách 1: O(N^3)

Vector nghiệm: (i, j)

Procedure isOK(i, j: integer); //O(N)

Var p, q: integer; S:longint;

Begin

S:=0;

For p:=i to j do

S:= S + a[p];

If S div (i-j+1) = K then

If j-i+1 >v then

Begin u:=i; v:= j-i+1; End;

End;

Procedure Solve; //O(N^2)

Var i, j: integer;

Begin

Max:=0;

For i:=1 to N-1 do

For j:=i+1 to N do

isOK(i,j);

End;

Nhận xét: với độ phức tạp O(N^3) thì chỉ phủ hợp với N<10^3.

Cách 2: O(N^2)

Procedure isOK(i, j: integer); //O(1)

Begin

If (S[j] – S[i-1]) div (i-j+1) = K then

If j-i+1 >v then

Begin u:=i; v:= j-i+1; End;

End;

Procedure Solve; //O(N^2)

Var i, j: integer;

Begin

Max:=0;

For i:=1 to N-1 do

For j:=i+1 to N do

isOK(i,j);

End;

Nhận xét: với độ phức tạp O(N^2) thì chỉ phủ hợp với N<30 000, nhưng vẫn chưa đạt đến N = 10^5 của đề bài.

Cách 3: O(NlogN)

Procedure isOK(j: integer); //O(logN)

Var i0: integer;

Begin

i0:=BinarySearch(S[j] – K(j+1)) then //O(logN)

if i0>0 then

If j-i0+1 >v then

Begin u:=i0; v:= j-i0+1; End;

End;

Procedure Solve; //O(N)

Var j: integer;

Begin

Max:=0;

For j:=1 to N do

isOK(j);

End;

Begin //main program

T[i].value = S[i-1] + K.i; T[i].i = i; //với mọi i, O(N)

QuickSort(T) //O(NlogN)

Solve; // O(NlogN)

End.

Nhận xét: độ phức tạp O(NlogN), chạy tốt với N = 10^7.

Cách 4: O(N). Tuy nhiên không khả thi do vấn đề bộ nhớ.

Đáp án Tin 10 - Bài 2 - Olympic 30-4-2013

Bài 2: Dầu khí (Đề thi Tin học 10 – Olympic 30/4/2013)

Một tàu thăm dò dầu khí của công ty Bình Minh đã xác định được một khu vực A có dạng hình chữ nhật có chiều dài M km, chiều rộng N km, chia thành MxN ô vuông bằng nhau, mỗi một ô của khu vực này chứa một lượng dầu có giá trị A[i,j]. Công ty Bình Minh muốn giữ lại một khu vực hình vuông chiều dài K km. còn các khu vực khác thì bán đi.

Yêu cầu: Hãy xác định hình vuông chiều dài K có tổng giá trị dầu khí lớn nhất?

Dữ liệu vào: Daukhi.inp:

- Dòng đầu tiên chứa 3 số nguyên M, N, K (M, N ≤ 1000; K ≤ min(M,N)) các số cách nhau bởi 1 khoảng trắng.

- Dòng thứ i trong M dòng tiếp theo chứa N số nguyên, số thứ i là A[i, j] ≤ 1000.

Dữ liệu ra: Daukhi.out: một số nguyên duy nhất chứa tổng giá trị lớn nhất của khu vực cần giữ lại.

Daukhi.inp	Daukhi.out
4 3 2 1 2 3 1 1 1 1 1 1 1 1 1	7

ĐÁP ÁN - HƯỚNG DẪN GIẢI

Cách 1: O(N^4)

Procedure isOK(i, j: integer); //O(N^2)

Var p, q: integer; S:longint;

Begin

S:=0;

For p:=1 to K do

For q:=1 to K do

S:= S + a[i+p-1, j+q-1];

If s>max then max:=S;

End;

Procedure Solve; //O(N^2)

Var i, j: integer;

Begin

Max:=0;

For i:=1 to M-K+1 do

For j:=1 to N – K + 1 do

isOK(i,j);

End;

Cách 2: O(N^3)

A	1	2	3
1	1	2	3
2	1	1	1
3	1	1	1
4	1	1	1

Gọi Sum[i,j] là tổng của hình vuông K có góc trái trên là (i,j).

Procedure isOK(i, j: integer); //O(N)

Var p, q: integer;

Begin

Sum[i,j]:=Sum[i-1,j];

For p:=1 to K do

Begin

Sum[i,j]:= Sum[i,j] + a[i+K-1, p+j-1];

Sum[i,j]:= Sum[i,j] – a[i-1, p+j-1];

End;

If sum[i,j]>max then max:=Sum[i,j];

End;

Cách 3: O(N^2)

Procedure isOK(i, j: integer); //O(1)

Var p, q: integer;

Begin

S[i,j]:=S[i-1,j] + S[i, j-1] – S[i-1, j-1] + a[i-1,j-1] – a[i-1, j+K-1] – a[i+K-1, j-1] + a[i+K-1, j+K-1] ;

If sum[i,j]>max then max:=Sum[i,j];

End;

Với O(N^2) thì có thể chạy được với N ~ 30 000.

Đáp án Tin 10 - Bài 1 - Olympic 30-4-2013

Bài 1: Cáp quang (Đề thi Tin học 10 – Olympic 30/4/2013)

Công ty viễn thông muốn thu gọn hệ thống mạng cáp quang của mình. Biết rằng hệ thống mạng hiện tại của công ty gồm n nút mạng, giữa hai nút mạng bất kỳ đều có đường kết nối trực tiếp hoặc gián tiếp nhau. Bạn hãy giúp công ty chọn phương án thu gọn sao cho giữa hai nút mạng bất kỳ vẫn có đường kết nối trực tiếp hoặc gián tiếp với nhau mà tổng chiều dài cáp quang toàn mạng còn lại là ít nhất.

Dữ liệu vào: cho trong NODE.INP:

- Dòng đầu ghi số nguyên dương N (N ≤ 1000);

- Những dòng tiếp theo, mỗi dòng chứa 3 số nguyên u,v và d, cho biết hai nút u và v có kết nối trực tiếp bằng cáp quang chiều dài d.

Kết quả: ghi ra NODE.OUT số nguyên S là tổng chiều dài cáp quang ít nhất giữ lại cho cả hệ thống.

NODE.INP	NODE.OUT
5 1 2 1 1 3 4 1 4 20 2 3 15 2 4 3 3 5 3 3 4 1 3 5 3 4 5 2	7

ĐÁP ÁN - HƯỚNG DẪN GIẢI

Đây là dạng bài đồ thị cơ bản, áp dụng thuật toán cây bao trùm tối thiểu. Bài toán có thể áp dụng thuật toán như Prim hoặc Kruskal, cả hai thuật toán này rất thông dụng, có cả mã nguồn C và Pascal.

Thứ Sáu, 14 tháng 2, 2014

TKB2014

TKB2014 đem lại những tính năng thú vị:

Hướng tối ưu TKB giáo viên: giảm buổi dạy, giảm tiết trống, giảm giáo án, cân bằng số tiết dạy, tránh tiết dạy,...
Hướng tối ưu TKB học sinh: cân bằng số môn học, giảm số môn học, số tiết học tự nhiên - xã hội trên mỗi buổi,...
Thuận lợi cho quản lý:

Xếp TKB trường THPT, THCS, Tiểu học. Đã hỗ trợ triệt để cho trường Tiểu học.
Xếp 2 ca trên cùng 1 TKB.
Ba công cụ di chuyển mạnh mẽ, trong đó có xuất phát đích trong cùng một buổi.
Bốn hệ điều hành thông dụng: Windows XP, Vista, 7 và 8 cho 32bit và 64bit.
Xuất 5 định dạng TKB khác nhau (toàn trường, giáo viên, lớp,...)

....

Mọi góp ý, thắc mắc, hay cần hỗ trợ khi các bạn gặp khó khăn trong quá trình xếp thời khóa biểu có thể trao đổi với tác giả thông qua công cụ trực quan Teamviewer hay ngay dưới bài viết này.

Xin cảm ơn.

Link download TKB2014 (cập nhật ngày 14/02/2014)
Link download Teamviewer