URI (BEECROWD) - 3171 - Cordão de Led - Estruturas e Bibliotecas - C e C++

Olá! Hoje vou apresentar a solução de mais um problema da categoria estruturas e bibliotecas! As coisas estão corridas por aqui, então só agora consegui um tempinho para trazer novas soluções. Acompanhe na sequência do post!

Plataforma: URI (BEECROWD)

Problema: 3171

Enunciado: Mariazinha quer montar sua árvore de Natal com os cordões de led comprados no ano passado. O problema é que sua irmã caçula acabou cortando estes cordões em vários pedaços. 

Mariazinha quer saber se após unir estes pedaços (enumerados com uma etiqueta por ela de 1 até N) o cordão está totalmente unido ou não, pois se faltar unir algum dos segmentos, as luzes do cordão de led não irão funcionar.

Escreva um programa que, dada uma série de ligações entre segmentos de cordões de led, indique se o cordão estará Completo ou Incompleto.

Solução:

Este é um problema que se resolve com um algoritmo clássico de grafos conhecido como BFS (Breadth-First Search), ou busca em largura.

Código em C++:

Utilizei a estrutura vector para criar um vetor de vetores de inteiros, simulando uma matriz de adjacência. Usei vector porque em C++ é mais fácil e tudo já está pronto para uso em bits/stdc++.h.

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;

bool bfs(int inicio, int n) {
   vector<bool> visitado(adj.size(), false);
   vector<int> q;
   q.push_back(inicio);
   int resposta = 0;
   visitado[inicio] = true;
   int vis;
   while (!q.empty()) {
      vis = q[0];
      resposta++;
      q.erase(q.begin());
      for (int i = 0; i < adj[vis].size(); i++) {
         if (adj[vis][i] == 1 && (!visitado[i])) {
            q.push_back(i);
            visitado[i] = true;
	 }
      }
   }
   return resposta == n;
}

int main() {
   int n, l, x, y;
   cin >> n >> l;
   adj = vector<vector<int>>(n, vector<int>(n, 0));
   while (l--) {
      cin >> x >> y;
      int indiceX = x - 1;
      int indiceY = y - 1;
      adj[indiceX][indiceY] = 1;
      adj[indiceY][indiceX] = 1;
   }
   if (!bfs(0, n))
      cout << "IN";
   cout << "COMPLETO" << endl;
   return 0;
}

Código em C:

Aqui criei uma matriz global de adjacência apenas para facilitar a sua manipulação.

#include <stdio.h>
#include <string.h>

#define MAX_TAM 100

int adj[MAX_TAM][MAX_TAM];
int visitado[MAX_TAM];

int bfs(int inicio, int n) {
    for (int i = 0; i < n; i++) {
        visitado[i] = 0;
    }

    int fila[MAX_TAM];
    int primeiro = 0;
    int ultimo = 0;
    int resposta = 0;

    visitado[inicio] = 1;
    fila[ultimo++] = inicio;

    while (primeiro < ultimo) {
        int atual = fila[primeiro++];
        resposta++;

        for (int i = 0; i < n; i++) {
            if (adj[atual][i] == 1 && !visitado[i]) {
                fila[ultimo++] = i;
                visitado[i] = 1;
            }
        }
    }

    return resposta == n;

}

int main() {
    int n, l, x, y;
    scanf("%d %d", &n, &l);
    memset(adj, 0, n * sizeof(int));

    while (l--) {
        scanf("%d %d", &x, &y);
        int indiceX = x - 1;
        int indiceY = y - 1;
        adj[indiceX][indiceY] = 1;
        adj[indiceY][indiceX] = 1;
    }

    if (!bfs(0, n))
        printf("IN");

    printf("COMPLETO\n");

    return 0;
}

Espero que tenham gostado de mais esse post! O PIX para doações segue sendo a chave aleatória 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Ajude-nos para que as postagens sigam acontecendo!

URI (BEECROWD) - 3357 - Rico do Mate - Estruturas e Bibliotecas - C e C++

Mais uma solução nova! Agora é o exercício 3357 (Rico do Mate), da categoria estruturas e bibliotecas!

Plataforma: URI (BEECROWD)

Problema: 3357

Enunciado: A erva-mate (Ilex paraguariensis) é uma planta nativa da América do Sul que é utilizada para a preparação de uma das bebidas mais característica e apreciada em boa parte da região sul do Brasil, o chimarrão. Normalmente consumido de forma compartilhada, os participantes formam uma roda e vão passando a cuia de mão-em-mão: após ingerir o chá de seu interior, um participante da roda de mate enche a cuia e passa para o próximo.

