Gúp đỡ hai bài tập chuyên Tin

HTML:
Câu 4 (1,0 điểm).  DÃY CON XEN KẼ CHẴN LẺ
Cho dãy số nguyên a = (a1, a 2, ….,an); với -10^4 ≤ ai ≤ 10^4 và 1 ≤ i ≤ n ≤ 10^4.
Yêu cầu: Hãy tìm dãy con dài nhất gồm m phần tử liên tiếp trong dãy a: ak, a k+1, ….,ak+m-1 với k+m-1 ≤ n; có các số đan nhau xen kẽ chẵn lẻ (phần tử đầu tiên có thể là số lẻ hoặc chẵn). Nếu có nhiều dãy con thỏa mãn điều kiện thì in ra dãy con đầu tiên.
Dữ liệu vào: Đọc từ file Dayso.inp gồm 2 dòng:
                        - Dòng 1 chứa số n;
                        - Dòng 2 chứa n số: a1, a 2, ….,an các số cách nhau một dấu cách.
Dữ liệu ra: Ghi ra file Dayso.out gồm 2 dòng:
 - Dòng 1 chứa số m;
                         - Dòng 2 là m phần tử liên tiếp trong dãy a: ak, a k+1, ….,ak+m-1 các số đan nhau xen kẽ chẵn lẻ và cách nhau ít nhất 1 dấu cách.
Ví dụ:  
Dayso.inp
Dayso.out
10 
23 14 -11 7 12 -15 48 -39 94 -29
7
7 12 -15 48 -39 94 -29
 
Câu 5 (1,0 điểm). TÌM ĐIỂM TRUNG BÌNH CUỐI NĂM CỦA HỌC SINH 
            Tổng kết cuối năm học, điểm trung bình (DTB) của từng học sinh trong một khối lớp có n học sinh được lưu trong một dãy a(a1, a 2, ….,an ). 
Yêu cầu: Hãy viết một chương trình giúp thầy Hiệu trưởng tìm DTB của học sinh đứng ở vị thứ k trong dãy a (k <= n) và số lượng học sinh đứng ở vị thứ k đó. DTB cao nhất thì xếp ở vị thứ 1.
Dữ liệu vào: Đọc từ file DTB.inp gồm 2 dòng:
                        - Dòng 1 chứa 2 số n, k cách nhau 1 dấu cách (1 ≤ n, k ≤ 10^3);
                        - Dòng 2 chứa n số: a1, a 2, ….,an  (3.5 ≤ a1, a 2, ….,an  ≤ 10.0)  là điểm trung bình tương ứng của n học sinh (1 → n), các số cách nhau một dấu cách.
Dữ liệu ra: Ghi ra file DTB.out:
- Trường hợp có học sinh đứng ở vị thứ k thì:
 + Dòng 1 là DTB ở vị thứ k;
 + Dòng 2 là số lượng học sinh ở vị thứ k (biết rằng nếu các học sinh có cùng điểm trung bình thì cùng một vị thứ). 
- Trường hợp không có học sinh đứng ở vị thứ k thì ghi: KHONG.
 
 
 
Ví dụ:  
DTB.inp
DTB.out
7 4
7.8 6.0 5.4 5.8 6.0 5.1 3.9
5.8
1
 
Sửa lần cuối:

tengiday

Happy life
Dạo này mình busy quá, mới publish bài nghiên cứu của mình xong.
Câu 4:
Giả sử đã tìm đc dãy chẵn lẻ [1 .. i] và biết rằng dãy [1 .. i+1] không thỏa mãn chẵn lẻ, như vậy nếu bạn cần tìm một dãy khác thì phải xuất phát từ đâu? Bài này mình nghĩ chắc chỉ cần O(n).

Câu 5:
Sort nó lại rồi dựa trên đó bắt đầu làm việc. Bài này chỉ cần O(n log n).
 
bài 5: thì đơn giản nên cũng được rồi bạn
bài 4: nhờ bạn nói rõ ý tưởng giải quyết đk ko ak
 

tengiday

Happy life
bài 5: thì đơn giản nên cũng được rồi bạn
bài 4: nhờ bạn nói rõ ý tưởng giải quyết đk ko ak
- Bài này mình thấy chỉ cần 1 nhận xét như mình đã nói: Nếu 1 dãy [1..i] là chẵn lẻ và [1..i+1] không phải chẵn lẻ thì khi ta muốn tìm một dãy mới thì nó phải bắt đầu từ i+1. Bạn suy nghĩ xem nhé!
- Sau đó tương tự từ i+1 tới k nào đó là chẵn lẻ và i+1 tới k+1 ko phải chẵn lẻ thì dãy mới cần duyệt phải bắt đầu từ k+1.
- Với mỗi đoạn như thế bạn chỉ giữ lại chiều dài lớn nhất.
Phần kiểm tra dãy là chẵn lẻ thì mình để lại cho bạn (muốn thêm A[i+1] vào một dãy A[1..i] đã là chẵn lẻ thì bạn chỉ cần so sánh A[i+1] với A thôi phải ko nào?).
 

tengiday

