Transformation

SRM 391 · 2008-02-26 · by stone

SRM 391 · 2008-02-26 · by stone · Math

Show categories

Class Name: Transformation

Return Type: String[]

Method Name: transform

Arg Types: (vector<string>)

Problem Statement

You are to transform a positive integer vector (A₁,A₂,...,A_n) into another positive integer vector (B₁,B₂,...,B_n) of the same length. The transformation must satisfy the conditions below:
1) For 1 &lt = i &lt =n., B_i must evenly divide into A_i.
2) The least common multiple of all A_i should be equal to that of all B_i.

You are given the original integer vector as a String[] A, where the i-th (1-based) element is a positive integer representing A_i. Return a String[] containing the transformed integer vector in the same format. Each element of the return String[] must be a positive integer with no leading zeroes. If there are multiple solutions, return the one where the first number is the smallest. If there are still multiple solutions, return the one with the smallest second number etc.

Notes

The least common multiple of a group of positive integers is the least positive integer which is a multiple of every integer in the group.

Constraints

A will contain between 1 and 50 elements, inclusive.
Each element of A will contain digits ('0' - '9') only.
Each element of A will represent a positive integer without leading zeros.
Each element of A will contain between 1 and 18 characters, inclusive.

Examples

{"1","2"}
Returns: {"1", "2" }

{"2","2"}
Returns: {"1", "2" }

{"1","3","6"}
Returns: {"1", "1", "6" }

{"2","3","6"}
Returns: {"1", "1", "6" }

{1,1,6},{1,3,2},{1,3,6},{2,1,3},{2,1,6},{2,3,1},{2,3,2},{2,3,3},{2,3,6} are all transformation results.

{"210","2","3","5","7"}
Returns: {"1", "2", "3", "5", "7" }

Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Transformation with a public method vector<string> transform(vector<string> A) · 143 test cases · 2 s / 256 MB per case