Por sua forte presença cultural, existem diversas crenças e lendas associadas à roda de mate, uma delas diz respeito à cuia que leva a última água da garrafa térmica. Segundo a crença, a pessoa mateadora que recebe esta última cuia vai ficar rica, talvez seja uma consolação, pois essa mateadora normalmente recebe menos chá.

Sabendo desta crença, uma mateadora ávida em programação decidiu fazer um programa para ajudar a descobrir quem será a rica do mate e o quanto de chimarrão ela vai tomar. Para tanto, ela leva em consideração o volume L de água da térmica, a quantidade Q de água que cabe em uma cuia e as pessoas que formam a roda.

Solução:

Aí vai!

Código em C++:

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

    int n;

    double l, q;

    cin >> n >> l >> q;

    string nomes[n];

    for (int i = 0; i < n; i++)

     cin >> nomes[i];

    int x = (int) (l / q);

    int r = x % n;

    double qtd = l - (x * q);

    if (qtd == 0.0) {

     qtd += q;

     r = (x - 1) % n;

    }

    cout << fixed <<  setprecision(1) << nomes[r] << " " << qtd << endl;

    return 0;

}

Código em C:

#include <stdio.h>

int main() {

    int n;

    double l, q;

    scanf("%d %lf %lf", &n, &l, &q);

    char nomes[n][13];

    for (int i = 0; i < n; i++)

        scanf("%s ", nomes[i]);

    int x = (int) (l / q);

    int r = x % n;

    double qtd = l - (x * q);

    if (qtd == 0.0) {

     qtd += q;

     r = (x - 1) % n;

    }

    printf("%s %.1lf\n", nomes[r], qtd);

    return 0;

}

URI (BEECROWD) - 1162 - Organizador de Vagões - Estruturas e Bibliotecas - C e C++

Opa! Tudo numa boa? Resolvendo agora aqui um exercício da categoria "Estruturas e Bibliotecas". Esses exercícios são um pouco mais complicados, mas deu pra resolver de boa. A solução foi baseada na implementação do Merge Sort, aí fluiu! Quem mais conseguiu resolver? Alguém fez diferente?

Antes de resolver qualquer algoritmo do URI (BEECROWD agora), recomendamos seguir os seguintes passos:

1. Ler todo enunciado do problema.
2. Ler os tópicos do fórum em caso de dúvidas
3. Preparar arquivos de entrada para teste, considerando as entradas de exemplo do URI, do udebug e outros valores limite;
4. Preparar o ambiente de desenvolvimento e utilizar os mesmos parâmetros dos compiladores do URI
5. Preparar um código-fonte padrão, já contendo a chamada às bibliotecas padrão, pré-processadores, retorno de função e um comando de escrita com "\n", pois no URI a grande maioria dos problemas exige a quebra de linha final.

Plataforma: URI (BEECROWD)

Problema: 1162

Enunciado:

Na estação de trem você ainda pode encontrar o último dos “organizadores de vagões”. Um Organizador de vagões um empregado cujo trabalho é apenas reordenar os vagões do trem, trocando-os de posição. Uma vez que os vagões são organizados em uma ordem considerada ótima, o condutor pode desconectar cada vagão e colocá-los na estação.

O título “organizador de vagões” é dado à pessoa que realiza esta tarefa, cuja estação fica perto de uma ponte. Ao invés da ponte poder subir ou descer, ela roda sobre um pilar que fica no centro do rio. Após rodar 90 graus, os barcos podem passar na esquerda ou direita dela. O Primeiro organizador de vagões descobriu que girando a ponte 180 graus com dois vagões em cima dela, é possível a troca de lugar entre os dois vagões. Obviamente a ponte pode operar no máximo com dois vagões sobre ela.

Agora que quase todos os organizadores de vagões já faleceram, a estação gostaria de automatizar esta operação. Parte do programa a ser desenvolvido é uma rotina que decide para um dado trem com um determinado número de vagões, o número de trocas entre trens adjacentes que são necessárias para que o  trem fique ordenado. Sua tarefa é criar tal rotina.

Linguagens: C e C++

Solução em C:

Para a ordenação dos vagões, nesta solução implementou-se o algoritmo merge sort.

Outro ponto importante é nunca esquecer da quebra de linha no fim do comando de escrita, o popular "\n".

#include <stdio.h>
int aux[50];
 
