10943  How do you add?
Moderator: Board moderators

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
The problemset's difficulty might be a bit easy for veteran problemsolvers, but it was intended to be a local contest, so that's why.
Perhaps I should always write very precisely, but ya, I didn't write it with the intention of posting it on UVa, just so that it happened that way, and maybe next year/semester I'll keep the possibility in mind! I also didn't have anyone to look over the problems (my professor had looked at it and thought the difficulty was okay, but of course, thinking of problems in algorithms terms and thinking of solving problems precisely is always different!) so I didn't have much feedback. Next time I'll work on it.
Thanks!
Perhaps I should always write very precisely, but ya, I didn't write it with the intention of posting it on UVa, just so that it happened that way, and maybe next year/semester I'll keep the possibility in mind! I also didn't have anyone to look over the problems (my professor had looked at it and thought the difficulty was okay, but of course, thinking of problems in algorithms terms and thinking of solving problems precisely is always different!) so I didn't have much feedback. Next time I'll work on it.
Thanks!
Check out http://www.algorithmist.com !
Thanks to Larry. I appreciate your contribution of the new tasks, though some of them are flawed.
I do think that it is unfair to change the problem description just because the judge solution doesn't solve the task. I would really love to see the test data changed to fit the problem description. If you are too busy to do that, I can help.
Thanks again everyone!!
P.S. This question makes me think of our old friend 10323 Factorial! You Must be Kidding!!! .....
[FYI, 'add up to N' means 'amount to N', or 'equal N when they are added together'. Clearly, negative numbers are NOT prohibited by this definition]
I do think that it is unfair to change the problem description just because the judge solution doesn't solve the task. I would really love to see the test data changed to fit the problem description. If you are too busy to do that, I can help.
Of course I have no way to affect their decision, but if they insist in changing the problem description to fit the wrong judge solution, I would be very disappointed, since I think that is not what a responsible problemsetter should do.Cho wrote:I think this is unlikely to happen.
Thanks again everyone!!
P.S. This question makes me think of our old friend 10323 Factorial! You Must be Kidding!!! .....
[FYI, 'add up to N' means 'amount to N', or 'equal N when they are added together'. Clearly, negative numbers are NOT prohibited by this definition]
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Learning poster
 Posts: 70
 Joined: Sat Feb 05, 2005 9:38 am
 Location: Gurukul
Hi Sarah_S,
Your code produce trailing zero. Just ignore it. Like , for input
Correct output should be
But ur code generates
Hope it helps. Thanks in advance.
Your code produce trailing zero. Just ignore it. Like , for input
Code: Select all
6 46
Code: Select all
9460
Code: Select all
009460
Some Love Stories Live Forever ....

 New poster
 Posts: 28
 Joined: Mon Nov 04, 2002 8:03 pm
 Location: South Korea, Seoul
 Contact:
It's easy DP.
D[ l, s ] = { l : Length of expression, s : sum of expression }
D[ l, s ] = SUM{ D[ l1 , m ] } for m=0 to N and l <= K
and,
output is
D[ l, s ] = SUM{ D[ l1 , m ] } for m=0 to N and l <= K
and,
output is
Since Larry is only interested in the last few digits of the answer, for each pair of numbers N and K, print a single number mod 1,000,000 on a single line.
Using Discrete Math
Of course this prob can be solved by DP and u can also solve this problem
using combination with repetition:
x1+x2+...+xk = n
how many solution does the above equation have answers the problem.
whie xi>=0 and xi <=n
Refrence : Discrete Mathmatics and Its Application by Rosen Page 336
using combination with repetition:
x1+x2+...+xk = n
how many solution does the above equation have answers the problem.
whie xi>=0 and xi <=n
Refrence : Discrete Mathmatics and Its Application by Rosen Page 336
10943  How do you add?
I try to solve this problem with Combinatorial Math, but get WA.
My method is below
1. input n and k // x1+x2+x3+...+xk = n
2. compute the value of C(n+k1,n) //C is the binomial coefficient
3. output
when I input
100 1 //output 1
100 2 //output 101
100 3 //output 5151
100 4 //output 176851
100 5 //output 598126
the corresponding answer is alright.
But,
n=100 k=6 my program output 760646 => wrong answer
(ps. the corect answer should be 560646)
who can help me? here is my code..
My method is below
1. input n and k // x1+x2+x3+...+xk = n
2. compute the value of C(n+k1,n) //C is the binomial coefficient
3. output
when I input
100 1 //output 1
100 2 //output 101
100 3 //output 5151
100 4 //output 176851
100 5 //output 598126
the corresponding answer is alright.
But,
n=100 k=6 my program output 760646 => wrong answer
(ps. the corect answer should be 560646)
who can help me? here is my code..
Code: Select all
#include <cstdio>
int main(int argc, char *argv[])
{
int n,k,m,result;
while(scanf("%d %d",&n,&k)) {
if(!n && !k)
break;
m = k+n1;
result = 1;
if(n>(m>>1))
n = m  n;
for(int i=1;i<=n;i++,m) {
result*=m;
result/=i;
result%=1000000;
}
printf("%d\n",result);
}
return 0;
}
When you're doing computations modulo some integer, you can't just divide like that (you can multiply, subtract, add, but not *divide*.)for(int i=1;i<=n;i++,m) {
result*=m;
result/=i;
result%=1000000;
}
Here's a numeric example, which shows it's wrong:
2000000 = 5000000 = 0 (mod 1000000).
But: 2000000/2 != 5000000/2 (mod 1000000).
(If the modulus were prime (which isn't the case in this problem), you could've implemented division as multiplication by the modular inverse of the divisor, though.)
10943  How do you add?
I think , the solution is C(N+K1,K1), but my program get WA.
In my program, 100 100 return 0. I don't know is it wrong.
This is my code:
In my program, 100 100 return 0. I don't know is it wrong.
This is my code:
Code: Select all
#include <vector>
#include <iostream>
using namespace std;
int C(int n, int k)
{
if(k==0) return 1;
if(k==1) return n;
int K;
if(k>(int)(n/2)) K = nk;
else K = k;
//cout<<"&&"<<n<<" "<<K<<endl;
vector<int> d;
vector<int> d1;
int i,j;
for(i=K;i>=2;i){
d.push_back(i);
d1.push_back(i);
}
int ret = 1;
int num;
for(i=n;i>nK;i){
num = i;
d = d1;
d1.clear();
for(j=0;j<d.size();j++){
if(num%d[j]==0){
//cout<<num<<" "<<d[j]<<endl;
num = (int)(num/d[j]);
}else{
d1.push_back(d[j]);
}
}
ret = (ret*num)%1000000;
//cout<<ret<<endl;
}
return ret;
}
int solve(int N, int K)
{
if(K==1) return 1;
return C(N+K1,K1);
}
int main()
{
vector<int> ret;
int N,K;
while(true){
cin>>N>>K;
if(N==0 && K==0) break;
ret.push_back(solve(N,K));
}
int i;
for(i=0;i<ret.size();i++){
cout<<ret[i]<<endl;
}
}
Re: 10943 WA
It is. There are so many ways to make 100 by summing up 100 elements. The answer for this problem isxlvector wrote:In my program, 100 100 return 0. I don't know is it wrong.
Code: Select all
420660
mod 1000000
My true result is not zero, but after mod 1000000, it is zero.
can someone tell me what 's wrong with my algo
can someone tell me what 's wrong with my algo