Page 1 of 1
10673 - Play with Floor and Ceil
Posted: Wed Mar 02, 2005 11:26 am
by 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?
Posted: Wed Mar 02, 2005 6:24 pm
by 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.
WA
Posted: Sat Apr 21, 2007 9:35 pm
by 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?
Posted: Sat Apr 21, 2007 9:56 pm
by Jan
Try the cases.
Input:
Code: Select all
5
42 8468
6335 6501
9170 5725
1479 9359
6963 4465
Hope these help.
Re: 10673 - Play with Floor and Ceil
Posted: Thu May 29, 2008 1:25 pm
by 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:
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;
}
Re: 10673 - Play with Floor and Ceil
Posted: Thu May 29, 2008 1:43 pm
by 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?
Posted: Thu May 29, 2008 7:06 pm
by 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.
Re:
Posted: Fri May 30, 2008 10:27 am
by hahahaken
DJWS wrote: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?
Posted: Fri May 30, 2008 1:15 pm
by 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.
Re: 10673 - Play with Floor and Ceil
Posted: Fri May 30, 2008 6:06 pm
by hahahaken
Solved, I think the most difficult part is to find the relationship between k,p and q using the modular
Re: 10673 - Play with Floor and Ceil
Posted: Mon Dec 01, 2008 5:00 pm
by 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
Re: 10673 - Play with Floor and Ceil
Posted: Sat Nov 28, 2009 11:55 am
by 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.