int merge(int v[], int left, int mid, int right) {
    int swaps = 0, i = left, j = mid, k = left;
    
    for (; i < mid && j <= right; k++) {
        if (v[i] > v[j]) {
            aux[k] = v[j++];
            swaps += mid - i;
        }
        else
            aux[k] = v[i++];
    }
    
    for (; i < mid; k++, i++)
        aux[k] = v[i];
    for (; j <= right; k++, j++)
        aux[k] = v[j];
    for (; left <= right; left++)
        v[left] = aux[left];
        
    return swaps;
}
 
int mergeInsertionSwap(int v[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2 + 1;
        return mergeInsertionSwap(v, left, mid - 1) + mergeInsertionSwap(v, mid, right) + merge(v, left, mid, right);
    }
    return 0;
}
 
int main() {
    int n, l, i;
    scanf("%d", &n);
    
    while (n--) {
        scanf("%d", &l);
        int vagoes[l];

        for (i = 0; i < l; i++)
            scanf("%d", &vagoes[i]);

        printf("Optimal train swapping takes %d swaps.\n", mergeInsertionSwap(vagoes, 0, l - 1));
    }
    
    return 0;
}

Solução em C++:

Para a ordenação dos vagões em C++ utilizou-se também o merge sort. A solução ficou muito parecida com a de C, mas utilizando comandos de entrada e saída da biblioteca iostream. Outro ponto de diferença é declarar variáveis locais no escopo de estrutura de seleção, o que compiladores C não costumam aceitar. Tirando isso é basicamente a mesma solução.

#include <iostream>
using namespace std;

int aux[50];
 
int merge(int v[], int left, int mid, int right) {
    int swaps = 0, i = left, j = mid, k = left;
    
    for (; i < mid && j <= right; k++) {
        if (v[i] > v[j]) {
            aux[k] = v[j++];
            swaps += mid - i;
        }
        else
            aux[k] = v[i++];
    }
    
    for (; i < mid; k++, i++)
        aux[k] = v[i];
    for (; j <= right; k++, j++)
        aux[k] = v[j];
    for (; left <= right; left++)
        v[left] = aux[left];
        
    return swaps;
}
 
int mergeInsertionSwap(int v[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2 + 1;
        return mergeInsertionSwap(v, left, mid - 1) + mergeInsertionSwap(v, mid, right) + merge(v, left, mid, right);
    }
    return 0;
}
 
int main() {
    int n, l;
    cin >> n;
    
    while (n--) {
        cin >> l;
        int vagoes[l];

        for (int i = 0; i < l; i++)
            cin >> vagoes[i];

        cout << "Optimal train swapping takes " << mergeInsertionSwap(vagoes, 0, l - 1) << " swaps." << endl;
    }
    
    return 0;
}

URI (BEECROWD) - 3176 - Time de Duendes - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 3176

Linguagens: C e C++

Enunciado:

No ano de 2020 o Papai Noel não poderá sair de casa para entregar presentes por conta da pandemia do Coronavirus. Então ele ordenou que seus duendes fossem entregar no lugar dele no dia do natal. Como eles são bastante inexperientes, irão se dividir em vários times compostos de três membros: Um líder, um entregador e um piloto de trenó. O plano do Papai Noel é que os líderes das equipes seja sempre os duendes mais velhos, por esse motivo ele pediu para todos escreverem seus nomes e idades em uma lista. Como você é um duende programador, resolveu ajudar o Papai Noel a organizar a lista e montar os times a partir dela.

Segue abaixo algumas regras e fatos:

- A lista deve ser organizada em ordem descendente de idade;

- Caso dois duendes possuírem a mesma idade, deve se organizar por ordem ascendente de nome;

- Não existe dois duendes de mesmo nome;

- Nenhum duende tem mais de 20 caracteres em seu nome;

- Os duendes da lista tem idade entre 10 e 100 anos;

- Os primeiros 1/3 dos duendes (os mais velhos), serão os líderes dos times;

- A ordem dos duendes entregadores e pilotos seguem a mesma lógica dos líderes. Ex) Se há 6 duendes na lista, haverá dois times, onde o duende mais velho é líder do time 1, e o segundo mais velho é líder do time 2. O terceiro mais velho é entregador do time 1 e o quarto mais velho é entregador do time 2. O quinto é piloto de trenó do time 1 e o último é piloto do time 2;

Solução:

