시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 100 | 30 | 25 | 32.895% |
To store long DNA sequences, your company has developed a LongLongString
class that can store strings with more than ten billion characters. The class supports two basic operations:
Ins(p, c)
: Insert the character c at position p.Del(p)
: Delete the character at position p.A DNA editing program is written as a series of Ins
and Del
operations. Your job is to write a program that compare two DNA editing programs and determine if they are identical, i.e., when applied to any sufficiently long string, whether the end result is the same. For example:
Del(1)
Del(2)
and Del(3)
Del(1)
are identical.Del(2)
Del(1)
and Del(1)
Del(2)
are different.Ins(1, x)
Del(1)
are identical.Ins(14, b)
Ins(14, a)
and Ins(14, a)
Ins(15, b)
are identical.Ins(14, a)
Ins(15, b)
and Ins(14, b)
Ins(15, a)
are different.Input will consist of the descriptions of two DNA editing programs. Each program will consist of some number of operations (between 0 and 2,000). Each operation will be given on its own line. The first character of the line will be D
for a Del
operation, I
for an Ins
operation, or E
marking the end of the program.
A Del
operation will have the D
character, followed by a space, and then a single integer between 1 and 1010, indicating the character position to delete. All characters after this deleted character will be shifted one position lower.
An Ins
operation will have the I
character, followed by a space, and then a single integer between 1 and 1010, indicating the location to insert the new character; all pre-existing characters with this index and higher will be shifted one position higher. Following this integer will be another space and then an uppercase alphabetic character that is the character to insert.
If the two programs are identical, print “0” on a single line (without quotation marks). Otherwise, print “1” on a single line (without quotation marks).
D 1 D 2 E D 3 D 1 E
0
D 2 D 1 E D 1 D 2 E
1
I 1 X D 1 E E
0
I 14 B I 14 A E I 14 A I 15 B E
0
I 14 A I 15 B E I 14 B I 15 A E
1
ICPC > Regionals > North America > Pacific Northwest Regional > 2017 Pacific Northwest Region Programming Contest > Division 1 I번
ICPC > Regionals > North America > Pacific Northwest Regional > 2017 Pacific Northwest Region Programming Contest > Division 2 V번
ICPC > Regionals > North America > Southeast USA Regional > 2017 Southeast USA Regional Programming Contest > Division 1 E번
ICPC > Regionals > North America > Southeast USA Regional > 2017 Southeast USA Regional Programming Contest > Division 2 E번