The 2024 ICPC Egyptian Collegiate Programming Contest (Practice)

AAST, Egypt, 2024

Problem A. Play with Koko

Input file: standard input
Output file: standard output
Balloon Color: Orange

Koko loves cats and has a lot of them. Recently, He found it difficult to name all of them.
He found a way to solve this by giving each cat an ID (2 ≤ ID), Which is the product of its parent’s IDs.
Now, Koko wants to play with you, he will give you two cats’ IDs, and you have to determine if they
have some common ancestor.

Input
The input begins with a positive integer (1 ≤ t ≤ 100), the number of test cases.
After that, follows t lines, each with two integers ai , bi identifying two cats’ IDs. (2 ≤ ai , bi ≤ 1000)

Output
For each test case, print "YES"if the cats ai and bi share a common ancestor and "NO"otherwise.

Example
standard input standard output
2 YES
2 4 NO
3 5

Page 1 of 4
 The 2024 ICPC Egyptian Collegiate Programming Contest (Practice)
AAST, Egypt, 2024

Problem B. Coprime Trees

Input file: standard input
Output file: standard output
Balloon Color: Red

Given n, l, and r, count the number of trees rooted at 1 which satisfy the following rules:

1. The number of nodes doesn’t exceed n.

2. The values of nodes are between l and r.

3. The greatest common divisor between any pair of nodes that lie on the same path from the root is
equal to 1.

4. Direct children of the same parent should have distinct values.

Two trees are considered distinct if they are not isomorphic, or if they are isomorphic but at least one of
the nodes values is different.
Print the number of such trees modulo 109 + 7.

Input
The first line of the input contains a single integer t (1 ≤ t ≤ 50) — the number of test cases. Then t test
cases follow.
Each test case contains three integers n, l, and r (1 ≤ n ≤ 55, 1 ≤ l, r ≤ 1018 , r − l + 1 ≤ 30) — the
maximum number of nodes, and the values limits.
The sum of n over all test cases does not exceed 55.

Output
For each test case, print a single integer — the number of distinct trees which satisfy the rules modulo
109 + 7.

Example
standard input standard output
2 10
1 1 10 1
2 3 3

Page 2 of 4
 The 2024 ICPC Egyptian Collegiate Programming Contest (Practice)
AAST, Egypt, 2024

Problem C. Yet Another Game

Input file: standard input
Output file: standard output
Balloon Color: Dark Blue

Alice and Bob are playing a game that progresses turn by turn and as usual, Alice moves first.
There are n piles, The ith pile contains ai stones. On each turn, a player can choose a non-empty pile
and remove from it any number of stones from L stones up to R stones (The pile’s size should become
non-negative). The player who can’t make a move losses.
You are asked to find out who will win the game if both players play optimally, and find the maximum
possible number of stones Alice can remove in the first turn such that the result will be the same.

Input
The first line of the input will contain a single integer T (1 ≤ T ≤ 104 ) — The number of test cases.
The first line of each test case will contain three integers n, L, and R (1 ≤ n ≤ 105 ), (1 ≤ L ≤ R ≤ 105 ),
(L ≤ an ).
The second line will contain n integers a1 ≤ a2 ≤ . . . ≤ an where ai denotes the number of stones in the
ith pile.
It’s guaranteed that the sum of an overall test cases won’t exceed 106 and the same for n.

Output
For each test case, print in a single line the winner’s name and the maximum possible number of stones
Alice can remove in the first turn such that the result will be the same.

Example
standard input standard output
3 Alice 5
1 1 5 Bob 4
5 Alice 3
1 1 4
5
2 1 3
4 5

Page 3 of 4
 The 2024 ICPC Egyptian Collegiate Programming Contest (Practice)
AAST, Egypt, 2024

Problem D. Guess Number

Input file: standard input
Output file: standard output
Balloon Color: Yellow

We have a hidden number N , where 1 ≤ N ≤ 109 , Your is task to find it.

You guess a number X and we respond with three types of responses, “>” if N > X , “<” if N < X , or
“=”. if the response is N equals X , which means your guess was correct and then, you shout print “! N”
and terminate the program immediately.
If you make more than 30 guesses, you will receive a Wrong Answer verdict.

Interaction Protocol
After printing a number X do not forget to output end of line and flush the output. Otherwise, you will
get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• stdout.flush() in Python;

• see documentation for other languages.

Example
standard input standard output
< 11
> 6
> 9
= 10
! 10

Page 4 of 4