Statistics

Problem Statement for "Deadfish"

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.

Definition

Class:
Deadfish
Method:
shortestCode
Parameters:
int
Returns:
int
Method signature:
int shortestCode(int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 200,000, inclusive.

Examples

  1. 3

    Returns: 3

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

  2. 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.

  3. 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.

  4. 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.

  5. 200000

    Returns: 207

  6. 199363

    Returns: 462

    max test

  7. 72

    Returns: 7

  8. 32

    Returns: 8

  9. 50

    Returns: 7

  10. 90

    Returns: 9

  11. 27

    Returns: 7

  12. 6

    Returns: 5

  13. 43

    Returns: 8

  14. 16

    Returns: 4

  15. 8

    Returns: 5

  16. 447

    Returns: 15

  17. 743

    Returns: 13

  18. 487

    Returns: 12

  19. 813

    Returns: 13

  20. 220

    Returns: 10

  21. 854

    Returns: 10

  22. 124

    Returns: 10

  23. 930

    Returns: 12

  24. 325

    Returns: 8

  25. 553

    Returns: 8

  26. 5898

    Returns: 41

  27. 4161

    Returns: 49

  28. 1821

    Returns: 37

  29. 4204

    Returns: 14

  30. 9012

    Returns: 22

  31. 4364

    Returns: 17

  32. 7598

    Returns: 16

  33. 1546

    Returns: 35

  34. 2241

    Returns: 32

  35. 5567

    Returns: 27

  36. 11845

    Returns: 46

  37. 27035

    Returns: 153

  38. 41936

    Returns: 79

  39. 37210

    Returns: 50

  40. 43002

    Returns: 18

  41. 25149

    Returns: 151

  42. 47712

    Returns: 201

  43. 74339

    Returns: 23

  44. 88257

    Returns: 50

  45. 92879

    Returns: 143

  46. 161456

    Returns: 160

  47. 154845

    Returns: 407

  48. 171731

    Returns: 351

  49. 162069

    Returns: 353

  50. 116630

    Returns: 354

  51. 145491

    Returns: 359

  52. 137272

    Returns: 388

  53. 40595

    Returns: 207

  54. 131073

    Returns: 39

  55. 199487

    Returns: 338

  56. 5555

    Returns: 15

  57. 199999

    Returns: 206

  58. 159678

    Returns: 332

  59. 14

    Returns: 6

  60. 78965

    Returns: 19

  61. 49729

    Returns: 9

  62. 166788

    Returns: 338

  63. 111321

    Returns: 236

  64. 66553

    Returns: 7

  65. 3362

    Returns: 11

  66. 141334

    Returns: 66

  67. 30

    Returns: 9

  68. 225

    Returns: 6

  69. 87

    Returns: 9

  70. 60

    Returns: 6

  71. 139

    Returns: 13

  72. 421

    Returns: 9

  73. 59

    Returns: 7

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: