Contest da semana #1
Разница между en12 и en13, 0 символ(ов) изменены
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 &mdash; 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 &mdash; 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↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский Sazzon 2016-11-26 18:19:20 53
en16 Английский Sazzon 2016-11-26 17:51:29 0 (published)
en15 Английский Sazzon 2016-11-26 16:55:52 13 (saved to drafts)
en14 Английский Sazzon 2016-11-26 16:54:49 222
en13 Английский Sazzon 2016-11-26 04:38:38 0 (published)
en12 Английский Sazzon 2016-11-26 04:37:20 66
en11 Английский Sazzon 2016-11-26 04:35:43 183
en10 Английский Sazzon 2016-11-26 04:29:48 5037
en9 Английский Sazzon 2016-11-26 04:08:17 1026 Tiny change: 'xidade :**\n\n**Auto' -
en8 Английский Sazzon 2016-11-26 03:55:53 1546 Tiny change: 'ade : O(n!)\n\n*_n' -
en7 Английский Sazzon 2016-11-26 03:26:24 161
en6 Английский Sazzon 2016-11-26 03:10:25 1802 Tiny change: ' sum[ j ] - sum[ i ] ' -
en5 Английский Sazzon 2016-11-26 02:56:47 1398 Tiny change: 'ade :** O(S.size())\n\n[Anag' -
en4 Английский Sazzon 2016-11-26 02:26:38 117
en3 Английский Sazzon 2016-11-26 02:19:53 2 Tiny change: ' todos! \nEsse é o' -> ' todos! \n\nEsse é o'
en2 Английский Sazzon 2016-11-26 02:19:27 18
en1 Английский Sazzon 2016-11-26 02:18:35 3701 Initial revision (saved to drafts)