Имея проблемы с пониманием части кода

Question

У меня есть эта проблема:

У вас есть п проблема. Вы оценили трудность i-го как целого числа ci. Теперь вы хотите подготовить набор проблем для конкурса, , используя некоторые из проблем, которые вы сделали.

Задача конкурса должна состоять как минимум из двух проблем. Вы считаете, что общая сложность проблем конкурса должна быть не менее l и не более r. Кроме того, вы считаете, что разница между трудностями самого простого и сложного из выбранных задач должна быть не менее x.

Найдите количество способов выбрать набор проблем для конкурса.

Входные данные Первая строка содержит четыре целых числа N, L, R, X (1 ≤ N ≤ 15, 1 ≤ L ≤ R ≤ 109, 1 ≤ х ≤ 106) - количество проблем, которые вы имеете, минимальное и максимальное значение общей сложности набора проблем и минимальная разница в сложности между самой сложной проблемой в пакетом и самой простой.

Вторая строка содержит n целых чисел c1, c2, ..., cn (1 ≤ ci ≤ 106) - трудность каждой проблемы.

Выход Напечатать количество способов выбрать подходящий набор проблем для конкурс.

Я попытался решить проблему, но, к сожалению, я не мог этого сделать. Я попросил друга, чтобы дать мне идею, и он решил ее для меня, но я не понимаю, что-то:

Код:

#include <stdio.h> 
int a[25], l, r, x, i, j, n, ans; 
int main(){ 
    scanf("%d %d %d %d", &n, &l, &r, &x); 
    for(i=0; i<n; i++) scanf("%d", &a[i]); 
    for(i=0; i<(1<<n); i++){ 
     int s = 0; 
     int max = 0, min = 1e9; 
     for(j=0; j<n; j++){ 
      if((i>>j)&1){ 
       if(a[j] > max) max = a[j]; 
       if(min > a[j]) min = a[j]; 
       s += a[j]; 
      } 
     } 
     if(l <= s && s <= r && max-min >= x) ans++; 
    } 
    printf("%d", ans); 
    return 0; 
} 

1. Почему он проходит через этот массив до i<(1<<n), если он только получили n элементов?

2. Почему он это делает: if((i>>j)&1)?

Я знаю, что 1<<n является эквивалентом умножения на степени двойки и 1>>n эквивалентно целочисленное деление на 2^п, но это не имеет никакого смысла здесь.

Answer 1

У вас есть возможные проблемы, и каждый из них может быть включен или исключен из набора проблем. Это означает, что есть две возможности для каждой проблемы, поэтому с n проблемами есть 2^n опций для создания возможных наборов проблем.

С помощью строки for(i=0; i<(1<<n); i++) вы выполняете итерацию всех этих возможных наборов задач, каждая из которых идентифицируется целым числом от 0 до 2^n - 1. Далее нам нужно определить, какие проблемы принадлежат определенному набору проблем, и мы имеем целое число, которое представляет его.

Для этого мы берем двоичное представление этого целого числа. Он будет иметь n бит и позволяет сказать, что каждый бит соответствует проблеме: если он равен 1, тогда проблема включена, иначе это не так.Это то, что делает линия if((i>>j)&1): она проверяет, находится ли бит в позиции j внутри целого числа i, что означает, что соответствующая проблема включена.

Остальное проще: из всех включенных проблем вы вычисляете минимум, максимум и сумму. Затем проверьте, находится ли сумма s в допустимом диапазоне, и если разница между максимумом и минимумом составляет не менее x.