CCC '13 S5 - Factor Solitaire - DMOJ: Modern Online Judge

CCC '13 S5 - Factor Solitaire

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

Canadian Computing Competition: 2013 Stage 1, Senior #5

In the game of Factor Solitaire, you start with the number $1$ $1$ , and try to change it to some given target number $n$ $n$ by repeatedly using the following operation. In each step, if $c$ $c$ is your current number, you split it into two positive factors $a$ $a$ , $b$ $b$ of your choice such that $c = a \times b$ $c = a \times b$ . You then add $a$ $a$ to your current number $c$ $c$ to get your new current number. Doing this costs you $b$ $b$ points.

You continue doing this until your current number is $n$ $n$ , and you try to achieve this at the cost of a minimum total number of points.

For example, here is one way to get to $15$ $15$ :

start with $1$ $1$
change $1$ $1$ to $1+1 = 2$ $1 + 1 = 2$ — cost so far is $1$ $1$
change $2$ $2$ to $2+1 = 3$ $2 + 1 = 3$ — cost so far is $1+2$ $1 + 2$
change $3$ $3$ to $3+3 = 6$ $3 + 3 = 6$ — cost so far is $1+2+1$ $1 + 2 + 1$
change $6$ $6$ to $6+6 = 12$ $6 + 6 = 12$ — cost so far is $1+2+1+1$ $1 + 2 + 1 + 1$
change $12$ $12$ to $12+3 = 15$ $12 + 3 = 15$ — done, total cost is $1+2+1+1+4=9$ $1 + 2 + 1 + 1 + 4 = 9$ .

In fact, this is the minimum possible total cost to get $15$ $15$ . You want to compute the minimum total cost for other target end numbers.

Input Specification

The input consists of a single integer $N \ge 1$ $N \geq 1$ . In at least half of the cases $N \le 50\,000$ $N \leq 50 000$ , in at least another quarter of the cases $N \le 500\,000$ $N \leq 500 000$ , and in the remaining cases $N \le 5\,000\,000$ $N \leq 5 000 000$ .

Output Specification

Compute the minimum cost that gets you to $N$ $N$ .

Sample Input 1

Copy

Output for Sample Input 1

Copy

Sample Input 2

Copy

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

For example, start with $1$ $1$ , then get to $2$ $2$ , $4$ $4$ , $5$ $5$ , $10$ $10$ , $15$ $15$ , $30$ $30$ , $60$ $60$ , $61$ $61$ , $122$ $122$ , $244$ $244$ , $305$ $305$ , $610$ $610$ , $671$ $671$ , $1342$ $1342$ , and then $2013$ $2013$ .

Comments

-3

thunder200911133 commented on June 26, 2024, 12:37 a.m.

Can the factors be decimal?

2

nitishjoson83 commented 80 days ago

In mathematics, a factor is: A positive integer that can divide another number evenly. A number that is an exact divisor of another number, leaving no remainder. Each number is a factor of itself. A prime number has only two factors: the number itself and 1 Hope that helps!

15

HyperGraphJ commented on July 6, 2020, 8:38 p.m. ← edit 4 →

In comments of my solution, I sketch a proof that gives description to all possible sequences of moves that will achieve minimum cost and derives an algebraic identity satisfied by the cost function which suggests the considerably different algorithm that I implement.

14

d3story commented on June 5, 2020, 4:17 p.m.

hint! back is the way to go!!!