Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2420
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2420
Guerra por Território
Por OBI - Olimpíada Brasileira de Informática 2012 
Brazil
Timelimit: 1
Tombólia do Oeste e Tombólia do Leste travaram uma guerra durante 50 anos. O motivo da guerra era o tamanho do território de cada país. Pelo bem da população dos dois países, os governos resolveram fazer um tratado para finalizar a guerra. O tratado consiste em fazer um divisão justa, e certamente contínua, do território. Eles resolveram pedir sua ajuda para calcular o ponto de divisão do território. Depois de tantos anos de guerra, os países não podem lhe pagar uma viagem para ver previamente o território que será dividido. Ao invés disso, eles prepararam uma lista a1,a2,…,aN de inteiros que indicam o tamanho de cada seção do território. A seção a1 é vizinha da seção a2 que por sua vez é vizinha da seção a3; e assim por diante. Os governos querem uma divisão em uma seção k de tal forma que a1 + a2 + … + ak = ak+1 + ak+2 + … + aN.
Sua tarefa é dada uma lista de inteiros positivos a1, a2,..., aN , determinar a seção k tal que soma dos comprimentos das seções a1 até ak é igual a soma dos comprimentos das seções ak+1 até aN.
Entrada
A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 105) indicando o número de seções do território. A segunda linha da entrada contém N inteiros a1, a2,..., aN (1 ≤ ai ≤ 100, para i = 1, 2, . . . , N.)separados por um único espaço que indicam os comprimentos das seções.
Saída
Seu programa deve imprimir uma única linha contendo um inteiro que indica a seção do território onde acontecerá a divisão.(É garantido que sempre existe uma divisão que satisfaz as condições dos países).
| Exemplos de Entrada | Exemplos de Saída |
|
4 5 3 2 10 |
3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define false 0
#define MAXSIZE 100100
unsigned vet[MAXSIZE];
int bb(int, int);
int main (void)
{
unsigned n, i, tmp, somatotal;
scanf("%u", &n);
int soma;
soma = somatotal = 0;
scanf("%u", &vet[0]);
somatotal += vet[0];
for (i = 1; i < n; ++i)
{
scanf("%u", &tmp);
vet[i] += vet[i - 1] + tmp;
somatotal += tmp;
}
printf("%u\n", bb(somatotal / 2, n) + 1);
}
int bb(int key, int tam)
{
int hi, low, mid;
low = 0;
hi = tam - 1;
while (hi > low)
{
mid = low + ((hi - low) / 2);
if (vet[mid] < key)
low = mid + 1;
else
hi = mid;
}
return low;
}
Input
5 3 2 10
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
int main() {
int i, a, resp = 0;
scanf("%d", &a);
int vetor[a];
for (i = 0; i < a; i++) {
int davez;
scanf("%d", &davez);
resp += davez;
vetor[i] = resp;
}
for (i = 0; i < a; i++) {
if (2 * vetor[i] == resp) {
printf("%d\n", i + 1);
return 0;
}
}
}
Input
5 3 2 10
Output