Olá todos!
Esse é o primeiro editorial feito pelos alunos da UECE no Codeforces. Esse contest foi criado como um treino do grupo de estudos da maratona. A seleção das questões do UVa, organização do contest foi feita com muito empenho pelo alissonrgs. Obrigado especial aos que ajudaram a fazer este editorial: wjoao, Lamartine e novamente ao alissonrgs.
Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. Em último caso vejam o código.
Pré-requisitos: Nenhum
O problema é facilmente resolvido se pensarmos que se houver um restaurante e uma farmácia no mesmo local (se houver um caractere 'Z' na string) a distância mínima já vai ser 0. Se não houver, basta iterar por toda a string guardando a posição da última aparição de 'R' e 'D'. Quando uma nova posição aparecer, verificar se a distância entre os 2 atuais é menor do que a anteriormente calculada.
Code#include <bits/stdc++.h>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))
typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;
const int INF = 0x3f3f3f3f;
using namespace std;
int main(){
int l;
while(scanf("%d%*c", &l) && l){
char c;
int res = INF, d = -1, r = -1;
REP(i, l){
scanf("%c", &c);
if(c == 'R'){
r = i;
if(d != -1) res = min(res, abs(r-d));
} else if(c == 'D'){
d = i;
if(r != -1) res = min(res, abs(r-d));
} else if(c == 'Z') res = 0;
}
if(d != -1 && r != -1) res = min(res, abs(r-d));
cout << res << endl;
}
return 0;
}
Complexidade : O(n)
*n sendo o valor de L na questão.
Autor : Filipe Herculano Rocha
Pré-requisitos: next_permutation
Para resolver essa questão vou usar dois métodos da biblioteca padrão: sort() e next_permutation(). O sort vai fazer a primeira string e o next_permutation vai gerar a próxima permutação da string inicial, na ordem lexicográfica. O problema é que a questão quer em ordem alfabética, então “Ba” virá antes de “aB”, dando resposta errada. Meu truque foi fazer um vetor com valores relativos aos caracteres, de modo que a string AaBbCc… vire o vetor {0,1,2,3,4,5...}. Daí, uso sort e next_permutation nesse vetor. Na hora de imprimir, verifico se o valor é par. Se for, então é maiúsculo. Senão, minúsculo.
Code#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
vector<int> v;
string s;
int n,i,x;
cin>>n;
while(n--){
v.clear();
cin>>s;
for(i=0; i<s.size(); i++){
if(s[i]<'a') x = (s[i]-'A')*2;
else x = (s[i]-'a')*2 + 1;
v.push_back(x);
}
sort(v.begin(), v.end());
do{
for(i=0; i<s.size(); i++){
if(v[i]%2==0) cout<<(char)(v[i]/2 + 'A');
else cout<<(char)(v[i]/2 + 'a');
} cout<<endl;
} while( next_permutation(v.begin(), v.end()) );
}
return 0;
}
Complexidade : O(n!)
*n sendo o tamanho da string.
Autor : Lamartine Cabral
Pré-requisito: Algoritmo de Euclides extendido
Esse problema é a aplicação prática do algoritmo de Euclides extendido.
Code#include <bits/stdc++.h>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))
typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;
const int INF = 0x3f3f3f3f;
using namespace std;
ll x, y, d;
void euclid(ll a, ll b){
if(b == 0){
x = 1;
y = 0;
d = a;
return;
}
euclid(b, a%b);
ll x1 = y;
ll y1 = x - (a / b) * y;
x = x1;
y = y1;
}
int main(){
ll a, b;
while(~scanf("%lld %lld", &a, &b)){
euclid(a, b);
printf("%lld %lld %lld\n", x, y, d);
}
return 0;
}
Complexidade : O(log n)
Autor: Filipe Herculano Rocha
Pré-requisitos: Nenhum
Com uma simples passada por todo o vetor com as alturas finais dos blocos, nós conseguimos o resultado. Dado uma altura de um bloco i (0 <= i < C) em um vetor v, se o bloco for o primeiro, deve-se somar ao contador abs(A-v[i]) . Caso i não seja o primeiro, deve-se verificar se ele é menor que o bloco anterior e se for soma-se ao contador abs(v[i]-v[i-1]) . O motivo é que raios são comuns em alturas superiores à direita, porém não são comuns quando a altura é menor.
Code#include <bits/stdc++.h>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))
typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;
const int INF = 0x3f3f3f3f;
using namespace std;
int main(){
int a, c;
while(scanf("%d", &a) && a){
scanf("%d", &c);
int v[c], cnt = 0;
REP(i, c) scanf("%d", &v[i]);
REP(i, c){
if(i) {
if(v[i] < v[i-1]) cnt += abs(v[i]-v[i-1]);
} else cnt += abs(a-v[i]);
}
cout << cnt << endl;
}
return 0;
}
Complexidade : O(n)
*n sendo o valor de C na questão.
Autor : Filipe Herculano Rocha
Pré-requisitos: Nenhum
Como o tamanho máximo do vetor é N = 18 (bem pequeno), uma solução possível era testar todos os conjuntos existentes. Com um loop para representar o tamanho do conjunto a ser testado (1 <= i <= N), bastava realizar mais dois loops com os valores do vetor, um de (0 <= j < N) e o outro com o tamanho do conjunto (j <= k < j + i), multiplicava os valores do conjunto e no final testava se o valor era maior.
Code#include <bits/stdc++.h>
#define NMAX 18
#define ll long long
using namespace std;
int v[NMAX+1];
int main() {
int n, _case = 1;
while( ~scanf( "%d", &n ) && n ) {
for( int i = 0; i < n; i++ )
scanf( "%d", &v[i] );
ll maxp = 0;
for( int i = 1; i <= n; i++ ) {
for( int j = 0; j < n; j++ ) {
ll p = 1;
for( int k = j; k < j + i && k < n; k++ )
p *= v[k];
maxp = max( maxp, p );
}
}
printf( "Case #%d: The maximum product is %Ld.\n\n", _case++, maxp );
}
return 0;
}
Complexidade: O(N^3)
Autor: Alisson Soares
Pré-requisitos: Ordenação, busca binária
Para achar a solução da questão, tinha que receber os N elementos, e ordená-los. Após isso receber Q consultas, cada uma delas, tinha que retornar o índice do número e se existir mais de um número igual, pegar o menor índice, no vetor ordenado. Para se ordenar um vetor, pode-se usar a função sort. Ex: int vetor[n]; sort(vetor, vetor+n); Para realizar a busca binária em um vetor ordenado, você pode usar o lower_bound do cpp: Ex: int *p = lower_bound(vetor, vetor+n, valor_buscado); Obs: Detalhe que o lower_bound retorna um ponteiro para a posição do vetor, onde está o elemento encontrato, e caso ele não exista, ele retorna para algum número menor que o número buscado, e o mais próximo dele. Logo ao fazer o lower_bound, é necessário verificar se o valor de *p é igual ao valor da busca. Se for igual é porque foi achado e é necessário achar o indice e para isso é necessário apenas fazer uma operação de ponteiros, diminuindo p por vetor( A posição atual do ponteiro no meio do vetor, menos a posição do ponteiro inicial do vetor ) e o resultado disso é o indice, baseado em 0. Caso não fosse igual, o elemento não teria sido achado.
Complexidade : O(n*log n + q*log n)
Código com busca binária#include <bits/stdc++.h>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))
typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;
const int INF = 0x3f3f3f3f;
using namespace std;
int bs(vector<int> v, int num){
int head = 0, tail = v.size()-1, body;
while(head <= tail){
body = (head+tail)/2;
if(v[body] == num){
if(body == 0 || v[body-1] != v[body]) return body;
else tail = body-1;
} else if(v[body] > num) tail = body-1;
else head = body+1;
}
return -1;
}
int main(){
int n, q, caso = 1;
while(scanf("%d %d", &n, &q) && (n || q)){
int index;
vector<int> v(n);
REP(i, n) scanf("%d", &v[i]);
sort(all(v));
printf("CASE# %d:\n", caso++);
REP(i, q){
int temp;
scanf("%d", &temp);
index = bs(v, temp);
if(index == -1) printf("%d not found\n", temp);
else printf("%d found at %d\n", temp, index+1);
}
}
return 0;
}
Autor : Filipe Herculano Rocha
Código com lower_bound#include<bits/stdc++.h>
using namespace std;
int numeros[10100];
int n, m, a, t =1;
int main(){
while( cin >> n >> m && n ){
for(int i = 0; i < n; i++){
cin >> a;
numeros[i] = a;
}
sort(numeros, numeros + n);
cout << "CASE# "<< t++ << ":" << endl;
for(int i = 0; i < m; i++){
cin >> a;
int * it = lower_bound(numeros, numeros+n, a);
if( it == numeros+n ){ // O numero pesquisado era maior do que todos existentes
cout << a << " not found" << endl;
}else{
int peso = *it;
if( peso == a ){ // Verifica se o numero encontrato é igual ao pesquisado
cout << peso << " found at " << (int)(it-numeros)+1 << endl;
}else{
cout << a << " not found" << endl;
}
}
}
}
return 0;
}
Autor: João Vitor
Pré-requisitos: Prefix Sum
Como a string tinha apenas 1s e 0s era possível aplicar a soma de prefixos, assim usando um vetor, bastava passar uma única vez por toda a string e ir somando o valor da posição da string com a posição anterior do vetor ( sum[ i ] = str[ i ] + sum[ i-1 ] ). Feito isso as consultas ficam O(1), pois para uma consulta de i até j com j > i, basta calcular ( sum[ j ]-sum[ i ] + s[ i ] ), se for igual a diferença dos índices ( j — i + 1 ) é porque todos os valores na string são 1s, e caso for 0 é porque todos os valores na string são 0s.
Esse problema também era possível com força bruta, a cada consulta bastava fazer um ‘for’ verificando se uma posição no vetor era diferente da anterior, caso fosse é porque a sequência não é de mesmos dígitos, caso contrário sim.
Code#include <bits/stdc++.h>
#define NMAX 1000000
using namespace std;
int sum[NMAX+1];
int ctoi( char c ) { return (int)( c - '0' ); }
int main() {
string s;
int q, i, j, _case = 1;
while( cin >> s ) {
sum[0] = ctoi( s[0] );
for( int k = 1; k < (int)s.size(); k++ )
sum[k] = sum[k-1] + ctoi( s[k] );
cin >> q;
cout << "Case " << _case++ << ":" << endl;
while( q-- ) {
cin >> i >> j;
if( i > j ) swap( i, j );
int v = sum[j] - sum[i] + ctoi( s[i] );
if( v == j-i+1 || v == 0 )
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
Complexidade: O(n+q)
*n sendo o tamanho da string e q sendo a quantidade de queries
Autor: Alisson Soares
Pré-requisitos: Bit — Fenwick Tree
Utilização básica da bit. Usa-se o operador de Update em um ponto. e de Query para saber o resultado da soma entre intervalos.
Code#include<bits/stdc++.h>
#define MAXN 200005
int n, a, b, t= 1;
int Bit[MAXN];
char op[10];
void Update(int p, int v){
while(p < MAXN){
Bit[p] += v;
p += p & -p;
}
}
int Query(int p){
int ans = 0;
while(p > 0){
ans += Bit[p];
p -= p & -p;
}
return ans;
}
int main(){
while( scanf(" %d", &n) && n){
memset(Bit, 0, sizeof Bit);
for(int i = 1; i <= n; i++){
scanf("%d", &a);
Update(i, a);
}
if( t != 1 ) printf("\n");
printf("Case %d:\n", t++);
while( scanf(" %s", op) && op[0] != 'E' ){
if( op[0] == 'S' ){
scanf(" %d%d", &a, &b);
int atual = Query(a) - Query(a-1);
Update(a, b - atual);
}else if( op[0] == 'M' ){
scanf(" %d%d", &a, &b);
printf("%d\n", Query(b)-Query(a-1));
}
}
}
return 0;
}
Complexidade: O(n*logn + q*logn)
*q sendo a quantidade de queries na BIT.
Autor: João vitor