Binary Ternary Search Play 1

Time limit1sMemory limit256 MB

Summary

For every index in a sorted array of size N, compare the number of probes binary search and ternary search need to reach it, and count how often binary wins, ties, and loses.

Level: Medium6 of 10
Topics: Divide and conquer, Binary search, Recursion, Implementation
Solved: No attempts yet

Problem

Seojun is once again playing an algorithm game with his father. Seojun plays binary search, and his father plays ternary search.

There is an array A of size N, sorted in ascending order, whose elements are distinct integers. When the i-th element Ai of A is found with binary search and with ternary search, let Bi and Ti be the number of elements of A that must be referenced before Ai is found. Seojun has been given the mission of printing, one per line, the number of elements of A with Bi less than Ti, the number of elements of A with Bi equal to Ti, and the number of elements of A with Bi greater than Ti, in that order. Help him out.

The pseudocode of the binary search algorithm on an array of size N is as follows.

binary_search(A[0..N−1], value, left, right) {
    mid = ⌊(left + right) / 2⌋
    if (A[mid] == value)
        return mid
    else if (value < A[mid])
        return binary_search(A, value, left, mid - 1)
    else
        return binary_search(A, value, mid + 1, right)
}

The pseudocode of the ternary search algorithm on an array of size N is as follows.

ternary_search(A[0..N-1], value, left, right) {
    left_third = left + ⌊(right − left) / 3⌋
    right_third = right - ⌊(right − left) / 3⌋
    if (A[left_third] == value) 
        return left_third
    else if (A[right_third] == value)
        return right_third
    else if (value < A[left_third])
        return ternary_search(A, value, left, left_third − 1)
    else if (value < A[right_third])
        return ternary_search(A, value, left_third + 1, right_third − 1)
    else
        return ternary_search(A, value, right_third + 1, right)
}

Input

The first line gives the size N of array A (1 ≤ N ≤ 500,000). The indices of array A are [0, N−1].

Binary Ternary Search Play 1

Problem

Input

Output

Examples1