Thứ Ba, 28 tháng 3, 2017

One-dimensional Japanese Crossword

One-dimensional Japanese Crossword
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Recently Adaltik discovered japanese crosswords. Japanese crossword is a picture, represented as a table sized a × b squares, and each square is colored white or black. There are integers to the left of the rows and to the top of the columns, encrypting the corresponding row or column. The number of integers represents how many groups of black squares there are in corresponding row or column, and the integers themselves represents the number of consecutive black squares in corresponding group (you can find more detailed explanation in Wikipedia https://en.wikipedia.org/wiki/Japanese_crossword).
Adaltik decided that the general case of japanese crossword is too complicated and drew a row consisting of n squares (e.g. japanese crossword sized 1 × n), which he wants to encrypt in the same way as in japanese crossword.
The example of encrypting of a single row of japanese crossword.
Help Adaltik find the numbers encrypting the row he drew.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the length of the row. The second line of the input contains a single string consisting of n characters 'B' or 'W', ('B' corresponds to black square, 'W' — to white square in the row that Adaltik drew).
Output
The first line should contain a single integer k — the number of integers encrypting the row, e.g. the number of groups of black squares in the row.
The second line should contain k integers, encrypting the row, e.g. corresponding to sizes of groups of consecutive black squares in the order from left to right.
Examples
input
3
BBW
output
1
2
input
5
BWBWB
output
3
1 1 1
input
4
WWWW
output
0
input
4
BBBB
output
1
4
input
13
WBBBBWWBWBBBW
output
3
4 1 3
Note
The last sample case correspond to the picture in the statement.
Người đăng: vào lúc Không có nhận xét nào:

Chủ Nhật, 26 tháng 3, 2017

The Monster

The Monster
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times b, b + a, b + 2a, b + 3a, ... and Morty screams at times d, d + c, d + 2c, d + 3c, ....
The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.
Input
The first line of input contains two integers a and b (1 ≤ a, b ≤ 100).
The second line contains two integers c and d (1 ≤ c, d ≤ 100).
Output
Print the first time Rick and Morty will scream at the same time, or  - 1 if they will never scream at the same time.
Examples
input
20 2
9 19
output
82
input
2 1
16 12
output
-1
Note
In the first sample testcase, Rick's 5th scream and Morty's 8th time are at time 82.
In the second sample testcase, all Rick's screams will be at odd times and Morty's will be at even times, so they will never scream at the same time.
Người đăng: vào lúc Không có nhận xét nào:

Not Afraid

Not Afraid
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them.
There are n parallel universes participating in this event (n Ricks and n Mortys). I. e. each of n universes has one Rick and one Morty. They're gathering in m groups. Each person can be in many groups and a group can contain an arbitrary number of members.
Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility).
Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there's a group such that every member in that group is a traitor (they will plan and destroy the world).
Summer knows that if there's a possibility that world ends (there's a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there's at least one scenario (among all 2n possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.
Input
The first line of input contains two integers n and m (1 ≤ n, m ≤ 104) — number of universes and number of groups respectively.
The next m lines contain the information about the groups. i-th of them first contains an integer k (number of times someone joined i-th group, k > 0) followed by k integers vi, 1, vi, 2, ..., vi, k. If vi, j is negative, it means that Rick from universe number  - vi, j has joined this group and otherwise it means that Morty from universe number vi, j has joined it.
Sum of k for all groups does not exceed 104.
Output
In a single line print the answer to Summer's question. Print "YES" if she should cancel the event and "NO" otherwise.
Examples
input
4 2
1 -3
4 -2 3 2 -3
output
YES
input
5 2
5 3 -2 1 -1 5
3 -5 2 5
output
NO
input
7 2
3 -1 6 7
7 -5 4 2 4 7 -3 4
output
YES
Note
In the first sample testcase, 1st group only contains the Rick from universe number 3, so in case he's a traitor, then all members of this group are traitors and so Summer should cancel the event.
Người đăng: vào lúc Không có nhận xét nào:

Innokenty and a Football League

