BFDIV - Ancient Aliens

no tags 

Everyone knows that our human ancestors relied on extraterrestrial beings to teach them about science and technology. After helping us build pyramids and chart the stars, our alien mentors decided we needed some time to grow in isolation, so they took some dolphins and left to colonise another planet. Just before leaving, though, they gave us instructions on how to contact them in case of an emergency, such as global warming, nuclear holocaust, or a shortage of fish. The intergalactic telephone they designed consisted of a large golden box powered by alien arc technology. It was entrusted to the United Anarchist Alliance, but was lost when they went to war with the Unified Anarchist League after unsuccessful negotiations to decide which name was more logical for anarchists to call themselves. It remained lost for several centuries at the bottom of a lake until renowned archaeologists Indiana Serkis and Meronym Spader discovered it by chance during a fishing trip. Upon opening the box and pressing the large red button they found inside, an ancient alien immediately appeared and asked them deep, probing questions to determine whether humanity had advanced to the point where the aliens could come back to Earth and chill with us. Among other things, the aliens asked Indiana what his favorite color was, and what the result would be if 38157917385 were divided by 53387519, expressed as quotient and remainder. Since mathematics was never Indiana’s or Meronym’s strong suit, they’ve asked you to write a program for them to perform such computations automatically. They have a computer with them that only understands one language, but they assure you that despite its simplicity the language is Turing complete and perfectly capable of computing the desired quantities efficiently.

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 x (0 ≤ x ≤ 10^20) and y (1 ≤ y ≤ 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 quotient and remainder of x divided by y, separated by a space.

Example

Input:

5
0 42
42 42
123 45
12 345
10000 42

Output:

0 0
1 0
2 33
0 12
238 4

Additional Info

There are two randomly generated data sets, one with T=1000 and the other with T=500. The average number of digits in x is about 13.5, the average number of digits in y is about 8, and the probability that the quotient is nonzero is about 0.82.

My solution at the time of publication has 1516 bytes (not golfed) and runs in 0.14s with 1.9M memory footprint.


hide comments
Mitch Schwartz: 2018-03-28 11:06:08

I decided to solve this again from scratch without looking at any old code, and arrived at a much simpler solution than my original one. It's 760 bytes (not golfed) and runs in 0.05 seconds.

=(Francky)=> Glad to see you again ;-)

Last edit: 2018-03-29 15:24:50
(Tjandra Satria Gunawan)(曾毅昆): 2013-07-08 00:27:02

phew, finally after 17 hours working (~_~)

Ans(Mitch): Congratulations on another fast solution (or were you hoping for something faster?), and on being the first to solve my entire first wave of problems. :)

Re(Tjandra): Thanks for all your problem, I really enjoy it :-D (Although I almost have no time to solve it, haha).. Next month (August), I'll spend a lot of my time on SPOJ (Because I on holiday at that month, so I have much free time). I'll wait your next problem :-)
And about this problem, I have faster(?expected?) solution, but It'll use much more BF cell and longer code, so I lazy to code it, now I think my current code is fast enough ;-) (Although I think my code is slow before I submit it, because too many pointer movement). Btw, I never make such complex BF code before.. Feel good after solve this problem in 0.08s..

Last edit: 2013-07-10 17:13:19
(Tjandra Satria Gunawan)(曾毅昆): 2013-07-07 12:18:31

hmm, this is harder than I thought, 7 hours thinking and still not found "efficient" data structure to solve this problem. I'm afraid that I can't update My Page on time (7 July 2013 SPOJ time). I'll apply my slow method, hope I can finish on time (before 8 July SPOJ time)..

Mostafa 36a2: 2013-07-06 03:38:44

just In BF you can see clearly that a simple improvement in the inner most loop will save a lot of time !
I think I can go further in improving this code .

(Edit) Still some work here and there ,and may be some special cases handling, but I think thats enough for now i'm enthusiastic to solve BFBASE,BFREGEX .
Thank You very much Mitch,I've learned a lot,much more than i thought,Thanks:).

Ans(Mitch): Thanks for the appreciation! Looks like I'll need to publish some more problems at some point.

Last edit: 2013-07-06 15:20:09
Mostafa 36a2: 2013-07-03 15:18:22

YEAH :D
I've failed in my last three exams[to Solve this problem],
finally ACCEPTED :D
Thanks GOD that I made the code easy to maintain
I will improve it as much as I can.
Thank you very much Mitch for your help
(even I seemed like a fool here :p )

Ans(Mitch): Hmm, I can't tell exactly what you mean, you seem to be saying that this problem distracted you from your studies, causing you to fail. D: Anyway, congrats! Hope all is well.

(mostafa): Yes,Exactly that's what I meant :)
but don't care ,all is well as I solve it finally .

Last edit: 2013-07-04 04:57:52
Mostafa 36a2: 2013-07-03 11:08:30

Wow ! you've worked hard on it !
I think I can Start Optimizing now
Because I think this submission #9596508
is correct,but Very Slow ,isn't it :p

Ans(Mitch): Try the test case "0 123456789012345".

Last edit: 2013-07-03 11:51:19
Mostafa 36a2: 2013-07-02 22:04:43

@Mitch: i'll improve it but can you tell me if every thing goes right !
my first code gives wrong answer ,but i think the second is correct isn't it ?

Ans(Mitch): I ran your submission #9593791 against some small test data on ideone, and it seems to fall into infinite (or practically infinite) loop sometimes.

(mostafa): Thanks,It's fail on 999 99,and so 9999 99 ...
But also it's very slow for cases like
99999999999999999999 1
how much time did your code solve it ?

Ans(Mitch): For a file with 1000 instances of "99999999999999999999 1", my code runs in 0.30s.

Last edit: 2013-07-03 10:29:14

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