Neste exercício, na solução em C, criei uma estrutura (struct) para os dados dos duendes, que são idade e nome. A ordenação foi feita com o qsort (Quick Sort), disponível na biblioteca stdlib. A comparação entre os doentes (função compara) foi feita pela idade primeiramente, e o desempate pelo nome, em ordem alfabética. A comparação entre idades é feita diretamente acessando a variável age de cada ponteiro comparado (a e b). A comparação entre os nomes foi feita com a função strcmp, disponível na biblioteca string. Acredito que essa era a parte mais difícil da solução. Outro ponto que merece destaque é que a leitura do nome do duende foi feito para o array de char "nome". Este valor foi copiado para a estrutura Duende criada (hue[indice].name) através da função strcpy, também disponível na biblioteca string.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    int age;
    char name[22];
} Duende;

int compara(const void *a, const void *b) {
    Duende *a2 = (Duende *)a;
    Duende *b2 = (Duende *)b;    
    if (a2->age == b2-> age)
        return strcmp(a2->name, b2->name);
    return a2->age < b2->age;
}

int main() {
    int n, i, idade, times, k;
    char nome[22];
    Duende hue[30];
    scanf("%d ", &n);
    times = n/3;
    for (i = 0; i < n; i++) {
        scanf("%s %d", nome, &idade);
        strcpy(hue[i].name, nome);
        hue[i].age = idade;
    }
    qsort ((void *)&hue, n, sizeof(Duende), compara);
    for (i = 0; i < times; i++) {
        printf("Time %d\n", i + 1);
        for (k = i; k < n; k += times)
            printf("%s %d\n", hue[k].name, hue[k].age);
        printf("\n");
    }
    return 0;
}

A solução em C++ usa lógica semelhante, mas aqui não usei qsort, e sim sort, disponível na biblioteca algorithm. Também não foi necessário utilizar strcpy e strcmp, sendo possível fazer atribuição diretamente com o sinal de = e comparação diretamente com <=, o que facilita um pouco, pelo menos na minha opinião.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Duende {
    int age;
    string name;
};
bool compara(Duende a, Duende b) {
    if (a.age == b.age)
        return a.name <= b.name;
    return a.age > b.age;
}
int main() {
    int n, i, idade, times, k;
    string nome;
    Duende hue[30];
    cin >> n;
    times = n/3;
    cin.ignore();
    for (i = 0; i < n; i++) {
        cin >> nome >> idade;
        hue[i].name = nome;
        hue[i].age = idade;
    }
    sort(hue, hue + n, compara);
    for (i = 0; i < times; i++) {
        cout << "Time " << i + 1 << endl;
        for (k = i; k < n; k+=times) {
            cout << hue[k].name << " " << hue[k].age << endl;
        }
        cout << endl;
    }
    return 0;
}

URI (BEECROWD) - 2633 - Churras no Yuri - Estruturas e Bibliotecas - C e C++

Essas são as soluções em C e C++ para o exercício Churras no Yuri, do URI/BEECROWD! Espero que curtam!

Plataforma: URI (BEECROWD)

Problema: 2633

Enunciado:

Yuri é um bom companheiro. Sempre fazemos o churras dos “manos ;)” na casa dele! Desta vez, o motivo do churrasco é que os manos estão finalmente começando a passar em bons concursos! Então, hoje teremos aquela edição especial do churras, with alcohol and futebol de sabão!

A empresa do futebol de sabão está demorando para encher o campo e Yuri, já entendiado, começou a viajar na seguinte pergunta: se assássemos as carnes por ordem da data de validade, qual seria a sequência de peças de carne resultante? Como o MacBook de Yuri está muito longe (e a preguiça está muito perto), ele pediu a sua ajuda para responder esta pergunta.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct par {
    char s[22];
    int d;
};
int compara(const void *a, const void *b) {
    struct par *aa = (struct par *)a;
    struct par *bb = (struct par *)b;
    return aa->d - bb->d;
}
int main() { 
    int n, data, i;
    struct par p[10];
    char rango[22];
    while (scanf("%i ", &n) != EOF) { 
        for (i = 0; i < n; i++) {
            scanf("%s %i ", rango, &data);
            strcpy(p[i].s, rango);
            p[i].d = data;
        }
        qsort(p, n, sizeof(struct par), compara);
        for (i = 0; i < n; i++) {
            if (i)
                printf(" ");
            printf("%s", p[i].s);
        }
        
        printf("\n");
        memset(p, 0, n*sizeof(p[0]));
    }
    return 0; 
}

Código em C++:

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std; 

bool compara(pair<string, int>& a, pair<string, int>& b) {
    return a.second < b.second;
}
 
