A Long Problem

View as PDF

Submit solution

Points: 0 (partial)
Time limit: 5.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
C++

You will be given 20 functions to implement; then, your functions will be graded in random order. If any of your functions do not receive an AC verdict, you will be awarded the prefix of correct functions.

Note: If you do not implement every function and return an answer, you will receive a CE (Compilation Error) or RTE (Runtime Exception) verdict.

Function 1

int divide(int a, int b)
  • a: the dividend.
  • b: the divisor.
  • This procedure should return the quotient of a and b (i.e., the integer result of \frac{a}{b}).
  • This procedure will be called up to 10^5 times.
  • 1 \le a, b \le 10^9

divide(5, 2) should return 2.

Function 2

int count_occurrences(string s, string pattern)
  • s: the string to search for the pattern.
  • pattern: the pattern to find in the string.
  • This procedure should return the number of occurrences of pattern in s.
  • This procedure will be called up to 10^3 times.
  • 1 \le |pattern| \le |s| \le 100
  • s and pattern will only contain lowercase letters.
  • Note that |str| denotes the length of the string str.

count_occurrences("babab", "bab") should return 2.

Function 3

vector<int> sort_array(vector<int> arr)
  • arr: the vector of integers to sort.
  • This procedure should return arr in ascending order (i.e., it should be strictly non-decreasing).
  • This procedure will be called up to 10^3 times.
  • 1 \le |arr| \le 10^3
  • 1 \le arr_i \le 10^9
  • Note that |arr| denotes the length of vector arr, and that arr_i denotes every integer in the vector arr.

sort_array({5, 3, 6000, 20}) should return {3, 5, 20, 6000}.

Function 4

int max_size_k(vector<int> arr, int k)
  • arr: the vector of integers to find the maximum k subarray.
  • k: the size of the maximum size subarray to find.
  • This procedure should return the maximum sum of a subarray of size k in arr.
  • This procedure will be called up to 10^3 times.
  • 1 \le k \le |arr| \le 10^3
  • 1 \le arr_i \le 10^6
  • Note that |arr| denotes the length of vector arr, and that arr_i denotes every integer in the vector arr.

max_size_k({5, 6, 100, 20, 5}, 2) should return 120.

Function 5

char find_upper(char ch)
  • ch: the lowercase letter to be converted to uppercase.
  • This procedure should return the uppercase version of ch.
  • This procedure will be called up to 10^5 times.
  • ch will be a lowercase letter.

find_upper('c') should return 'C'.

Function 6

bool is_prime(int n)
  • n: the number to check primality.
  • This procedure should return true if n is prime and false if n is not prime.
  • This procedure will be called up to 10^5 times.
  • 1 \le n \le 10^3

is_prime(107) should return true.

Function 7

int distinct_integers(vector<int> arr)
  • arr: the vector to count the number of distinct integers.
  • This procedure should return the number of distinct integers in arr.
  • This procedure will be called up to 10^3 times.
  • 1 \le |arr| \le 100
  • 1 \le arr_i \le 100
  • Note that |arr| denotes the length of vector arr, and that arr_i denotes every integer in the vector arr.

distinct_integers({5, 100, 3, 20, 20, 5, 1}) should return 5.

Function 8

bool is_inside(int x, int y, int rx, int ry, int w, int h)
  • x: the x-coordinate of the bottom-left of the rectangle.
  • y: the y-coordinate of the bottom-left of the rectangle.
  • rx: the x-coordinate of the rock.
  • ry: the y-coordinate of the rock.
  • w: the rectangle's width (the length that it extends horizontally in the positive x-direction).
  • h: the rectangle's height (the length that it extends vertically in the positive y-direction).
  • This procedure should return true if the rock is contained (or on the side) of the rectangle and false otherwise.
  • This procedure will be called up to 10^5 times.
  • 1 \le x, y, rx, ry, w, h \le 10^9

is_inside(1, 1, 5, 5, 4, 4) should return true.

Function 9

bool is_even(int n)
  • n: the number to check evenness.
  • This procedure should return true if n is an even number and false otherwise.
  • This procedure will be called up to 10^5 times.
  • 1 \le n \le 10^9

is_even(5) should return false.

Function 10

bool is_bit_on(int bit, int num)
  • bit: the number of the bit to check if it's on.
  • num: the number to check for the bit.
  • This procedure should return true if the bit^\text{th} rightmost zero-indexed bit is toggled on in the binary representation of num and false otherwise.
  • This procedure will be called up to 10^5 times.
  • 1 \le num \le 2^{29}
  • 0 \le bit \le 28

is_bit_on(2, 4) should return true.

Function 11

