Soluções Doces do Dias das Bruxas

Solução por Lucca Siaudzionis

Primeiramente, vamos definir:

$s_1$ = $a_1$
$s_2$ = $a_1 + a_2$
$s_3$ = $a_1 + a_2 + a_3$
$...$
$s_k$ = $a_1 + a_2 + ... + a_k$

Se, para algum $i$ , $s_i \equiv 0 \ (mod \ c)$ , já achamos nosso subconjunto e o problema acabou! Vamos então supor que não exista nenhum $i$ que satisfaça tal propriedade.

Logo, temos $(c-1)$ possíveis valores para os restos que os $s_i$ 's podem deixar na divisão por $c$ (os números de $1$ a $c-1$ ) e temos $n$ valores para $s_i$ , com $n > c-1$ . Desta forma, pelo princípio das casas de pombo, existem dois números distintos $i$ e $j$ tal que $s_i \equiv s_j \ (mod \ c)$ , desta maneira, temos (supondo $i < j$ ):

$s_j \equiv s_i \ (mod \ c) \Rightarrow s_j - s_i \equiv 0 \ (mod \ c) \Rightarrow a_{i+1} + a_{i+2} + ... + a_j \equiv 0 \ (mod \ c)$

Desta forma, achamos nosso subconjunto!

Vamos então ao código:

	//
	// halloween.cpp
	//
	// Created by Lucca Siaudzionis on 03/03/15.
	//
	// URI 1656 - Doces do Dia das Bruxas

	#include <cstdio>

	//------------------
	#define MAXN 100100

	int c, n;
	int resto[MAXN];
	int candy[MAXN];
	//------------------

	int main(){

	while(scanf("%d %d", &c, &n) && n){

	for(int i = 1;i <= n;i++){
	scanf("%d", &candy[i]);
	candy[i] %= c;
	}

	for(int i = 1;i <= c;i++) resto[i] = -1;

	int sum = 0;
	resto[0] = 0;
	for(int i = 1;i <= c;i++){

	sum += candy[i];
	sum %= c;

	if(resto[sum] != -1){
	printf("%d", resto[sum]+1);
	for(int j = resto[sum]+2;j <= i;j++) printf(" %d", j);
	printf("\n");
	break;
	}

	resto[sum] = i;
	}

	}

	return 0;
	}

view raw

doce_do_dias_das_bruxas.cpp

hosted with ❤ by GitHub