A. Love Triangle
One way to verify a function is by checking if there exists an "i" for which the output of the function, when applied three times consecutively (i.e., f(f(f(i)))), is equal to "i". In other words, the condition to check is whether f(f(f(i))) equals "i"
length = int(input())
planes = list(map(lambda x: int(x) - 1, input().split()))
flag = False
for i in range(length):
if planes[planes[planes[i]]] == i:
flag = True
print("YES" if flag else "NO")
B. Divide and Multiply
To maximize the sum of an array, we can first divide all numbers in the array by 2 as many times as possible and count the number of successful divisions as "k". Then, we should identify the largest number remaining in the array after these divisions. To obtain the maximum sum, we need to multiply this largest remaining number by 2 raised to the power of "k".
numOfTests = int(input())
for _ in range(numOfTests):
length = int(input())
arr = list(map(int, input().split()))
twos = 0
for i in range(length):
while arr[i] % 2 == 0:
twos += 1
arr[i] //= 2
arr.sort()
total = sum(arr[:-1]) + (arr[-1] * (1 << twos))
print(total)
C. Sherlock and his girlfriend
We have a bunch of jewelry pieces with different prices. We want to color them in a way that if the price of any piece is a multiple of a prime number, then it should have a different color than the other pieces whose prices are also multiples of that prime number.
To solve this, we need to first find all the prime numbers up to a certain range (in this case, up to 105) using the Sieve of Eratosthenes method. Then, we can color all the jewelry pieces whose prices are prime numbers with one color, and color the rest of the pieces with a different color. This ensures that if a piece's price is a multiple of a prime number, it will have a different color than the other pieces whose prices are also multiples of that prime number.
def build_sieve(num_jewelries):
sieve = [1 for i in range(num_jewelries)]
sieve[1] = 1
i = 2
while i * i <= num_jewelries:
if sieve[i] == 1:
for j in range(i * i, num_jewelries, i):
sieve[j] = 2
i += 1
return sieve
def main():
num_jewelries = int(input())
sieve = build_sieve(num_jewelries + 2)
if num_jewelries > 2:
print(2)
else:
print(1)
for i in range(2, num_jewelries + 2):
print(sieve[i], end = " ")
main()