10689 - Yet another Number Sequence

[marcadian]

I got WA, can anybody help me? here's my code

Code: Select all

AC

[marcadian]

found the mistake, what a silly thing

[uDebug]

Minilek,

Thanks for the great pointer. That really helped.

Next, the following line in the problem description was misinterpreted by me

However, you should NOT print any leading zero.

For the following input

Code: Select all

100 100 10 2

The AC output is

Code: Select all

0

and not just a blank line. If you print a blank line, you'll get WA. Just print the integer value and you should be fine.

Also, be warned that using a map will probably give you a TL. (And if you think some more, you don't really require one.)

Finally, here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

16
0 1 14 1
0 1 24 1
0 1 74 1
25 67 3 1
98 25 1000000000 1
0 1 9842 2
34 88 224242 2
100 100 10 2
56 24 83943 3
89 14 983821 3
1 100 1000000000 4
45 64 999999999 4
0 0 100000 4
100 90 0 4
41 67 1 3
55 89 2 4

AC Output:

Code: Select all

7
8
7
9
3
21
92
0
664
54
8126
1269
0
100
67
144

P.S: Post updated per brianfry713's input (see below). The word "wrong" was changed to "misinterpreted".

[brianfry713]

"you should NOT print any leading zero" doesn't mean that you shouldn't print 0, a single zero isn't considered a leading zero because it's not "leading" anything. Your interpretation of that line was incorrect, not the problem description.

[uDebug]

a single zero isn't considered a leading zero because it's not "leading" anything. Your interpretation of that line was incorrect, not the problem description.

Thanks for sharing your thoughts.

This isn't about a single zero. I believe the test case I shared above actually evaluates to 8900 (if the number's expanded out fully) - or thereabouts anyway. So, are we supposed to print no zeroes, one zero or two zeroes? Are two zeroes "leading" anything? Does the first zero "lead" the other? What makes it so clear that the first zero should be printed and not the second one?

From reading the problem description, it was not clear to me that exactly one zero should be printed in this case.

P.S: I've updated my post to reflect what you've said. Specifically, I changed "wrong" to "misinterpreted".

[brianfry713]

Print the result mod 10^m.

If the last two digits are 00, the first 0 is a leading 0 and should not be printed, just one 0 should be printed.

Your question about which 0 should be printed if there are two 0's makes no sense.

[uDebug]

Thanks. Point taken. I did reword my post to reflect what you said.

[piyukr]

I have used the input given earlier in this thread:

Code: Select all

16
0 1 14 1
0 1 24 1
0 1 74 1
25 67 3 1
98 25 1000000000 1
0 1 9842 2
34 88 224242 2
100 100 10 2
56 24 83943 3
89 14 983821 3
1 100 1000000000 4
45 64 999999999 4
0 0 100000 4
100 90 0 4
41 67 1 3
55 89 2 4

and I am getting expected out as well, still I am getting WA. Can someone help me locate the bug in this code?:

Code: Select all

#include <bits/stdc++.h>
using namespace std;
int fib[15010];
int main() {
	int a, b, c, i, m, t, x;
	unsigned long long n;
	//freopen("input.txt", "r", stdin);
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d %llu %d", &a, &b, &n, &m);
		c = (pow(10, m));
		fib[1] = a % c;
		fib[2] = b % c;
		if (m == 1)
			x = 60;
		else if (m == 2)
			x = 300;
		else if (m == 3)
			x = 1500;
		else if (m == 4)
			x = 15000;
		for (i = 3; i <= x; i++)
			fib[i] = (fib[i - 1] + fib[i - 2]) % c;
		n = (n + 1) % x;
		printf("%d\n", fib[n]);
	}
	return 0;
}

Thanks!