Innokenty and a Football League
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Innokenty is a president of a new football league in Byteland. The first task he should do is to assign short names to all clubs to be shown on TV next to the score. Of course, the short names should be distinct, and Innokenty wants that all short names consist of three letters.
Each club's full name consist of two words: the team's name and the hometown's name, for example, "DINAMO BYTECITY". Innokenty doesn't want to assign strange short names, so he wants to choose such short names for each club that:
  1. the short name is the same as three first letters of the team's name, for example, for the mentioned club it is "DIN",
  2. or, the first two letters of the short name should be the same as the first two letters of the team's name, while the third letter is the same as the first letter in the hometown's name. For the mentioned club it is "DIB".
Apart from this, there is a rule that if for some club x the second option of short name is chosen, then there should be no club, for which the first option is chosen which is the same as the first option for the club x. For example, if the above mentioned club has short name "DIB", then no club for which the first option is chosen can have short name equal to "DIN". However, it is possible that some club have short name "DIN", where "DI" are the first two letters of the team's name, and "N" is the first letter of hometown's name. Of course, no two teams can have the same short name.
Help Innokenty to choose a short name for each of the teams. If this is impossible, report that. If there are multiple answer, any of them will suit Innokenty. If for some team the two options of short name are equal, then Innokenty will formally think that only one of these options is chosen.
Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of clubs in the league.
Each of the next n lines contains two words — the team's name and the hometown's name for some club. Both team's name and hometown's name consist of uppercase English letters and have length at least 3 and at most 20.
Output
It it is not possible to choose short names and satisfy all constraints, print a single line "NO".
Otherwise, in the first line print "YES". Then print n lines, in each line print the chosen short name for the corresponding club. Print the clubs in the same order as they appeared in input.
If there are multiple answers, print any of them.
Examples
input
2
DINAMO BYTECITY
FOOTBALL MOSCOW
output
YES
DIN
FOO
input
2
DINAMO BYTECITY
DINAMO BITECITY
output
NO
input
3
PLAYFOOTBALL MOSCOW
PLAYVOLLEYBALL SPB
GOGO TECHNOCUP
output
YES
PLM
PLS
GOG
input
3
ABC DEF
ABC EFG
ABD OOO
output
YES
ABD
ABE
ABO
Note
In the first sample Innokenty can choose first option for both clubs.
In the second example it is not possible to choose short names, because it is not possible that one club has first option, and the other has second option if the first options are equal for both clubs.
In the third example Innokenty can choose the second options for the first two clubs, and the first option for the third club.
In the fourth example note that it is possible that the chosen short name for some club x is the same as the first option of another club yif the first options of x and y are different.
Người đăng: vào lúc Không có nhận xét nào:

Anton and School - 2

Anton and School - 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
As you probably know, Anton goes to school. One of the school subjects that Anton studies is Bracketology. On the Bracketology lessons students usually learn different sequences that consist of round brackets (characters "(" and ")" (without quotes)).
On the last lesson Anton learned about the regular simple bracket sequences (RSBS). A bracket sequence s of length n is an RSBS if the following conditions are met:
  • It is not empty (that is n ≠ 0).
  • The length of the sequence is even.
  • First  charactes of the sequence are equal to "(".
  • Last  charactes of the sequence are equal to ")".
For example, the sequence "((()))" is an RSBS but the sequences "((())" and "(()())" are not RSBS.
Elena Ivanovna, Anton's teacher, gave him the following task as a homework. Given a bracket sequence s. Find the number of its distinct subsequences such that they are RSBS. Note that a subsequence of s is a string that can be obtained from s by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.
Because the answer can be very big and Anton's teacher doesn't like big numbers, she asks Anton to find the answer modulo 109 + 7.
Anton thought of this task for a very long time, but he still doesn't know how to solve it. Help Anton to solve this task and write a program that finds the answer for it!
Input
The only line of the input contains a string s — the bracket sequence given in Anton's homework. The string consists only of characters "(" and ")" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000.
Output
Output one number — the answer for the task modulo 109 + 7.
Examples
input
)(()()
output
6
input
()()()
output
7
input
)))
output
0
Note
In the first sample the following subsequences are possible:
  • If we delete characters at the positions 1 and 5 (numbering starts with one), we will get the subsequence "(())".
  • If we delete characters at the positions 1, 2, 3 and 4, we will get the subsequence "()".
  • If we delete characters at the positions 1, 2, 4 and 5, we will get the subsequence "()".
  • If we delete characters at the positions 1, 2, 5 and 6, we will get the subsequence "()".
  • If we delete characters at the positions 1, 3, 4 and 5, we will get the subsequence "()".
  • If we delete characters at the positions 1, 3, 5 and 6, we will get the subsequence "()".
