SoloCodigo

Asuntos Oficiales => Retos => Mensaje iniciado por: Binary en Lunes 16 de Agosto de 2004, 14:38

Título: Ultimo
Publicado por: Binary en Lunes 16 de Agosto de 2004, 14:38

Bueno, ya que ninguno de los anteriores fue resuelto... demosle la bienvenida al ultimo que posteo, por lo menos sera facil:

Descripcion:
Encontrar una subsequencia de numeros de largo N (2 <= N <= 100 000 000) de la sequencia dada, de modo que la suma de todos los numeros de la subsequencia sea divisible por K (2 <= K <= 10 000 000).

Entrada:
En la primera linea: dos enteros: N y K
En la segunda: N enteros

Salida:
En la primera linea, 2 enteros: i, j (denotando que la sequencia encerrada entre Si... Sj, es la secuencia deseada).... para un i <= j.

Ejemplo:

Entrada:
7 10
2 4 3 5 2 7 2

Salida:
3 5

Explicacion:
S(3) --> 3
S(4) --> 5
S(5) --> 2
3 + 5 + 2 = 10
10 % 10 = 0.

Saludos....
P.D. Por favor, nada de N^2 o N^3 porque N es bastante grande.

Título: Re: Ultimo
Publicado por: JuanK en Lunes 16 de Agosto de 2004, 16:27

si ninguno de los ancerrar el post publicando tu solucion, tal como esta en los demas retos, por ejemplo del del protocolo hdlc, una evz hecho eso yo mismo cerrare el post.

Título: Re: Ultimo
Publicado por: Binary en Lunes 16 de Agosto de 2004, 18:20

se supone que hay una o mas personas tratando de solucionar los anteriores.... espero que lo hagan... en una semana posteo soluciones...

Título: Re: Ultimo
Publicado por: Binary en Martes 24 de Agosto de 2004, 00:59

Código: Text

1.  
2. // Divisibility
3. #include &#60;stdio.h&#62;
4. #define MAXR 10000001
5.  
6. int r[MAXR];
7.  
8. int main()
9. {
10.   int n, k, i, num, mod, found;
11.   __int64 sum = 0;
12.   FILE *fin, *fout;
13.  
14.   fin = fopen(&#34;div.in&#34;, &#34;r&#34;);
15.   fout = fopen(&#34;div.out&#34;, &#34;w&#34;);
16.  
17.   found = 0;
18.   fscanf(fin, &#34;%d %d&#34;, &n, &k);
19.   for(i = 0; i &#60; n; i++) {
20.     fscanf(fin, &#34;%d&#34;, &num);
21.     sum += num;
22.     mod = (int)(sum % k);
23.     if(r[mod] != 0) {
24.       fprintf(fout, &#34;%d %d&#092;n&#34;, r[mod]+2, i+1);
25.       found = 1;
26.       break;
27.     }
28.     r[mod] = i;
29.   }
30.  
31.   if(!found)
32.     fprintf(fout, &#34;NO SOLUTION&#092;n&#34;);
33.  
34.   fclose(fin);
35.   fclose(fout);
36.   return 0;
37. }
38.  
39.