Trang 1/2 12 cuối
kết quả từ 1 tới 12 trên 13

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

  1. #1
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    HTML Code:
    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
     
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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).
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. 2 thành viên đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    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

  5. Đã cảm ơn tuonglong:


  6. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi tuonglong Xem bài viết
    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[i] thôi phải ko nào?).

  7. Đã cảm ơn tengiday:


  8. #5
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    cho mình xin code để học bạn ơi......

  9. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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;

  10. 2 thành viên đã cảm ơn tengiday:


  11. #7
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    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

  12. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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ẻ

  13. #9
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    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

  14. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi tuonglong Xem bài viết
    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).

  15. Đã cảm ơn tengiday:


  16. #11
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

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

    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)

  17. Đã cảm ơn tuonglong:


  18. #12
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi tuonglong Xem bài viết
    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))

  19. Đã cảm ơn tengiday:


Trang 1/2 12 cuối