Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | winetasting.in, winetasting.out | Sursă | IIOT 2021-22 Runda 3 |
| Autor | Giorgio Audrito | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Wine Tasting
There are N vineyards arranged in a row, numbered from 0 to N-1. Giorgio starts the tour from vineyard L, once the first tasting is over he will move on to the vineyard L+1, then to the vineyard L+2 and so on until he reaches the vineyard R. Note that Giorgio can start and end his tour on the same vineyard.
To visit the vineyard i Giorgio has to pay V[i] euro. The cost of a tour is the cost of each vineyard visited.
There are a total of N*(N+1)/2 different tours, Giorgio will choose one of the tours in the following way:
First, he sorts the tours in ascending order of cost, in case of a tie, the tours with the smallest starting vineyard come first. Then, he chose the K-th tour from this order.
Help Giorgio find the first and the last vineyards of the K-th tour!
Date de intrare
The first line of the input file winetasting.in contains the integers N and K. The second line contains N integers V[i].
Date de ieşire
The output file winetasting.out contains a single line which has the integers L and R: the first and the last vineyards of Giorgio's tour.
Restricţii
- 1 ≤ N ≤ 2*10^5
- 1 ≤ K ≤ N*(N+1)/2
- 1 ≤ v[i] ≤ 10^9
- For tests worth 50 points, V[i] = 1 for all values in the input.
- For tests worth 20 more points, 1 ≤ N ≤ 1000.
Exemplu
| winetasting.in | winetasting.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
In the first sample case there are 10 possible tours, in order:
from 0 to 0: the cost is 1
from 3 to 3: the cost is 1
from 1 to 1: the cost is 2
from 0 to 1: the cost is 1+2=3
from 2 to 2: the cost is 3
from 2 to 3: the cost is 3+1=4
from 1 to 2: the cost is 2+3=5
from 0 to 2: the cost is 1+2+3=6
from 1 to 3: the cost is 2+3+1=6
from 0 to 3: the cost is 1+2+3+1=7
The fourth tour starts from vineyard 0 and end in vineyard 1.
