StrangeParticles
SRM 299 · 2006-04-22 · by Vovka
SRM 299 · 2006-04-22 · by Vovka · Graph Theory
Problem Statement
Problem Statement
There are a number of strange particles flying in space and interacting with each other. When two particles collide, three outcomes are possible:
- 1.) Nothing happens
- 2.) The first particle disappears
- 3.) The second particle disappears
You will be given a
The particles will randomly collide and interact with each other for some period of time. You don't know the order or the number of interactions that will occur. After all the interactions are over, there will be a number of particles that have not disappeared. Return the lowest possible value for this number.
Constraints
- interacts will contain between 1 and 50 elements, inclusive.
- Each element of interacts will contain the same number of characters as there are elements in interacts.
- Each character in interacts will be '+', '-' or '0'.
- Character i in element i of interacts will be '0'.
- Character i in element j of interacts will be opposite to character j in element i ('-' is opposite to '+' and '+' is opposite to '-', '0' is opposite to itself)
Examples
0)
{"0+-","-0+","+-0"}
Returns: 1
Three particles form a cycle. Only one particle can remain.
1)
{"000","000","000"}
Returns: 3
No particle can disappear at all.
2)
{"0++++++++++++++",
"-0+++++++++++++",
"--0++++++++++++",
"---0+++++++++++",
"----0++++++++++",
"-----0+++++++++",
"------0++++++++",
"-------0+++++++",
"--------0++++++",
"---------0+++++",
"----------0++++",
"-----------0+++",
"------------0++",
"-------------0+",
"--------------0"}
Returns: 1
3)
{"00000000000000000000000000000+00000000000000+000++","0000000000000000+00000000000000000000000000000+000","000000+00000+000000000000000000000000000+0000++000","0000000000+000000000000000000000000000000000000000","00000+00000000000000000000000000000000000000000000","0000-00000000000000000000000000000000+000000000000","00-0000000+00000000000000000000000+000000000000000","00000000000000000000000000000000000000000+0000+000","00000000000000+000000000+0000000000+00000000000000","00000000000000000000000000000000000+00000000000000","000-00-000000000000000000000000+000+00000000000+00","0000000000000000000000000000000+0+00000000000+0000","00-000000000000000000000000+0000000000000000000000","00000000000000000000000000000000000000000000000000","00000000-000000000000000000000+0000000000000000000","0000000000000000000+000000000000000000000000000000","0-000000000000000000000000000000000+0000000+000000","00000000000000000000+0000000+0000000000000000+0000","0000000000000000000000000000000000000000000+000000","000000000000000-00000000000+00+0000000000000000000","00000000000000000-000000000000000+0000000000000000","00000000000000000000000000000000000000000+00000000","00000000000000000000000000000000000000000000000000","0000000000000000000000000000+000000000000000000+00","00000000-0000000000000000000000000000000+000000000","00000000000000000000000000000000000000000+000000+0","0000000000000000000000000000000000000+000000000000","000000000000-000000-000000000000000000000000000000","00000000000000000-00000-00000+0000000000+000000000","-000000000000000000000000000-000000000+00000000000","00000000000000-0000-00000000000000000+000000000000","0000000000--00000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000-00000000-0000000000000000+000000000000","000000-0000000000000000000000000000+000000+0000000","00000000---00000-00000000000000000-000+00000000000","00000000000000000000000000000000000000+00000000000","00000-00000000000000000000-000-00-0000000000000000","00000000000000000000000000000-00000--0000000000000","00000000000000000000000000000000000000000000000000","00-000000000000000000000-000-000000000000000000000","0000000-0000000000000-000-00000000000000000000+000","0000000000000000000000000000000000-00000000000000+","0000000000000000-0-0000000000000000000000000000000","-0000000000000000000000000000000000000000000000+++","00-00000000-00000-00000000000000000000000000000000","0--0000-000000000000000000000000000000000-00000000","0000000000-000000000000-00000000000000000000-00000","-000000000000000000000000-000000000000000000-00000","-00000000000000000000000000000000000000000-0-00000"}
Returns: 15
4)
{"0000000000000000000000++00000000000++0000000+00000","000000000000000000000000000000000000000+0000000000","0000000000000000000+00000+0000000000000000000000+0","00000000+00000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000+00000","0000000000000000000000+000000000000000000000000000","0000000000000000000000000000000+00000000000000000+","000-0000000000000000+0000000000000000000+000000000","000000000000000000+0000000000000000000000000000000","000000000000000000000000+000000000000000000000+000","0000000000000++00000000000000000000000+00000000000","00000000000000000000000000000000000+0000+000000000","00000000000-0000000000000+000000000000000000000000","00000000000-00000+00++0000000000000000000000000000","00000000000000000000000000000000000000000000000000","0000000000000000000000000000000000000000000+0000+0","00000000000000-000000000000+0000000000000000000000","000000000-0000000000000000000000000000000000+00000","00-0000000000000000000000000000000000000000000+000","00000000-00000-00000000000000000+00+00000000000000","00000000000000-0000000000+0000+0000000000000000000","-00000-00000000000000000000000+0000+000000+0000000","-000000000000000000000000000000000000000+000000000","0000000000-00000000000000000000000000000000++00000","00-0000000000-0000000-000000000000000000000000+000","00000000000000000000000000000000000000000000000000","00000000000000000-00000000000000000000000000000000","000000000000000000000000000000++00+000000000000000","000000000000000000000000000000000+0000000000000000","000000000000000000000--00000-000000000000+00000000","0000000-00000000000000000000-000000000000000000000","00000000000000000000-000000000000000+000000000+000","00000000000000000000000000000-0000+000+00+00000000","0000000000000000000000000000-0000-0000000000000000","-00000000000-0000000-0-0000000000000000000+0000000","-0000000000000000000000000000000-00000000000000000","0000000000000000000000000000000000000000000000+000","00000000000-000000000000000000000-000000000++00000","0-00000000000000000000000000000000000000+00000000+","00000000-000-0000000000-000000000000000-000000+000","000000000000000000000000000000-00-0000000000000000","0000000000000000000000-000000000000-00000000000000","0000000000000000-0000000-0000000000000-00000000000","-0000-000000000000-00000-0000000000000-00000000000","00000000000000000000000000000000000000000000000000","0000000000-00000000-00000-000000-0000-00-000000000","00000000000000000000000000000000000000000000000000","00-0000000000000-000000000000000000000000000000000","0000000-0000000000000000000000000000000-0000000000"}
Returns: 16
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StrangeParticles with a public method int remain(vector<string> interacts) · 94 test cases · 2 s / 256 MB per case