int main() { 
    
    int n;
    
    while (cin >> n) {
        
        map<string, int> linhas;
        vector<pair<string, int> > vet; 
        string rango;
        int data;
        
        while (n--) {
            cin >> rango >> data;
            linhas.insert({rango, data});
        }

        for (auto& it : linhas)
            vet.push_back(it); 
      
        sort(vet.begin(), vet.end(), compara); 
        
        for (auto& it : vet) {
            if (&it == &vet.front())
                cout << it.first;
            else
                cout << ' ' << it.first; 
        }
        
        cout << endl;
    }
    
    return 0; 
}

URI (BEECROWD) - 2482 - Etiquetas de Noel - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 2482

Enunciado:

Como de costume, neste ano Noel recebeu muitos pedidos de presentes. Só que em função de alguns imprevistos, não terá como entregar todos os presentes pessoalmente neste ano. Daí então decidiu utilizar o velho e bom correio tradicional, para alguns pedidos que podem ser entregues por carta.

Para esta tarefa, pediu ajuda ao elfo Evergreen Xadada, para que ele imprimisse etiquetas a todos os envelopes que serão destinados a algumas destas crianças, cujo pedido pode ser entregue por carta. Cada uma destas etiquetas deverá conter apenas o nome da criança e a saudação "Feliz Natal" no respectivo idioma desta criança. Para auxiliar nesta tarefa, Noel disponibilizou uma tabela com vários idiomas e o nome e o país de cada uma das crianças selecionadas, de acordo com o exemplo abaixo. Você deve ajudar Evergreen fazendo um programa que imprima estas etiquetas.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>
#include <string.h>
int main() {
    int n, m, i, pos;
    char a[200];
    char b[200];
    char felizNatal[200][200];
    char linguagem[200][200];
    scanf("%d ", &n);
    for (i = 0; i < n; i++) {
        scanf ("%[^\n]%*c", linguagem[i]);
        scanf ("%[^\n]%*c", felizNatal[i]);
    }
    scanf("%d ", &m);
    while (m--) {
        scanf ("%[^\n]%*c", a);
        scanf ("%[^\n]%*c", b);
        printf("%s\n", a);
        for (i = 0; i < n; i++) {
            if (!strcmp(b, linguagem[i])) {
                pos = i;
                break;
            }
        }
        printf("%s\n\n", felizNatal[pos]);
    }
    memset(felizNatal, 0, sizeof(felizNatal));
    memset(linguagem, 0, sizeof(linguagem));
    return 0;
}

Código em C++:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, i, pos;
    string a, b;
    vector<string> felizNatal, linguagem;
    cin >> n;
    cin.ignore();
    for (i = 0; i < n; i++) {
        getline(cin, a);
        linguagem.push_back(a);
        getline(cin, b);
        felizNatal.push_back(b);
    }
    cin >> m;
    cin.ignore();
    while (m--) {
        getline(cin, a);
        getline(cin, b);
        cout << a << endl;
        for (i = 0; i < n; i++) {
            if (!b.compare(linguagem.at(i))) {
                pos = i;
                break;
            }
        }
        cout << felizNatal.at(pos) << endl << endl;
    }
    felizNatal.clear();
    linguagem.clear();
    return 0;
}

URI (BEECROWD) - 2290 - Números Apaixornados - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 2290

Enunciado:

Será dado a você um vetor com N números, onde todos estarão em pares. Porém somente dois desses números acabaram ficando sem par, esses números são ditos números apaixornados, você consegue identificar quais são esses números?

Por exemplo, A = {1, 1, 3, 3, 5, 5, 5, 7}, os números apaixornados são 5 e 7.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>

void merge(long long int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    long long int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(long long int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
int main() {
    long long int resposta[2], numeros[100001], atual, proximo;
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        mergeSort(numeros, 0, n-1);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2; indice++) {
		    
		    atual = numeros[indice];
		    proximo = numeros[indice + 1];

			if (atual == proximo && indice < n - 1)
				indice++;
			else if (contador++ == 1)
			    printf("%lld\n", atual);
			else
			    printf("%lld ", atual);
		}
    }
    return 0;
}

Código em C++:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int compara (const void *a, const void *b) {
    
    long long int *a2 = (long long *)a;
    long long int *b2 = (long long *)b;

	if (*a2 == *b2)
		return 0;
	else if (*a2 > *b2)
		return 1;
	else
		return -1;

}

int main() {
    long long int resposta[2], numeros[100001];
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        qsort(numeros, n, sizeof(long long int), compara);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2;) {

			if (numeros[indice] == numeros[indice + 1] && indice < n - 1)
				indice += 2;
				
			else {
				cout << numeros[indice++];
				
				if (contador++ == 1)
					cout << endl;
					
				else
					cout << " ";
			}
		}
    }
    return 0;
}