Special Square Number
All submissions for this problem are available.
A special square number is a number containing the digits 0-9 such that 0 can occur any number of times while the other digits 1-9 must occur squared times. E.g. 1 must occur 1x1 times, 2 must occur 2x2 times… 9 must occur 9x9 times. The digits may be ordered in any way and it need not be the case that the all same digits be consecutive. Some examples of special square numbers are 1, 12222, and 301333333223322.
Your task is to accept a number and convert it into a special square number containing all the digits that exist in the input number i.e. if the input number has only digits 1 and 2 , the special square number must contain only the digits 1 and 2. Care must be taken that the same no. of zeros appear in the special square number after conversion as in the original number. You can perform the following operations each having a particular cost.
- Replace an existing digit with another cost: 1
- Add a new digit cost: 4
- Delete an existing digit cost: 8
You are required to write a program in such a way that the input number must be converted into a special square number with minimum cost using any operations.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows"
- A single integer N for each test case
T lines giving minimum cost for conversion of each N to corresponding special square number in order of test cases.
- 1 ≤ T ≤ 10
- 1 ≤ (no. of digits in N) ≤ 1000
Input: 3 1 1122 333033322222223 Output: 0 5 10
First line of input specifies that there are 3 test cases. The next 3 lines which follow each input a number.
For 1, the minimum cost is 0 as it already is a special square number.
For 1122, a 1 is extra while we need two more 2s. So the minimum cost is obtained if we replace a 1 by 2 (cost 1) and add an extra 2 (cost 4). So, minimum cost 5 is output.
For 333033322222223, there can be any no. of zeroes. There are seven 3s and seven 2s. So, we replace two 2s by 3s (cost 2x1) and delete a 2 (cost 8). So, minimum cost is 10.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.