Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Circuit 101

By jackal_1586 · Limits 8s, 512 MB

Calculating equivalent resistance is the basic knowledge for solving any circuit related problems. Solving these problems always involve some resistors with fixed resistance. But in reality, that’s never possible due to thermal and manufacturing issues. Thus any resistor is provided with a tolerance level to account for the manufacturing issues. In other words, every resistor has a certified lower and upper bound of the resistance at standard temperature. Now, you are given n resistors with separate lower and upper bounds. After connecting them in series, what would the probability of getting equivalent resistance equal to x? For simplicity, we will consider that resistance can only be positive integers and probability of getting any value of resistance within the bound is equal.


First line of the input contains two integers n (0 < n ≤ 100) and q (0 < q ≤ 105) where n represents the number of resistors and q for number of queries. Each of the next n line contains two integers l and r (0 < l ≤ r ≤ 50000) representing lower and upper bound of the resistors. Next q line each contains an integer x (0 < x ≤ 105), the desired value of equivalent resistance.


For each query find P(x), probability of getting x as equivalent resistance. P(x) can be written as a/b where a and b are integers. Print P(x) modulo 1000003.


2 3
1 3
1 2

Formula to calculate equivalent resistance of n resistors connected in series, Req = R1 + R2 + R3 …. + Rn.



    76% Solution Ratio

    imranziadEarliest, Jan '17

    sahedsohelFastest, 89572.3s

    akash.kuetLightest, 1.6 MB

    RHaqueShortest, 1302B


    Login to submit


    Probability P(x) can be defined as a/b, where a = number of ways x can be made and b = number of all...

    Related Contests