Do you think the TA would be that nice to show you the solution at the title? Well, who knows XDDDD, you decide!!
Anyway, in this problem we are to find the optimal strategy in a single-player game, called "the Dao of Multiples and Factors" (倍因道). The rule is as followed:
In the integers from 1 to N, you can choose to categorize each number as either "FACTOR" or "MULTIPLE".
Those categorized as "FACTOR" does not gain points themselves, but of course, it has its own use, as will be seen shortly; Those categorized as "MULTIPLE" (says some number M), gain points that equal to the number of factors that divide M, and is categorized as "FACTOR".
So for example, suppose the numbers 1,2,5 are categorized as "FACTOR", 3,4,6,7,8,9,10 are categorized as "MULTIPLE", then the total score is 1+2+2+1+2+1+3=12.
Now given N, find the maximum score you could obtain!!!
First line contains an integer t, indicating the number of testcases. Then follows t testcases, each with an integer N specified.
For each testcase, output the maximum score that could be obtained.
2 1 6
0 6
This series of homework are all problems with ungiven input size! It is (at least the original aim of it is) to enable us to acutally think about a problem from scratch, without the "additional informations" implicated by a specific given problem size.
Of course, we do hope it'd be a rather fun experience, since in real life problems often we do not know whether a problem exhibits an efficient algorithm or is even solvable!!
Anyway, the input size, though not specified, will be "reasonable". That is, if the optimal algorithm is O(n3), then n would be something like 300, if O(nlgn), then perhaps 200000.. etc. Also if values are not otherwise specified, they could be expected to be for example, int.
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|