Interval cíclic P72067


Statement
 

pdf   zip

thehtml

Teniu n nombres enters a1, …, an. Els col·loqueu mantenint l’ordre en sentit horari en una circumferència, de manera que a la dreta de cada ak està ak+1, excepte per a an, que a la dreta té a1.

Donada una s, és possible trobar un interval de nombres consecutius que sumi s?

Entrada

L’entrada conté diversos casos, cadascun amb s, n i els n nombres a1, …, an. Podeu suposar −1014s ≤ 1014, 1 ≤ n ≤ 105, i −109ak ≤ 109.

Sortida

Escriviu una línia per a cada cas. Si no hi ha cap interval que sumi s, escriviu “NO”. Altrament, escriviu "SI", seguit de l’inici i del final de l’interval, que ha de tenir entre 1 i n elements. Si hi ha més d’una solució, trieu la que vulgueu, però seguiu estrictament el format dels exemples.

Puntuació

  • Cas A:  ‍30% Punts ‍

    Casos on 0 ≤ s ≤ 1014 i 0 ≤ ak ≤ 109, com l’exemple d’entrada 1.

  • Cas B:  ‍70% Punts ‍

    Resta de casos.

Public test cases
  • Input

    7  4  1 2 3 4
    7  4  1 2 3 4
    23  1  23
    0  3  42 42 42
    168  3  42 42 42
    3000000000  3  1000000000 1000000000 1000000000
    

    Output

    SI 4 2
    SI 3 4
    SI 1 1
    NO
    NO
    SI 2 1
    
  • Input

    -3  4  -1 8 9 -2
    2  5  1 -1 -1 -1 1
    -3000000000  3  -1000000000 -1000000000 -1000000000
    -23  4  -10 20 -30 42
    3  2  9 -6
    -3  2  -2 -3
    23  10  8 3 4 -1 4 0 4 -7 4 -3
    

    Output

    SI 4 1
    SI 5 1
    SI 2 1
    NO
    SI 2 1
    SI 2 2
    SI 9 7
    
  • Information
    Author
    Xavier Povill
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++