Page 5 of 7
Problem 138
Posted: Thu Dec 04, 2003 12:26 am
by Charlla
Hy!
There are a relantionship between [6 , 8] and [35, 49]
? I tried to find but I didn't get it.
If I find it, I will generate the other numbers in a easy way.
Thanks,
Charla
Posted: Thu Dec 04, 2003 1:07 am
by Nikolay Archak
Hi!
I can give you a hint if you want.
You should find first 10 pairs of numbers n, m with a property
that 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m
For example, 1 + ... + 5 = 7 + 8 = 15.
Here, n corresponds to the programmer house number and m to the maximum house number on this street.
Problem 138 - Pell's Formula
Posted: Fri Dec 05, 2003 3:41 am
by Charlla
Hy!
How can I generate the next pair of numbers using the Pell's Formula
(if it is possible, of course.)?
Thanks,
Charlla
Posted: Fri Dec 05, 2003 11:19 am
by Farid Ahmadov
Just write on a paper first 6 numbers found by brute force and try to find relation between them.
Posted: Sat Dec 06, 2003 7:43 am
by anupam
i have found the numbers but yet can't get any relation. plz help.
138 - Understanding
Posted: Fri Dec 19, 2003 5:08 am
by Charlla
Hy!
I understood the relation 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m
that you said. But, how can I "guess" that after 6, the next number should
be 35?
Thanks,
Charlla
==========
Nikolay Archak wrote:Hi!
I can give you a hint if you want.
You should find first 10 pairs of numbers n, m with a property
that 1 + 2 + ... + (n-1) = (n+1) + (n+2) + ... + ,m
For example, 1 + ... + 5 = 7 + 8 = 15.
Here, n corresponds to the programmer house number and m to the maximum house number on this street.
Posted: Fri Dec 19, 2003 6:50 am
by yiuyuho
you'll have to spot the pattern.
There is a 2 parameter recursion I know that works, but I dunno why.
Furthermore, you can look into pell's equation, you can transform the problem into pell's equation and use the algorithm for pell to do it. you can google pell, I do not familiar with the details.
Problem 138 - Pell's Equation
Posted: Sun Dec 21, 2003 4:11 pm
by Charlla
Hy!
Thanks a lot. I'll try.
Charlla
----------
yiuyuho wrote:you'll have to spot the pattern.
There is a 2 parameter recursion I know that works, but I dunno why.
Furthermore, you can look into pell's equation, you can transform the problem into pell's equation and use the algorithm for pell to do it. you can google pell, I do not familiar with the details.
Posted: Thu Jan 29, 2004 8:03 pm
by El-idioto
Hi all,
In case you're not sure whether your solution is correct, or just plain want to know some examples, here are the first 12 solutions.
I have omitted solution 10 to prevent people from simply sending in this list.
Code: Select all
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
........ ........
271669860 384199200
1583407981 2239277041
138 - Steet numbers
Posted: Mon Mar 08, 2004 7:57 pm
by Rav
I need help from people's whos have linux and same compiler like OJ. plz write output for this program, becouse i get that output on my win98 with devc++(orginal compiler):
[output removed]
And there is code:
Best Regards Rav
Posted: Mon Mar 08, 2004 8:27 pm
by Raiyan Kamal
Your answer is correct. I compared them with my AC code.
Posted: Mon Mar 08, 2004 11:25 pm
by Rav
Yes i know that
. but try send this to OJ, in 0,004s is WA.
Re: 138 - Steet numbers
Posted: Tue Mar 09, 2004 2:11 am
by junbin
Rav wrote:I need help from people's whos have linux and same compiler like OJ. plz write output for this program, becouse i get that output on my win98 with devc++(orginal compiler):
[output removed]
And there is code:
Best Regards Rav
I think you need long long.. not long int
138 the Math way.
Posted: Mon Apr 05, 2004 8:39 am
by _.B._
Greetings!.
What's the Math way to do this problem?.
I work with Pascal, and I made it adding and testing, but it takes so much time (even with (a+b)*(b-a+1)/2 will take too long).
What formulas can be used?.
Thanks in advance.
Re: 138 the Math way.
Posted: Tue Apr 06, 2004 3:22 am
by junbin
_.B._ wrote:Greetings!.
What's the Math way to do this problem?.
I work with Pascal, and I made it adding and testing, but it takes so much time (even with (a+b)*(b-a+1)/2 will take too long).
What formulas can be used?.
Thanks in advance.
I think the maths formula is already posted somewhere on this forum.. just do a search for it. Alternatively, go to the main page (acm.uva.es/problemset) and then scroll to the bottom. Visit Steven Halim's website. The answer is on there somewhere as well.