10689 - Yet another Number Sequence

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Post by marcadian » Fri Oct 27, 2006 6:22 am

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

Code: Select all

AC
Last edited by marcadian on Sat Dec 09, 2006 7:52 am, edited 1 time in total.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Post by marcadian » Mon Nov 06, 2006 7:30 am

found the mistake, what a silly thing

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10689 - Yet another Number Sequence

Post by uDebug » Thu Mar 13, 2014 12:37 pm

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".
Last edited by uDebug on Thu Mar 13, 2014 9:22 pm, edited 2 times in total.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10689 - Yet another Number Sequence

Post by brianfry713 » Thu Mar 13, 2014 8:26 pm

"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.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10689 - Yet another Number Sequence

Post by uDebug » Thu Mar 13, 2014 9:16 pm

brianfry713 wrote: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".
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10689 - Yet another Number Sequence

Post by brianfry713 » Fri Mar 14, 2014 8:07 pm

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.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10689 - Yet another Number Sequence

Post by uDebug » Sat Mar 15, 2014 3:18 am

Thanks. Point taken. I did reword my post to reflect what you said.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

piyukr
New poster
Posts: 17
Joined: Sun Jan 26, 2014 10:35 am

Re: 10689 - Yet another Number Sequence

Post by piyukr » Sat Jan 21, 2017 7:46 pm

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!

Post Reply

Return to “Volume 106 (10600-10699)”