kết quả từ 1 tới 7 trên 7

một số bài tập sách chuyên tin mọi người giúp ak

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    một số bài tập sách chuyên tin mọi người giúp ak

    3.9. Cho : (n<= 10000) điểm trên mặt phẳng Oxy, ñiểm thứ i có tọa ñộ là
    (xi,yi). Ta định nghĩa khoảng cách giữa 2 ñiểm P(xP, yP) và Q(xQ, yQ) bằng
    |xp - xq| + |yp- yq|. Hãy tìm ñiểm f có tọa độ nguyên mà tổng khoảng
    cách (theo cách ñịnh nghĩa trên) từ f tới N ñiểm đã cho là nhỏ nhất
    (|xi|, |yi| nguyên không vượt quá 10^9)
    3.10. Cho : (n <= 10000) đoạn thẳng trên trục số với các điểm đầu xi và độ dài
    di ( |xi|, di là những số nguyên và không vượt quá 10^9. Tính tổng độ dài
    trên trục số bị phủ bởi : đoạn trên.
    Ví dụ: có 3 đoạn x1 = -5, d1 = 10; x2 = 0, d2 = 6; x3 =100, d3 =10
    thì tổng ñộ dài trên trục số bị phủ bởi 3 ñoạn trên là: 21
    3.11. Cho N (N <= 300) điểm trên mặt phẳng Oxy, ñiểm thứ i có tọa ñộ là (xi, yi).
    Hãy ñếm số cách chọn 4 ñđểm trong N ñiểm trên mà 4 điểm ñó tạo thành 4
    hỉnh của một hình chữ nhật. (|xi|, |yi| nguyên không vượt quá 1000)
    Ví dụ: có 5 ñiểm (0, 0), (0, 1), (1, 0), (-1, 0), (0, -1) có duy nhất 1 cách chọn
    4 ñiểm mà 4 ñiểm ñó tạo thành 4 ñỉnh của một hình chữ nhật.
    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: một số bài tập sách chuyên tin mọi người giúp ak

    Bài 3.9:
    Đây là bài tìm minimum Manhattan distance (khoảng cách đc tính ko có square và root). Bởi vì cách tính khoảng cách là independent, bạn có thể tìm median của tất cả tọa độ x (gọi là mX) và median của tất cả tọa độ y (gọi là mY). Lưu ý là vì là tọa độ nguyên nên mX và mY có thể là 1 đoạn. Điểm cần tím sẽ ở xung quanh (mX, mY). Độ phức tạp đã tối ưu sẽ là O(n), nếu bạn ko làm đc thì O(n log n) vẫn chấp nhận đc.

    Bài 3.10:
    Bạn có thể sort lại theo xi rồi từ đó xử lý nhé. Bài này có thể giải đc O(n log n).

    Bài 3.11:
    Bài này mình chưa nghĩ ra cách tốt hơn là đếm hết toàn bộ, nhưng như vậy thì phải hơn 300 triệu lận. Mình nghĩ cách tốt hơn là tính slope của 2 điểm rồi dựa vào đó mà làm. Tiếc là dùng Pascal, nếu mà có C/C++ thì dùng hash sẽ tiện hơ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. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Reply: một số bài tập sách chuyên tin mọi người giúp ak

    giải giúp bài 3.9 và 3.10 đi bạn ten j day ơi.thank bạn nhiều

  5. Đã cảm ơn ngoclinhqbinh:


  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: một số bài tập sách chuyên tin mọi người giúp ak

    Bài 3.9:
    Code bài này rất dễ. Mình hoàn toàn để lại cho bạn. Tím median của 1 dãy: tức là phần tử chia dãy làm đúng 2 phần bằng nhau. Ví dụ với -10, 0, 1, 3, 4 thì 1 là median. Bạn chỉ cần sort lại rồi thì nó là phần tử 'a[n div 2 + 1]' thôi (cách này ko tối ưu nhưng nó đủ để bạn làm đc bài này trong giới hạn cho phép). Median của x và y chính là điểm f cần tìm.

    Bài 3.10:
    Code mình viết tạm thế này nhé:
    Mã:
    type arr = array[1..10000] of longint;
         arr2 = array[0..1, 1..20000] of longint;
    var x, d : arr;
        n : integer;
    
    procedure qsort(var a : arr2; L, R : integer);
    var i, j, mid : integer;
        midV, midI, t : longint;
    begin
        mid := L + ((R - L) shr 1);
        midV := a[0, mid]; midI := a[1, mid];
        i := L; j := R;
        while (i < j) do
            begin
                while ((a[0, i] < midV) or ((a[0, i] = midV) and (a[1, i] < midI))) do
                    inc(i);
                while ((midV < a[0, j]) or ((midV = a[0, j]) and (midI < a[1, j]))) do
                    dec(j);
                if (i <= j) then
                    t := a[0, i]; a[0, i] := a[0, j]; a[0, j] := t;
                    t := a[1, i]; a[1, i] := a[1, j]; a[1, j] := t;
                    inc(i); dec(j);
            end;
        if (L < j) then
            qsort(a, L, j);
        if (i < R) then
            qsort(a, i, R);
    end;
    
    function cover(x, d : arr; n : integer) : longint;
    var i, count : integer;
        left, answer : longint;
        a : arr2;
    begin
        for i := 1 to n do
            begin
                a[0, (i shl 1) - 1] := x[i];
                a[1, (i shl 1) - 1] := -1;
                a[0, i shl 1] := x[i] + d[i];
                a[1, i shl 1] := 1;
            end;
            
        n := n shl 1;
        qsort(a, 1, n);
        
        answer := 0;
        count := a[1, 1];
        left := a[0, 1];
        i := 2;
        while (i <= n) do
            begin
                count := count + a[1, i];
                if (count = 0) then
                    begin
                        answer := answer + a[0, i] - left;
                        inc(i);
                        if (i <= n) then
                            begin
                                left := a[0, i];
                                count := a[1, i];
                            end;
                    end;
                inc(i);
            end;
        exit(answer);
    end;

    Bài này lúc đọc input thì tạo luôn mảng a, ko cần lưu x và d làm chi nhé.

    Bài 3.11: nếu như dữ liệu ko cố tình gây khó khăn thì có thể làm bài này còn O(n^2 log n), hơn rất nhiều so với O(n^4).

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


  8. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Reply: một số bài tập sách chuyên tin mọi người giúp ak

    bài 3.9 cho mình hỏi là nều số lượng phần tử là chẵn thì như bạn nêu ví dụ ở trên còn nếu lẻ thì sẽ lấy như thế nào hả bạn
    -10, 0, 1, 3, 4 4 theo bạn sẽ lấy là 3 hả bạn

  9. Đã cảm ơn ngoclinhqbinh:


  10. #6
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Reply: một số bài tập sách chuyên tin mọi người giúp ak

    3.9 mình xin code 3.9 tối ưu nhất được ko bạn

  11. Đã cảm ơn ngoclinhqbinh:


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

    Reply: một số bài tập sách chuyên tin mọi người giúp ak

    - Nếu là -10, 0, 1, 3, 4, 4 thì median là trung bình của 1 và 3. Tuy nhiên, với đề này thì nó là đoạn các giá trị nguyên [1, 3]. Kết hợp với median của coordinate còn lại sẽ cho 1 hình chữ nhật (hoặc đoạn). Tất cả các điểm trong hình chữ nhật này (hoặc đoạn) đều thỏa mãn điểm f cả. Vì đề ko nói rõ là bao nhiêu điểm nên mình chỉ lấy 1 điểm là đủ.
    - Thuật toán mình ghi cho bạn là khá tối ưu bởi vì cách tìm median bằng sort trc có độ phức tạp O(n log n), trong khi có cách làm tốt hơn tìm median (khó viết hơn, dùng divide and conquer) sẽ có độ phức tạp là O(n). Cái này bạn nên tham khảo trên mạng vì viết cái này hơi phê, ko dễ như nói đâu nhé. Mình từng dùng C/C++ viết cũng mất mấy tiếng mới debug ra.
    - N chỉ tối đa là 10000 nên dùng sort là đc rồi, đừng bon chen chi. Cách làm O(n) muốn thấy hiệu quả thì N cần lên tới hàng chục triệu nhé.

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