Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

In Berland each high school student is characterized by academic performance — integer…

  1. User

    In Berland each high school student is characterized by academic performance — integer value between 1 and 5.

    In high school 0xFF there are two groups of pupils: the group A and the group B. Each group consists of exactly n students. An academic performance of each student is known — integer value between 1 and 5.

    The school director wants to redistribute students between groups so that each of the two groups has the same number of students whose academic performance is equal to 1, the same number of students whose academic performance is 2 and so on. In other words, the purpose of the school director is to change the composition of groups, so that for each value of academic performance the numbers of students in both groups are equal.

    To achieve this, there is a plan to produce a series of exchanges of students between groups. During the single exchange the director selects one student from the class A and one student of class B. After that, they both change their groups.

    Print the least number of exchanges, in order to achieve the desired equal numbers of students for each academic performance. Input

    The first line of the input contains integer number n (1 ≤ n ≤ 100) — number of students in both groups.

    The second line contains sequence of integer numbers a1, a2, ..., an (1 ≤ ai ≤ 5), where ai is academic performance of the i-th student of the group A.

    The third line contains sequence of integer numbers b1, b2, ..., bn (1 ≤ bi ≤ 5), where bi is academic performance of the i-th student of the group B.

    Output

    Print the required minimum number of exchanges or -1, if the desired distribution of students can not be obtained.

    Examples

    Input

    4 5 4 4 4 5 5 4 5

    Output

    1

    Input

    6 1 1 1 1 1 1 5 5 5 5 5 5

    Output

    3

    Input

    1 5 3

    Output

    -1

    Input

    9 3 2 5 5 2 3 3 3 2 4 1 4 1 1 2 4 4 1

    Output

    4

  2. DeepSeek Assistant

    We are given two groups A and B, each with n students (1 ≤ n ≤ 100). Each student has an academic performance rating from 1 to 5.

    We want to redistribute students between groups so that for each rating value v from 1 to 5, the number of students with rating v in group A equals the number in group B. Initially we have counts in A and B (each total n). After redistribution, the total number of students in each group remains n, and the multiset of ratings in each group may change, but overall combined counts for each rating are fixed: the total number of students with rating v is countA[v] + countB[v]. For the two groups to have equal numbers for each rating, each group must have exactly half of the total count for each rating. So for each v, the required number in each group after redistribution is (countA[v] + countB[v]) / 2. Since total per rating might be odd, then it's impossible. So first check: for each rating, total count must be even. If any is odd, output -1.

    If all totals are even, then we need to achieve the target distribution by exchanging one student from A with one from B. Each exchange swaps a student from A with a student from B, effectively moving a rating from A to B and another from B to A. The goal: final counts for each rating in A should be target[v] = (total[v])/2.

    Let current counts in A be aCount[1..5]. We need to transform to target. Exchanges can transfer ratings between groups. Essentially, we have surplus and deficit per rating: surplus in A = aCount[v] - target[v] (could be positive, negative, or zero). If surplus positive, A has too many of that rating; they need to be moved to B. If surplus negative, A needs more of that rating, i.e., B has too many. Because the total surplus sum over all ratings is zero (since both groups have n, sum of surpluses = sum aCount - sum target = n - n = 0). Also note that the total number of surplus ratings (positive sum) equals total deficit sum (absolute). Exchanges can simultaneously fix a surplus and a deficit: we take a student from A with rating v (which A has too many) and swap with a student from B with rating w (which A has too few, i.e., B has too many). After swap, A loses one v and gains one w, so surplus[v] decreases by 1, surplus[w] increases by 1 (since deficit reduced). Actually if surplus[v] positive (A extra v) and surplus[w] negative (A needs w), then after swapping a v from A with a w from B, A loses v (surplus[v] decreases by 1) and gains w (surplus[w] increases by 1, moving towards zero). So each exchange can reduce the total absolute surplus by at most 2 (since we correct one excess and one deficit simultaneously). However, if we swap two students both from surplus categories? That wouldn't help; better to pair surplus with deficit.

    Thus, the minimal number of exchanges required is half the sum of positive surpluses (or sum of absolute values of surpluses divided by 2). Because each exchange can fix at most one unit of surplus and one unit of deficit, so the number of exchanges needed equals the total surplus (positive sum). More formally, let S = sum_{v} max(0, surplus[v]) = sum_{v} max(0, aCount[v] - target[v]). Then answer = S. (We can also compute sum of absolute deficits/2). This is a classic problem: minimum number of swaps to balance two sets.

    But need to confirm: Is it always achievable with exactly S exchanges? Since each exchange we can always pick a surplus rating in A and deficit rating in B (or equivalently deficit rating in A). But do we need to worry about intermediate states? Probably greedy works: any pairing of surplus and deficit can be resolved by exchanging corresponding students. Since we have exactly the required numbers, S exchanges suffice. Also we might have to consider if we can reduce by swapping a student with same rating? That would be useless because it doesn't change counts. So minimal is indeed S.

    Edge Cases: Verify with examples.

    Example 1: n=4 A: 5,4,4,4 => counts: 5:1, 4:3, others 0. B: 5,5,4,5 => counts: 5:3, 4:1. Total per rating: 5:4, 4:4, others 0 => each even, target per group: 5:2, 4:2. Current A: 5:1, 4:3 => surplus: 5: -1 (needs one more 5), 4: +1 (has extra 4). Positive surplus sum = 1. Answer 1 matches.

    Example 2: n=6 A: all 1 => aCount[1]=6, others 0. B: all 5 => bCount[5]=6. Total per rating: 1:6 (even => target each group 3 of 1), 5:6 (target each group 3 of 5). So A currently: 1:6 => surplus[1] = 6-3=+3. 5:0-3=-3 (deficit). Positive surplus = 3, answer 3 matches.

    Example 3: n=1 A:5, B:3. Total 5:1 (odd) => -1 matches.

    Example 4: n=9 A: 3 2 5 5 2 3 3 3 2 => counts: let's compute: rating 1:0, 2:3? Actually list: 3,2,5,5,2,3,3,3,2 => 3 appears? Let's count: 3 appears: positions 1,6,7,8? Actually first is 3, sixth 3, seventh 3, eighth 3 => that's four? Wait we have 9 numbers: indices:1:3,2:2,3:5,4:5,5:2,6:3,7:3,8:3,9:2. So 3: indices 1,6,7,8 => 4? That's four 3s? Actually also maybe more: list: 3,2,5,5,2,3,3,3,2. So 3 appears at pos1, pos6, pos7, pos8 -> that's 4. 2 appears at pos2, pos5, pos9 -> 3. 5 appears at pos3, pos4 -> 2. So A counts: 1:0, 2:3, 3:4, 4:0, 5:2. Total A sum = 3+4+2=9.

    B: 4 1 4 1 1 2 4 4 1 => counts: 1: appears at pos2,4,5,9? Actually B: 4,1,4,1,1,2,4,4,1 => count 1: pos2,4,5,9 => 4? pos2=1, pos4=1, pos5=1, pos9=1 => 4. 2: pos6=2 => 1. 3:0. 4: pos1,3,7,8 => 4? pos1=4, pos3=4, pos7=4, pos8=4 => 4. 5:0. So B counts: 1:4,2:1,4:4. totals per rating: rating1: 0+4=4 => even target per group =2; rating2: 3+1=4 => target each 2; rating3: 4+0=4 => target each 2; rating4: 0+4=4 => target each 2; rating5: 2+0=2 => target each 1. All even? 4,4,4,4,2 all even. Good. Target A: should have counts: 1:2, 2:2, 3:2, 4:2, 5:1. Current A: 1:0, 2:3, 3:4, 4:0, 5:2. So surplus = A - target: 1: -2 (deficit 2), 2: 3-2=+1, 3:4-2=+2, 4:0-2=-2, 5:2-1=+1. Positive sum = 1+2+1 = 4. Answer given 4 matches.

    Thus solution: compute counts for A and B for ratings 1..5, check if total for each rating is even, else -1. Then compute target per group = total/2. Compute positive surplus sum (i.e., sum over v of max(0, aCount[v] - target[v])). Output that sum.

    Complexities: O(n).

    Now need to implement in Python.

    Double-check reasoning: Could there be a scenario where we need more than surplus sum due to constraints? For example, if we have surplus of rating v in A and deficit of same rating v? That can't happen because surplus is defined relative to target. So all good.

    Alternatively, we can think of the minimal exchanges as half of the L1 distance between A and target (since each exchange reduces L1 by 2). So answer = (1/2) * sum |aCount[v] - target[v]|. That's same as sum of positive surpluses.

    Thus implementation straightforward.

    Edge: n up to 100, fine.

    Now produce final answer. ```python

    def solve() -> None: import sys

    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]
    b = [int(next(it)) for _ in range(n)]
    
    cntA = [0] * 6   # indices 1..5
    cntB = [0] * 6
    for v in a:
        cntA[v] += 1
    for v in b:
        cntB[v] += 1
    
    possible = True
    target = [0] * 6
    for v in range(1, 6):
        total = cntA[v] + cntB[v]
        if total % 2 != 0:
            possible = False
            break
        target[v] = total // 2
    
    if not possible:
        print(-1)
        return
    
    ans = 0
    for v in range(1, 6):
        if cntA[v] > target[v]:
            ans += cntA[v] - target[v]
    print(ans)
    

    if name == "main": solve()