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 −1014 ≤ s ≤ 1014, 1 ≤ n ≤ 105, i −109 ≤ ak ≤ 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++