Solução por Anita Ramos
Este problema é muito interessante, pois na sua resolução utilizamos o que chamamos de $$PA$$ (Progressão Aritmética) para definir até quando um loop “indeterminado” irá durar e por ser necessário determinar e armazenar novos valores a partir de valores já pré-estabelecidos, mas que variam de acordo com a entrada.
Iniciando a programação então, após adicionar a biblioteca e declarar as variáveis, o programa lê o primeiro valor de entrada $$N$$ e estabelece um loop com o comando $$for()$$ para ler todos os $$N$$’s seguintes valores da segunda linha de entrada. Depois, como o valor de $$N$$ será usado para estabelecer até quando um loop será válido e por isso não pode ser alterado, as variáveis $$lasti$$ e $$j$$ assumirão o seu valor.
Na parte da lógica do programa, utilizamos um loop com o comando $$for()$$ para determinar a cor de cada bola depois das $$N$$’s primeiras bolas utilizando uma $$PA$$ (para determinar quantas bolas serão até a última), que começa com $$i = 2$$ para não analisar a primeira bola do segundo andar de um caso de teste, pois pela ideia utilizada, o par dela seria a última boa do primeiro andar e isso não se encaixa com o que dito no enunciado, já que nenhuma bola é formada por um caso desses. Em seguida, a variável $$cont$$ assume o valor da posição anterior à da bola sendo observada, ou seja, $$i – 1$$, que será o “vizinho” ou o “par” dessa bola e a variável $$soma$$ recebe o valor da soma de duas bolas vizinhas. Se essa soma for igual a 0, ou seja, se as bolas forem de cores diferentes, $$k$$, que representa a posição da bola formada por esse par de bolas analisados, assume o valor de $$i + j – 1$$ (que é exatamente a k-ésima bola de uma sequência) e o vetor $$v$$ de posição $$k$$ recebe -1 como seu valor, ou seja, a bola é branca. Se essa soma for igual a 2 ou a -2, ou seja, se as bolas forem da mesma cor, $$k$$, que representa a posição da bola formada por esse par de bolas analisados, assume o valor de $$i + j – 1$$ (que é exatamente a k-ésima bola de uma sequência) e o vetor $$v$$ de posição $$k$$ recebe 1 como seu valor, ou seja, a bola é preta. Por último, se a bola analisada for a última de um andar, ou seja, se $$i = lasti$$, soma-se 1 à variável $$i$$ para “pular” a primeira bola do próximo andar (já que pela ideia ela não tem um vizinho considerável), soma-se à $$lasti$$ o valor de $$j-1$$ (que será a posição da última bola do próximo andar) e subtrai-se 1 da variável $$j$$, porque no próximo andar teremos uma bola a menos.
No final, imprimimos “preta” se o valor do vetor $$v$$ da posição da última bola da sequência for 1 ou “branca” se o valor do vetor $$v$$ da posição da última bola da sequência for -1 e o programa retorna a 0.
Segue o código comentado para melhor compreensão da solução:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> //biblioteca utilizada | |
| const int MAXN=2100; //define o tamanho de MAXN que determinará o tamanho de um vetor | |
| int main() | |
| { | |
| int N,i,v[MAXN],cont=1,lasti,k,j,soma; //declaração das variáveis | |
| scanf("%d", &N); //lê 'N' na primeira linha de entrada | |
| for(i=1; i<=N; i++) //loop para ler todos os valores da segunda linha de entrada de acordo com o 'N' | |
| { | |
| scanf("%d", &v[i]); //lê o valor de entrada 1 ou -1 | |
| } | |
| lasti=N; //'lasti' assume o valor de 'N' | |
| j=N; //'j' assume o valor de 'N' | |
| for(i=2; i<=N*(N+1)/2; i++) //loop para determinar a cor de cada bolinha depois das 'N's bolinhas de entrada por PA | |
| { | |
| cont=i-1; //'cont' assume o valor de 'i'-1 | |
| soma=v[cont]+v[i]; //'soma' recebe o valor da soma de duas bolinhas vizinhas que compõe uma nova bolinha no próximo andar | |
| if(soma==0) //se 'soma' for 0, ou seja, se as bolinhas vizinhas são de cores diferentes | |
| { | |
| k=i+j-1; //'k' assume o valor de 'i'+'j' | |
| v[k]=-1; //o valor do vetor da bolinha é -1, ou seja, ela é branca | |
| } | |
| if(soma==2 || soma==-2) //se 'soma' for 2 ou -2, ou seja, se as bolinhas vizinhas são da mesma cor | |
| { | |
| k=i+j-1; //'k' assume o valor de 'i'+'j' | |
| v[k]=1; //o valor do vetor da bolinha é 1, ou seja, ela é preta | |
| } | |
| if(i==lasti) //se 'i' for igual a 'lasti' | |
| { | |
| i++; //soma-se 1 à variável 'i' | |
| lasti=lasti+j-1; //'lasti' é igual a 'lasti' + 'j' – 1 | |
| j–; //subtrai-se 1 da variável 'j' | |
| } | |
| } | |
| if(v[k]==1)printf("preta"); //imprimi 'preta' se o valor do vetor da última bola for 1 | |
| else printf("branca"); //imprimi 'branca' se o valor do vetor da última bola não for 1, nesse caso, se ele for -1 | |
| return 0; //retorna a 0 | |
| } |