Bình luận

• 
  

  -3

  giaminh2211    6:01 p.m. 20 Tháng 8, 2021

  Bài này bảng B thi chính thức ko ai làm được :(((

• 
  

  32

  AisukiUwU    5:52 p.m. 9 Tháng 8, 2021 ← chỉnh sửa 6 →

  Em xin chia sẻ lời giải bài toán này như sau:

  Bài chỉ mang tính chất tham khảo, vui lòng không chép code :<

  ---

  Hint: Với mỗi quả cân w[i] ta có thể chưa đặt ( 0 ), đặt vào bên trái ( 1 ) hoặc đặt vào bên phải ( 2 ). Vậy có thể dùng một dãy tam phân có độ dài là n để mô tả trạng thái bài toán.

  Với 1 trạng thái dãy tam phân, ta tính số cách để tiếp tục đặt đến hết thỏa mãn:

  • Giả sử dãy tam phân tam phân hiện tại là x ( int x[14] )
  • Xét lần lượt các quả cân chưa đặt ( x[i] == 0 ) thì ta có thể xét 2TH:
    + Nếu mà cân nặng bên trái khi thêm quả cân thứ i vào mà vẫn nhỏ hơn hoặc bằng cân nặng bên phải thì ta có thể đặt quả cân thứ i sang bên trái
    +Quả cân thứ i sẽ đặt sang bên phải
  • Gọi để quy tiếp cho tới khi đặt hết

  Code của phần trên như sauu:

  long long tinh(int d){
      int x[14];
      int d2=d;
      for(int i=0;i<n;i++){
          x[i]=d2%3;
          d2=d2/3;
      }
      long long sum1=0, sum2=0, sl=0;
      for(int i=0;i<n;i++){
          if(x[i]==1){
              sum1+=w[i];
              sl++;
          }
          else if(x[i]==2){
              sum2+=w[i];
              sl++;
          }
      }
      if(sl==n)   return 1;
  
      long long cnt=0;
      for(int i=0;i<n;i++){
          if(x[i]==0){
              if(sum1+w[i]<=sum2){
                  cnt=cnt+tinh(d+p[i]);
              }
              cnt=cnt+tinh(d+2*p[i]);
          }
      }
      return cnt;
  }
  

  Đẩy mảng có nhớ để “tăng tốc” thành DP

  Code để có được 80 điểm:

  #include<bits/stdc++.h>
  using namespace std;
  
  long long n, w[30], p[30], dp[50000005], l[50000005];
  
  long long tinh(int d){
      if(dp[d]==1)    return l[d];
      int x[30];
      int d2=d;
      for(int i=0;i<n;i++){
          x[i]=d2%3;
          d2=d2/3;
      }
      long long sum1=0, sum2=0, sl=0;
      for(int i=0;i<n;i++){
          if(x[i]==1){
              sum1+=w[i];
              sl++;
          }
          else if(x[i]==2){
              sum2+=w[i];
              sl++;
          }
      }
      if(sl==n)   return 1;
  
      long long cnt=0;
      for(int i=0;i<n;i++){
          if(x[i]==0){
              if(sum1+w[i]<=sum2){
                  cnt=cnt+tinh(d+p[i]);
              }
              cnt=cnt+tinh(d+2*p[i]);
          }
      }
      dp[d]=1;
      l[d]=cnt;
      return cnt;
  }
  
  int main(){
      cin >> n;
      for(int i=0;i<n;i++){
          cin >> w[i];
      }
      p[0]=1;
      for(int i=1;i<n;i++){
          p[i]=p[i-1]*3;
      }
      cout << tinh(0);
  }
  

  ---

  Tiếp theo là sub 3, ở sub 3 thì ta có thể thấy n<=28, nhưng có một điều đặc biệt ở đây đó chính là w[i]=2^(i-1), dùng chương trình trên để tìm quy luật

  Sau khi thử vài test như sau

  Input: 2 1 2        Output: 3
  Input: 3 1 2 4      Output: 15
  Input: 4 1 2 4 8        Output: 105
  

  Như vậy quy luật sub 3 là f[n]=f[n-1]*(2n+1), với f[0]=1

  Nhưng vì số rất lớn ( Có thể lên tới 40 chữ số ) nên để AC thì ta phải sử dụng Bignum

  Code để AC:

  long long n, w[30], p[30], dp[50000005], l[50000005];
  
  string nhan(string a, int b){
      int nho=0, res;
      string c="";
      for(int i=a.length()-1;i>=0;i--){
          res=(a[i]-48)*b+nho;
          nho=res/10;
          c=char((res%10)+48)+c;
      }
      while(nho>0){
          c=char((nho%10)+48)+c;
          nho=nho/10;
      }
      return c;
  }
  
  long long tinh(int d){
      if(dp[d]==1)    return l[d];
      int x[30];
      int d2=d;
      for(int i=0;i<n;i++){
          x[i]=d2%3;
          d2=d2/3;
      }
      long long sum1=0, sum2=0, sl=0;
      for(int i=0;i<n;i++){
          if(x[i]==1){
              sum1+=w[i];
              sl++;
          }
          else if(x[i]==2){
              sum2+=w[i];
              sl++;
          }
      }
      if(sl==n)   return 1;
  
      long long cnt=0;
      for(int i=0;i<n;i++){
          if(x[i]==0){
              if(sum1+w[i]<=sum2){
                  cnt=cnt+tinh(d+p[i]);
              }
              cnt=cnt+tinh(d+2*p[i]);
          }
      }
      dp[d]=1;
      l[d]=cnt;
      return cnt;
  }
  // :3
  int main(){
      cin >> n;
      for(int i=0;i<n;i++){
          cin >> w[i];
      }
      p[0]=1;
      for(int i=1;i<n;i++){
          p[i]=p[i-1]*3;
      }
      if(n<=14)   cout << tinh(0);
      else{
          long long j=1;
          string kq="1";
          for(int i=1;i<=n;i++){
              kq=nhan(kq,j);
              j=j+2;
          }
          cout << kq;
      }
  }
  

  1 phản hồi
• 
  

  -6

  lethienquan28052006    10:40 a.m. 9 Tháng 8, 2021

  ai cho em xin solution bài này với ạ

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.