SPOJ.com - Problem ASCDFIB

ASCDFIB - Ascending Fibonacci Numbers

#sorting

John is trying to learn the Fibonacci sequence. This is what he has learned so far. The first two terms of the sequence are f(1) = 0 and f(2) = 1. The next term f(n) is then calculated by adding the previous two terms f(n-1) and f(n-2). Therefore,

f(1) = 0

f(2) = 1

f(3) = f(2) + f(1) = 1 + 0 = 1

f(4) = f(3) + f(2) = 1 + 1 = 2

f(5) = f(4) + f(3) = 2 + 1 = 3

f(6) = f(5) + f(4) = 3 + 2 = 5

After calculating this for a while, John realized that the values are becoming too big. In order to keep the values small, John changed his algorithm. Instead of calculating f(n) = f(n-1)+f(n-2), he decided he will calculate f(n) = ( f(n-1)+f(n-2) ) % 10^5.

Now John wants to do some research on his new modified Fibonacci sequence. He will give you an integer A (A<=10^5) and an integer B (B<=10^6). You have to output all the terms from f(A) to f(A+B) in ascending order (non-decreasing order). But printing so many numbers is too much of a hassle. So, if there are more than 100 terms in the output, then only print the first 100.

Input

The first line contains an integer T (T<=100), which is the number of test cases.
Each test case contains two positive integers A and B as mentioned before.

Output

For each test case, print case number (Check sample output) and then print the terms from f(A) to f(A+B) in ascending order (non-decreasing order). If there are more than 100 terms in the output, then only print the first 100.

Example

Input:
3
1 3
3 3
100 1

Output:
Case 1: 0 1 1 2
Case 2: 1 2 3 5
Case 3: 15075 69026

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 Next >

	Samiul: 2014-06-23 15:31:23 The sample test cases are not present in the real test case. The sample test cases are something that I have created afterwards to clear the doubts people were having. I should have randomly generated all the test cases, but instead, in order to make things difficult I set the value of B 10^6 always. Now I realize it wasn't a good idea. So basically, you will get AC as long as you are printing first 100 numbers as asked for. Whether you are printing n or (n+1) terms shouldn't matter. I thank Mitch Schwartz, Francky and Sajal Sharma for bringing attention towards this issue. From now on, I will always keep few random test cases in judge data. Since the real complexity of the problem is getting the terms in ascending order, I think this little mishap won't effect much.
	Mitch Schwartz: 2014-06-02 12:05:19 @Sajal Sharma: We are not admins, and we can't read your code. It can be hard to tell tone in a pure text medium, but you are giving off some upset and rude vibes. As already stated, my AC code gives output in accordance with sample I/O. I solved the problem long ago, and resubmitted that code after reading your comment to see if the judging had changed since then. I went out of my way to do this in order to help address your concern. (Granted, it didn't take much effort, but still, your level of appreciation seems pretty much zero.) Using the normal judge, it's not possible for both answers to that particular case to get AC. There are 146 solvers, and nobody else has left a comment reporting such an error before you. Now, when I changed my code to handle range [A,A+B) instead of [A,A+B], it became clear(er) you most likely have a bug in your program, as the result of that would be: Case 1: 0 1 1 Case 2: 1 2 3 Case 3: 69026 You can notice that the Fibs here are indexed differently from how they are usually defined, and you probably have mishandled this in order to get the inconsistent result that you posted. Maybe you are handling small Fibs as a special case? The explanation seems simple: your and your friend's code are both wrong, it's just that the test data is weak enough to allow them to pass. Also, note that neither Francky nor I suggested that you were lying about your assertion, just that it might have been based on some false premise or careless mistake, which merits double checking. Last edit: 2014-06-02 12:48:43
	Cosmos: 2014-06-02 01:44:34 @Francky i changed my code somewhere and i went with this kind of ouput : (11676733) Case 1: 0 1 1 Case 2: 1 2 3 Case 3: 15075 and it got accepted and then with the same code i went with this kind of output : (11676720) Case 1: 0 1 1 2 Case 2: 1 2 3 5 Case 3: 15075 69026 and it showed wrong answer... what should i infer from it??? --ans(Francky)--> I read that Mitch ask you to double check your assertion, did you do it again ? It would be very curious as a recent check show there's no problem with IO from psetter... You didn't answer about your curious first AC : very different time and memory... @francky : you can check the codes by the submissions IDs i have provided and diff them... there's just one difference in a loop...and that's what i am telling you... and about the curious case u were blabbering about.. i double checked with my friends code and it had this kind of o/p format : Case 1: 0 1 1 Case 2: 1 2 3 Case 3: 15075 and it got accepted... why would i lie about this??? seriously dude if you are so curious that i am bullshitting it... then go and check it.... Last edit: 2014-06-02 11:23:40
	Francky: 2014-05-30 23:37:02 @Sajal Sharma: (You have a curious submission #11676686). It's not very fair to set the fault on psetter :( Please change your wordings.
	Mitch Schwartz: 2014-05-30 23:31:16 @Sajal Sharma: Please double check your assertion. My AC code gives answers in accordance with the sample I/O.
	Cosmos: 2014-05-30 23:18:57 Such a huge mistake in the problem statement... costed me so many WAs... really rubbish on the part of problem setter.... actual output needed- Case 1: 0 1 1 Case 2: 1 2 3 Case 3: 15075 and not Case 1: 0 1 1 2 Case 2: 1 2 3 5 Case 3: 15075 69026
	Hasil Sharma: 2014-03-25 10:01:24 Finally AC !!!
	innovolt: 2014-03-11 17:39:05 easy1 bt gud1 ....lv u heap and hashing
	Zeus: 2014-02-20 16:30:37 @Mohammad Samiul Islam my solution is working fine in ideone but giving SIGSEGV on spoj... please help... id: 11102470
	NOVICE: 2014-01-17 15:39:53 getting WA please help!(was expecting TLE)

Submit solution!

Added by:	forthright48
Date:	2013-09-13
Time limit:	3s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Editorial