ACM Association Insider Programming Contest 1

Contest Backdrop

Dark age has returned, minions of the new dark lord are harassing School of Witchcraft and Wizardry continually. You, the new generation of witches and wizards, are summoned to suppress them. However, it is already 2021, it is muggle's technology (a thing so called computer) stands for a chance to manage all the schemes of attack and training. As muggle-born ACM team members, you are chosen to help us!

Contest Problems

A - Ash's Trouble

Statement

"Expecto Patronum is a spell of crucial importance to guard us from the dementors", says professor Ciyiding Xia.

Since Ash Weasley is asleep deeply, he is absolutely no idea of the approaching of Prof. Xia.

"Now, I am pretty sure that Mr. Weasley is familiar with the spell, otherwise he is really wishing a bed here in my class."

With the whole class laughing over loud, Ash is awaked.

Standing in front of him the angry professor, he can not be more embarrassed.

"Sorry, professor", Ash whispers.

"Practice is the soul of magic, why don't you show us? Mr. Weasley."

"But, I am not sure what we have just learnt."

"Any thing you learned from the Defense Against the Dark Arts Class is appropriate."

As poor Ash is totally freaked out, we can not be assure what he will preform. This is the key moment to determine whether he will be expelled from school, please help him to calculate the score of his spell.

Input Description

There will be at most $100$ line.

For each line, there will be one magical spell and the length of it will not exceed $100$.

As professor's requirement goes, spells$\in$ ['Expecto Patronum','Expelliarmus','Immobulus','Protego'].

Output Description

For each line in the input, output a integer in a single line, denoting the score of Ash's spell.

The score is calculated by following rules:

• If the spell is intact, he will get $100$.
• For each mismatch, his score will subtract $10$ point.

Sample Input

Expecto Patronum
Immobulu
Proto

Sample Output

100
90
70

Hint

Note that Ash is too nervous to preform a spell. So, the spell could be misleading. Under that circumstances, we just calculate the maximum score he can get.

B - Biochemistry

To onlinejudge administrator: Be aware that the time limit should be set to a higher value depending on the hardware.

Statement

Biochemistry is the branch of science that explores the chemical processes within and related to living organisms. In the modern magical world, it is finally integrated with Potions.

Now, Bill wants to test a new potion using a method in Biochemistry. He will throw herbs into the pot repeatedly and will have to know the biggest amount of herb in every throw. Help him please.

Input Description

There will be $T$ testcases.

For each testcase, there will be a integer $n(1\le n\le10^6)$ in the first line, denoting the number of the throws.

For the next $n$ lines, there will be a string $s_i$ and a integer $w_i(w_{i}<10^3)$, denoting the name and the amount of the herb.

It is guaranteed that the length of the herb will not exceed $15$ and will not be spaces within.

Output Description

For each testcase, print the herb's name with the biggest amount and also the amount of it in each throw. If the same amount exists, output the herb with the smallest lexicographical order.

Sample Input

1
3
fluxweed 10
moly 20
fluxweed 30

Sample Output

fluxweed 10
moly 20
fluxweed 40

C - Chase

Statement

Gou Dan, a despicable death eater, got the secret of school and ran away. Once he succeeds in his escape, the school will be set into a great danger. However, the manager of the school gave you the Marauder's Map, so that you can get exact location of him.

To simplify the situation, let us assume that the school is constructed by rooms and corridors only. As you can see, the corridors are too open to hide, so Gou Dan will not stay in any one of them. For each corridor, it connects two rooms with a length $x$. As tricky as Gou Dan, he cursed on you. You can access a room in an even number of distances only.

Under current emergency, you have to find out the shortest path to the exit. It is time to use muggle's technology to solve it.

Input Description

There will be $T$ testcases.

For each testcase, there will be $4$ integers $n$,$m$,$s$,$e$ in the first line, denoting the number of rooms, the number of corridors, the start room and the exit.

For the next $m$ lines, there will be 3 integers $u$,$v$,$w$ in each one of them, denoting there is a corridor connect the room $u$ and $v$ with length $w$.

It is guaranteed that the sum of both $n$ and $m$ will not exceed $10^6$.

Output Description

For each testcase, print the length of the shortest path to the exit in a single line.

If there is no such path, print "-1".

Sample Input

1
4 4 1 4
1 2 1
2 3 1
1 3 6
3 4 2

Sample Output

8

D - Dig Treasure

Statement

It is once said that there is countless treasure hidden in the forbidden forest near the school castle. If the death eaters get them, the might use them to bewitch peoples' heart. So, by finding them eariler matters.

To be pointed out, as some of the items are enchanted, the are unlimited, while the rest of them are not.

Ash wants to dig them all, but due to the space limit of his backpack, he can only load some of the items. Please help him.

Input Description

There will be $2$ integers $N,V$($0\le N\le 10^4,0\le V\le 2*10^2$), in the first line, denoting the number of different items and the space of Ash's backpack.

For the following $N$ line, each line contains $3$ integers $v_i$, $w_i$, $t_i$($0\le v_i,w_i\le100$), denoting the space cost, the value and the type($1$ for unlimited, $0$ for limited).

Output Description

Print the maximum value of the tresure Ash can get in a single line.

Sample Input

3 10
1 5 0
2 5 1
1 1 1

Sample Output

26

E - Envelope

Statement

New year arrives, Prof. Xia is dispensing new year red envelopes.

A crazy fan of metaphor like him, however, let out a puzzle to his students. He assures that any one who can solve that could get a extreamly large delicious cake.

The puzzle is:

You are given a row vector $A$ and a column vector $B$. Can you find the median number of $B*A$?

Ash wants the cake, could you please help him?

Input Description

Two lines, denoting vector $A,B$ .

Each line contains $n$ integer, it is gurateed that $0\le n\le10^5,0\le n_i\le10^3$ and $n$ is odd.

Output Description

Print the median of the matrix calculated in a single line.

Sample Input

1 2 3
4 5 6

Sample Output

10

Hint

The cake is a lie.

F - Female Necklace

Statement

Ash is about to give away an female necklace to an elegant lady - Doris.

The breads on the necklace has mulitple different colors. As Doris has a particular bias on the pattern of the beads, Ash wants to make it suitable.

But how? Here is the defination of good pattern:

After removing the arrangements that contains only one color, it is possible to divide all the arrangements equally according to the necklace type so that each group has $L$ combinations ($L(L>c)$ happens to be the length of the necklace).

e.g. Number of the colors equals 2, length of the necklace equals 3. There will be 8 arrangements.

aaa
aab
aba
baa
bba
bab
abb
bbb

By removing the arrangement that contains only one color, 2 types of combination left(as the figure down below).

To save his Galleon, Ash demands you to find the smallest length of the necklace that satisfies the requirement.

Input Description

There will be one integer $N(1\le N\le10^5)$ in the first line, denoting $N$ queries.

For the following $N$ lines, there will be one integer $c(1<c\le10^6)$, denoting the number of colors.

Output Description

For each query, print $L(L>c)$ in a single line.

Sample Input

1
2

Sample Output

3

Hint

Cost horse :D.

Testcase and Datamaker: Download