DCP-229: Game Kufa Back to All Problems

Medium Data Structures > Range Minimum Query/Lowest Common Ancestor

Shafi and Rafi are twin brothers. They are very interested on mathematics. Shafi wants to play a game “Panouti” with his brother, Rafi, using an Array, **A**, of **n** different integers. The rules are as follows: <br/> 1. Shafi plays first and two players move in alternating turns. <br/> 2. In a single move, a player chooses the maximum element currently present in the Array, **A**, and removes it as well as all the other elements of its right. <br/>For example A = [2, 3, 5, 4, 1] then, it becomes A = [2, 3] after the first move, because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).If there are more than one maximum element then leftmost will be choosen.<br/> 3. The modifications made to the array during each turn are permanent, so the next player (Rafi) continues the game with the remaining array. <br/> 4. For each turn every players get a Point. This Point actually the position of the maximum element which Shafi or Rafi turned. <br/> 5. If the difference between total Shafi’s point and Rafi’s point is a Prime number then Rafi will win otherwise Shafi will win. <br/> Now, Shafi and Rafi play **g** games. Given the initial array of each games. Can you find and print the name of the winner? <br/> <br/> If Shafi wins print: Shafi=X (one space) Rafi=Y Shafi win Else print: Rafi=Y (one space) Shafi=X Rafi win Where X and Y is the total points of Shafi and Rafi. Input: ---------- The first line contains a single integer denoting **g** (the number of games). The **2*g** subsequent lines describe each game array over two lines: <br/> 1. The first line contains a single integer, **n** , denoting the number of elements in array **A**. <br/> 2. The second line contains **n** different space-separated integers describing the respective values of **a<sub>1** </sub>, **a <sub>2** </sub>, **a<sub>3**</sub> …. **a<sub>n**</sub> for array **A**. <br/> Constraints: ---------- 0 < g < 51 <br/> 0 < n < 10001 <br/> 0 < a <sub>i</sub> < 1000001 <br/> **summation of n over all games will be 10000.** Output: ---------- For each game, print the total points and name of the winner on a new line. You may follow the above instructions and Sample input output format. Sample Input 1 5 5 2 6 3 4 Sample Output Game 1: Rafi=1 Shafi=3 Rafi win *Analysis: You have an array of elements [5, 2, 6, 3, 4] <br/> Shafi will turn 6, so Shafi’s point = 3 (position of the largest number), then all right numbers will be reduced. So, you have [5, 2] <br/> Rafi will turn 5 and his point = 1(position of the largest number), then all right numbers will be reduced. So, you have [] empty array. <br/> Now the difference between Shafi’s point and Rafi’s point is 2 (3-1=2) is a Prime number, as a result Rafi will win.* > N:B: see the detail of prime numbers > https://en.wikipedia.org/wiki/Prime_number

Problem Setter:

Pranta Sarker

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 sazal_dev Cpp 0.00s
02 mir_lutfur_rahman Cpp14 0.00s
03 feodorv C 0.00s
04 kissu_pari_na Cpp14 0.00s
05 umli Cpp 0.00s
06 curiousblue Cpp14 0.00s
07 Robbinb1993 Cpp 0.00s
08 Morass Cpp14 0.01s
09 Key_logger Cpp14 0.01s
10 ovis96 Cpp14 0.01s
11 njrafi Cpp14 0.01s
12 BishalG Cpp 0.01s
13 ssavi Cpp14 0.01s
14 subhashis_cse Cpp 0.02s
15 Najat Cpp14 0.02s
16 prodipdatta7 Cpp14 0.02s
17 _GhOstMan_ Cpp14 0.02s
18 tahsinbd Cpp 0.02s
19 hrOarr Cpp14 0.03s
20 ayesha49 Cpp 0.04s
21 saiful130104 Cpp14 0.07s
22 tariqiitju Cpp 0.14s
23 cse_nazmul Cpp 0.15s
24 Peregrine_Falcon Cpp14 0.15s
25 mjtbasif Cpp14 0.16s
26 anikatahsin Cpp 0.17s
27 emrul Cpp14 0.17s
28 Bruteforcekid Cpp 0.17s
29 Reayz Cpp 0.18s
30 Logic_Hunter Cpp14 0.19s
31 FariD Cpp14 0.20s
32 sumon23 Cpp14 0.20s
33 Mr_adnan Cpp14 0.20s
34 showmic Cpp14 0.33s
35 Brokenlog Cpp 0.33s
36 SakibAlamin Cpp14 0.34s
37 _dipu Cpp14 0.39s
38 ssohan Cpp 0.42s
39 joymollick Cpp14 0.61s
40 zitul_mahmud Cpp14 0.64s
41 RandyWaterhouse Python3 1.96s

Your feedback is our precious!

Or call +88 02 9853138 for support