SPOJ.com - Problem BASECONV

BASECONV - Base Conversion

no tags

Leo didn't do all the job in his last problem, somebody gave him the numbers in a convenient base. It was the bottleneck of the problem... Now your task is to do this job.

Input

The first line of input contains three integers T, the number of test cases, B1, the first base, B2, the second base.
Follow 2×T lines.
For each test case, on the first line your are given one integer k.
On the second line you are given k integers : the digits of N in base B1.

N = a₀×B1⁰ + ... + a_i×B1ⁱ + ... + a_k-1×B1^k-1

Output

For each test case, you have to print the number N in base B2. See sample for details.

Example

Input:
1 10 100
5
5 4 3 2 1

Output:
3
45 23 1

Explanations

For the lonely case, N = 5×10⁰ + 4×10¹ + 3×10² + 2×10³ + 1×10⁴ = 12345.
We have: N = 45×100⁰ + 23×100¹ + 1×100². You have to print 3, the number of digits, then the digits: 45, 23 and 1.

Constraints

0 < T <= 50
1 < B1,B2 <= 10^9
1 < k <= 10000
0 <= a_i < B1  , a_k-1>0

Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(13.34*6.97), based on my Python3/Pike experiments.
You may try before the tutorial edition.
Have fun ;-)

Edit(2017-02-11) : With compiler updates, a new time limit is set.
Time limit is sqrt(T_basic_pike_code * T_awaited_python_code) = sqrt(3.93*1.57), based on my Python3/Pike experiments.
Thanks @Blue_Mary for pointing this out.

Submit solution!

hide comments

< Previous 1 2 Next >

	Min_25: 2017-08-24 11:44:04 @liouzhou_101: I often see http://www.spoj.com/comments/all/ to remove/report some comments.
	liouzhou_101: 2017-08-24 05:27:54 @Min_25 Thank you for sharing it. Moreover, I wonder how you can discover my comment so soon?
	Min_25: 2017-08-24 01:02:00 @liouzhou_101: It needs some preparation (cf. https://ideone.com/NLKgGo). (I learned it from some contestants.)
	liouzhou_101: 2017-08-23 18:24:16 @Min_25 How do you use GMP in your C++14 code? I found that simply include GMP can lead to CE.
	Robert Lewon: 2017-04-26 11:17:09 We have announced compiler changes in our blog entry: http://blog.spoj.com/index.php/2017/02/10/the-big-update-more-languages-available-than-ever-before/. Some libraries (like GMP) could become a part of the standard set of libraries in updated versions. The "Clusters" page is now updated. The memory limit remains the same - 1.5GB.
	Michael Kharitonov: 2017-04-25 23:29:46 GMP is avalible?! Since compiler update in February or since even before that? And why cluster is still showing "Intel G860" when it is actually "Intel Xeon E3-1220 v5"? How big is memory limit? =(Francky)=> I've written to admins for a precise answer. Please be patient. Last edit: 2017-10-27 22:09:30
	Min_25: 2017-04-25 22:01:11 My C++14 solution uses GMP. So, the complexity is O(M(k) log(k)). As far as I know, Python and PyPy uses Karatsuba multiplication (O(n^1.59)) for the "" operator and long division (O(n^2)) for the "//" operator. So, O(M(k) log(k)) solutions will run in O(k^2) time with Python if we use builtin operators. Last edit: 2017-04-25 22:02:49*
	Michael Kharitonov: 2017-04-25 19:11:21 Got AC with complexity k^2 per test. Just curious what are the complexities for mentioned solutions in Pike and Python and have anyone wrote klog^2(k) solution. =(Francky)=> I'd say my Python solution is a klog^2(k) (in spirit). In spirit because, I'm not sure about the real speed of the bignum multiplication using Python. If Python use FFT then it's klog^2(k), else it's a bit slower. The basic codes I was referring to is the k^2 solution. I had set the constraints to allow Python AC using this smart method. Maybe Min_25 will answer about his solutions, I will not answer for him. I hope this answer is helpful. Last edit: 2017-04-25 20:05:13*
	[Rampage] Blue.Mary: 2017-02-11 17:34:02 The time limit of this problem should be updated: with updated pike compiler ver 8.0, pike code gets 4-5 times faster. Please do it ASAP. =(Francky)=> Done ; Thanks for your catch. I'll make a turn of all my problems and check if some changes are needed. I found very various speedup coef on the problem I solved. I didn't check too much for my own problems. I still don't know if admins will rejudge or not, or pseudo-rejudge... nor if time_limit could be automatically changed... ??? I should be informed in some days. I'll share. But as consequence, Viplov Jain's solution in Haskell would have TLE (at 4.27s) on rejudge... I hope a fair solution can be found for Haskell. Last edit: 2017-02-11 18:32:35
	Michael Kharitonov: 2017-02-06 09:25:24 Nice problem, maybe you or me should set a hard one with expected complexity klog^2(k) per test. k<=250000; B1,B2<=10^4 is my thought. =(Francky)=> You can set a new edition with harder constraints, for sure ! My todo list is a bit overloaded, and I may be unable to set good constraints as I like, if possible, to write solutions in various languages. Thanks for your ideas. Last edit: 2017-02-06 18:34:53*

Submit solution!

Added by:	Francky
Date:	2014-03-19
Time limit:	2.483s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem