Hi, I have no idea how to solve this problem. can anyone help me?
# | User | Rating |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | maroonrk | 154 |
5 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | pajenegod | 144 |
Hi, I have no idea how to solve this problem. can anyone help me?
Name |
---|
Every positive number can be represented as a form like this: 2^x * 3^y * z, where z is not divisible by 2 and 3.
Let's suppose that n = 2^x * 3^y * z. Then we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.
Now, let's define a plane P[z]. For each number 2^x * 3^y * z, draw a point in P[z]. Then, the problem will be solvable :)
Sorry for the poor English.
We can have 2n and 3n in set S if we didn't include n in set S.
can you code your idea please to make me understand your idea very well.
Sorry for my mistake..
Let's suppose that
n = 2^x * 3^y * z
. (wherez
is not divisible by 2 and 3) If we includen
in setS
, we cannot have2n = 2^(x+1) * 3^y * z
and3n = 2^x * 3^(y+1) * z
in setS
.Let's define a plane
P[z]
wherez
is not divisible by 2 and 3. For each positive integeri = 2^x * 3^y * z (<= N)
, draw a point(x, y)
atP[z]
.If we select the point
(x, y)
inP[z]
, then we cannot select the point(x+1, y)
and(x, y+1)
inP[z]
. So the problem is: how many ways can we choose points such that the condition above is satisfied?The value of
x
andy
are very small, so we can do this in DP.Good idea, but how to do this in DP effectively, notice that we have n/3 numbers less than n that not divisible by 2 and 3 and we have 500 test cases per input.
You can use bitmasks.. It needs more complex solution than just bitmasking. Think about it :)