Sum of cubes Please,help.

# | User | Rating |
---|---|---|

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 195 |

4 | vovuh | 189 |

5 | Um_nik | 186 |

5 | antontrygubO_o | 186 |

7 | pikmike | 185 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

Sum of cubes Please,help.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2020 18:45:37 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

isn't it just dp? suppose dp[i] denotes the minimum number such that the sum of cubes of its digits is i. Then, dp[n]=min(add a digit 9 to left of dp[n-729], add a digit 8 to left of dp[n-512],...,add digit 1 to left of dp[n-1]). This, of course, requires some edge cases. eg. dp[1]=1(base case 1). dp[2]=min(add 1 to left of dp[1])=11. It needs 9*n operations so it is O(n).

Code?

Why do you need a code? I believe that the logic is good enough. I think the code to this would be short and easy. You should give it a try yourself. Or maybe you can ask if you are having a problem somewhere in your own code. Asking for help is one thing and just relying on others is another thing. Please try to understand. I am not discouraging you from asking though.