The rest of the subsequnces are not RSBS. So we got 6 distinct subsequences that are RSBS, so the answer is 6.
Note: Có thể sử dụng các hàm trong bài tập để áp dụng vào các bài toán yêu cầu xử lý số lớn và chia module kết quả. Sử dụng các hàm trên và cách tính modulo bên dưới để giải bài 2, đề thi olympic tin học quốc gia khối chuyên tin.

long long big_modulo(long long a, long long b){
 if (b==0) return 1;
 if (b%2==1){
  return ((a%MOD)*(big_modulo(a, b/2))%MOD)%MOD;
 }
 if (b%2==0){
  long long c = big_modulo(a, b/2);
  return ((c%MOD)*(c%MOD))%MOD;
 }
}
Người đăng: vào lúc Không có nhận xét nào:

Thứ Tư, 22 tháng 3, 2017

Mahmoud and a Triangle

Mahmoud and a Triangle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.
Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.
Input
The first line contains single integer n (3 ≤ n ≤ 105) — the number of line segments Mahmoud has.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the lengths of line segments Mahmoud has.
Output
In the only line print "YES" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "NO" otherwise.
Examples
input
5
1 5 3 2 4
output
YES
input
3
4 1 2
output
NO
Note
For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle

Người đăng: vào lúc Không có nhận xét nào:

Mahmoud and Longest Uncommon Subsequence

Mahmoud and Longest Uncommon Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
While Mahmoud and Ehab were practicing for IOI, they found a problem which name was Longest common subsequence. They solved it, and then Ehab challenged Mahmoud with another problem.
Given two strings a and b, find the length of their longest uncommon subsequence, which is the longest string that is a subsequence of one of them and not a subsequence of the other.
A subsequence of some string is a sequence of characters that appears in the same order in the string, The appearances don't have to be consecutive, for example, strings "ac", "bc", "abc" and "a" are subsequences of string "abc" while strings "abbc" and "acb" are not. The empty string is a subsequence of any string. Any string is a subsequence of itself.
Input
The first line contains string a, and the second line — string b. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is not bigger than 105 characters.
Output
If there's no uncommon subsequence, print "-1". Otherwise print the length of the longest uncommon subsequence of a and b.
Examples
input
abcd
defgh
output
5
input
a
a
output
-1
Note
In the first example: you can choose "defgh" from string b as it is the longest subsequence of string b that doesn't appear as a subsequence of string a.

Người đăng: vào lúc Không có nhận xét nào:

Pasha and String

Pasha and String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Pasha got a very beautiful string s for his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to |s| from left to right, where |s| is the length of the given string.
Pasha didn't like his present very much so he decided to change it. After his birthday Pasha spent m days performing the following transformations on his string — each day he chose integer ai and reversed a piece of string (a segment) from position ai to position |s| - ai + 1. It is guaranteed that 2·ai ≤ |s|.
You face the following task: determine what Pasha's string will look like after m days.
Input
The first line of the input contains Pasha's string s of length from 2 to 2·105 characters, consisting of lowercase Latin letters.
The second line contains a single integer m (1 ≤ m ≤ 105) —  the number of days when Pasha changed his string.
The third line contains m space-separated elements ai (1 ≤ ai; 2·ai ≤ |s|) — the position from which Pasha started transforming the string on the i-th day.
Output
In the first line of the output print what Pasha's string s will look like after m days.
Examples
input
abcdef
1
2
output
aedcbf
input
vwxyz
2
2 2
output
vwxyz
input
abcdef
3
1 2 3
output
fbdcea
Người đăng: vào lúc Không có nhận xét nào:
Đăng ký: Bài đăng (Atom)