Time Limit: 1 second
You have been hired by the Cheap Communication Organization (CCO) to work on a communication breakthrough: sub-message sum (SMS). This revolutionary idea works as follows.
Given a binary string of length
For example, if 110010
is 2,2,1. This is because
Since you are a very junior developer, your job is not to find the original binary string from a given SMS, but rather the number of binary strings that could have formed this SMS.
The first line of input contains the two space-separated integers
The second line of input contains
Marks Awarded | Bounds on |
Additional Bounds on |
---|---|---|
3 marks | ||
3 marks | None | |
4 marks | ||
4 marks | ||
4 marks | ||
7 marks | None |
Output the remainder of
7 4
3 2 2 2
3
The possible strings of length 7 are 1011001
,
1101010
, and 1110011
.
Time Limit: 5 seconds
Thanks to your help with cropping her picture, Rebecca’s scenic photo is now featured on the front cover of the newest issue of her magazine. However, it seems that some of her readers still aren’t pleased with the picture. In particular, they seem to believe that the mountain in the picture is fake!
For simplicity, we can describe the picture as a sequence of
Luckily, Rebecca can still pay her editors to modify the picture and
reprint the magazine. Unfortunately for her though, the editors have a
very peculiar pricing scheme for their work. The only way Rebecca can
edit the picture is by sending emails to her editors containing the
integers
To please her readers, Rebecca would like to edit the picture so that they believe it contains a real mountain. Can you tell her the minimum cost required to do so?
The first line of input contains an integer
The second line of input contains
Marks Awarded | Bounds on |
Bounds and constraints on |
---|---|---|
3 marks | for some |
|
3 marks | ||
3 marks | ||
3 marks | ||
4 marks | ||
5 marks | ||
4 marks |
Output the remainder of
8
3 2 4 5 4 1 2 1
14
Rebecca can send two emails, the first containing the integers
The
Time Limit: 2 seconds
The
Since you are the mayor of Line Town, you are implementing the third pillar of your plan entitled “Community, Candy, and Organization” (CCO). As such, you have taken the mayoral power to swap the resident’s locations. In one swap, you may tell two adjacent residents to swap their positions in the line. However, this swap will cause both residents to negate their happiness values.
You would like to perform some swaps so that the residents’ happiness values are in non-decreasing order from left to right in the line. Determine whether this is possible, and if so, the minimum number of swaps needed.
The first line of input contains a single integer
The next line of input contains
Marks Awarded | Bounds on |
Bounds on |
---|---|---|
3 marks | ||
3 marks | ||
3 marks | ||
4 marks | ||
4 marks | ||
3 marks | ||
2 marks | No additional constraints. | |
3 marks | No additional constraints. |
On a single line, output the minimum number of swaps, or
6
-2 7 -1 -8 2 8
3
It is possible to perform
Swap the
Swap the
Swap the
The residents are now arranged in non-decreasing order of happiness
values as required. No non-decreasing arrangement can be obtained with
less than
4
1 -1 1 -1
-1
There is no sequence of swaps that will place residents in non-decreasing order of happiness values.
Time Limit: 1 second
Finn is playing a game of “Flip it and Stick it” which is abbreviated
as FiSi. FiSi is a one-player game played on two strings, 0
s and
1
s. Finn is allowed to make moves of the following
form:
Select a substring of
For example, Finn may take the string 101100
, take the substring 011
starting at index 111000
in
one move.
Finn wins the game if
The first line of input contains the string
The second line of input contains the string
In the table below,
Marks Awarded | Bounds on |
---|---|
1 mark | |
3 marks | |
4 marks | |
5 marks | |
5 marks | |
7 marks |
Output the minimum number of moves needed or
100110
10
2
Finn starts with the string 100110
. He cannot avoid
10
as a substring in one move, but he can in two moves.
For example, his first move could be to reverse the substring from
index 110
) to get
100011
. Then, his second move can be to reverse the
substring from index 1000
) to get
000111
, which does not have 10
as a
substring.
000
00
-1
No matter how many moves Finn makes, the string
Time Limit: 2 seconds
A trader would like to make a business of travelling between cities,
moving goods from one city to another in exchange for a profit. There
are
The
The first line of input contains two space-separated integers
The next
The last line of input contains
Marks Awarded | Bounds on |
Bounds on |
---|---|---|
2 marks | ||
7 marks | ||
3 marks | ||
4 marks | ||
4 marks | ||
5 marks |
On the first line, output the maximum possible total profit.
On the second line, output
On the third line, output
If there are multiple possible correct outputs, any correct output will be accepted.
4 1
1 2
1 3
2 4
3 1 4 1
7
2
1 3
On day
On day
At this point, the trader cannot reach another city in which they have not done business before getting laid off, so their total profit is 7.
5 2
1 2
1 3
2 4
2 5
3 1 4 1 5
14
5
1 4 5 2 3
The trader can make a profit in every city by visiting them in the
order
Note that the trader strategically delays doing business in city
Time Limit: 4 seconds
Alice has a collection of sticks. Initially, she has
Alice would like to use her sticks to make some isosceles triangles.
An isosceles triangle is made of two sticks of the same length, say
There are
Your task is to determine the maximum number of isosceles triangles Alice can make after each event if she uses her sticks optimally.
The first line of input contains two space-separated integers
The second line of input contains
The next
Initially and after each event, the number of sticks of length
Marks Awarded | Bounds on |
Additional Constraints |
---|---|---|
5 marks | There are at most |
|
5 marks | No additional constraints. | |
5 marks | The number of sticks of each length is
either |
|
5 marks | For each event, |
|
5 marks | No additional constraints. |
Output
4 3
3 1 4 1
3 -3
1 6
2 1
1
3
4
After the first event, Alice can make a single triangle with sticks
of lengths
After the second event, Alice can make
After the third event, Alice can make