Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: các bạn giúp mình giải 2 bài này với

  1. #1
    Ngày gia nhập
    04 2020
    Bài viết
    2

    Mặc định các bạn giúp mình giải 2 bài này với

    Bài 1: Cow Baseball (6 điểm)
    Nông dân John (FJ) có N con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng.
    Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò (X,Y,Z) hoàn thành hai cú ném. Con bò X ném trái bóng cho con bò Y ở bên phải cô ta, và con bò Y ném trái bóng cho con bò Z ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò (X,Y,Z) mà FJ có thể theo dõi.
    INPUT
    Dòng 1: Số lượng các con bò là N (3 <= N <=1000).
    Dòng 2..1+N: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng 0..100,000,000).
    OUTPUT
    Dòng 1: Số lượng bộ ba con bò (X,Y,Z), trong đó con bò Y nằm bên phải con bò X, con bò Z nằm bên phải con bò Y, và khoảng cách giữa Y và Z nằm giữa XY và 2XY (bao gồm cả giá trị này), trong đó XY là khoảng cách của X đến Y.
    BASEBALL.inp
    5
    3
    1
    10
    7
    4
    BASEBALL.out
    4
    • 50% test có n <= 500
    Giải thích : Có bốn bộ ba con bò ở các vị trí 1-3-7, 1-4-7, 4-7-10, 1-4-10.
    Bài 2: Balanced Cow Subsets (7 điểm)
    Nông dân John (FJ) có N con bò (2 <= N <= 20), trong đó con bò thứ I sản xuất được M(i) đơn vị sữa một ngày (1 <= M(i) <= 100,000,000). FJ muốn sắp xếp quá trình lấy sữa của ông ta hàng ngày, vì vậy ông ta thêm vào máy vắt sữa mới trong nhà kho. Tuy nhiên, nó chỉ hoạt động nếu như sản lượng sữa ở bên trái nhà kho bằng sản lượng sữa ở bên phải.
    Chúng ta gọi tập các con bò là “cân bằng” nếu như ta có thể chia chúng thành hai nhóm có sản lượng sữa là ngang nhau. Vì vậy, FJ muốn biết có bao nhiêu tập các con bò thỏa mãn điều kiện khi chia chúng ra thì hai nhóm có sản lượng sữa là bằng nhau.
    INPUT
    *Dòng 1: Số tự nhiên N.
    *Dòng 2..1+N: Dòng thứ i+1 chứa số M(i).
    OUTPUT
    *Dòng 1: Số tập cân bằng của các con bò.
    SUBSETS.inp SUBSETS.out
    4
    1
    2
    3
    4
    SUBSETS.out
    3
    • 30 % test có n <= 10
    Giải thích : Có 3 tập cân bằng: Tập {1,2,3} có thể chia ra thành {1,2} và {3}, tập {1,3,4} chia ra thành {1,3} và {4}, tập {1,2,3,4} có thể chia ra thành {1,4} và {2,3}
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    483

    Trích dẫn Nguyên bản được gửi bởi baopheng Xem bài viết
    Bài 1: Cow Baseball (6 điểm)
    Nông dân John (FJ) có N con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng.
    Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò (X,Y,Z) hoàn thành hai cú ném. Con bò X ném trái bóng cho con bò Y ở bên phải cô ta, và con bò Y ném trái bóng cho con bò Z ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò (X,Y,Z) mà FJ có thể theo dõi.
    INPUT
    Dòng 1: Số lượng các con bò là N (3 <= N <=1000).
    Dòng 2..1+N: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng 0..100,000,000).
    OUTPUT
    Dòng 1: Số lượng bộ ba con bò (X,Y,Z), trong đó con bò Y nằm bên phải con bò X, con bò Z nằm bên phải con bò Y, và khoảng cách giữa Y và Z nằm giữa XY và 2XY (bao gồm cả giá trị này), trong đó XY là khoảng cách của X đến Y.
    BASEBALL.inp
    5
    3
    1
    10
    7
    4
    BASEBALL.out
    4
    • 50% test có n <= 500
    Giải thích : Có bốn bộ ba con bò ở các vị trí 1-3-7, 1-4-7, 4-7-10, 1-4-10.
    Bài 2: Balanced Cow Subsets (7 điểm)
    Nông dân John (FJ) có N con bò (2 <= N <= 20), trong đó con bò thứ I sản xuất được M(i) đơn vị sữa một ngày (1 <= M(i) <= 100,000,000). FJ muốn sắp xếp quá trình lấy sữa của ông ta hàng ngày, vì vậy ông ta thêm vào máy vắt sữa mới trong nhà kho. Tuy nhiên, nó chỉ hoạt động nếu như sản lượng sữa ở bên trái nhà kho bằng sản lượng sữa ở bên phải.
    Chúng ta gọi tập các con bò là “cân bằng” nếu như ta có thể chia chúng thành hai nhóm có sản lượng sữa là ngang nhau. Vì vậy, FJ muốn biết có bao nhiêu tập các con bò thỏa mãn điều kiện khi chia chúng ra thì hai nhóm có sản lượng sữa là bằng nhau.
    INPUT
    *Dòng 1: Số tự nhiên N.
    *Dòng 2..1+N: Dòng thứ i+1 chứa số M(i).
    OUTPUT
    *Dòng 1: Số tập cân bằng của các con bò.
    SUBSETS.inp SUBSETS.out
    4
    1
    2
    3
    4
    SUBSETS.out
    3
    • 30 % test có n <= 10
    Giải thích : Có 3 tập cân bằng: Tập {1,2,3} có thể chia ra thành {1,2} và {3}, tập {1,3,4} chia ra thành {1,3} và {4}, tập {1,2,3,4} có thể chia ra thành {1,4} và {2,3}
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <algorithm>
    4. using namespace std;
    5.  
    6. long vitri[]={1,3,4,7,10};
    7. void run()
    8. {
    9.     vector<long> vt(vitri,vitri+5);
    10.     sort(vt.begin(),vt.end());
    11.     long dem=0;
    12.     int l=vt.size();
    13.     for(int i1=0;i1<l-2;i1++)
    14.     {
    15.         for(int i2=i1+1;i2<l-1;i2++)
    16.         {
    17.             int d=vt[i2]-vt[i1];
    18.             int i3=i2+1;
    19.             while(i3<l && (vt[i3]-vt[i2]<d))
    20.             {
    21.                 i3++;
    22.             }          
    23.             while(i3<l && (vt[i3]-vt[i2]<=d*2))
    24.             {
    25.                 dem++;
    26.                 cout.width(10);
    27.                 cout<<vt[i1];
    28.                 cout.width(10);
    29.                 cout<<vt[i2];
    30.                 cout.width(10);
    31.                 cout<<vt[i3]<<"\n";
    32.                 i3++;
    33.                
    34.             }
    35.         }
    36.     }
    37.     cout<<dem<<"\n";
    38. }
    39. int main(int argc, char *argv[])
    40. {
    41.     run();
    42. }
    43. /*
    44. 1         3         7
    45.          1         4         7
    46.          1         4        10
    47.          4         7        10
    48. 4
    49.  
    50. [Program finished]
    51. */
    Phần nhập và xuất bạn tự hoàn thiện nhé.

  3. #3
    Ngày gia nhập
    04 2020
    Bài viết
    2

    cái bài 1 là giới hạn chạy 0,1s thôi bạn, bạn có cách nào chạy nhanh hơn ko bạn

  4. #4
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    483

    Trích dẫn Nguyên bản được gửi bởi khoaph Xem bài viết
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <algorithm>
    4. using namespace std;
    5.  
    6. long vitri[]={1,3,4,7,10};
    7. void run()
    8. {
    9.     vector<long> vt(vitri,vitri+5);
    10.     sort(vt.begin(),vt.end());
    11.     long dem=0;
    12.     int l=vt.size();
    13.     for(int i1=0;i1<l-2;i1++)
    14.     {
    15.         for(int i2=i1+1;i2<l-1;i2++)
    16.         {
    17.             int d=vt[i2]-vt[i1];
    18.             int i3=i2+1;
    19.             while(i3<l && (vt[i3]-vt[i2]<d))
    20.             {
    21.                 i3++;
    22.             }          
    23.             while(i3<l && (vt[i3]-vt[i2]<=d*2))
    24.             {
    25.                 dem++;
    26.                 cout.width(10);
    27.                 cout<<vt[i1];
    28.                 cout.width(10);
    29.                 cout<<vt[i2];
    30.                 cout.width(10);
    31.                 cout<<vt[i3]<<"\n";
    32.                 i3++;
    33.                
    34.             }
    35.         }
    36.     }
    37.     cout<<dem<<"\n";
    38. }
    39. int main(int argc, char *argv[])
    40. {
    41.     run();
    42. }
    43. /*
    44. 1         3         7
    45.          1         4         7
    46.          1         4        10
    47.          4         7        10
    48. 4
    49.  
    50. [Program finished]
    51. */
    Phần nhập và xuất bạn tự hoàn thiện nhé.
    Dòng 19 đến 22 mình tìm i3 bằng phương pháp tuyến tính, bạn tìm nó bằng ph pháp nhị phân thử xem.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn