Connection Status:
Competition Arena > Deadfish

Deadfish

TCO18 Fun 1A · 2018-04-20 · by Nickolas

TCO18 Fun 1A · 2018-04-20 · by Nickolas · Dynamic Programming
Class Name: Deadfish
Return Type: int
Method Name: shortestCode
Arg Types: (int)
Problem Statement

Problem Statement

Deadfish+ is a programming language with only 4 commands. All commands modify a single register. The register is initially set to zero, and during the execution of a program it can store an arbitrarily large integer value. The commands are:
  • "i" - increment the value,
  • "d" - decrement the value,
  • "s" - square the value, and
  • "p" - sort the digits of the number into non-increasing order (i.e., biggest to smallest).

For example, "p" changes 4070 to 7400, and it changes -4070 to -7400 (the minus sign is preserved).

You are given an int N. Return the minimal number of commands necessary to make the register hold the number N.

Constraints

  • N will be between 1 and 200,000, inclusive.
Examples
0)
3
Returns: 3

The fastest way to get to 3 is "iii" - three increments.

1)
5
Returns: 4

One fastest way to get a 5 is "iisi": two increments to get a 2, square to get a 4 and one more increment. Another optimal way is "ddsi": two decrements change the register to -2, squaring that gives 4, and the final increment changes it to 5.

2)
15
Returns: 5

The fastest way to get 15 is "iissd". The value in the register will change as follows: 0, 1, 2, 4, 16, 15.

3)
61
Returns: 5

The fastest way to get 61 is "iissp". The value in the register will change as follows: 0, 1, 2, 4, 16, 61.

4)
200000
Returns: 207
5)
199363
Returns: 462

max test

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

Coding Area

Language: C++17 · define a public class Deadfish with a public method int shortestCode(int N) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous