10673 - Play with Floor and Ceil

[salamander]

Sample Input:

3
5 2
40 2
24444 6

Sample Ouput :
1 1
1 1
0 6

why
input :40 2 --> output : 1 1

i think 40%2 == 0 and the output should be 0 2 not 1 1

anyone could help me?

[Mohammad Mahmudur Rahman]

Note that this is problem is one with multiple output format. So, for x = 40, k = 2, both 0 2 & 1 1 are correct. You need to print any of the correct solutions.

[Satish]

Code: Select all

#include<iostream.h>
int main(void)
{
    long long int a,b,c,r,s,q,p;
    cin>>a;
    while(a--)
    {
       cin>>b>>c;
       r=(b/c);
       if(b%c==0)
       s=(b/c);
       else
       s=r+1;
       if((r+s)==b)
       {p=1;q=1;}
       else
       {
       if(c*s==b)
       {p=0;q=c;}
       else
       {
        if(b/c==1)
        {p=c;q=b-c;}
       }
       }
       cout<<p<<" "<<q<<endl;
    }
    return(0);
}
              

whats wrong in my code?

[Jan]

Try the cases.

Input:

Code: Select all

5
42 8468
6335 6501
9170 5725
1479 9359
6963 4465

Output:

Code: Select all

0 42
0 6335
9170 0
0 1479
6963 0

Hope these help.

[hahahaken]

By solving the formula
x = p (x/k) + q (x/k)
x = (p+q) / k * x
(p+q) / k = 1
p+q = k

Sample input:

Code: Select all

3
5 2
40 2
24444 6

Sample output:

Code: Select all

1 1 <-- 1+1=2
1 1 <-- 1+1=2
0 6 <-- 0+6=6

But I have submitted for 2 times using different methods and both are wrong answer, I don't know why, can anyone please help me?
It should be a simple question, right?

1st time:

Code: Select all

#include <iostream>
using namespace std;
int main()
{
    int t;
    long long int x,k,p,q;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> x >> k;
        if (k % 2 == 0)
        {
            p = k / 2;
            q = p;
        }
        else
        {
            p = k / 2;
            q = k - p;
        }
        cout << p << " " << q << endl;
    }
    return 0;
}

2nd time:

Code: Select all

#include <iostream>
using namespace std;
int main()
{
    int t;
    long long int x,k;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> x >> k;
        cout << "0" << " " << k << endl;
    }
    return 0;
}

[hahahaken]

After I got wrong answers for 2 times, I search for google for some info and discover that those symbols are not brackets
I misunderstood that the "floor" and "ceil" are brackets at first
There are functions called floor and ceil in the math library in C++ which represent round down and round up respectively, but what should I do to them?
There are no hints at all in how to calculate p and q, but I don't know why my wrong method solving the equation can get the sample output from the question.
P.S. Actually there is sth called "Extended Euclidean algorithm" to solve thisproblem, but I don't know what it is, can anyone give me a help?

[DJWS]

You can simply separate this problem into two cases and discuss each of them: "k divides x" and "k does not divide x." BTW, you can also think about the modular. Modular is somehow related to the floor and the ceil function.

This problem can be solved by very simple formula instead of the extended Eucildean algorithm.

[hahahaken]

You can simply separate this problem into two cases and discuss each of them: "k divides x" and "k does not divide x." BTW, you can also think about the modular. Modular is somehow related to the floor and the ceil function.

This problem can be solved by very simple formula instead of the extended Eucildean algorithm.

I am sorry that I haven't learnt about any concept about floor and ceil in mathematics, can you explain more on what to do with the modular command?

[DJWS]

In this problem you need not to find all possible solutions, but only one of them. Thus you can make a simple assumption, e.g. "p equals zero", and make the things simpler. See if the assumption is reasonable. If reasonable, that is a solution.

In addition, Modular can be used if you need to analysis all possible solutions. Modular is a big concept. You can search websites or books to obtain more information.

[hahahaken]

Solved, I think the most difficult part is to find the relationship between k,p and q using the modular

[Articuno]

I have solved this problem using my own method and it is giving correct output. But it has got TLE. Can anyone suggest any bug in my code?
Or is my poor approach is the cause of this TLE. Please help....

Here is my code

Code: Select all

Got AC
My algo was not good enough

[Taman]

Code: Select all

            p=0;
            while(1)
            {
                if(((x-floor(x/k)*p)%(ceil(x/k)))==0)
                {
                cout<<p<<" "<<(x-floor(x/k)*p)/ceil(x/k)<<endl;
                break;
                }
                p++;
            }

What's wrong with this algo? This algo gives me WA.