PROBLEM LINK:
Author & Editoralist: Jafar Badour
Tester: Teja Reddy
PROBLEM EXPLANATION
There are N boxes on a table, numbered 1 through N from left to right. Each box has a number written on it; let’s denote the number written on box i by A_i.
Two players ― Jafar and Almir ― are playing a game that lasts for K turns. The rules of the game are as follows:
- Before the game starts, they flip a coin to decide the starting player.
- In the first turn, the starting player chooses a box and places the ball in it.
- Afterwards, the players alternate turns (in the second turn, the non-starting player is playing).
- In each turn, the current player can move the ball one box to the left (unless it is in box 1) or one box to the right (unless it is in box N).
- The result of the game is the number written on the box containing the ball after K turns.
Jafar plays in such a way that when the game ends, the number on the box which contains the ball is the biggest possible. On the contrary, Almir wants this number to be the smallest possible.
You know which player moves first. Determine the result of the game, assuming that both players play optimally.
DIFFICULTY:
Easy
PREREQUISITES:
None
EXPLANATION:
If K is odd then the starting player has a full control of the game.
If Jafar is starting then answer is the box with maximum value, and for almir it’s box with the smallest value.
The reasoning is simple, the player places the ball in his target box, and the second player wll move it to an adjacent one. What the first player does is simply returning it back.
If K is even, then the second player would make the last move. Let’s assume that Jafar is starting. He must choose a box such that the minimum of his neighbors (box to left\box to right) is maximum possible. After Jafar places the ball, Almir is forced to move it to one of the neighbors. What Jafar does is simply return it back to the starting box, and then Almir would return it to the neighboring box with a smaller value.
If Almir is starting he must choose a box such that the maximum of his neighbors (box to left\box to right) is the minimum possible.
Don’t forget to consider placing the ball at the first box or last box.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = (1<<20);
int T , n , K , p , arr[MX];
int main(){
cin>>T;
while(T--){
cin>>n>>K>>p;
for(int j = 1 ; j <= n ; j++) cin>>arr[j];
if(K % 2){
if(!p) cout<<*max_element(arr+1 , arr+1+n)<<endl;
else cout<<*min_element(arr+1 , arr+1+n)<<endl;
}
else{
int ans;
if(!p){
ans = max(arr[2] , arr[n-1]);
for(int j = 2 ; j < n ; j++)
ans = max(ans , min(arr[j-1] , arr[j+1]));
}
else{
ans = min(arr[2] , arr[n-1]);
for(int j = 2 ; j < n ; j++)
ans = min(ans , max(arr[j-1] , arr[j+1]));
}
cout<<ans<<endl;
}
}
}
this is needed
