30/09/2018, 21:27

Em đã bó tay bó chân trước bài toán này

Đề bài:

s3.amazonaws.com

GIVCANDY.pdf

124.13 KB

Lời giải hiện tại của em, chưa thể nộp được vì mắc lỗi TLE

/* coder: Anh Tuan Nguyen */
#include <bits/stdc++.h>
using namespace std;

int main()
{
#ifdef gsdt
    freopen("input.txt","r",stdin);
#endif // gsdt

    int T;
    scanf("%d",&T);
    while(T--)
    {
        uint64_t res=INT_MAX;
        uint64_t A,B,C,D;
        //bool ok=true;
        scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&D);
        for(int q=0; q<10000000000; q++)
        {
            if(A<B) swap(A,B), swap(C,D);

            uint64_t r=A-B;
            if(r<res)
            {
                res=r;
                /*cout<<A<<" "<<B<<" "<<"["<<res<<"]"<<endl;
                if(A<=0||B<=0||res==0)
                {
                    cout<<"Q="<<q<<endl;
                    break;
                }*/
                //ok=false;
            }
            if(r>D) B+=D*(r/D);
            else B+=D;
            //if(A==B)cout<<A<<" "<<B<<endl;
        }
        printf("%I64d
",res);
    }
    return 0;
}

Mong các anh chị giúp em ý tưởng.

Gió viết 23:41 ngày 30/09/2018

Giả sử số gói kẹo của a và b lần lượt là x và y. Khi đó hiệu số kẹo dc xác định bởi: A-B+Cx-Dy.
Đặt A-B=m. Xét trường hợp:

  1. m chia hết cho UCLN(C,D) khi đó phương trình m+Cx-Dy=0 luôn có nghiệm
  2. m không chia hết cho UCLN(C,D). Ta biết rằng Cx-Dy=UCLN(C,D)=g luôn có nghiệm. Nên giá trị nhỏ nhất hiệu số kẹo =min(abs(m%g),abs(UCLN(C,D)-m%g))
    Hình như đây là bài tập cuộc thi mà?
hacked viết 23:36 ngày 30/09/2018

Anh ơi, anh là sinh viên năm mấy?
Anh có tham gia nhiều vào các cuộc thi lập trình không? (chắc chắn là có rồi )
Thành tích cao nhất của anh là gì ạ?
Và cho em hỏi luôn, anh học trường nào? ngành nào?
Em cám ơn anh

Bài liên quan
0