SPOJ.com - Problem BFMUL

BFMUL - Farmer Joe

no tags

Farmer Joe is a strange fellow indeed. He owns a rare breed of cow that eats chocolate and produces chocolate milk, and each cow has exactly L legs. Lately, Joe has been suffering from sore feet, and his intuition tells him that it must be from the chocolate milk. The cows, he suspects, are in pain from stepping on sharp pebbles while crossing the road with chickens in their bare hooves. Naturally, they are transferring their pain karmically through the milk. So he has taken it upon himself to make proper hoofwear for all of them. As he lives at the top of an ivory tower, he finds it most convenient to count their heads. (Each cow has exactly one head.) Joe would like to know how many shoes he must make given that he has counted H heads, and in fact he wrote a program for just this purpose but can’t seem to find it. The program is written for a special computer that he constructed while he was writing his dissertation on Turing machines. He has asked for your help in replacing his program. Please help him quickly, so his cows can suffer as little as possible.

Note: You can use any programming language you want, as long as it is brainf**k.

Input

The first line contains an integer T (1 ≤ T ≤ 1000). Then follow T lines, each containing integers L and H (0 ≤ L,H ≤ 10^20) separated by a single space. Each line, including the last, is terminated by a single newline (linefeed) character, which has ASCII value 10.

Output

T lines containing the number of shoes Farmer Joe must make.

Example

Input:

5
0 0
0 42
42 0
42 42
12345 67890

Output:

Additional Info

There are two randomly generated data sets, one with T=1000 and the other with T=500. L and H are generated independently, and the average number of digits in either is about 11.

My solution at the time of publication has 410 bytes (not golfed) and runs in 0.27s with 1.8M memory footprint.

Submit solution!

hide comments



	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-07-06 12:22:25 Seems that I'm fastest for now ;-) Ans(Mitch): That's a good speed technique, congrats. :) When solving these problems, my primary goal wasn't speed or golfing but simplicity of design (except in the case of BFBINADD, of course), so I'm not surprised to see that my model solution's time was quite improvable, although I thought my BFREGEX1 time was a little closer to optimal before Smithers and you submitted. ;) Last edit: 2013-07-09 23:37:22
	Smithers: 2013-06-23 02:49:20 Phew Took the whole day but that was a lot of fun. Mitch's code must be really fast to run in 0.27s; I don't know how you've managed that. I'm surprised to hear that there are 2 different methods already, as I'm struggling to think of more than 1. Re: the bug in bff-1.0.3.1, from what has been fixed in the code, it looks like the bug happens when the pointer goes off the start of the array? If so then I don't need to worry as I never go further left than the start. My own brainfuck implementation runs into undefined behaviour and usually a SIGSEGV in this case anyway. By the way, do others actually use the number of cases at the start of the input or, like me, just read until EOF? Ans(Mitch): Congrats, I'm glad you enjoyed it! I've found that even for very simple BF problems (like some of the code golf tasks) there can be a surprising variety of choices for memory layout and navigation, managing copies, etc.; for here, your setup is a little closer to mine than Mostafa's but still pretty different. I took some time to try out a small "improvement" to your code and it ended up being 1.97s, compared with your 1.91s! So maybe my code would go a little faster by changing that aspect to the way you did it. And yes, bad memory allocation when moving too far to the left of the starting point is the bug that was fixed in 1.0.5; it was clearly an intended feature but with buggy implementation. And I tend to read until EOF as well. :) Last edit: 2013-07-11 13:37:14
	Mostafa 36a2: 2013-06-20 18:37:14 Hah!! Look At My Last triple :D if i put nothing of sth in some place WA if put one of this some thing TLE if i put two of them AC :D. Moving to BFDIV (as i ACed no need to improve for now at least) Ans(Mitch): Congrats! You're the first solver of any of my problems. :) It's very interesting to see your approach, it's quite different from mine. Regarding the 0/1/2 of something, I've sent you an email on it. :) Last edit: 2013-06-21 04:03:24
	Mostafa 36a2: 2013-06-20 14:26:11 @Mitch : Thanks For the feedBack any way i'm getting now NZEC maybe there is a problem with the judge ! i'll try it later .. more efficiency :) BTW I really missed BF for a long time Thanks for the problems. Best Regards :) Ans(Mitch): Thanks for your appreciation. You're getting NZEC because of the bug in bff that was fixed going from 1.0.4 to 1.0.5. Jander also encountered this bug while working on BFBIGTHN. I'll try making a special request to admins to upgrade to bff 1.0.5. Working around the bug, I was able to make a simple modification to your code and get AC. :) Last edit: 2013-06-20 15:45:27
	Mostafa 36a2: 2013-06-20 06:07:21 Hello Mitch .. I want to congratulate you that you Finally made your own problems :) also for bieng the 9th of The World Rank __________________________________ About the problem .. nice test for BF effeciency ,but I've get WA ... can you tell me Where is it? Ans(Mitch): Thanks. :) After almost three weeks, I'm glad to see a serious submission to one of my problems. You seem to have an issue with cleaning up between test cases. For the large data set you get 6 lines wrong out of 1000, but in isolation your code gives the right answer for those test cases. And FYI ideone's servers are a bit slower than cube's; on ideone your code ran in ~5s for the large data set (with 3 trials, the times were 5.1s, 4.77s, 5.05s), compared with ~3.2s here. :p Last edit: 2013-06-20 11:03:42
	NARUTO (y): 2013-06-14 14:12:21 r u on facebook actually i want to be in contact with u for ur guidelines for programming if u have no problem then please give me ur facebook link Ans(Mitch): I'm pretty inactive on facebook. I haven't provided contact info on my profile because for now I'm not very good about responding to messages in a timely manner, but I've sent you an email. Last edit: 2013-06-15 07:32:20
	NARUTO (y): 2013-06-14 03:09:23 i don't know about brainfK from where i can learn about this and please tell me it is easy language or hard as compare to c/c++ Ans(Mitch): It's easier to learn but harder to use, in a manner of speaking. "Icemens brainfuck tutorial" is a good introduction: http://www.youtube.com/watch?v=OnQobTyqEd0 . Last edit: 2013-06-14 04:23:47**
	NARUTO (y): 2013-06-13 16:07:02 how to come out from tle my id=9473586 please help Ans(Mitch): Your submissions aren't written in brainfuck. Last edit: 2013-06-13 16:13:30
	Akash: 2013-06-11 21:09:53 How do we take such large inputs in BF? Can you plzz provide any link to a good advanced tutorial Ans(Mitch): Taking input is easy, as there is only one possible command to do so; it's the processing that requires some thought. :) For a tutorial of sorts, I recommend Daniel B. Cristofani's "Suggestions for intermediate brainfuck programmers" at http://www.hevanet.com/cristofd/brainfuck/intermediate.html . Edit: Thanx for the link..had no idea of such large computation in BF...will try this problem once I go through the tutorial...:) Last edit: 2013-06-13 05:37:09
	Vaibhav Sinha: 2013-06-08 18:11:51 If possible, allow other languages too. Ans(Mitch): Maybe you will be interested in VFMUL, MUL, or TMUL. Last edit: 2013-06-08 18:41:10

Submit solution!

Added by:	Mitch Schwartz
Date:	2013-06-01
Time limit:	5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	BF