Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shopping Mania

By reborn · Limits 1s, 256 MB · Interactive

Shapla and Jui have entered the final round of Shopping Mania, an annual shopping game played by two players. The rules of the game are described below:

  1. There are nn items with prices p1,p2,,pnp_1, p_2, \dots, p_n. There is also a constant value kk, denoted as Maximum Skips in a Row. These values are made known to the players at the very beginning.

  2. The host presents an item. The items are presented one by one and item ii is only presented when all the items before it i.e. the items numbered 1,2,,i11, 2, \dots, i-1 are purchased by any of the players.

  3. The player who has the turn decides whether to purchase this item or skip it in this turn. An item can only be skipped when there was at least one purchase made by any of the players in the last kk turns or if the game hasn’t been played for kk turns yet.

    • If the item is purchased, the item is added to the player’s cart.

      • If it was the last item i.e. nn’th item, the game ends.

      • Otherwise, the host presents the next item. Turn changes to the other player. And the game continues from Step-3 again.

    • If the item can be skipped and is skipped in this turn by the current player, the turn changes to the other player, and the game continues from Step-3.

  4. When the game ends, the prices of the items in each players’ cart are summed up and the player with the biggest sum wins the game. If both of them an equal sum of prices in their carts, both are declared winners.

Shapla won the toss and can decide who has the first turn. Can you advise Shapla whether to go first or second and in each of her turns whether to purchase or skip the current item so that she eventually wins?

Interaction

This is an interactive problem. The judge will play as Jui opposing you. Please refer to the Notes section for help on interactive problems.

There will be two integers n,kn,k on the first line of input. The next line follows with nn space separated integers p1,p2,,pnp_1, p_2, \dots, p_n.

Now you must output “first” or “second” (without the quotes) to indicate if Shapla should have the first turn or not.

  • In each of Shapla’s turns, you must output “purchase” or “skip” (both without the quotes, and you can only output “skip” if it’s valid) on a line.

  • In each of Jui’s turns, the judge will output “purchase” or “skip” on a line as well. You can be assured that the judge output will be valid. You must input this line.

  • When any player xx purchases current item ii, there will be a line of input with the text “xx purchased item ii”. You must input this line. However, this line is only for convenience and you may not do anything with it.

The game ends when nn purchases have been made and your program must quit immediately. You will get an “Accepted” verdict if Shapla and you have won this game or a “Wrong Answer” if you haven’t. If your program doesn’t quit and expect further inputs, it might get all sorts of verdicts excluding “Accepted” and including “Idleness limit exceeded”.

Please note that any invalid output from your program will result in a “Wrong Answer” verdict as well. Do refer to the sample interaction for better understanding.

Sample Interaction

Inputs are shown on the left and your outputs are shown on the right. Note that on line 11, Jui had no other option but to purchase item 3, since in the last k=3k =3 turns there were no purchases made.

Constraints & Scoring

For all sub-tasks:

  • 1pi1051 \le p_i \le 10^5.

Sub-tasks:

  1. Sub-task 1 (14 points):

    • 2n32 \le n \le 3

    • 0k10 \le k \le 1.

  2. Sub-task 2 (6 points):

    • 2n1042 \le n \le 10^4

    • k=0k = 0.

  3. Sub-task 3 (80 points):

    • 2n1042 \le n \le 10^4

    • 0k500 \le k \le 50.

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems

    Discussion

    Statistics


    40% Solution Ratio

    Um_nikEarliest, 4M ago

    Deshi_TouristFastest, 0.0s

    Um_nikLightest, 262 kB

    NirjhorShortest, 1445B

    Submit

    Login to submit

    Editorial

    Since, to win, any player needs more or equal scores than the other player, considering the other pl...

    Toph uses cookies. By continuing you agree to our Cookie Policy.