KEMBAR78
Cs3230 Programming Assignment 2 2 | PDF | Computer Programming | Computer Science
Scribd
Upload
31 views3 pages

Cs3230 Programming Assignment 2 2

This document provides instructions for programming assignment 2 in CS3230, which is due on November 17th at 23:59. The problem involves forming the best team of athletes for a competition by selecting x runners and y swimmers from a pool of n athletes, where each athlete has a running and swimming time. The goal is to minimize the total time taken by the team. Sample inputs and outputs are provided to demonstrate the required formatting and outputs. Constraints on the values of n, x, y, and individual times are also outlined. Students must submit their solutions in C++ or Java to CodeCrunch to be graded based on time complexity and passing all test cases.

Uploaded by

Nguyễn Phước Lộc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views3 pages

Cs3230 Programming Assignment 2 2

This document provides instructions for programming assignment 2 in CS3230, which is due on November 17th at 23:59. The problem involves forming the best team of athletes for a competition by selecting x runners and y swimmers from a pool of n athletes, where each athlete has a running and swimming time. The goal is to minimize the total time taken by the team. Sample inputs and outputs are provided to demonstrate the required formatting and outputs. Constraints on the values of n, x, y, and individual times are also outlined. Students must submit their solutions in C++ or Java to CodeCrunch to be graded based on time complexity and passing all test cases.

Uploaded by

Nguyễn Phước Lộc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

CS3230 programming assignment 2

Due: 17 Nov 23:59

1 Problem statement
You are a coach of an athletic team with n athletes. You wish to send some of
your athletes to a competition.
The rules of the competition are as follows:

• A team consists of x runners and y swimmers.


• Each person is only allowed to participate in one sport; in other words a
single person cannot be both a runner and a swimmer.
• The score of a team is the total time taken by all x runners and all y
swimmers.

As the coach, you know that athlete i (1 ≤ i ≤ n) takes a[i] time to run and
b[i] time to swim. Your task is to form the best team and find the minimum
possible total time taken by choosing x runners and y swimmers.

2 Input format
The first line of the input consists three space-separated integers, n, x, y. n lines
then follow. The i-th of these lines consists of two space-separated integers a[i]
and b[i].

3 Output format
Output a single integer, the minimum possible total time taken by x runners
and y swimmers.

4 Samples
Sample input 1
3 1 1

1
670 7279
1264 4798
7392 135

Sample output 1
805

Sample input 2
4 1 1
8580 8343
3721 6099
5225 4247
940 340

Sample output 2
4061

Sample input 3
5 1 1
6082 1564
4428 5648
6992 6200
3946 9225
9944 6939

Sample output 3
5510

5 Constraints
• 3 ≤ n ≤ 105

• 0 ≤ x, y ≤ n, x + y ≤ n
• 1 ≤ a[i] ≤ 104 (for all 1 ≤ i ≤ n)
• 1 ≤ b[i] ≤ 104 (for all 1 ≤ i ≤ n)

Required time complexity for full credit (5 points): O(n log n).
Solutions which run in O(n2 log n) will receive 4 points - you will only need
to pass test cases satisfying n ≤ 4000 to get these 4 points.

2
6 Submission instructions and grading
(Same policy as previous assignment) Submit your solution to CodeCrunch in
either C++ or Java. You need to pass all test cases to get 5 points (or all test
cases satisfying n ≤ 4000 to get 4 points).
The tasks will be labelled full and partial.
• If your final submission to full is correct, you will receive 5 points and
your submission to partial will be ignored. If you are confident of your
submission to full, you do not need to submit to partial.
• If your submission to full is incorrect, or you did not submit to full, then
your solution to partial will be graded, in which you may receive 3 points
if your solution to partial is correct.

• If multiple submissions are made, only the last one will be graded.

7 Collaboration policy
You may discuss the problems with your classmates, though you should write
up your solutions on your own. Please note the names of your collaborators in
your submission. You may want to refer to the plagiarism policy from Lecture
2.
You are not allowed to share code.

You might also like