That combobreaker will also come soon :)

i cannot see a E Accepted by you either div2 or div1 :D

Look at ur poor rating, WOW such a idiot! Do you think you "Expert" have the right to scold me?

Is it the last IOI that you can participate? If you were born in 1997 according to you id, you may participate in ACM-ICPC next year~

cool)

This seems familiar to me, may you name the teacher?

Is your teacher name َ"Ali Ghasaab" :)? He knows me very well :) give my regards to my best ever teacher...

It reminds me of a theory like this: every number can be named not more than 50 chars. The proof is similar: if there exists a number that cannot be named less than chars, it can be named as "The first number cannot be named in 50 chars". It is 44-chars name.

256؟؟

ну у меня еще иф стоял на k == 1 xD

Вот да.

Только увидев этот комментарий (в точности описывающий мое решение), понял, что есть такой контртест. Чего же тогда в моей комнате ноль взломов? Наверно, довольно популярный баг.

Yes, you are right. Maybe this is not the intended way. Now I too am confused.

you can consider only the edges that connect a smaller number to a bigger one (not vice-versa)

Here's a quick proof:

Clearly we cannot do anything with primes greater than . (Let be a prime, then it can only be matched with an apple with number at least 2p. But 2p > n. So we cannot match p.) We can't do anything about 1 either, and if there are an odd number of apples remaining, we must remove one (since all groups have two apples and thus the total number of apples used is even). My solution makes sure that all the remaining apples are matched, which due to the above proof, is maximum.

My solution works as follows:

• Generate all primes below n and reverse the order, so we process from the largest prime.
• For each prime p > 2, observe the apples p, 2p, 3p, ..., kp where kp ≤ n < (k + 1)p. We ignore all apples that have been used before. Now, greedily take the two apples with largest numbers together.
• In the case we are left with a single apple p, then observe that 2p must be used in the previous group. Replace it with p, so we keep 2p to be used later in the final pass.
• Finally, for prime p = 2, we greedily match every even apples remaining.

It shouldn't be hard to see that all apples not in the form 2p or 2^k are used in step 2, and all remaining apples (except probably one) that are not used in step 2 are used in step 4.

Thanks! I think that's because the problems I did fit with my ability, and the remaining problems I didn't do are hard enough that not many other people did those. :P