10958 - How Many Solutions?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

10958 - How Many Solutions?

Post by Monsoon » Sun Oct 30, 2005 3:49 pm

i don't know if i understand good this problem, but what is correct answer for m=1 n=0 and p=1 ?

we have 1/x+0/y=1
i think it have inf number of solutions x=1 y is Z\{0},
but we have no option to give inf,

so i should answer 1? :wink:

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Oct 30, 2005 3:59 pm

I used an assert in my program that n, m, and p are never 0, so I am sure there is no such test case in the judge input.

mmij
New poster
Posts: 10
Joined: Mon Jul 11, 2005 7:13 am
Location: PlanetEarth

Post by mmij » Sun Oct 30, 2005 7:13 pm

can anybody give some sample i/o for the problem????

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

10958 - How Many Solutions?

Post by taha » Mon Oct 31, 2005 4:39 pm

Actually i have no idea how to solve this one.

i reached that y=(pnx)/(x-pm) so for how many value of x the numerator is divisible by the denominator ?

i m not sure was this the right way to attempt that problem or not.

any hints ??

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Oct 31, 2005 6:19 pm

i reached that y=(pnx)/(x-pm)
From this point, you can rewrite your equation as:

y = pnx/(x-pm) = pn(1 + pm/(x-pm)),
y = pn + nmp^2/(x-pm).

(x-mp) is an integer, and it must be a divisor of nmp^2.
So, just count the number of divisors of nmp^2, and print as the answer 2*tau(nmp^2)-1.
(because there are negative and positive divisors, and the solution x=0,y=0 is not valid in the original equation.)

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Tue Nov 01, 2005 1:50 pm

what will be the output for the following :-

Code: Select all

-100 5 -450
-1000 1000 -1000
1000 1000 1000
5 5  5
5 -5 5
-5 5 5
5 -5 -5
-5 5 -5
i am getting wa please help
thanx in advance
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Tue Nov 01, 2005 2:19 pm

My AC program outputs:

Code: Select all

Case 1: 399
Case 2: 337
Case 3: 337
Case 4: 9
Case 5: 9
Case 6: 9
Case 7: 9
Case 8: 9
Good luck!

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Tue Nov 01, 2005 6:36 pm

Thanx txandi for u r reply i got ac . i was having trouble with overflow ........
thanx anywayzzzzzzzzz
bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Nov 06, 2005 7:31 pm

According to the statement: "Input is terminated by a case where the value of m, n and p (-1000 ≤ m, n, p ≤ 1000) is zero."

So what happened if m=0 or n=0 or p=0?

Thx in advance :wink:

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Nov 06, 2005 7:45 pm

Antonio Ocampo wrote:According to the statement: "Input is terminated by a case where the value of m, n and p (-1000 ≤ m, n, p ≤ 1000) is zero."

So what happened if m=0 or n=0 or p=0?

Thx in advance :wink:
There is no such case where m or n or p is 0 except the last one. My program terminates if one of them is 0.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Nov 07, 2005 1:28 am

Thx a lot mamun. I got AC.

Keep posting :)

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sat Nov 19, 2005 9:31 am

I passed the above IO but i get WA. Can anyone give some more critical io? Thanks.

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Sun Nov 20, 2005 1:09 am

mf wrote:

Code: Select all

y = pnx/(x-pm) = pn(1 + pm/(x-pm))
I've also found y = pnx/(x-pm) but I couldn't find this result. All the following explanation I understood, but not this step. Can anyone help me?
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Nov 20, 2005 4:10 am

Spoiler maybe:





----
y = pnx / (x-pm) = [pn(x-pm)+(pn)(pm)]/(x-pm) = pn + (pn)(pm)/(x-pm) :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Tue Nov 22, 2005 2:56 am

Thanx a lot, hadnt noticed that =]
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Post Reply

Return to “Volume 109 (10900-10999)”