Codeforces 977D Editorial

Правка en2, от aMitkvikram, 2018-05-07 16:37:18

977D — Divide by three, multiply by two

  1. We can see that all numbers in given sequence are distinct. since all numbers in sequence are of the form . Hence if ai = aj then = = \dfrac{2^m}{3^n}$ which is not possible because any power of 2 will be an even number and any power of 3 will be an odd number.

  2. if there exists in sequence then 2$a_i$ can not be in sequence and vice versa. We can prove it using contradiction. Suppose there is a number ai such that both

    Unable to parse markup [type=CF_TEX]

    exists in sequence. by little bit of tricks this = , this again is not possible by same argument as above, we just have to change the order of exponents.
  3. Hence for each ai in sequence we see if or 2$a_i$ is present(remember that only one of them can be present). Now if there is any ai such that both and 2$a_i$ is not in sequence then this shoudld be an. if there is any such ai that for all 0$\leq$ j \leq$  ≠  ai AND 2$a_i$  ≠  ai, then this a1.

  4. Once you have got a1 you keep on producing sequence just by doing binary search for and 2$a_i$ (remember only one of them is present so once you find it you print it).

Теги dfs and similar, #sorting, #binary search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский aMitkvikram 2018-06-21 20:00:24 13
en10 Английский aMitkvikram 2018-06-21 19:59:23 14
en9 Английский aMitkvikram 2018-06-21 19:58:14 46 Tiny change: '^m}{3^n}$ which is n' -> '^m}{3^n}$ $\implies$ $2^{x - m} = 3^{y - n}$which is n'
en8 Английский aMitkvikram 2018-05-07 16:44:43 2 (published)
en7 Английский aMitkvikram 2018-05-07 16:43:12 2 Tiny change: 'eq$ $j\leq$ $\dfrac{' -> 'eq$ $j\leqn:$ $\dfrac{'
en6 Английский aMitkvikram 2018-05-07 16:42:31 5
en5 Английский aMitkvikram 2018-05-07 16:41:49 3 Tiny change: 'l $0\leq$ j $ $\leq$ $\' -> 'l $0\leq$ $j $\leq$ $\'
en4 Английский aMitkvikram 2018-05-07 16:41:03 17
en3 Английский aMitkvikram 2018-05-07 16:39:32 5
en2 Английский aMitkvikram 2018-05-07 16:37:18 1244 Tiny change: 'n4. Once yuou have go' -> 'n4. Once you have go'
en1 Английский aMitkvikram 2018-05-07 16:17:24 339 Initial revision (saved to drafts)