int create_max(vector<int> dig)
  • dig: the vector of integers to reorder to find the maximum possible number.
  • This procedure should return the maximum number created by reordering the digits in dig.
  • This procedure will be called up to 10^4 times.
  • 1 \le |dig| \le 9
  • 0 \le dig_i \le 9
  • Note that |v| denotes the length of vector v, and that v_i denotes every integer in the vector v.

create_max({0, 0, 9, 3, 9}) should return 99300.

Function 12

int factorial(int n, int m)
  • n: the number to calculate its factorial.
  • m: the number to mod the answer by.
  • This procedure should return n! mod m (n! is the product of all integers from 1 to n, and mod m returns the remainder after dividing by m).
  • This procedure will be called up to 10^3 times.
  • 1 \le n \le 10^3
  • 2 \le m \le 10^9

factorial(50, 100007) should return 34694.

Function 13

bool should_feed(int h, int m, int th)
  • h: the hunger level of the dog.
  • m: the multiplier of the hunger level to get the hunger score.
  • th: the threshold where you will feed the dog if its hunger score is greater than or equal to this.
  • This procedure should return true if the hunger score (calculated by multiplying h by m) is greater than or equal to th and false otherwise.
  • This procedure will be called up to 10^5 times.
  • 1 \le h, m \le 10^4
  • 1 \le th \le 10^8

should_feed(1, 1, 1) should return true.

Function 14

pair<int, int> lowest_terms(int num, int denom)
  • num: the numerator of the fraction.
  • denom: the denominator of the fraction.
  • This procedure should return the fraction in lowest terms (i.e., their greatest common divisor is 1) with the numerator as the first element and denominator as the second element.
  • This procedure will be called up to 10^4 times.
  • 1 \le num, denom \le 10^9

lowest_terms(5, 15) should return {1, 3}.

Function 15

int find_sum(int n)
  • n: the number to sum all numbers up to.
  • This procedure should return the sum of natural numbers up to and including n.
  • This procedure will be called up to 10^3 times.
  • 1 \le n \le 10^3

find_sum(5) should return 15.

Function 16

string find_type(int type)
  • type: the number corresponding to the different strings in the problem.
  • This procedure should return max, do if type is 1, dhruv, fold if type is 2, abayomi, open if type is 3, snjezana, write if type is 4, yuxuan, close if type is 5, mohamed, move if type is 6, scarlet, crush if type is 7, anastasia, tear if type is 8, aksana, press if type is 9, alejandro, cut if type is 10.
  • This procedure will be called up to 10^5 times.
  • 1 \le type \le 10

find_type(6) should return "mohamed, move".

Function 17

string largest_lex(vector<string> arr)
  • arr: the vector of strings to find the maximum lexicographical string.
  • This procedure should return the lexicographically largest string in arr (for two strings that differ at a specific character, one string is lexicographically larger if that letter is further in the alphabet than the other letter).
  • If two strings have different lengths but identical prefixes, prefer the longer string.
  • This procedure will be called up to 10^3 times.
  • 1 \le |arr| \le 100
  • 1 \le |arr_i| \le 10
  • Each string will only contain lowercase letters.
  • Note that |arr| denotes the length of vector arr, and that arr_i denotes every string in the vector arr.

largest_lex({"abc", "bca", "dcd", "cba"}) should return "dcd".

Function 18

vector<int> add_colours(vector<int> c1, vector<int> c2)
  • c1: the red, green, and blue integer values of colour 1.
  • c2: the red, green, and blue integer values of colour 2.
  • This procedure should return the sum of each red, green, and blue value in colours 1 and 2 as a vector with red as the first value, green as the second, and blue as the third.
  • This procedure will be called up to 10^4 times.
  • Note that a colour can only have a maximum value of 255 for a red, green, or blue value after summing.
  • |c1| = |c2| = 3
  • 0 \le c1_i, c2_i \le 255
  • Note that |v| denotes the length of vector v, and that v_i denotes every integer in the vector v.

add_colours({255, 50, 125}, {255, 0, 100}) should return {255, 50, 225}.

Function 19

string remove_occurrences(string s, string pattern)
  • s: the string to remove all occurrences of pattern from.
  • pattern: the pattern to remove from s.
  • This procedure should return s after removing all occurrences of pattern from it.
  • This procedure will be called up to 100 times.
  • Note that earlier pattern matches take precedence.
  • 1 \le |pattern| \le |s| \le 100
  • s and pattern will only contain lowercase letters.
  • Note that |str| denotes the length of the string str.

remove_occurrences("abcabcab", "abcab") should return "cab".

Function 20

bool AC()
  • This procedure should return true.
  • This procedure will be called up to 10^5 times.

AC() should return true.


Comments

There are no comments at the moment.