One day, Shareefeh was sitting with her younger sister Fadia, who was studying number theory to prepare herself for marriage. Shareefeh proudly told her that she was already an expert in number theory (which, of course, made sense — after all, she had managed to meet Abu Shehab's standards).
Fadia found herself stuck on the final problem given to her by Em Zeki. Em Zeki had promised that if Fadia solved this problem, she would IMMEDIATELY find her a husband. The problem was as follows:
Given an array of $$$n$$$ integers, rearrange the array to maximize the sum of the $$$GCD$$$ (greatest common divisor) of every pair of adjacent elements. More formally, rearrange the array to maximize: $$${\sum_{i = 2}^n GCD(a_i , a_{i-1})}$$$
The first line contains a single integer $$$t (1≤t≤10^4)$$$ — the number of test cases. Then, $$$t$$$ test cases follow.
The first line of each test case contains one integer $$$n (2≤n≤2\cdot10^5)$$$ — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_i(1≤a_i≤10)$$$ — the elements of the array.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot10^5$$$.
For each test case, output the maximum possible sum of the $$$GCD$$$s of adjacent elements after rearranging the given array.
234 2 841 5 7 10
6 7
Shareefeh was feeling bored, so she decided to take a nap during 3aser. Shareefeh started having ahlam il 3aser—her dream was about her playing a game of cards with Zahreyye, Abu Shehab's ex-wife.
Shareefeh and Zahreyye were the best card players around, and they decided to face each other after an argument about who loves Abu Shehab more.
They reached the point where they could choose any card from the deck, no matter its position.
To make the game more interesting, Zahreyye introduced new rules. Given a card deck with $$$n$$$ cards where each card has its own value.
Taking turns, when a player draws a card, its value is added to their score, and the opponent's score becomes
$$$opponent's$$$ $$$score$$$ = $$$max(0,$$$ $$$opponent's$$$ $$$score$$$ $$$-$$$ $$$gcd($$$$$$opponent's$$$ $$$score$$$, $$$card$$$ $$$value))$$$
The score of any player will never be less than 0 at any time.
Note that the player can draw the same card any number of times she wants.
The game will consist of $$$k$$$ turns, where in each turn, Shareefeh and Zahreyye take turns drawing a card from the deck (they play alternately — Shareefeh draws a card first, then returns it to the deck, followed by Zahreyye who also draws a card and returns it back to the deck afterward), if both play optimally, who wins?
The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.
For each test case the first line of input will contain two integers $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^{5})$$$ — denotes the number of cards and the number of draws.
The second line contain $$$n$$$ numbers $$$a_i$$$ $$$(1 \leq a_i \leq 10^{5})$$$ — $$$a_i$$$ denotes the value of the $$$i_{th}$$$ card.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot10^5$$$.
For each test case, print "Shareefeh" if Shareefeh wins, othewise print "Zahreyye"
11 71
Zahreyye
Abu Shehab travels very often; sometimes he goes to 7alab to see Abu elNoor, and sometimes he goes to Palestine to give them weapons and help them. Meanwhile, Shareefeh stays alone at home.
She reads lots of books, and she was thinking how beautiful this world is. She wants to visit many places like Abu Shehab does. She wants to visit Petra, the Dead Sea, Wadi Rum, and several places in this huge world.
After begging Abu Shehab several times to take her, he finally agreed and booked a trip on a coaster bus.
The coaster bus will carry several families together on each trip. The coaster bus, of length $$$n$$$, will have many seats of different sizes.
It will have $$$n-1$$$ seats for one person, $$$n-1$$$ seats for two people, and one seat (3al loge) that carries four people.
$$$m$$$ families booked a trip on a bus of length $$$n$$$. A huge problem may arise if two people from different families sit together on the same seat, so the bus driver needs to distribute the people among the seats so that no two people from different families share the same seat.
Can you help the bus driver decide if it is possible to assign each person a seat so that no problems arise?
The first line of input will contain one integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, which is the number of test cases.
For each test case:
The first line of input will contain two integers $$$n$$$ and $$$m$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$, $$$(1 \leq m \leq 2 \cdot 10^5)$$$, which represent the length of the bus and the number of families, respectively.
The second line will contain $$$m$$$ integers, the $$$i_{th}$$$ one, denoted by $$$a_i$$$ $$$(1 \leq a_i \leq 10^6)$$$, representing the number of people who booked the trip from the $$$i_{th}$$$ family.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$, and the sum of $$$m$$$ will not exceed $$$2 \cdot 10^5$$$.
For each test case:
If it is impossible to assign seats to people while satisfying the rules, print "No"; otherwise, print "Yes" .
You can output the answer in any case. For example, the strings "yEs", "yes", and "YES' will also be recognized as positive responses.
310 54 6 2 1 110 13110 132
Yes Yes No
The bus in all samples looks like:
One possible arrangement in first sample:
One day, Shareefeh noticed a box in her room that belonged to Abu Shehab's ex-wife, Zahreyye. The box was filled with her jewelry. Feeling jealous, Shareefeh convinced Abu Shehab to throw it away. However, she soon felt guilty and begged Abu Shehab to retrieve the box so she could wear the jewelry herself.
Wanting to add a personal touch, Abu Shehab decided to design a custom necklace for Shareefeh. The necklace would be crafted using $$$n$$$ gemstones, each consisting of two halves — each half having its own color (both halves could even share the same color).
To make the necklace truly special, Abu Shehab asked Shareefeh's sister, Motee3a, for her favorite colors. Motee3a provided $$$n$$$ pairs of color preferences, each pair representing possible colors for a single gemstone.
Shareefeh with one of the Abu Shehab's ex-wife necklace . Abu Shehab then went to Souq Al-Hamidiyah and bought $$$n$$$ gemstones according to these preferences.
Afterward, he visited Khater's jewelry store, handed over the $$$n$$$ gemstones, and asked Khater to assemble a necklace. Khater would start with a chain and sequentially insert each gemstone into it. He could insert each gemstone from either side. Finally, after inserting the last gemstone, he would close the chain, making the necklace a continuous loop where the first gemstone is adjacent to the last.
Abu Shehab had only one request: the necklace must be formed so that each color appears in at most one continuous segment (i.e., every color, if present, should appear in a single uninterrupted block in the necklace cycle).
Can you help Khater determine whether this is possible and deliver the answer to Abu Shehab as soon as possible?
The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.
For each test case:
The first line of input will contain one integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — denotes the number of sides for the stone and the number of Shareefeh's preferences.
The next $$$n$$$ lines contain two integers each, the i-th of them contains two space-separated integers $$$a_i$$$ and $$$b_i$$$ $$$( 1 \le a_i , b_i \le 2 \cdot n)$$$ — the i-th pair denotes the two colors that Shareefeh prefers.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print "Yes" if Khater can create such jewel, print "NO" otherwise.
You can output the answer in any case. For example, the strings "yEs", "yes", and "YES" will also be recognized as positive responses.
361 11 23 33 44 42 211 231 21 31 4
Yes Yes No
First example:
Let:
$$$1$$$ —> Yellow,
$$$2$$$ —> Green,
$$$3$$$ —> Red,
$$$4$$$ —> Blue,
The picture is:
So3ad 5anom organized a 3azeemeh in her house for neswan Al7arah to eat Kebbeh Dabbabeh and enjoy the atmosphere together.
After Em Zekki finished roasting the Kebbeh, she put the Kebbeh in a bag that looks like a stack that contains $$$n$$$ Kebbeh. The $$$i_{th}$$$ one has a size that equals $$$a_i$$$, where $$$a_1$$$ is the Kebbeh at the bottom of the stack and $$$a_n$$$ is the Kebbeh on top of the stack.
Shareefeh saw 7ameedeh eating lots of Kebbeh, then she told her not to eat too much so she doesn't become fat like Em Zekki. 7ameedeh didn't listen and continued eating because the Kebbeh was so delicious.
Shareefeh also wants to eat Kebbeh, but she doesn't want to get fat so she can marry Abu Shehab.
Shareefeh can remove any number of Kebbeh from the bag, but she can't put them back. So, she has to choose an integer $$$k$$$ such that $$$(1 \leq k \leq n)$$$ and remove the $$$k$$$ Kebbeh that are on top of the stack to eat them.
Shareefeh will sort the Kebbeh based on its size, then she will start eating them one by one, starting from the first one (the one with the minimum size).
For Shareefeh, a sequence of Kebbeh will make her gain more weight than another one if it is lexicographically greater than the other one.
Shareefeh wants to eat Kebbeh but doesn't want to gain too much weight, so she wants to choose an integer $$$k$$$ that makes her gain the minimum possible weight.
Can you help Shareefeh and tell her the integer $$$k$$$ she should choose such that after taking the top $$$k$$$ Kebbeh and sorting them by their size, the resulting sequence will be lexicographically minimal?
The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.
For each test case:
The first line of input will contain one integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$, which is the number of Kebbeh Shareefeh has.
The second line will contain $$$n$$$ integers, the $$$i_{th}$$$ one, denoted by $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$, representing the size of the $$$i_{th}$$$ Kebbeh.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print an integer $$$k$$$ on the first line, which represents the number of Kebbeh Shareefeh will take.
On the second line, print $$$k$$$ integers that represent the sequence of Kebbeh Shareefeh will eat.
3110041 2 3 444 3 2 1
1 100 4 1 2 3 4 1 1
After Shareefeh moved to Abu Shehab's house the number of snacks became much less and one day Shareefeh craved Balilah, after a while she heard Abu Ghalib calling "Balilah Balbalooky w bel mele7 wel leymoon sala2ooky ya 3zeeez alf lera engleeez".
She stopped Abu Ghalib and asked him to buy Balilah, Abu Ghalib stores his Balilah in a basket that looks like a stack that contains $$$n$$$ Balayel, the $$$i_{th}$$$ one has a tastiness that equals to $$$a_i$$$, where $$$a_1$$$ is the Balilah in the bottom of the stack and $$$a_n$$$ is the Balilah on top of the stack.
Abu Ghalib can remove any number of Balilah from his stack but he can't put them back, so he has to choose an integer $$$k$$$ such that $$$(1 \leq k \leq n)$$$, and remove the $$$k$$$ Balilah that are on top of the stack and sell them to Shareefeh.
Abu Ghalib knows that Shareefeh will sort the Balilah based on its tastiness then she will start eating them one by one starting from the first one (the one with minimum tastiness).
For Shareefeh a sequence of Balilah will provide a better experience than another one if it is lexicographically greater than the other one.
If Shareefeh wasn't satisfied with the Balilah she will tell Abu Shehab and he will kick Abu Ghalib out of Haret AlDabe3, so Abu Ghalib wants to choose an integer $$$k$$$ that gives Shareefeh the best experience.
Can you help Abu Ghalib and tell him the integer $$$k$$$ he should choose such that after taking the top $$$k$$$ Balilah and sorting them by their tastiness the resulting sequence will be lexicographically maximal?
The first line of input will contain one integer $$$t$$$, which is the number of test cases $$$(1 \leq t \leq 10^4)$$$.
For each test case:
The first line of input will contain one integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$, which is the number of Balilah Abu Ghalib has.
The second line will contain $$$n$$$ integers, the $$$i_{th}$$$ one, denoted by $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$, representing the tastiness of the $$$i_{th}$$$ Balilah.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print an integer $$$k$$$ on the first line, which represents the number of Balilah Abu Ghalib will sell to Shareefeh.
On the second line, print $$$k$$$ integers that represent the sequence of Balilah Shareefeh will eat.
4110041 2 3 444 3 2 142 1 4 3
1 100 1 4 4 1 2 3 4 2 3 4
Shareefeh just got married and moved in with Abu Shehab, when she walked into Ard-El-Dyar, she found out that Abu Shehab has no tree, she was mad and said how could you do this to the environment.
Se wants to help Abu Shehab improve his home's environment by planting a tree. She envisions a tree structure represented by a permutation $$$p$$$ of the integers from $$$1$$$ to $$$n$$$.
The tree is constructed as follows: for each $$$i$$$ from $$$2$$$ to $$$n$$$, there is an directed edge connecting $$$i$$$ to $$$\min(p_j : 1 \le j \lt i)$$$.
Shareefeh has specific requirements for this tree:
- Depth: The depth of the tree (the maximum distance from the root to a leaf) must be exactly $$$d$$$.
- Leaves: The tree must have exactly $$$k$$$ leaves, root can never be a leaf.
The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.
For each test case
The only line of input will contain three integers $$$n$$$, $$$d$$$, and $$$k$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ $$$(1 \leq d, k \leq 2 \cdot 10^5)$$$ — denotes the length of the permutation, the depth of the tree, and the number of leaves.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print the permutation $$$p$$$ in a single line or print $$$-1$$$ denoting that such permutation does not exist.
2 5 3 2 5 3 1
5 3 1 2 4 -1
