Computing Algorithms Assignment 2 X Instructions
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 3
| Download | |
| Open PDF In Browser | View PDF |
2801ICT Computing Algorithms – Assignment 2 (10%) (Due Week 11) This assignment must be done individually. The submission date is as specified in the Course Profile (May13, 2019) and the submission method will be communicated during trimester. Problem Description Scott and Rusty are playing a game named "Maximize The Score". In this game, there are n balls placed on the table. Each ball has a value written on it. The game starts with a toss. If head comes, then Scott starts the game, else Rusty starts the game. The game is played in the form of rounds. Hence, if Scott wins the toss, the first round will be played by Scott, second round will be played by Rusty, third round will be played by Scott and so on. In each round, the player is allowed to take at max k turns. In each turn, the player picks one ball from the table. Please note that each round is entirely played by one player only so if it is Scott's round, then he will play x turns (x <= k) and the next round will be played by Rusty. Rusty is little bit crazy about sum of digits and so he will only pick the ball, whose sum of digits of the value is maximum (for e.g. if 4 and 11 are present on the table, he will pick 4 as the sum of digits of 4 is greater than that of 11). If more than one ball have maximum sum of digits, then he can pick any one of them. Scott doesn't care about sum of digits so he can pick any ball from table. They both want to maximize their score and so both of them will play optimally. Score of a player is the sum of values of all the balls taken by the player. Your task is to print the score Scott and Rusty will achieve if they both play optimally. See the sample case for better understanding Input format: First line contains an integer , denoting the number of test-cases. Next lines contain the test-cases as shown below: First line contains two integers and , representing the number of balls present on the table and the maximum number of turns allowed per round. Second line contains n space separated integers (a1, a2, ... an). Here, ai indicates the score written on th ball. Third line contains result of the toss. Here, "HEADS" indicates Scott starts the game, while "TAILS" indicates Rusty starts the game. Output format: For each testcase, print scores achieved by Scott and Rusty, if they both play optimally. Constraints: 1 <= T <= 10 1 <= n, k <= 100000 1 <= ai <= 1000000000(1e9) Sample Input 2 32 1000 99 98 TAILS 21 56 HEADS Sample Output 1000 197 65 Explanation In first testcase, the winner of toss is Rusty and so Rusty plays first round. In this round, he can have 2 turns and so he will take 2 turns. In first turn, he has no choice but to pick 99 as it has largest sum of digits. Similarly, in second turn he has to pick 98. Now, Scott plays his round. As there is only one ball left, Scott can only take one turn and pick that ball. So, final score of Scott = 1000 and final score of Rusty = 99 + 98 = 187. In second testcase, the winner of toss is Scott and so Scott plays the first round. In this round, he will of course pick 6 as he wants to maximize the score. Then Rusty plays second round and picks 5. So, final score of Scott = 6 and final score of Rusty = 5. Results for C++ Implementation Input Output 1 2 3 4 5 1000 197 240 150 2100000000 98888899 9538 2256 30031 17796 CPU Time (Secs) 0.000005 0.000005 0.000004 0.000011 0.000057 Input Output 6 7 8 9 10 4726793900 3941702128 13793 12543 2195 1643 3923529875 3049188235 0 284401 CPU Time (Secs) 0.000010 0.000015 0.000040 0.000008 0.000027 Results for Python Implementation Input Output 1 2 3 4 5 1000 197 240 150 2100000000 98888899 9538 2256 30031 17796 CPU Time (Secs) 0.000029 0.000051 0.000033 0.000160 0.001435 Input Output 6 7 8 9 10 4726793900 3941702128 13793 12543 2195 1643 3923529875 3049188235 0 284401 CPU Time (Secs) 0.000167 0.000266 0.000827 0.000119 0.000573 Notes 1. When solving this problem, you should demonstrate your understanding of implementing a priority queue using heap. Instead of using sorted arrays, you must use priority queues to allow Scott and Rusty to pick balls according to their preferences. You should not use any library/package for priority queue and heap. 2. You must design your own algorithm and write the program code submitted. The program must be able to be run from the command line passing the path to the Input.txt file as an argument. The naming convention for your program file is:_ Maximise_The_Score.py (or _ Maximise_The_Score.cpp or _ Maximise_The_Score.java)(without the <>) and try and keep the program within a single file. 3. You must produce a Power-point presentation describing your algorithm (including the pseudocode), correctness of your algorithm, the results of the problem (sample Input.txt is provided) and performance analysis. Marking This assignment is worth 10% of your final grade. The assignment will be marked out of 100 and marks will be allocated as follows: 1. (Algorithmic Design) Overview, Algorithm Description, Algorithm Pseudo-Code: 30 marks 2. (Implementation) Quality of code (e.g. appropriate naming conventions, code comments, class structure, method structure, appropriate use of data structures etc.): 15 marks 3. (Result and Algorithm Analysis) The results of the problem (sample Input.txt is provided), correctness of the algorithm and performance analysis: 10+15+15=40 marks 4. (Presentation) Power-point presentation: 15 marks Submission Student should submit a zip file ( _Algorithm_Assignment_2.zip) consisting of the following: 1. A document covering 1 and 3: _Algorithm_Assignment_2.pdf, 2. Source code file: _ Maximiser_Le_Score.py (cpp/java) and 3. A power point presentation file: _Algorithm_Assignment_2.ppt (/pptx). Please note that all submitted assignments will be analysed by a plagiarism detector including the submitted source code of the program. If any form of plagiarism is found, it will be dealt with in accordance with university policy: https://www.griffith.edu.au/academic-integrity/academic-misconduct.
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.4 Linearized : No Page Count : 3 XMP Toolkit : XMP toolkit 2.9.1-13, framework 1.6 About : uuid:96e2b385-6334-11e9-0000-5aeb72c72ba0 Producer : GPL Ghostscript 9.06 Modify Date : 2019:04:17 16:21:52+10:00 Create Date : 2019:04:17 16:21:52+10:00 Creator Tool : PScript5.dll Version 5.2.2 Document ID : uuid:96e2b385-6334-11e9-0000-5aeb72c72ba0 Format : application/pdf Title : Microsoft Word - Computing Algorithms Assignment 2 - Final.docx Creator : s2980936 Author : s2980936EXIF Metadata provided by EXIF.tools