Submission #146663

# Submission time Handle Problem Language Result Execution time Memory
146663 2019-08-25T05:50:16 Z pichulia 분수 (KPI13_fractions) C++11
0 / 1
1000 ms 376 KB
#include<stdio.h>
unsigned long long int find_r(unsigned long long int x, unsigned long long int b)
{
    unsigned long long int l,r,mid;
    l=2; r=b;
    while(l<r)
    {
        mid = (l+r)/2;
        if((x*mid/b) < mid-1) r = mid;
        else l=mid+1;
    }
    return l-1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        unsigned long long int a,b,c,d;
        unsigned long long int k,s;
        scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
        unsigned long long int x,y;
        unsigned long long int p,q,r;
        k = a/b;
        y=1;
        while(1)
        {
            p=d+(a*y/b)*d;
            q=c*y;
            if(p<q)break;
            r = a*y%b;
            s = find_r(r,b);
            y += s+(p-q)/(c-k*d);
        }
        x = a*y/b+1;
        printf("%llu %llu\n",x,y);
    }
}

Compilation message

fractions.cpp: In function 'int main()':
fractions.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&t);
     ~~~~~^~~~~~~~~
fractions.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Execution timed out 1066 ms 376 KB Time limit exceeded
13 Halted 0 ms 0 KB -