O enunciado dessa questão é bem direto: devemos iterar pela matriz procurando o elemento zero. Note que o enunciado garante que só há um 0 por matriz.
Clique para ver o código (S2 Forbes)
#include <bits/stdc++.h>
using namespace std;
/* O(N * M). */
int main(){
int n, m, x, i, j;
scanf("%d%d", &n, &m);
// Para cada elemento da matriz NxM.
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
scanf("%d", &x);
if (!x){ // O mesmo que if (x == 0)
printf("%d %d\n", i, j);
}
}
}
return 0;
}Nesse problema, a distäncia total é a soma das distâncias absolutas entre os andares de parada do relatório.
Clique para ver o código
#include <bits/stdc++.h>
using namespace std;
#define N 100000
int v[N];
/* O(N). */
int main(){
int n, ans, i;
// Ignoramos o segundo inteiro H, pois é irrelevante para o nosso problema.
scanf("%d%*d", &n);
for (i = 0; i < n; i++){
scanf("%d", v + i);
}
ans = 0;
// Somando as as diferenças absolutas entre o andares.
for (i = 1; i < n; i++){
ans += abs(v[i] - v[i - 1]);
}
// Multiplicando a resposta por 4 pois a distância entre andares consecutivos é 4.
printf("%d\n", 4 * ans);
return 0;
}Nesse problema, devemos iterar pela matriz coluna por coluna, checando 3 casos:
- se a coluna é totalmente crescente (para toda linha i em uma coluna fixa j, temos que m[i-1][j] < m[i][j])
- se a coluna é totalmente decrescente (para toda linha i em uma coluna fixa j, temos que m[i-1][j] > m[i][j])
- se a coluna possui os mesmos valores (para toda linha i em uma coluna fixa j, temos que m[i-1][j] == m[i][j])
Clique para ver o código
#include <bits/stdc++.h>
using namespace std;
#define N 100
#define M 100
long long mat[N][M];
/* O(N * M). */
int main(){
bool equal, asc, desc;
int n, m, i, j;
scanf("%d%d", &n, &m);
// Lendo a matriz NxM.
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
scanf("%lld", mat[i] + j);
}
}
for (j = 0; j < m; j++){
// Dizendo que inicialmente os elementos dessa coluna são iguais, ascendentes e descendentes.
equal = asc = desc = true;
// Para cada par de elementos consecutivos nessa coluna.
for (i = 1; i < n; i++){
// A coluna continua sendo igual se ela era igual até a última iteração e se o elemento atual for igual ao anterior.
equal = equal and (mat[i - 1][j] == mat[i][j]);
// A coluna continua sendo ascendente se ela era ascendente até a última iteração e se o elemento atual for maior que o anterior.
asc = asc and (mat[i - 1][j] < mat[i][j]);
// A coluna continua sendo descendente se ela era descendente até a última iteração e se o elemento atual for menor que o anterior.
desc = desc and (mat[i - 1][j] > mat[i][j]);
}
// Se for uma coluna com elementos iguais, ascendentes ou descendentes.
if (equal or asc or desc){
printf("S\n");
}
else{
printf("N\n");
}
}
return 0;
}Esse problema é provavelmente o que tem a implementação mais complicada desse contest. Uma das possíveis soluções é marcar todos os espaços que são visíveis por inimigos (e aqueles que não são possíveis de serem ocupados pelo jogador: paredes)
Após esse processamento, temos que contar quantas posições nos sobraram.
Clique para ver o código
#include <bits/stdc++.h>
using namespace std;
#define N 1000
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
char mat[N][N];
int aux[N][N];
int n, m;
/* O(1) Retorna true se a coordenada (x, y) estiver dentro da matriz NxM. */
bool inside(int x, int y){
return x >= 0 and x < n and y >= 0 and y < m;
}
/* O(1) Retorna true se a coordenada (x, y) estiver dentro da matriz NxM e se não for uma parede. */
bool valid(int x, int y){
return inside(x, y) and mat[x][y] != '#';
}
/* O(max(N, M)) Marca todas as posições a partir de (x, y) usando o passo dado pelo vetor direção (x_step, y_step) com a marcação da direção dir. */
void fill(int x, int y, int dir, int x_step, int y_step){
// Enquanto a casa (x, y) for válida e não tiver sido vista pela mesma direção dir.
while (valid(x, y) and !(aux[x][y] & (1 << dir))){
// Marcando a casa (x, y) como vista pela direção dir.
aux[x][y] |= (1 << dir);
// Dando um passo para alguma das direções.
x += x_step;
y += y_step;
}
}
/* O(N * M). */
int main(){
int ans, i, j;
// Lendo a matriz de caracteres.
scanf("%d%d%*c", &n, &m);
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
scanf("%c", mat[i] + j);
}
// Ignorando o '\n'.
scanf("%*c");
}
// Podemos ler também da seguinte forma:
// scanf("%d%d", &n, &m);
// for (i = 0; i < n; i++){
// for (j = 0; j < m; j++){
// scanf(" %c", mat[i] + j); // Note o espaço antes do %c. Esse espaço faz com que o %c não pegue nenhum whitespace (' ', '\t', '\n').
// }
// }
// Para cada elemento da matriz NxM.
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
if (mat[i][j] == 'U'){ // Se for um inimigo olhando pra cima.
fill(i, j, UP, -1, 0);
}
else if (mat[i][j] == 'D'){ // Se for um inimigo olhando pra baixo.
fill(i, j, DOWN, 1, 0);
}
else if (mat[i][j] == 'L'){ // Se for um inimigo olhando pra esquerda.
fill(i, j, LEFT, 0, -1);
}
else if (mat[i][j] == 'R'){ // Se for um inimigo olhando pra direita.
fill(i, j, RIGHT, 0, 1);
}
}
}
ans = 0;
// Contando o número de casas vazias que não são visíveis por nenhum inimigo.
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
// Se aux[i][j] não estiver marcado (for igual a 0) e se a posição mat[i][j] for vazia (não for uma parede).
if (!aux[i][j] and mat[i][j] == '.'){
ans++;
}
}
}
if (ans == 0){
printf("NO SOLUTION\n");
}
else if (ans == 1){
printf("ONLY ONE SOLUTION\n");
}
else{
printf("MULTIPLE SOLUTIONS\n");
}
return 0;
}Esse problema é interessante, devemos calcular uma soma de P.A.. Mas é importante notar que somar utilizando um for seria muito lento, portanto utilizaremos a fórmula.
Clique para ver o código
#include <bits/stdc++.h>
using namespace std;
/* O(1). */
int main(){
long long n, b;
scanf("%lld%lld", &n, &b);
// A resposta é uma soma de PA com o primeiro elemento dado por B, o último elemento dado por B - N + 1 e o número de elementos dado por N.
printf("%lld\n", ((2 * b - n + 1) * n) / 2);
return 0;
}