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.↵
↵
**Sorry for the lack of translation, we are from Brazil and the group is closed. Don't downvote this post just because you don't understand the language. We are using the platform to communicate internally. Please be nice !** :-)↵
↵
[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.↵
↵
**Sorry for the lack of translation, we are from Brazil and the group is closed. Don't downvote this post just because you don't understand the language. We are using the platform to communicate internally. Please be nice !** :-)↵
↵
[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↵
↵
