Money MattersProblem code: MONEY |
The Government of Byteland has decide to issue new currency notes with special protection features to commemorate a great mathematician.
It has decided to issue notes summing up to N such that all the sums from 1 to N should be possible to be made by selecting some of the notes. Also this has to be done in way such that if any note from 1 to N can be made in more than one way by combining other selected notes then that set of notes is not valid.
For example, with N = 7,
The valid sets are:
{1,1,1,1,1,1,1}
{1,1,1,4}
{1,2,2,2}
{1,2,4}
Invalid sets are:
{1,1,1,2,2} beacuse the sum adds up to 7 but 2 can be made by {1,1} and {2}, 3 can be made by {1,1,1} and {1,2}, 4 can be made by {1,1,2} and {2,2} and similarly 5, 6 and 7 can also be made in multiple ways using the same set.
{1,1,3,6} beacuse all from 1 to 7 can be uniquely made but the sum is not 7 (its 11).
Before implementing this idea of issuing these new set of notes, the Government wants to know how many possible valid sets are there for a given N. Your program should help the Government to find this out.
Input
First line will contain the number of test cases T (1<=T<=6666).
Each test case will have one line containing an integer N (<= 2^31-1).
Output
For each value of N output the total number of valid sets on a separate line.
Example
Input: 3 7 111212121 1000 Output: 4 75 13
| Date: | 2010-01-26 |
| Time limit: | s |
| Source limit: | 50000 |
| Languages: |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
The problem statement is
The problem statement is incomplete
@Balajiganapathi: Can u pls
@Balajiganapathi: Can u pls explain how
sorry.........my browser did
sorry.........my browser did not display the problem properly.........
the output section was not visible
now i can see it
what is the time limit for
what is the time limit for the problem !???
I have the correct logic, but
I have the correct logic, but the upper limit of N is a problem. Either memoization fails because array size is too big (even if I use short int) or time limits exceed if non-memoized. Any suggestions?
If the upper limit of N is a
If the upper limit of N is a problem then obviously you do not have the right logic :P So you'll need to think of a brand new approach to the problem.
my solution is correct and
my solution is correct and also work for upper limit.. i have not used array..
in my system i get result. but in this site it takes times to execute. i get Time Limit Exceeded error..
Therefore your solution is
Therefore your solution is not correct. You'll need to program something that works faster.
what is the max value it
what is the max value it should accept??
how much time has been
how much time has been alloted for execution of extreme test case 2147483647..
printing 6666 test cases is
printing 6666 test cases is taking time..
i am solving highest poosbile values in less then second but printing result is taking time
Any one can explain for N =
Any one can explain for N = 11......
why {1,6} is invalid when
why {1,6} is invalid when N=7?
Because that clearly doesn't
Because that clearly doesn't let you have all sums from 1 to 7.
@Stephen, thanks mate... i
@Stephen, thanks mate... i got it.. i shoud have read the problem carefully... :(
can i post C#3.0 solution to
can i post C#3.0 solution to this one.. because when i registered it only shows up C#1.0 & C#2.0 in laguage choice...
I am getting wrong answer
I am getting wrong answer when i submit my solution. Can I know for what value is the algorithm failing ? As i have tried manually, for few small input values and it seems to give correct answer. And also, one of my solution gives a time limit exceeded error, is that mean that the answer returned by that code is correct?
i got what was wrong with my
i got what was wrong with my code... Now again back to time limit exceeded... :(
I am still getting Time
I am still getting Time Limit Exceeded error, even after optimizing my algorithm. I have tested it on my machine for 1000 inputs, and it solves them in 3minutes, which averages each output time to within 1sec. Though for one of the input - "1492192799" which has answer of "748543104", it took around 2 sec (which must be because of large output value), the other outputs were returned/printed within 1sec of time.
Your code must complete the
Your code must complete the entire input file (ie possibly 6666 test cases) in 1 second total. FAQ
Hi, The problem does not
Hi,
The problem does not mention the time limit for the problem. Can you please mention a time limit so I can verify running the code on my machine and compare times. Thanks.
Can you please tell me what
Can you please tell me what is the expected solution for N=8 including the Sets.
Thanks
@Uday : for n=11 there are 8
@Uday : for n=11 there are 8 valid sets
@vardhan : for n=8 the result is 2:
{1,1,1,1,1,1,1,1}
{1,1,3,3}
My program gives correct
My program gives correct answer for the given test cases but it gives WA on submitting.Can you please check my answer or give a good test case.
ID : 402394
can someone point out why am
can someone point out why am i getting runtime err. id 407752
Hello I tested my code and it
Hello
I tested my code and it shows time limit exceeded.. May i know how much time did my algo took?
Can someone print the valid
Can someone print the valid sets for N=1000.. that would help a lot..
respected sir/madam, upon
respected sir/madam,
upon submission, it is showing a runtime error message. but the program is working here without any syntax errors in my laptop. could you please help me with this problem. i even tested the program for the output and its working well enough here.
Also for N=11 I am getting 7
Also for N=11 I am getting 7 valid sets.. Please someone print valid sets for N=11..
@beginner for 11 sets are: {1
@beginner
for 11 sets are:
{1 1 1 1 1 1 1 1 1 1 1}
{1 1 1 1 1 6}
{1 1 1 4 4}
{1 1 3 3 3}
{1 1 3 6}
{1 2 2 2 2 2}
{1 2 2 6}
{1 2 4 4}
what is the answer if i input
what is the answer if i input N=11 and N=9?
can u give me the possible combination...
yahooooooooooooooooooo
yahooooooooooooooooooo :)
this was an acheivement .. atleast for me..
can any one let me know the
definitly....this one is
can anyone tell me the output