Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2090
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2090
I Went to Market And Bought...
By Gabriel Duarte, UNIFESO 
Brazil
Timelimit: 3
A common joke among children is "I went to market and bought..." her several children form a line and each must speak one item would buy in the market, but to increase the difficulty it is necessary that each child repeat all products that it has been said since the beginning of the game. The game ends when someone misses the order of the product or when the last child in line hits the sequence.
Let's imagine that Mary, Peter and Amanda began to play and have already decided who will say what product, Maria will tell Bread, Peter likes cheese and Amanda will talk Apple.
Assuming that the queue is organized in alphabetical order the game should go as follows:
1 - Amanda says: "I went to market and bought bread"
2 - Mary says: "I went to market and bought bread and apple"
3 - Peter says: "I went to market and bought bread, apple and cheese"
Therefore the order of the products were: bread, bread, apple, bread, apple and cheese.
His high school friends decided to hold this game to pass the time. After some playing time the list of products that each one should say was getting too big, in this way, see if anyone missed is not a simple task. That's when your friends reminded that you are programmer and could easily solve this problem.
Given the amount of people in the queue and what product each will say, they need a program to inform what is the K-th product to be said. So it will be easier to determine if someone missed or not.
You will be able to help your friends?
Input
The input contains several test cases. The first line of each test case will have two integer N and K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ min (2 * 10⁹, N * (N + 1) / 2)), representing the number of children at play and which product your friends want to know, see the example for details. The next row will have the sequence s1, s2, s3, ..., sn, where the product si is the ith product that the child will tell, each word contains a maximum of 20 lowercase letters. The entry ends when N = 0 and is not to be processed.
Output
For each test case you should print what the K-th product to be said.
| Input Sample | Output Sample |
|
2 2 |
maca |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
typedef struct string{
char produto[30];
} string;
#define true 1
#define false 0
#define MAXSIZE 100100
int main (void)
{
unsigned i, j;
unsigned n, k;
string shepa[MAXSIZE];
while (scanf("%d %d", &n, &k), n)
{
long long hi, low, mid;
for (i = 1; i < = n; ++i)
scanf("%s", shepa[i].produto);
low = 1; hi = n;
while (low < hi)
{
mid = low + (hi - low) / 2;
if (mid * (mid + 1) / 2 >= k)
hi = mid;
else
low = mid + 1;
}
printf("%s\n", shepa[k - ((low - 1) * low / 2)].produto);
}
}
Input
maca mamao
4 5
arroz feijao uva melancia
0 0
Output
feijao