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()
D. Fadi and LCM
Given a number num, we want to find two positive integers a and b such that their LCM is equal to num and the maximum of a and b is minimized. To do so, we can start by finding the prime factors of num. We can then divide the prime factors into two sets a and b such that their product is num.
To minimize the maximum of a and b, we want to divide the prime factors as evenly as possible between a and b. This means that we want to split the prime factors into two sets of approximately equal size. To do so, we can start by initializing a to 1 and b to num, and then iterate over all the possible factors of num starting from 2.
For each factor i, we check if it is a divisor of num and whether the LCM of i and num // i is equal to num. If both conditions are satisfied, we update a and b accordingly. By doing so, we are effectively finding a pair of positive integers a and b such that their product is num and their greatest common divisor (GCD) is 1, i.e., they are coprime.
import math
num = int(input())
a = 1
b = num
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0 and math.lcm(i, num // i) == num:
a = i
b = num // i
print(a, b)