We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Ants
  5. Discussions

Ants

Sort by

recency

|

17 Discussions

|

  • CS_2212256_T
     + 0 comments
    #!/bin/python3

import math
import os
import random
import re
import sys

def solve(V):
    n = len(V)
    meets = (n // 2) * (n - n // 2) * 2 * 2 * 10**5

    V.sort()

    pos = 0
    while pos < n and (V[pos] - V[pos - 1]) % 1000 <= 1:
        pos += 1

    run = 0
    for i in range(pos, pos + n):
        if (V[i % n] - V[(i - 1) % n]) % 1000 == 1:
            run += 1
        else:
            if run > 0:
                meets += (run + 1) // 2 * 2
                run = 0

    if run > 0:
        meets += (run + 1) // 2 * 2

    return meets


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    V_count = int(input().strip())

    V = list(map(int, input().rstrip().split()))

    result = solve(V)

    fptr.write(str(result) + '\n')

    fptr.close()

  • 2003480100085_CS
     + 0 comments

    python solution

    def solve(V): n = len(V) # instead of turning, the ants can be seen to pass each other # so they simply go around and around. # in each direction go about half of them, # meeting the other half 2 times a round, 2x hello in a meeting # 1 round is 10_000 sec, 10**9 sec is 10**5 rounds meets = (n//2) * (n-n//2) * 2 * 2 * 10**5 # now what about the last 6 sec? => must maximize meetings here # 6 sec is 0.6 m per ant, that is ants can only meet if adjacent V.sort() for pos in range(n): if (V[pos]-V[pos-1])%1000 > 1: break run = 0 for i in range(pos, pos+n): if (V[i%n]-V[(i-1)%n])%1000 == 1: run += 1 else: meets += (run+1)//2 * 2 run = 0 else: if run: meets += (run+1)//2 * 2 return meets

  • cafelatte
     + 0 comments

    Most solutions (and even the editorial) are not fully correct, because they ignore this case:
    If there are ants on positions 999 and 0 (distance 1 over ends of intervall) the algorithms may give wrong results, e.g : the algos find one pair (0,1), not two pairs (1,2), (999,0) .
    (see also post of ygrinev below).

    Clumsy but correct solution:

    def solve(V):
    n = len(V)
    # instead of turning, the ants can be seen to pass each other
    # so they simply go around and around. 
    # in each direction go about half of them,
    #   meeting the other half 2 times a round, 2x hello in a meeting
    # 1 round is 10_000 sec, 10**9 sec is 10**5 rounds
    meets = (n//2) * (n-n//2) * 2 * 2 * 10**5
    # now what about the last 6 sec? => must maximize meetings here
    # 6 sec is 0.6 m per ant, that is ants can only meet if adjacent
    V.sort()
    for pos in range(n): 
        if (V[pos]-V[pos-1])%1000 > 1: break
    run = 0
    for i in range(pos, pos+n):
        if (V[i%n]-V[(i-1)%n])%1000 == 1:
            run += 1
        else:
            meets += (run+1)//2 * 2
            run = 0
    else:
        if run: meets += (run+1)//2 * 2
    return meets

  • 2001640100149A
     + 0 comments

    public static int solve(List V) { int n=V.size(),c=0; int x = 2*n/2*(n-n/2)*100000; Collections.sort(V);

    for(int i=0;i<n-1;i++)
{
    if(V.get(i+1)-V.get(i) == 1)
    {
        c++;
        i++;
    }
}
if(V.get(n-1) - V.get(0) == 1)
    c++;
x+=c;
return x*2;

    }

    }

  • ygrinev
     + 0 comments

    Not clear: if V[n-1] is 999 and V[0] is 0 would the following be wrong:

    if(V[n-1]-V[0]==1) c++;

    Simple case {0, 999}, the answer should be 40000002, but it is 40000000 !