Solução Guerra por Território - Semana 1

Solução por Rogério Júnior

Checar qual seção que divide igualmente o território de valor $A$ equivale a checar qual delas é tal que, somando-a a a todos os territórios anteriores a ela, obtemos exatamente $\frac{A}{2}$ . Assim, vamos salvar o valores da entrada em um vetor $secao$ e a soma deles em uma variável $A$ . Depois, declaramos uma variável $soma$ , que será inicializada com o valor $0$ , e adicionaremos a ela, um a um, o valor de cada um dos territórios armazenados em $secao$ . Quando o valor de $soma$ for exatamente $\frac{A}{2}$ , então imprimiremos na tela o índice que correspondente àquela seção. É importante lembrar, porém, que para checar essa igualdade, devemos fazer $2*soma==A$ , pois, em C++, como $A$ e $2$ são inteiros, $\frac{A}{2}$ retorna $\lfloor\frac{A}{2}\rfloor$ . Vamos ao código:

	#include <cstdio> // printf, scanf

	int secao[100100], A, soma, n; // declare o vetor secao e as variáveis A, soma e n

	int main(){

	scanf("%d", &n);

	for(int i=1; i<=n; i++){ // leia a entrada

	scanf("%d", &secao[i]); // salve o valor de cada seção no vetor
	A+=secao[i]; // some o valor da seção atual a A para que, ao final da leitura da entrada, ela tenha o valor da soma de todos os territórios
	}

	for(int i=1; i<=n; i++){ // para cada índice do vetor

	soma+=secao[i]; // adicione seu valor a soma
	if(2*soma==A){ // cheque se a soma está valendo metade do território total

	printf("%d\n", i); // se sim, imprima o valor do índice em que isso ocorreu
	break; // e pare o loop
	}
	}

	return 0;
	}

view raw

guerra_por_territorio.cpp

hosted with ❤ by GitHub

Abaixo, a solução, em Java, do leitor Roger Benet:

	import java.io.*;
	public class solucao{
	public static void main(String[] args)throws IOException{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	int[] vet = new int[110000];
	int i,n,sm1,sm2;
	String[] aux;
	n = Integer.parseInt(in.readLine());
	aux = in.readLine().split(" ");
	sm1 = 0;
	sm2 = 0;
	for(i = 0; i < n; i++){
	vet[i] = Integer.parseInt(aux[i]);
	sm1 += vet[i];
	}
	sm1 -= vet[i-1];
	sm2 += vet[i-1];
	for(i = n - 2; i > -1; i--){
	if(sm1 == sm2){
	out.write((i+1)+"\n");
	break;
	}
	else {
	sm1 -= vet[i];
	sm2 += vet[i];
	}
	}
	out.flush();
	}
	}

view raw

guerra_por_territorio_roger_benet.java

hosted with ❤ by GitHub