**Zadání**\\
Viz odkaz: [[https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=particles|Částice v magnetickém poli]].\\
=== Nejrychlejší řešení v Javě ===
import java.util.*;
import java.io.*;
public class Main {
HashMap> pairs = new HashMap<>();
Set prosle = new HashSet<>();
char[] elektrony;
char[][][] tabulka;
void vyplnTabulku(int level) {
for (int i = 0; i < elektrony.length; i++) {
if (level + i == elektrony.length) break;
char prvni, posledni;
for (int j = i; j < level + i; j++) {
int k = 0;
while (tabulka[i][j][k] != 0) {
prvni = tabulka[i][j][k];
int q = 0;
while (tabulka[j + 1][i + level][q] != 0) {
posledni = tabulka[j + 1][i + level][q];
Pair p = new Pair(prvni, posledni);
aktualizuj(p, i, level + i);
q++;
}
k++;
}
}
}
}
void aktualizuj(Pair p, int row, int col) {
if (!pairs.containsKey(p)) return;
ArrayList bla = pairs.get(p);
for (Character character : bla) {
int k = 0;
while( tabulka[row][col][k] != 0 & tabulka[row][col][k] != character) {
k++;
}
if (tabulka[row][col][k] == 0) {
tabulka[row][col][k] = character;
tabulka[row][col][k + 1] = 0;
}
}
}
void pocitej() {
for (int i = 1; i < elektrony.length; i++) {
vyplnTabulku(i);
}
}
void printResult() {
char[] result = tabulka[0][elektrony.length - 1];
ArrayList resul = new ArrayList<>();
for (int i = 0; i < result.length; i++) {
if (result[i] == 0) break;
resul.add(result[i]);
}
Collections.sort(resul);
Character[] p = new Character[resul.size()];
resul.toArray(p);
for (int i = 0; i < p.length; i++) {
System.out.print(p[i]);
if (i != p.length -1) System.out.print(" ");
}
}
public void load(int elektronu, int pravidel, BufferedReader br) throws IOException {
elektrony = new char[elektronu];
tabulka = new char[elektronu][elektronu][27];
String line = br.readLine();
for (int i = 0; i < elektrony.length * 2; i+=2) {
char c = line.charAt(i);
elektrony[i/2] = c;
tabulka[i/2][i/2][0] = c;
}
for (int i = 0; i < pravidel; i++) {
line = br.readLine();
char prvni = line.charAt(0);
char druhy = line.charAt(2);
char vysl = line.charAt(4);
Pair p = new Pair(prvni, druhy);
if (!pairs.containsKey(p)) {
ArrayList bla = new ArrayList();
bla.add(vysl);
pairs.put(p, bla);
} else {
ArrayList bla = pairs.get(p);
bla.add(vysl);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String cisla = br.readLine();
StringTokenizer st = new StringTokenizer(cisla, " ");
String c = st.nextToken();
int elektronu = Integer.parseInt(c);
c = st.nextToken();
int pravidel = Integer.parseInt(c);
Main main = new Main();
main.load(elektronu, pravidel, br);
main.pocitej();
main.printResult();
}
private class Pair {
char prvni;
char druhy;
public Pair(char prvni, char druhy) {
this.prvni = prvni;
this.druhy = druhy;
}
public char getPrvni() {
return prvni;
}
public char getDruhy() {
return druhy;
}
@Override
public int hashCode() {
int hash = 3;
hash = 59 * hash + this.prvni;
hash = 59 * hash + this.druhy;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Pair other = (Pair) obj;
if (this.prvni != other.prvni) {
return false;
}
if (this.druhy != other.druhy) {
return false;
}
return true;
}
}
}
=== Nejrychlejší (a jediné) řešení v C/C++ ===
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define LOG(x) cout << x << endl;
//#define TEST "03"
#define ALPHABET 26
#define CTON(c) ((int)(c - 'a'))
#define NTOC(n) ((char)(n + 'a'))
struct rule {
int first, second, result;
};
ifstream fin;
int n, p;
bool ***matrix; // matrix of order n * n * ALPHABET, matrix[i][j] contains bit set of particles, which can be released by applying laser to orbits i-j
bool ***rules; // matrix of order ALPHABET * ALPHABET * ALPHABET, rules[i][j] contains all particles produced by colliding particles i and j
void read_input() {
#ifdef TEST
string path = "/Users/petr/Desktop/datapub/pub";
path += TEST; path += ".in";
fin.open(path);
#define cin fin
#endif
// parse data from cin
cin >> n >> p;
// alloc matrix and read input sequence of n chars
matrix = new bool **[n];
for (int i = 0; i < n; i++) {
matrix[i] = new bool *[n];
char c; cin >> c; // read one from n particles
int particle = CTON(c);
for (int j = 0; j < n; j++) {
matrix[i][j] = new bool [ALPHABET];
for (int k = 0; k < ALPHABET; k++) {
if (i == j && k == particle) {
matrix[i][j][k] = true; // initialize matrix on the diagonal
} else {
matrix[i][j][k] = false; // below and above diagonal are 0's
}
}
}
}
// alloc rules
rules = new bool **[ALPHABET];
for (int i = 0; i < ALPHABET; i++) {
rules[i] = new bool *[ALPHABET];
for (int j = 0; j < ALPHABET; j++) {
rules[i][j] = new bool [ALPHABET];
for (int k = 0; k < ALPHABET; k++) {
rules[i][j][k] = false;
}
}
}
// read rules
for (int i = 0; i < p; i++) {
char ci, co, cv;
cin >> ci >> co >> cv;
// each row consists of 3 chars: [i] [o] -> [v]
int ii = CTON(ci);
int io = CTON(co);
int iv = CTON(cv);
// flip the proper bit
rules[ii][io][iv] = true;
}
}
void compute() {
// gradually approach top right corner of the matrix
for (int phase = 1; phase <= n - 1; phase++) {
// iterate above main diagonal
for (int field = 0; field < n - phase; field++) {
// fill field matrix[field][field + phase]
// use fields matrix[field][field + phase - k] and matrix[field + phase - k + 1][field + phase]
// where k is from 1..phase
for (int k = 1; k <= phase; k++) {
for (int particleA = 0; particleA < ALPHABET; particleA++) {
if (!matrix[field][field + phase - k][particleA]) {
// only proceed, if the particle can be produced
continue;
}
for (int particleB = 0; particleB < ALPHABET; particleB++) {
if (!matrix[field + phase - k + 1][field + phase][particleB]) {
// only proceed, if the particle can be produced
continue;
}
// use the rules to figure out the output of reaction A + B
for (int r = 0; r < ALPHABET; r++) {
if (rules[particleA][particleB][r]) {
// matching rule found, flip the bit
matrix[field][field + phase][r] = true;
}
}
}
}
}
}
}
}
void cleanup() {
// do some cleaning up
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
delete [] matrix[i][j];
}
delete [] matrix[i];
}
delete [] matrix;
#ifdef TEST
fin.close();
#endif
}
void output() {
bool first = true;
for (int i = 0; i < ALPHABET; i++) {
if (matrix[0][n - 1][i]) {
if (!first) {
cout << " ";
}
cout << NTOC(i);
first = false;
}
}
cout << endl;
}
int main(int argc, const char * argv[])
{
read_input();
compute();
output();
cleanup();
return 0;
}