Happy life
Mình nghĩ code thì đại khái thế này. Mình chưa test kỹ. Mình ngán viết code Pascal lắm vì hơn 10 năm rồi mình ko dùng Pascal nữa.
Mã:
procedure Dayso(a : arr; n : integer);
var i, j, max_len, max_ind : integer;
begin
    max_len := 0;
    max_ind := 0;
    i := 1;
    while (i <= n) do
        begin
            j := i + 1;
            while (j <= n) do
                begin
                    if (((a[j] and 1) xor (a[j - 1] and 1)) = 0) then
                        break;
                    inc(j);
                end;
            if (max_len < j - i) then
                begin
                    max_len := j - i;
                    max_ind := i;
                end;
            i := j;
        end;
    writeln(max_len);
    for i := max_ind to max_ind + max_len - 1 do
        write(a[i],' ');
end;
 
if (((a[j] and 1) xor (a[j - 1] and 1)) = 0) then
chỗ này là gì vậy bạn, hình như xử lí bit phải không. mình chư từng tìm hiểu cái dạng này,có cách nào thay đổi chỗ này ko bạn.\
thank bạn
 

tengiday

Happy life
Dòng điều kiện đó có ý rằng:
Mã:
Nếu cả a[j] và a[j-1] đều là chẵn, hoặc cả a[j] và a[j-1] đều là lẻ
 
Mình chuẩn bọ thi tin học trẻ ko chuyên nên rất cần những bài tập này..mà ôn chưa dk bao nhiêu
thấy mấy bài tập này cop lên cho mọi người giúp
bạn ghi if (((a[j] and 1) xor (a[j - 1] and 1)) = 0) then thì sao máy có thể hiểu được là đều chẵn hoặc lẻ hả bạn.mình muốn câu lệnh thật dễ hiểu hơn
 

tengiday

Happy life
Mình chuẩn bọ thi tin học trẻ ko chuyên nên rất cần những bài tập này..mà ôn chưa dk bao nhiêu
thấy mấy bài tập này cop lên cho mọi người giúp
bạn ghi if (((a[j] and 1) xor (a[j - 1] and 1)) = 0) then thì sao máy có thể hiểu được là đều chẵn hoặc lẻ hả bạn.mình muốn câu lệnh thật dễ hiểu hơn
Câu lệnh dễ hiểu hơn thì bạn dùng mod 2. Mình đã nói ở post kia, 'a and 1' dùng để kiểm tra tính chẵn lẻ. Hàm 'xor' là hàm cộng ko nhớ. Cho đơn giản, 'a xor b' =1 nếu chỉ một trong 2 số a, b là 1; và =0 nếu cả 2 a và b đều bằng 0 hoặc 1.
Nếu bạn học về bit nhiều thì sẽ thấy câu lệnh dùng bit chạy nhanh và đơn giản hơn (đương nhiên sẽ khó hiểu hơn).
 
if (((a[j] and 1) xor (a[j - 1] and 1)) = 0)
MÌNH SỬA CHỖ NÀY NHƯ VẬY DK KO BẠN
if (((a[j] MOD 2 <> 0 ) or (a[j - 1] MOD 2)) = 0)
 

tengiday

Happy life
if (((a[j] and 1) xor (a[j - 1] and 1)) = 0)
MÌNH SỬA CHỖ NÀY NHƯ VẬY DK KO BẠN
if (((a[j] MOD 2 <> 0 ) or (a[j - 1] MOD 2)) = 0)
Mình kiến nghị bạn nên viết một đoạn code nhẹ rồi thử. Ví dụ như:
Mã:
writeln( (2 mod 2 <> 0) or (6 mod 2) );
writeln( (3 mod 2 <> 0) or (7 mod 2) );
writeln( (2 mod 2 <> 0) or (7 mod 2) );
writeln( (9 mod 2 <> 0) or (4 mod 2) );
Nếu vẫn chưa đc thì viết một cách thô thiển nhất, dạng như:
Mã:
((a mod 2 <> 0) and (b mod 2 <> 0)) or ((a mod 2 = 0) and (b mod 2 = 0))
 
Cám ơn bạn. Mình mới học nên những lời giải thích thế này rất tuyệt. Nếu mình có gì k biết, bạn giúp mình với.
- Bài này mình thấy chỉ cần 1 nhận xét như mình đã nói: Nếu 1 dãy [1..i] là chẵn lẻ và [1..i+1] không phải chẵn lẻ thì khi ta muốn tìm một dãy mới thì nó phải bắt đầu từ i+1. Bạn suy nghĩ xem nhé!
- Sau đó tương tự từ i+1 tới k nào đó là chẵn lẻ và i+1 tới k+1 ko phải chẵn lẻ thì dãy mới cần duyệt phải bắt đầu từ k+1.
- Với mỗi đoạn như thế bạn chỉ giữ lại chiều dài lớn nhất.
Phần kiểm tra dãy là chẵn lẻ thì mình để lại cho bạn (muốn thêm A[i+1] vào một dãy A[1..i] đã là chẵn lẻ thì bạn chỉ cần so sánh A[i+1] với A thôi phải ko nào?).
 
Top