15842번 - Koala Game 서브태스크점수다국어언어 제한함수 구현

Koala has created a new game and she has challenged you! She begins by placing down N items, numbered from 0 to N-1. She then secretly assigns each item i an integer value between 1 and N so that no two items have been assigned the same value. Item has been assigned the value Pi. She has challenged you to identify some properties of the sequence of values P = P₀, P₁, ..., P_N-1.

To do this, you will ask Koala to play a series of rounds. In each round, you are given W blue stones, and Koala is given W red stones. You go first by placing some (or possibly all) of your stones next to some items of your choosing. Koala, seeing your arrangement, responds similarly by placing some (or possibly all) of her stones next to some of the items. Koala then wins all items which have strictly more red stones than blue stones next to them. Koala always distributes her stones so that she maximises the sum of the values of the items that she wins. If there are are multiple ways to do this, she picks a way which maximises the total number of items that she wins. If there are still multiple ways to do this, she picks any of these ways.

Koala is very lazy and will fall asleep if you ask her to play too many rounds. Your task is to identify patterns in Koala's sequence P by playing as few rounds as possible.

In this task, there are four functions for you to implement: minValue, maxValue, greaterValue and allValues. Each function requires you to identify a different property of the sequence P. You are strongly recommended to use the template implementation for your language as a starting point for your solution. Note that even if you are only attempting some of the subtasks, you must still provide an implementation for all four functions (though some of these implementations may be empty). Your program must not read from standard input, write to standard output or interact with any files.

In each function the parameter N is the number of items in the game and the parameter W is the number of stones both you and Koala play with in each round of the game.

• minValue(N, W) --- This function should return the item number i with the minimum value, that is, P_i = 1.
• maxValue(N, W) --- This function should return the item number i with the maximum value, that is, P_i = N.
• greaterValue(N, W) --- This function should compare the value of items 0 and 1, and return the number of the item which is greater. Specifically, it should return 0 if P0 > P1 and return 1 otherwise.
• allValues(N, W, P) --- This function should determine the entire sequence P and place it in the provided array P:specifically, P[i] should contain the value Pi of item i for all 0 ≤ i ≤ N-1.

In each testcase, the grader will call precisely one of these functions one or more times. Each function call is to be treated as a separate game. Which function is called and the maximum number of times it may be called depends on the subtask (see below). You may assume that Koala has fixed her sequence P before each function call, and it will not change throughout the duration of the function. She may then change her sequence before the next function call.

The implementation for each function should call the function playRound to gain information about Koala's sequence.

• playRound(B, R) --- Ask Koala to play a round with you.
  • The array B describes how many blue stones you place next to each item. Specifically, for all 0 ≤ i ≤ N-1, B[i] blue stones will be placed next to the item numbered i. Each B[i] must be a non-negative integer and the sum B[0] + B[1] + ... + B[N-1] must not exceed W.
  • The grader will fill the provided array R to describe Koala's response. Specifically, for all 0 ≤ i ≤ N-1, Koala will place R[i] red stones next to the item numbered i.
  • Each subtask specifies a hard limit on the number of times you may call playRound per game. Please note that using fewer calls than this limit may yield a higher scoring solution (see below).

• If playRound is called with an invalid array B, or the number of calls to playRound exceeds the hard limit for any game within a testcase, the entire testcase will be marked as Not Correct, scoring 0.
• If a function does not correctly determine the required properties of Koala's sequence P for a particular game within a testcase, the entire testcase will be marked as Not Correct, scoring 0.
• Both Subtask 4 and Subtask 5 require you to implement the function allValues, with different values of W. You may use this to differentiate the two subtasks in your implementation -- see the template implementation in your language for further details.

Consider the following sequence P.

Below are a series of example calls made to playRound, and a valid response by the grader to each (note that there may be more than one valid response for any given call to playRound).

Feedback for each of the functions that the grader calls below (exactly one per testcase) is provided in the given order as "Sample Data" upon submission. You may call playRound at most 3200 times in each of these 5 testcases.

The sample grader reads from standard input in the following format:

• line 1: two integers F, G;
• line 2 to G + 1: each line contains two integers N, W followed by N integers P₀, P₁, ..., P_N-1 describing a single game.

The integer F determines which function the sample grader will call:

The integer G determines how many times the specified function will be called. Each subsequent line describes a game with Koala's sequence.

The sample grader will write two lines to standard output for each function call. The first line contains the number of times playRound was called.

• If F = 4, the second line contains the contents placed in the array P by your implementation of the function allValues;
• Otherwise, if F = 1, 2 or 3, the second line contains a single integer: the return value of the corresponding function.

For instance, the fourth testcase in "Sample Data" (which calls allValues with N = 6 and W = 12) can be described with the following sample input file.

4 1
6 12 5 3 2 1 6 4

• In this subtask, the grader will only call the function minValue. This function will be called at most 100 times per testcase.
• N = 100.
• W = 100.
• You may call playRound at most 2 times per game.

• In this subtask, the grader will only call the function maxValue. This function will be called at most 100 times per testcase.
• N = 100.
• W = 100.
• You may call playRound at most 13 times per game.
• The score for a testcase in this subtask depends on the maximum number of times C_max that playRound is called among all games in that testcase. Precisely your score will be:
  • 15 points if C_max ≤ 4;
  • 7 points if 5 ≤ C_max ≤ 13.

• In this subtask, the grader will only call the function greaterValue. This function will be called at most 1100 times per testcase.
• N = 100.
• W = 100.
• You may call playRound at most 14 times per game.
• The score for a testcase in this subtask depends on the maximum number of times C_max that playRound is called among all games in that testcase. Precisely your score will be:
  • 18 points if C_max ≤ 3;
  • 14 points if C_max = 4;
  • 11 points if C_max = 5;
  • 5 points if 6 ≤ C_max ≤ 14.

• In this subtask, the grader will only call the function allValues. This function will be called exactly once per testcase.
• N = 100.
• W = 200.
• You may call playRound at most 700 times.

• In this subtask, the grader will only call the function allValues. This function will be called exactly once per testcase.
• N = 100.
• W = 100.
• You may call playRound at most 3200 times.
• The score for a testcase in this subtask depends on the number of times C that playRound is called. Precisely your score will be:
  • 53 points if C ≤ 100;
  • 53 - 8log₂(C/100) points if 101 ≤ C ≤ 3200. In particular, if C = 3200 your solution will score 13 points.

• public.zip