[Solution] Delicious Queries CodeChef Solution

Problem

Chef has prepared a menu for his new restaurant. The menu consists of $N$ dishes whose flavour is given by $M_1, M_2, \dots, M_N$, where $M_i$ denotes the flavour of the $i^{th}$ dish.

Chef has some rules in his restaurant-

• A dish is served only if the customer has already eaten all the dishes preceding it on the menu.
• Each dish will only be served once.

Aman, the richest man in the area, stops by the restaurant one day and inquires about the deliciousness of a dinner that he may have there. Aman has a favourite ingredient $p$ which is a prime number and he wants to eat dishes with the most flavour that contains this ingredient. A dish with flavour $M_i$ contains the ingredient $p$ only if $p$ is a divisor of $M_i$.

In order for Aman to patronise Chef's restaurant on a regular basis, he agrees to reorder his menu to fulfil Aman's wishes. He decides that he will reorder the dishes that contain Aman's favourite ingredient while leaving the position of other dishes unchanged. For example, if $M = [1, 2, 3, 4, 5, 6]$ and $p = 2$ then Chef can reorder his menu into $[1, 4, 3, 2, 5, 6]$ or into $[1, 4, 3, 6, 5, 2]$ but not into $[2, 1, 3, 4, 5, 6]$ since the first dish with flavour $1$ does not contain $p$ as $p$ is not a divisor of $1$.

Aman wants to know the deliciousness of his meal, which is the total sum of flavours of all dishes if he eats $k$ dishes (first $k$ dishes of the menu) and his favourite ingredient is $p$. Can you help Chef find the maximum deliciousness after reordering his menu?

You have to answer $Q$ queries and each query will contain the favourite ingredient $p$ and the number of dishes Aman

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 wants to eat $k$. Each query is independent, i.e. changes made to the menu in one query do not affect the next one.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains one integer $N$ — the number of dishes.
  • The next line contains $N$ space-separated integers $M_1, M_2, \ldots, M_N$- the flavours of the dishes
  • The third line contains $Q$ — the number of queries.
  • Each of the next $Q$ lines contains two space-separated integers $p$ and $k$ — the favourite ingredient of Aman and the number of dishes he will eat.

Output Format

For each test case, output $Q$ lines, the $i^{th}$ line containing the answer to the $i^{th}$ query.

Explanation:

Test case $1$: The menu is $[1, 2, 3, 4, 5]$ and we have $2$ queries.

• The first query has $p = 2$ and $k = 3$. Chef can reorder the menu to $[1, 4, 3, 2, 5]$. Now Aman will eat dishes with flavour $1$, $4$ and $3$. Deliciousness will be $1 + 4 + 3 = 8$
• The second query has $p = 3$ and $k = 4$. Chef cannot reorder the menu and it remains the same. Now Aman will eat dishes with flavour $1$, $2$, $3$ and $4$. Deliciousness will be $1 + 2 + 3 + 4 = 10$

Test case $2$: The menu is $[3, 4, 1, 8, 9, 2, 4, 10, 7, 20]$.

• One optimal arrangement for the first query is $[3, 10, 1, 20, 9, 2, 4, 8, 7, 4]$
• One optimal arrangement for the second query is $[3, 4, 1, 8, 9, 2, 4, 10, 7, 20]$