“Premature optimization is the root of all evil.”
― Donald Ervin Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms
Las soluciones se explicarán en más detalle en clase.
Basta darse cuenta que la respuesta tiene la forma $abcabcabc \dots$ donde $abc$ es una permutación de $RGB$, luego podemos probar todas las opciones en $O(3!n) = O(n)$
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
cin >> n;
string s;
cin >> s;
vector <char> p = {0, 1, 2};
string X = "RGB";
int mn = INT_MAX;
string ans;
do {
int cnt = 0;
for (int i = 0; i < 3 and i < s.size(); i++) {
for (int j = i; j < s.size(); j += 3) {
cnt += s[j] != X[p[i]];
}
}
if (cnt < mn) {
mn = cnt;
string ret = "";
for (int k = 0; k < s.size(); k++) {
ret += X[p[k % 3]];
}
ans = ret;
}
} while (next_permutation(begin(p), end(p)));
cout << mn << endl;
cout << ans << endl;
return (0);
}
Notemos que $abcdefghij$ será una permutación de $0123456789$. Luego, pademos buscar la respuesta en cada permutación en $O(q!n)$ con $q = 10$, pero $n \leq 1000$ así que ese enfoque daría TLE
. Sim embargo, notamos que podemos guardar un contador de frecuencia por posiciones y luego simular la suma con ello, logrando así una solución en $O(q!L S)$ con $L \leq 6 \land S = 10$
#include <bits/stdc++.h>
using namespace std;
const int LEN = 6, SIGMA = 10;
int cnt[LEN + 1][SIGMA + 1], val[SIGMA + 1];
bool invalid[SIGMA + 1];
int main () {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string number;
cin >> number;
invalid[number[0] - 'a'] = true;
int sz = number.size();
for (int j = 0; j < sz; j++) {
cnt[LEN - sz + j][number[j] - 'a']++;
}
}
string sigma = "abcdefghij";
int ans = INT_MAX;
do {
if (invalid[sigma[0] - 'a']) continue;
int p = 0;
for (const char ch: sigma) val[ch - 'a'] = p++;
int sum = 0, carry = 0, power = 1;
for (int i = LEN - 1; i >= 0; i--) {
int ac = 0;
for (int j = 0; j < SIGMA; j++) {
ac += cnt[i][j] * val[j];
}
ac += carry;
sum = sum + power * (ac % 10);
power *= 10;
carry = ac / 10;
}
while (carry) {
sum = sum + power * (carry % 10);
power *= 10;
carry /= 10;
}
ans = min(ans, sum);
} while (next_permutation(begin(sigma), end(sigma)));
cout << ans << endl;
return (0);
}
Sea $abcd$ una permutación de $AGTC$
Luego, notemos que una matriz de $1 \times n$ tendra la forma:
$$ababababababab \dots$$Una matriz de $2 \times n$ tendrá la forma:
$$ababab \dots$$$$cdcdcd \dots$$Ahora, observamos que una matriz de $n \times m$ en todas las filas impares tendrá alguna de estas 2 formas:
$$ababab \dots \text{ | } bababa \dots$$Y las filas pares tendrán alguna de estas 2 formas:
$$cdcdcd \dots \text{ | } dcdcdc \dots$$Asi, para cada permutación de $AGTC$ podemos probar obtener una matriz con las anteriores caracteristicas (de manera que minimicemos la cantidad de celdas a cambiar) y luego intentamos hacer lo mismo en la matriz transpuesta en $O(4!nm) = O(nm)$.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector <string> table;
int rowCheck (vector <string>& tmp, string pat) {
int totalCost = 0;
for (int row = 0; row < n; row++) {
char a, b;
if (row & 1) a = pat[2], b = pat[3];
else a = pat[0], b = pat[1];
int cost1 = 0, cost2 = 0;
for (int col = 0; col < m; col++) {
if (col & 1) cost1 += table[row][col] != b;
else cost1 += table[row][col] != a;
}
swap(a, b);
for (int col = 0; col < m; col++) {
if (col & 1) cost2 += table[row][col] != b;
else cost2 += table[row][col] != a;
}
totalCost += min(cost1, cost2);
if (cost1 < cost2) swap(a, b);
for (int col = 0; col < m; col++) tmp[row][col] = (col & 1) ? b : a;
}
return totalCost;
}
int colCheck (vector <string>& tmp, string pat) {
int totalCost = 0;
for (int col = 0; col < m; col++) {
char a, b;
if (col & 1) a = pat[1], b = pat[3];
else a = pat[0], b = pat[2];
int cost1 = 0, cost2 = 0;
for (int row = 0; row < n; row++) {
if (row & 1) cost1 += table[row][col] != b;
else cost1 += table[row][col] != a;
}
swap(a, b);
for (int row = 0; row < n; row++) {
if (row & 1) cost2 += table[row][col] != b;
else cost2 += table[row][col] != a;
}
if (cost1 < cost2) swap(a, b);
totalCost += min(cost1, cost2);
for (int row = 0; row < n; row++) tmp[row][col] = (row & 1) ? b : a;
}
return totalCost;
}
int main () {
cin >> n >> m;
table.resize(n);
for (int row = 0; row < n; row++) cin >> table[row];
string AGCT = "AGCT";
int mn = n * m + 1;
vector <string> ans;
do {
vector <string> tmp1(n, string(m, ' '));
vector <string> tmp2(n, string(m, ' '));
int ret1 = rowCheck(tmp1, AGCT);
int ret2 = colCheck(tmp2, AGCT);
if (ret1 <= ret2 and ret1 < mn) {
ans = tmp1;
mn = ret1;
}
if (ret2 <= ret1 and ret2 < mn) {
ans = tmp2;
mn = ret2;
}
} while (next_permutation(begin(AGCT), end(AGCT)));
for (string row: ans) cout << row << endl;
cerr << mn << endl;
return (0);
}
Podemos simplemente generar todas las fracciones improvias en el rango pedido, ordenarlas e imprimir la respuesta en $O(n ^ 2)$
#include <bits/stdc++.h>
using namespace std;
struct Fraction {
int num, den;
Fraction() {}
Fraction(const int& _num, const int& _den):
num(_num), den(_den) {}
bool operator < (const Fraction& other) const {
return num * other.den < den * other.num;
}
inline void print() const {
cout << num << "/" << den << endl;
}
};
int n, k;
int main() {
while (cin >> n >> k) {
vector <Fraction> arr;
for (int den = 1; den <= n; den++) {
for (int num = 1; num <= den; num++) {
// __gcd(a, b) = mcm(a, b)
if (__gcd(num, den) == 1) {
arr.push_back(Fraction(num, den));
}
}
}
sort(begin(arr), end(arr));
arr[k - 1].print();
}
return (0);
}
Notemos que queremos obtener un ordenamiento de los números de manera que al juntarlos de el mayor número posible. Luego, podemos ordenarlos con una relación de orden (ver código) en $O(n ^ 2 log n)$
#include <bits/stdc++.h>
#define SIZE 60
using namespace std;
int n;
string v[SIZE], s1, s2;
bool cmp(const string& x, const string& y){
s1 = x + y, s2 = y + x;
return (s1 > s2);
}
int main(){
while(scanf("%d", &n), n!=0){
for (int i = 0; i < n; i++) cin >> v[i];
sort(v, v + n, cmp);
for (int i = 0; i < n; i++) cout << v[i]; cout << endl;
}
return(0);
}
Creamos un struct
con los datos necesarios para cada equipo y conforme vamos leyendo la entrada vamos actualizando sus parámetros. Luego, ordenamos los equipos de acuerdo a la relación señalada en el problema y los imprimos en $O(n log n)$
// En clase se detallara de que otras formas se podría haber implementado la solución
#include <bits/stdc++.h>
#define SIZE 20
using namespace std;
struct Team{
char name[SIZE], lower_name[SIZE];
int points, games, goals, sgoals, dif;
}aux;
int tc, t, g, pos1, pos2, g1, g2, j;
char s[SIZE], team1[SIZE], team2[SIZE];
vector <Team> v;
inline bool equals(Team x, Team y) {
return (x.points == y.points && x.dif == y.dif && x.goals == y.goals);
}
bool cmp(const Team& x, const Team& y) {
if(x.points != y.points) return (x.points > y.points);
if(x.dif != y.dif) return (x.dif > y.dif);
if(x.goals != y.goals) return (x.goals > y.goals);
return (strcmp(x.lower_name, y.lower_name) < 0);
}
void lowerNames() {
for(int i = 0; i < v.size(); i++){
for(j = 0; v[i].name[j]; j++) v[i].lower_name[j] = tolower(v[i].name[j]);
v[i].lower_name[j] = '\0';
}
}
int findTeam(char x[]) {
for(int i = 0; i < v.size(); i++) if(strcmp(v[i].name, x)==0) return i;
}
void printResults() {
int it = 1;
for(int i = 0; i < v.size(); i++, it++){
if(i == 0 || equals(v[i], v[i - 1]) == false) printf("%2d.", it);
else printf(" ");
printf("%16s %3d %3d %3d %3d %3d ", v[i].name, v[i].points, v[i].games, v[i].goals, v[i].sgoals, v[i].dif);
if(v[i].games) printf("%6.2f\n", 100.0 * v[i].points / (3.0 * v[i].games));
else printf(" N/A\n");
}
}
int main(){
while (scanf("%d %d\n", &t, &g), t | g) {
if (tc++) putchar('\n');
v.clear();
for (int i = 0; i < t; i++) scanf("%s", s), strcpy(aux.name, s), v.push_back(aux);
for (int i = 0;i < g; i++){
scanf("%s %d - %d %s", team1, &g1, &g2, team2);
pos1 = findTeam(team1);
pos2 = findTeam(team2);
if(g1 > g2) v[pos1].points += 3;
else if(g1 < g2) v[pos2].points += 3;
else v[pos1].points += 1, v[pos2].points += 1;
v[pos1].games += 1, v[pos2].games += 1;
v[pos1].goals += g1, v[pos2].goals += g2;
v[pos1].sgoals += g2, v[pos2].sgoals += g1;
v[pos1].dif += g1 - g2;
v[pos2].dif += g2 - g1;
}
lowerNames();
sort(v.begin(), v.end(), cmp);
printResults();
}
return(0);
}
Cada angulo dado tiene 2 opciones (rotación horaria o antihoraria). Luego, simplemente podemos probar todas las opciones en $O(2 ^ n)$
#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> angle;
bool check (int mask) {
int cur = 0;
for (int bit = 0; bit < n; bit++) {
if ((mask >> bit) bitand 1) cur += angle[bit];
else cur -= angle[bit];
}
return (cur % 360) == 0;
}
int main () {
cin >> n;
angle.resize(n);
for (int i = 0; i < n; i++) cin >> angle[i];
bool ok = false;
for (int mask = 0; mask < (1 << n); mask++) ok |= check(mask);
puts(ok ? "YES" : "NO");
return (0);
}
Iteramos los bits y si esta prendido de acuerdo a la paridad de la cantidad de bits prendido encontrad hasta el momento vamos construyendo la respuesta.
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
while (cin >> n, n) {
int a = 0, b = 0;
bool toA = true;
for (int bit = 0; bit < 32; bit++) {
if ((n >> bit) & 1) {
if (toA) a |= 1 << bit;
else b |= 1 << bit;
toA = !toA;
}
}
cout << a << ' ' << b << endl;
}
return (0);
}
Notemos que si selecciono una celda 2 veces el tablero no se altera. Así, para cada pieza solo tiene sentido el tomarla o el no tomarla. Luego, podemos simular las celdas que tomamos en $O(2 ^ n n ^ 2)$ donde $n = 16$
#include <bits/stdc++.h>
using namespace std;
int main () {
int dr[] = {0, 1, 0, -1, 0};
int dc[] = {0, 0, 1, 0, -1};
vector <string> grid(4);
vector <string> black(4, string(4, 'b'));
vector <string> white(4, string(4, 'w'));
for (int i = 0; i < 4; i++) cin >> grid[i];
int ans = INT_MAX;
for (int mask = 0; mask < (1 << 16); mask++) {
vector <string> tmp = grid;
int cnt = 0;
for (int bit = 0; bit < 16; bit++) {
if ((mask >> bit) & 1) {
cnt++;
int r = bit / 4;
int c = bit % 4;
for (int d = 0; d < 5; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (0 <= min(nr, nc) and max(nr, nc) < 4) {
if (tmp[nr][nc] == 'b') tmp[nr][nc] = 'w';
else tmp[nr][nc] = 'b';
}
}
}
}
if (tmp == black or tmp == white) {
ans = min(ans, cnt);
}
}
if (ans == INT_MAX) puts("Impossible");
else cout << ans << endl;
return (0);
}
Un algoritmo recursivo puede ser descrito asi:
Escribe un programa recursivo que reciba un entero e imprima su representación binaria.
¿Qué diferencia hay entre la Solución 1 y Solución 2?
#include <bits/stdc++.h>
using namespace std;
// Solucion 1
void rec1 (int num, string& bin) {
if (num == 0) return;
bin += '0' + (num % 2);
rec1(num / 2, bin);
}
void printBinary1 (int num) {
string bin = "";
if (num == 0) bin = "0";
else rec1(num, bin);
reverse(begin(bin), end(bin));
cout << bin << endl;
}
// Solucion 2
void rec2 (int num, string& bin) {
if (num == 0) return;
rec2(num / 2, bin);
bin += '0' + (num % 2);
}
void printBinary2 (int num) {
string bin = "";
if (num == 0) bin = "0";
else rec2(num, bin);
cout << bin << endl;
}
int main () {
printBinary1(8);
printBinary2(8);
return (0);
}
C(n, m)
.rec(n, d)
que retorne la cantidad de d
s que posee el número n
.Escribe un programa recursivo que calcule $a ^ b$ en $log (b)$ para $a, b$ enteros.
Notamos que:
$$ power(a, b) = \begin{cases} 1 & \quad \text{si } b = 0\\ power(a, b / 2) ^ 2 & \quad \text{si } b \text{ es par}\\ a * power(a, \lfloor b / 2 \rfloor) ^ 2 & \quad \text{si } b \text{ es impar} \end{cases} $$#include <bits/stdc++.h>
using namespace std;
long long sq (long long a) { return (a * a); }
long long power (long long a, int b) {
if (b == 0) return 1;
if (b & 1) return a * sq(power(a, b / 2));
return sq(power(a, b / 2));
}
int main () {
cout << power(2, 60) << endl;
assert(power(2, 60) == (1LL << 60));
return (0);
}
Ahora, analizaremos como resolver estos problemas:
Soluciones
Básicamente nos piden:
$$\sum_{k = a}^{b}sumaDeDigitos(k)$$$$0 \leq a \leq b \leq 1e9$$Luego, la solucion trivial de iterar en el rango $[a, b]$ nos daría una complejidad $(b \log b)$ lo cual obviamente daría TLE.
Entonces, busquemos una solución más eficiente.
Primero, definamos:
$$S(x) = \sum_{k = 0}^{x}sumaDeDigitos(k)$$Luego, nuestro problema se reduce a calcular $S(b) - S(a - 1)$
Ahora, centremonos en calcular eficientemente $S(x)$
Sea $x = \overline{a_na_{n-1} \dots a_k \dots a_2a_1}$
Definamos $$cnt(x, k) = \sum_{i = 0}^{x} \text{el k-esimo digito de } i$$
Luego $$S(x) = \sum_{k = 0} ^ {n} cnt(x, k)$$
Así, como n es $O(log x)$, todo se reduce a calcular eficientemente $cnt(x, k)$
Ahora, para calcular $cnt(x, k)$ notemos que estaremos sumando los k-esimos digitos de los números $num \in [0, x]$.
Sea $num = \overline{p_np_{n-1}\dots p_{k +1}p_{k}k_{k -1}\dots p_{1}}$ (podemos considerar que $num$ siempre tiene n
digitos por simplicidad - si tiene menos de n
digitos simplemente podemos agregarle ceros al inicio y no afectara la respuesta -)
Ahora analicemos por casos:
Si $\overline{p_np_{n-1}\dots p_{k+1}} < \overline{x_nx_{n-1}\dots x_{k+1}}$
Entonces
$\overline{p_np_{n-1}\dots p_{k+1}} \in [0, \overline{x_nx_{n-1}\dots x_{k+1}} - 1] \to $ este numeral puede tomar $\overline{x_nx_{n-1}\dots x_{k+1}}$ valores
$\overline{p_{k-1}\dots p_{1}} \in [0, 999 \dots 9999] \to$ este numeral puede tomar $10 ^ {k - 1}$ valores
Ahora, notamos ademas que $p_k \in [0, 9]$
Luego, en este caso, la suma de los k-esimos dígitos sería:
$$10 ^ {k - 1} \times (\overline{x_nx_{n-1}\dots x_{k+1}}) \times (0 + 1 + 2 + \dots + 9) = 10 ^ {k - 1} \times (\overline{x_nx_{n-1}\dots x_{k+1}}) \times 45$$
Si $\overline{p_np_{n-1}\dots p_{k+1}} = \overline{x_nx_{n-1}\dots x_{k+1}} \quad \land \quad p_k < x_k$
Entonces
$\overline{p_np_{n-1}\dots p_{k+1}} \in [\overline{x_nx_{n-1}\dots x_{k+1}}, \overline{x_nx_{n-1}\dots x_{k+1}}] \to $ este numeral puede tomar 1 valor
$\overline{p_{k-1}\dots p_{1}} \in [0, 999 \dots 9999] \to$ este numeral puede tomar $10 ^ {k - 1}$ valores
Ahora, notamos ademas que $p_k \in [0, max(0, x_k - 1)]$
Luego, en este caso, la suma de los k-esimos dígitos sería:
$$10 ^ {k - 1} \times (0 + 1 + \dots + max(0, x_k - 1)) = 10 ^ {k - 1} \times max(0, x_k - 1) \times (max(0, x_k - 1) + 1) / 2$$
Si $\overline{p_np_{n-1}\dots p_{k+1}} = \overline{x_nx_{n-1}\dots x_{k+1}} \quad \land \quad p_k = x_k$
Entonces
$\overline{p_np_{n-1}\dots p_{k+1}} \in [\overline{x_nx_{n-1}\dots x_{k+1}}, \overline{x_nx_{n-1}\dots x_{k+1}}] \to $ este numeral puede tomar 1 valor
$\overline{p_{k-1}\dots p_{1}} \in [0, \overline{x_{k - 1}\dots x_1}] \to$ este numeral puede tomar $\overline{x_{k + 1} \dots x_1} + 1$ valores
Ahora, notamos ademas que $p_k \in [x_k, x_k]$
Luego, en este caso, la suma de los k-esimos dígitos sería:
$$p_k \times (\overline{x_{k + 1} \dots x_1} + 1)$$
Notamos que ya no hay mas casos para analizar, luego $cnt(x, k)$ sería la suma de los resultados obtenidos en cada caso, obteniendo:
$$cnt(x, k) = 10 ^ {k - 1} \times (\overline{x_nx_{n-1}\dots x_{k+1}}) \times 45 + 10 ^ {k - 1} \times max(0, x_k - 1) \times (max(0, x_k - 1) + 1) / 2 + p_k \times (\overline{x_{k + 1} \dots x_1} + 1)$$Ahora, con ello ya podemos calcular $S(x)$ lo cual nos permitirá resolver nuestro problema original.
Con ello solo quedaría implementar lo anteriormente descrito ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll s (ll num) { return num * (num + 1) / 2; }
ll sum (ll num, ll power = 1, ll r = 0) {
if (num == 0) return 0;
int d = num % 10;
return (num / 10) * 45 * power + s(max(0, d - 1)) * power + d * (r + 1) + sum(num / 10, power * 10, r + d * power);
}
int main () {
int a, b;
while (cin >> a >> b, a != -1 and b != -1) cout << sum(b) - sum(max(0, a - 1)) << endl;
return (0);
}
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
vector <string> grid;
int DR[] = {-1, -1, 1, 1, 0};
int DC[] = {1, -1, 1, -1, 0};
void print () {
for (int i = 0; i < grid.size(); i++) {
string& row = grid[i];
int j = row.size() - 1;
while (row[j] == ' ') row.erase(row.begin() + j);
cout << row << endl;
}
cout << '-' << endl;
}
void rec (int r, int c, int step) {
if (step == 0) {
grid[r][c] = 'X';
return;
}
for (int d = 0; d < 5; d++) {
rec(r + DR[d] * step, c + DC[d] * step, step / 3);
}
}
int main () {
int n;
while (cin >> n, n != -1) {
int gridSize = int(pow(3, n - 1));
grid = vector <string> (gridSize, string(gridSize, ' '));
int initial = (n == 1) ? 0 : gridSize / 3 + gridSize / 6;
int step = gridSize / 3;
rec(initial, initial, step);
print();
}
return (0);
}