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 [user:alissonrgs,2016-11-26]. Obrigado especial aos que ajudaram a fazer este editorial: [user:wjoao,2016-11-26], [user:Lamartinec,2016-11-26] e novamente ao [user:alissonrgs,2016-11-26].↵
↵
Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. **Em último caso** vejam o código.↵
↵
[Burguer Time?](https://uva.onlinejudge.org/external/116/11661.pdf)↵
------------------↵
**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.↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
**Complexidade :** O(n)↵
↵
*_n sendo o valor de L na questão_.↵
↵
**Autor :** Filipe Herculano Rocha↵
↵
[Anagram](https://uva.onlinejudge.org/external/1/195.pdf)↵
------------------↵
↵
**Pré-requisitos:** [next_permutation](http://www.cplusplus.com/reference/algorithm/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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(n!)↵
↵
*_n sendo o tamanho da string._↵
↵
**Autor :** Lamartine Cabral↵
↵
↵
↵
[Euclid Problem](https://uva.onlinejudge.org/external/101/10104.pdf)↵
------------------↵
↵
**Pré-requisito:** Algoritmo de Euclides extendido↵
↵
Esse problema é a aplicação prática do [algoritmo de Euclides extendido](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(log n)↵
↵
**Autor:** Filipe Herculano Rocha↵
↵
↵
[Laser Sculpture](https://uva.onlinejudge.org/external/116/11683.pdf)↵
------------------↵
↵
**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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(n)↵
↵
*_n sendo o valor de C na questão._↵
↵
**Autor :** Filipe Herculano Rocha ↵
↵
[Maximum Product](https://uva.onlinejudge.org/external/110/11059.pdf)↵
------------------↵
**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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(N^3)↵
↵
**Autor:** Alisson Soares↵
↵
↵
[Where is the Marble?](https://uva.onlinejudge.org/external/104/10474.pdf)↵
------------------↵
↵
**Pré-requisitos:** Ordenação, [busca binária](https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria), [lower_bound](http://www.cplusplus.com/reference/algorithm/lower_bound/)↵
↵
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)↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
**Autor :** Filipe Herculano Rocha↵
↵
<spoiler summary="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;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
**Autor:** João Vitor↵
↵
[Zeros and Ones](https://uva.onlinejudge.org/external/103/10324.pdf)↵
------------------↵
↵
**Pré-requisitos:** [Prefix Sum](https://en.wikipedia.org/wiki/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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(n+q)↵
↵
*_n sendo o tamanho da string e q sendo a quantidade de queries_↵
↵
**Autor:** Alisson Soares↵
↵
↵
[Pontentiometers](https://uva.onlinejudge.org/external/120/12086.pdf)↵
------------------↵
↵
**Pré-requisitos:** [Bit — Fenwick Tree](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/)↵
↵
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.↵
↵
<spoiler summary="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;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(n*logn + q*logn)↵
↵
*_q sendo a quantidade de queries na BIT._↵
↵
**Autor:** João vitor↵
↵
↵
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 [user:alissonrgs,2016-11-26]. Obrigado especial aos que ajudaram a fazer este editorial: [user:wjoao,2016-11-26], [user:Lamartinec,2016-11-26] e novamente ao [user:alissonrgs,2016-11-26].↵
↵
Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. **Em último caso** vejam o código.↵
↵
[Burguer Time?](https://uva.onlinejudge.org/external/116/11661.pdf)↵
------------------↵
**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.↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
**Complexidade :** O(n)↵
↵
*_n sendo o valor de L na questão_.↵
↵
**Autor :** Filipe Herculano Rocha↵
↵
[Anagram](https://uva.onlinejudge.org/external/1/195.pdf)↵
------------------↵
↵
**Pré-requisitos:** [next_permutation](http://www.cplusplus.com/reference/algorithm/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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(n!)↵
↵
*_n sendo o tamanho da string._↵
↵
**Autor :** Lamartine Cabral↵
↵
↵
↵
[Euclid Problem](https://uva.onlinejudge.org/external/101/10104.pdf)↵
------------------↵
↵
**Pré-requisito:** Algoritmo de Euclides extendido↵
↵
Esse problema é a aplicação prática do [algoritmo de Euclides extendido](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(log n)↵
↵
**Autor:** Filipe Herculano Rocha↵
↵
↵
[Laser Sculpture](https://uva.onlinejudge.org/external/116/11683.pdf)↵
------------------↵
↵
**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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade :** O(n)↵
↵
*_n sendo o valor de C na questão._↵
↵
**Autor :** Filipe Herculano Rocha ↵
↵
[Maximum Product](https://uva.onlinejudge.org/external/110/11059.pdf)↵
------------------↵
**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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(N^3)↵
↵
**Autor:** Alisson Soares↵
↵
↵
[Where is the Marble?](https://uva.onlinejudge.org/external/104/10474.pdf)↵
------------------↵
↵
**Pré-requisitos:** Ordenação, [busca binária](https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria), [lower_bound](http://www.cplusplus.com/reference/algorithm/lower_bound/)↵
↵
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)↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
**Autor :** Filipe Herculano Rocha↵
↵
<spoiler summary="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;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
**Autor:** João Vitor↵
↵
[Zeros and Ones](https://uva.onlinejudge.org/external/103/10324.pdf)↵
------------------↵
↵
**Pré-requisitos:** [Prefix Sum](https://en.wikipedia.org/wiki/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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(n+q)↵
↵
*_n sendo o tamanho da string e q sendo a quantidade de queries_↵
↵
**Autor:** Alisson Soares↵
↵
↵
[Pontentiometers](https://uva.onlinejudge.org/external/120/12086.pdf)↵
------------------↵
↵
**Pré-requisitos:** [Bit — Fenwick Tree](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/)↵
↵
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.↵
↵
<spoiler summary="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;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
**Complexidade:** O(n*logn + q*logn)↵
↵
*_q sendo a quantidade de queries na BIT._↵
↵
**Autor:** João vitor↵
↵
