Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- В задаче требуется найти кол-во чисел у которых в двоичном представлении выключенных битов не меньше включенных.( такие числа называются круглыми по условию)
- Ходы решения задачи:
- Ограничения наводят на комбинаторное решение:
- Для начала попробуем посчитать ответ для k вида k = 2^x (x-целое положительное)
- Для таких k ответ будет просто сумма ответов чисел у которых максимальный бит < k
- Рассмотрим числа у которых длина двоичных представлений = n, тогда понятно что нужные нам случаи содержат
- на n - 1 позиций от n/2 + n mod 2 до n - 1 нулей. Для каждого кол ва нулей нужно посчитай кол во вариаций их расположения, а это как раз число сочетаний.
- Тогда ответ для 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)
- Разобьем запрос о кол-ве "круглых" ( в задаче числа нужного множества называются круглыми/round ) <=k на два запроса:
- 1. кол-во круглых чисел <=k у которых максимальный бит меньше максимального бита k
- 2 кол во круглых чисел <=k у которых максимальный бит равен макс биту k
- Напишем функцию нахождения макс бита.
- На первый запрос мы умеем отвечать.
- 2 запрос:
- переформулируем задачу: нужно найти кол во лексикографически меньших либо равных строк той же длины(строка это битовое представление числа k), у которых кол-во нулей больше кол-ва единиц и все строки без лидирующих нулей
- Напомню cтрока a лексикографически меньше другой строки если a(i)<b(i) раньше встретится чем a(i)<b(i)
- Тогда для каждого вхождения 1-бита, за исключением лидирующего, достаточно посчитать число строк
- если бы вместо 1 стоял 0 в i-ом бите и после него следовал набор нулей удовлетворяющий условию задачи
- Заметим что можно не проходится каждый раз по числу сочетаний, предварительно предподсчитав преффикс суммы, но т к в данном случае это работает за константное время то можно ничего не менять.
- */
- function init_C(c: int[][], N: int) {
- for(let i = 0; i < N; i += 1){
- c.push([]);
- for(let j = 0; j < N; j += 1){
- c[i].push(0);
- }
- }
- for(let i = 0; i < N; i += 1){
- c[i][0] = 1;
- }
- for(let i = 1; i < N; i += 1){
- for(let j = 1; j <= i; j += 1){
- c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
- }
- }
- }
- function max(a: int, b: int)->int{
- if(a > b) {
- return a;
- }
- return b;
- }
- function get_bit(x: int, i: int) -> int{
- let bit: int = ((x >> i) & 1);
- return bit;
- }
- function find_max_bit(x: int) -> int{
- let res: int = 0;
- for(let i = 31; i >= 0; i -= 1) {
- if(get_bit(x, i) == 1){
- res = i;
- break;
- }
- }
- return res;
- }
- function solve(input: string) -> string {
- let c: int[][] = [];
- let N: int = 32;
- init_C(c, N);
- let line = input.split("\n");
- let k = int(line[0]);
- let fst_bt: int = find_max_bit(k);
- let ans: int = 0;
- for(let n = 1; n < fst_bt; n += 1) {
- let mn_zero: int = (n + 1)/2 + (n + 1) % 2;
- for(let i = mn_zero; i <= n; i += 1){
- ans += c[n][i];
- }
- }
- let need_zero: int = (fst_bt + 1)/2 + (fst_bt + 1) % 2;
- for(let i = fst_bt - 1; i >= 0; i -= 1) {
- if(get_bit(k, i) == 0) {
- need_zero -= 1;
- }
- else {
- let need: int = max(0, need_zero - 1);
- if(need > i) {
- break;
- }
- for(let j = need; j <= i; j += 1){
- ans += c[i][j];
- }
- }
- }
- if(need_zero <= 0) {
- ans += 1;
- }
- let out: string = "";
- out+="There are ";
- out+=string(ans);
- out+=" round numbers less than or equal to ";
- out+=string(k);
- out+=".";
- return out;
- }
Advertisement
Add Comment
Please, Sign In to add comment