Home>
while True:
    n, x = map (int, input (). split ())
    if n == x == 0:
        break
    cnt = 0
    for a in range (1, x // 3):
        for b in range (a + 1, x // 2):
            c = x --a --b
            if b<c<= n:
                cnt + = 1
    print (cnt)


The above code is the code that came out by googled the solution of the problem of AIZU ONLINE JUDGE.

Number of combinations
From the numbers from 1 to n, select 3 numbers without duplication and create a program to find the number of combinations whose sum is x.
For example, a combination of 3 numbers from 1 to 5 that add up to 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are two ways.
Input
Multiple datasets are given as input. For each dataset, whitespace-separated n, x are given on one line.
When both n and x are 0, the input ends.
Constraints
3 ≤ n ≤ 100
0 ≤ x ≤ 300
Output
For each dataset, output the number of combinations on one line.


I think it's very compact and amazing, but I don't understand why cnt is incremented when "b I would appreciate it if you could tell me.

  • Answer # 1

    I don't understand why cnt is incremented when "b

    aThe value of1From "Total valuexWhile changing to a number smaller than one-third of

    bThe value ofa + 1From "Total valuexWhile changing to a number less than half of

    Obtained by calculation (x --a --b)cThe value ofbLarger andnIs

    Then the total isxCombination to bea, b, cBecause you have found a pair.

    Supplement:

    From the numbers from 1 to n, select 3 numbers without duplication and the number of combinations whose sum is x

    Choosing three numbers from integers from 1 to n (not explicitly stated in the question sentence, but sure from the following sentences and examples) without duplication

    Since each of the three integers is different, a magnitude relationship holds.

    about it. So, in the blog that presents the solution,

    Each of the three unique integersa,b,cTo

    For convenience,aSuppose that the relationship of

    It is said. In other words, the smallest of the three integersa, The second smallest oneb, The third smallestcTreat as.

    ThenaIs "at least the total valuexIt is less than one-third of. " BecauseaAnd bigger than thatbOrcAnd the totalxBecause it has to be (if you allow duplication, the total valuexOne-third ofaIs the upper limit of).

    bThe value ofaMust be greater than the value ofxFromaIt also needs to be less than half the number minus the value of. BecausebAnd bigger than thatcThe total with and is "total valuexFromaThis is because it must be "the number obtained by subtracting the value of" (if duplication is allowed, the total valuexFromaHalf of the number minus the value ofbIs the upper limit of).

    cThe value of is "total valuexFromaWith the value ofbIt is calculated by "the number obtained by subtracting the value of".bNeed to be larger, yetnMust be:

    To search for the above efficientlyrangeSpecify a range of integers with, and when the condition is met (initial value 0)cntIncrease by 1 to get the final number of combinations.

    cnt + = 1Indented the same amount on the line immediately afterprint (f "{a} {b} {c}")If you try adding, the combinations found will be displayed, which will give you a better understanding.

  • Answer # 2

    The point is that the three numbers are a for the smallest number, b for the next number, and c for the largest number.
    Then, if a and b are changed, c is sought and it is checked whether it is within n.

    When a and b are decided, c = x-a-b and c are decided.
    If c is greater than b and less than or equal to n, it is valid.

    Since a is the smallest number, adding the remaining b and c will increase it by at least 3 times.
    Checking up to 1/3 of x is sufficient.
    If b is less and c larger than b is added, it will be doubled, so checking up to 1/2 of x is sufficient.

    Separately, you can check a from 1 to x and b from a + 1 to x, but for the above reason, if a, there is nothing that exceeds 1/3.

Trends