c - Having trouble understanding a portion of code -


i have problem:

you have n problems. have estimated difficulty of i-th 1 integer ci. want prepare problemset contest, using of problems you've made.

a problemset contest must consist of @ least 2 problems. think total difficulty of problems of contest must @ least l , @ r. also, think difference between difficulties of easiest , hardest of chosen problems must @ least x.

find number of ways choose problemset contest.

input first line contains 4 integers n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) — number of problems have, minimum , maximum value of total difficulty of problemset , minimum difference in difficulty between hardest problem in pack , easiest one, respectively.

the second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 106) — difficulty of each problem.

output print number of ways choose suitable problemset contest.

i tried solve unfortunately couldn't it. asked friend give me idea , solved me don't understand something:

code:

#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. why going through array till i<(1<<n) if got n elements?

  2. why this: if((i>>j)&1) ?

i know 1<<n equivalent of multiplying power of 2 , 1>>n equivalent integer division 2^n makes no sense here.

you have n possible problems, , each 1 can either included or excluded problem set. means there 2 options every problem, n problems there 2^n options creating possible problem sets.

with line for(i=0; i<(1<<n); i++) iterating these possible problems sets, each 1 identified integer between 0 , 2^n - 1. next, need identify problems belong problem set, , have integer represents it.

to that, take binary representation of integer. have n bits, , lets each bit corresponds problem: if 1 problem included, otherwise not. line if((i>>j)&1) doing: checks if bit in position j inside integer i equal 1, means corresponding problem included.

the rest easier: included problems, calculate minimum, maximum, , sum. then, check if sum s in valid range, , if difference between maximum , minimum @ least x.


Comments

Popular posts from this blog

twig - Using Twigbridge in a Laravel 5.1 Package -

jdbc - Not able to establish database connection in eclipse -

firemonkey - How do I make a beep sound in Android using Delphi and the API? -