Comments

• 
  

  1

  

  Kien_IT1_INED_K64  commented 41 days ago

  Ý tưởng: Sử dụng tìm kiếm nhị phân

  Mỗi ngày có 1 lượng khách mua bánh từ 1 -> k => Tổng số bánh mỗi ngày bán là : 1+2+...+k = k(k+1)/2;

  Ở mỗi ngày, cần phải tìm số k sao cho 1+2+...+k <= số bánh còn lại;

  Tổng số bánh của Kelquing đã bán trong 1 ngày là bình phương của số các số lẻ trong dãy 1 -> k với k tìm được ở mỗi ngày (số các số lẻ trong dãy = (k+1)/2 )

  Copy

  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  //code by Kien
  typedef pair<int,int> pii;
  #define fi first
  #define se second
  int main()
  {
      ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
      ll n; cin>>n;
      ll conLai = n;
      ll sum_K = 0;
      while(conLai>0){
          ll left = 1, right = 2e9, k=0;
          while(left <= right){
              ll mid = (left + right) /2 ;
              ll tong_banh_can = mid * (mid+1) /2;
              if(tong_banh_can <= conLai){
                  k = mid;
                  left = mid+1;
              }
              else
                  right = mid-1;
          }
  
          ll so_so_le = (k+1)/2;
  
          sum_K += so_so_le * so_so_le;
          conLai-= k*(k+1)/2;
      }
      cout<<sum_K;
  }

• 
  

  0

  

  Mxeno  commented 44 days ago

  tôi nhận ra là mình cần ôn lại môn toán:)))

• 
  

  1

  

  Mxeno  commented 44 days ago ← edited →

  Đầu tiên cần phải tìm số K sao cho tổng cấp cộng Sk <= n

  Copy

     K(K+1)/2 <= n
     K(K+1) <= 2n;
     giải phương trình k*k + k - 2n = 0
     Dt = 1 + 4*2n = 1 + 8n
     sử dụng công thức nghiệm 
     k = (-1 + sqrt(1+8n))/2
     **Công việc còn lại**
     tính Sx = ((2*1 + 2*(k/2-1))*(k/2)) (nếu k lẻ thì là (k+1)/2)
     Sx chính là số bánh Keqing bán. sau đó giảm dần n bằng cách trừ đi Sk

  Copy

  int sums(int u1,int n, int d){
      return ((2*u1+d*(n-1))*n)/2;
  }
  void solve(){
      int n;
      cin>>n;
      int k = (-1+sqrt(1+8*n))/2;
      int ans = sums(1,k%2==0?k/2:(k+1)/2,2);
      n-=(ans+sums(2,k%2==0?k/2:(k-1)/2,2));
      while (n>0){
          k = (-1+sqrt(1+8*n))/2;
          int u = sums(1,k%2==0?k/2:(k+1)/2,2);
          n-=(u+sums(2,k%2==0?k/2:(k-1)/2,2));
          ans+=u;
      }
      cout<<ans;
  }
  

• 
  

  0

  

  MinhDuc_CNTT1_K64  commented 44 days ago

  đỉnk quá