Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bytes.in, bytes.out | Sursă | IIOT 2021-22 Runda 1 |
| Autor | Ioan Popescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 3 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bytes
Seeking treasures of immense value to add to his almighty random knapsack, Prosto is travelling around the world. During one of his journeys he found a room filled with chests, each being locked. On every chest there is a boolean formula engraved on it.
The boolean formulas are XOR sums of multiple clauses, where a clause is the AND sum of some literals, which can be negated.
Alongside the formula on the chest, there is engraved a number k, which represents the number of distinct literals which can appear in the given formula. The i-th literal is represented as the i-th lowercase letter of the english alphabet e.g. the first literal is 'a', the second literal is 'b' and so on.
In order to unlock a chest you need to find the number of ways to assign each literal 0 or 1 such that the given formula evaluates to 1.
Let's say we have a chest with k=3 variables and the following formula: (a AND b) XOR (b AND c) XOR (a AND c). If the tuple of literals (a,b,c) is equal to one of the following tuples: (1,1,0), (1,0,1), (0,1,1), (1,1,1) then the given expression is 1, so the answer is 4.
Our protagonist promises you glory and 100 points if you can help him find the keys to some of his chests.
Date de intrare
The first line of the file bytes.in contains T, the number of chests.
For each chest you are given a number k representing the number of literals, and a string s which represents the formula written on the chest.
Date de ieşire
The output file bytes.out will contain on T lines the keys of the chests in the order they appear in the input.
Restricţii
- 1 ≤ T ≤ 15
- 1 ≤ k ≤ 14
- 1 ≤ |s| ≤ 10^5
- For tests worth 20 points, 1 ≤ k ≤ 10
- For tests worth 30 more points, there aren't any negated literals
- For tests worth another 20 points, 1 ≤ k ≤ 12
Exemplu
| bytes.in | bytes.out |
|---|---|
| 3 4 (c&d)(!a&b&!c)(b) 4 (!c) 4 (!c&!d)(!a&c&!d)(a&!b&c) | 6 8 8 |
Explicaţie
...
