CCM0128 - Computação II (2025i)

Considere o seguinte problema:

Problema K-Sum
- Instância: um inteiro \(k\geq1\) e uma sequência $a_0,\dots,a_{N-1}$ de $N$ inteiros
- Pergunta: qual é o número de $k$-uplas $(i_0,\dots,i_{k-1})$ tais que $0\leq i_0<\dots<i_{k-1}<N$ e $a[i_0]+\dots+a[i_{k-1}]=0$?

Neste exercício, você deve escrever um programa que resolve o Problema K-Sum. Seu programa deve chamar-se KSum.java. Seu programa deve receber $k$ na linha de comando e deve receber os $N$ inteiros $a_0,a_1,\dots$ na entrada padrão. Seu programa deve enviar a resposta para a saída padrão. Seu programa deve também enviar para a saída padrão o tempo gasto por ele para determinar a resposta. Para medir esse tempo, use o mesmo esquema usado em ThreeSum.java. Por simplicidade, você pode supor que $1\leq k\leq N/2$ (o caso $k>N/2$ pode ser reduzido a uma variante do Problema K-Sum com $k\leq N/2$).

Observação. Note que KSum.java generaliza ThreeSum.java, no sentido que a execução de KSum.lava com $k=3$ equivale à execução de ThreeSum.java.

Exemplos de execução.  Alguns exemplos de execução seguem abaixo. O programa Generator.java usado nestes exemplos gera sequências aleatórias de inteiros, como visto em sala.

$ java-introcs Generator 3 6 314314
-2
-1
1
1
-3
-2
$ java-introcs Generator 3 6 314314 | java-introcs ThreeSum
elapsed time = 0.0
2
$ java-introcs Generator 3 6 314314 | java-introcs KSum 3
elapsed time = 0.0
2
$ java-introcs Generator 100000 1000 314314 | java-introcs ThreeSum
elapsed time = 0.188
614
$ java-introcs Generator 100000 1000 314314 | java-introcs KSum 3
elapsed time = 1.349
614
$ java-introcs Generator 50 50 314314 | java-introcs ThreeSum
elapsed time = 0.0
146
$ java-introcs Generator 50 50 314314 | java-introcs KSum 3
elapsed time = 0.001
146
$ java-introcs Generator 50 50 314314 | java-introcs KSum 4
elapsed time = 0.004
1577
$ java-introcs Generator 50 50 314314 | java-introcs KSum 5
elapsed time = 0.02
12481
$ java-introcs Generator 50 50 314314 | java-introcs KSum 9
elapsed time = 18.802
11480449
$ java-introcs Generator 50 50 314314 | java-introcs KSum 10
elapsed time = 79.682
44929374
$ java-introcs Generator 50 34 314314 | java-introcs KSum 17
elapsed time = 27.051
8736749
$ java-introcs Generator 50 36 314314 | java-introcs KSum 18
elapsed time = 107.782
32540221
$

Siga os exemplos acima para formatar a saída de seu programa.

Desempenho.  Seu programa KSum.java pode ter tempo de execução proporcional a $k{N\choose k}$, mas não pior. Note que para valores um pouco maiores de $k$, é natural que não seja possível tratar entradas com $N$ grande.

Observação.  Um exercício teórico interessante é provar que de fato seu programa tem tempo de execução como exigido. Neste exercício, você não precisa entregar tal demonstração, mas é um exercício recomendado.

Entrega.  Entregue apenas seu programa KSum.java.