ivnikkk

Untitled

Jul 19th, 2022
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.08 KB | None | 0 0
  1. /*
  2. В задаче требуется найти кол-во чисел у которых в двоичном представлении выключенных битов не меньше включенных.( такие числа называются круглыми по условию)
  3. Ходы решения задачи:
  4. Ограничения наводят на комбинаторное решение:
  5. Для начала попробуем посчитать ответ для k вида k = 2^x (x-целое положительное)
  6. Для таких k ответ будет просто сумма ответов чисел у которых максимальный бит < k
  7. Рассмотрим числа у которых длина двоичных представлений = n, тогда понятно что нужные нам случаи содержат
  8. на n - 1 позиций от n/2 + n mod 2 до n - 1 нулей. Для каждого кол ва нулей нужно посчитай кол во вариаций их расположения, а это  как раз число сочетаний.
  9. Тогда ответ для n  left = n/3 +n mod 2, right = n - 1,   SUM (from i = left in  right) C_n - 1_ i   (C_n_k - число сочетаний из n по k)
  10. Разобьем запрос о кол-ве "круглых" ( в задаче числа нужного множества называются круглыми/round ) <=k на два запроса:
  11. 1. кол-во круглых чисел <=k у которых максимальный бит меньше максимального бита k
  12. 2 кол во круглых чисел <=k у которых максимальный бит равен макс биту k
  13.  
  14. Напишем функцию нахождения макс бита.
  15. На первый запрос мы умеем отвечать.
  16. 2 запрос:
  17. переформулируем задачу: нужно найти кол во лексикографически меньших либо равных строк той же длины(строка это битовое представление числа k), у которых кол-во нулей больше кол-ва единиц и все строки без лидирующих нулей
  18. Напомню cтрока a лексикографически меньше другой строки если  a(i)<b(i) раньше встретится чем a(i)<b(i)
  19.  
  20. Тогда для каждого вхождения 1-бита, за исключением лидирующего, достаточно посчитать число строк
  21. если бы вместо 1 стоял 0 в i-ом бите и после него следовал набор нулей удовлетворяющий условию задачи
  22. Заметим что можно не проходится каждый раз по числу сочетаний, предварительно предподсчитав преффикс суммы, но т к в данном случае это работает за константное время то можно ничего не менять.
  23.  
  24. */
  25.  
  26. function init_C(c: int[][], N: int) {
  27.     for(let i = 0; i < N; i += 1){
  28.         c.push([]);
  29.         for(let j = 0; j < N; j += 1){
  30.             c[i].push(0);
  31.         }
  32.     }
  33.    
  34.     for(let i = 0; i < N; i += 1){
  35.         c[i][0] = 1;
  36.     }
  37.    
  38.     for(let i = 1; i < N; i += 1){
  39.         for(let j = 1; j <= i; j += 1){
  40.             c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  41.         }
  42.     }
  43. }
  44.  
  45. function max(a: int, b: int)->int{
  46.     if(a > b) {
  47.         return a;
  48.     }
  49.     return b;
  50. }
  51.  
  52. function get_bit(x: int, i: int) -> int{
  53.     let bit: int = ((x >> i) & 1);
  54.     return  bit;
  55. }
  56.  
  57. function find_max_bit(x: int) -> int{
  58.     let res: int = 0;
  59.     for(let i = 31; i >= 0; i -= 1) {
  60.         if(get_bit(x, i) == 1){
  61.             res = i;
  62.             break;
  63.         }
  64.     }
  65.     return res;
  66. }
  67.  
  68. function solve(input: string) -> string {
  69.     let c: int[][] = [];
  70.     let N: int = 32;
  71.     init_C(c, N);
  72.    
  73.     let line = input.split("\n");
  74.     let k = int(line[0]);
  75.    
  76.     let fst_bt: int = find_max_bit(k);
  77.     let ans: int = 0;
  78.    
  79.     for(let n = 1; n < fst_bt; n += 1) {
  80.         let mn_zero: int = (n + 1)/2 + (n + 1) % 2;
  81.         for(let i = mn_zero; i <= n; i += 1){
  82.             ans += c[n][i];  
  83.         }
  84.     }
  85.    
  86.     let need_zero: int = (fst_bt + 1)/2 + (fst_bt + 1) % 2;
  87.    
  88.     for(let i = fst_bt - 1; i >= 0; i -= 1) {
  89.         if(get_bit(k, i) == 0) {
  90.             need_zero -= 1;
  91.         }
  92.         else {
  93.             let need: int = max(0, need_zero - 1);
  94.             if(need > i) {
  95.                 break;  
  96.             }
  97.             for(let j = need; j <= i; j += 1){
  98.                 ans += c[i][j];  
  99.             }
  100.         }
  101.     }
  102.     if(need_zero <= 0) {
  103.         ans += 1;
  104.     }
  105.     let out: string = "";
  106.     out+="There are ";
  107.     out+=string(ans);
  108.     out+=" round numbers less than or equal to ";
  109.     out+=string(k);
  110.     out+=".";
  111.     return out;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment