Vạn Dân Đường

Submit solution
Points: 2
Time limit: 1.0s
C 0.5s
C++ 0.5s
C11 0.5s
Memory limit: 977M
Author:
nqson
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hôm nay, Keqing phụ giúp Xiangling bán bánh mì ở Vạn Dân Đường. Hằng ngày có rất nhiều vị khách tới đây mua bánh mì của hai người. Vị khách thứ i trong ngày sẽ mua i cái bánh. Hôm nay, Keqing và Xiangling sẽ cùng nhau bán n bánh mì đến khi không còn đủ bánh cho khách mua nữa và đóng cửa kết thúc một ngày làm việc. Những chiếc bánh còn thừa trong ngày sẽ được bán tiếp vào các ngày tiếp theo đến khi hết bánh thì thôi.

Để tăng năng suất, Keqing và Xiangling sẽ thay phiên nhau bán bánh. Keqing sẽ bán bánh cho các vị khách lẻ, còn Xiangling sẽ bán bánh cho các vị khách chẵn. Hỏi sau một thời gian bán bánh, Keqing sẽ bán được bao nhiêu cái bánh

Đầu vào

1 số tự nhiên \(n\) là số lượng bánh mì

Đầu ra

Lượng bánh Keqing bán

Giới hạn

50%: \(1 \le n \le 10^{12}\)

50%: \(1 \le n \le 10^{18}\) (bao lâu mới bán được 1 tỷ tỷ cái bánh mì)

Ví dụ 1

Đầu vào

12

Đầu ra

6

Giải thích

Nhật ký bán bánh mì của Keqing:

Ngày 1: Keqing bán bánh mì cho vị khách thứ 1 và 3
        Xiangling bán bánh mì cho vị khách thứ 2 và 4
        Tổng kết: Số bánh Keqing bán: 4
                  Số bánh Xiangling bán: 6
                  Số bánh còn lại: 2

Ngày 2: Keqing bán bánh mì cho vị khách thứ 1
        Xiangling không bán được bánh mì cho ai cả
        Tổng kết: Số bánh Keqing bán: 1
                  Số bánh Xiangling bán: 0
                  Số bánh còn lại: 1

Ngày 3: Keqing bán bánh mì cho vị khách thứ 1
        Xiangling không bán được bánh mì cho ai cả
        Tổng kết: Số bánh Keqing bán: 1
                  Số bánh Xiangling bán: 0
                  Số bánh còn lại: 0

Hết bánh, sau 3 ngày Keqing bán được tổng cộng 6 cái bánh và Xiangling cũng bán được 6 cái bánh

Comments


  • 1
    Kien_IT1_INED_K64  commented on June 4, 2025, 11:58 a.m.

    Ý 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 )

    #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 on June 2, 2025, 2:08 a.m.

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


  • 1
    Mxeno  commented on June 2, 2025, 2:02 a.m. ← edited

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

       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
    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;
}