2020 CCC Preparation

I promised increasing difficulty, so here it is :)

Fiona commutes to work each day. If there is no rush-hour traffic, her commute time is 2 hours. However, there is often rush-hour traffic. Specifically, rush-hour traffic occurs from 07:00 (7am) until 10:00 (10am) in the morning and 15:00 (3pm) until 19:00 (7pm) in the afternoon. During rush-hour traffic, her speed is reduced by half. She leaves either on the hour (at XX:00), 20 minutes past the hour (at XX:20), or 40 minutes past the hour (at XX:40). Given Fiona's departure time, at what time does she arrive at work?

Input Specification

The input will be one line, which contains an expression of the form HH:MM, in which HH is one of the 24 starting hours (00, 01, ..., 23) and MM is one of the three possible departure minute times (00, 20, 40).

Output Specification

Output the time of Fiona's arrival, in the form HH:MM.

Sample Input

07:00

Sample Output

10:30

Explanation for Sample Output

Fiona drives for 3 hours in rush-hour traffic, but only travels as far as she normally would after driving for 1.5 hours. During the final 30 minutes (0.5 hours) she is driving in non-rush-hour traffic.

Hint (Click to reveal)

This problem was the fourth question from the 2016 Junior CCC competition. You can visit that question on the CCC Grader to grade your own solution.

My Python Solution is shown below.

# We change the HH:MM time into minutes since the
# start of the day, then simulate the commute
# in 10 minute chunks.

# Using this time system, traffic occurs between
# min 420 and 600, and between min 900 and 1140.
# This function tells us whether our next 10 min will be in traffic.

def traffic (n):
    if (n >= 420 and n < 600) or (n >= 900 and n < 1140):
        return True
    return False

h, m = input().split(":")

h = int(h)
m = int(m)

# convert HH:MM into minutes since midnight.

time = 60*h + m

# We assume the commute is 120km in length, and without
# traffic Fiona travels 10km every 10 minutes.
# However, in traffic, Fiona only travels 5km in 10 minutes.
# We keep track of how many 10 minute intervals occur
# until the total distance traveled reaches 120km.

distanceTravelled = 0
while distanceTravelled < 120:
    if traffic(time):
        distanceTravelled += 5
    else:
        distanceTravelled += 10
    time += 10

if time >= 1440:
    time -= 1440  # time rolls back to 0 if we cross midnight


# converts time, in minutes, back to HH:MM format.
# note that (time-time%60) finds the largest whole number multiple of 60 in time
# as time%60 is the remainder when time is divided by 60 (modulus function).

arrivalHr = int((time - time%60)/60)
arrivalMin = time%60

# Note that we're storing the hour and minute in ints, which don't consider
# leading zeros in the HH:MM format!
# Therefore, when constructing the output we must check whether we need
# to add a leading zero.

output = ""
if arrivalHr < 10:
    output += "0"
output += str(arrivalHr)
output += ":"
if arrivalMin < 10:
    output += "0"
output += str(arrivalMin)

print(output)
                    
                    

Good luck :)

You want to determine the chances that your favourite team will be the champion of a small tournament. There are exactly four teams. At the end of the tournament, a total of six games will have been played with each team playing every other team exactly once. For each game, either one team wins (and the other loses), or the game ends in a tie. If the game does not end in a tie, the winning team is awarded three points and the losing team is awarded zero points. If the game ends in a tie, each team is awarded one point.

Your favourite team will only be the champion if it ends the tournament with strictly more total points than every other team (i.e., a tie for first place is not good enough for your favourite team). The tournament is not over yet but you know the scores of every game that has already been played.

You want to consider all possible ways points could be awarded in the remaining games that have not yet been played and determine in how many of these cases your favourite team will be the tournament champion.

Input Specification

The first line of input will contain an integer 𝑇 which is your favourite team (1 ≤ 𝑇 ≤ 4). The second line will contain an integer 𝐺, the number of games already played (0 ≤ 𝐺 ≤ 5).

The next 𝐺 lines will give the results of games that have already been played. Each of these lines will consist of four integers 𝐴, 𝐵, 𝑆_𝐴, 𝑆_𝐵 separated by single spaces where 1 ≤ 𝐴 < 𝐵 ≤ 4, and 𝑆_𝐴, 𝑆_𝐵 ≥ 0. This corresponds to a game between team 𝐴 (which had score 𝑆_𝐴) and team 𝐵 (which had score 𝑆_𝐵) where team 𝐴 won if 𝑆_𝐴 > 𝑆_𝐵, team 𝐵 won if 𝑆_𝐴 < 𝑆_𝐵 and the game ended in a tie if 𝑆_𝐴 = 𝑆_𝐵. The pairs 𝐴 and 𝐵 on the input lines are distinct, since no pair of teams plays twice.

Output Specification

The output will consist of a single integer which is the number of times that team 𝑇 is the champion over all possible awarding of points in the remaining games in the tournament.

Sample Input 1

3
3
1 3 7 5
3 4 0 8
2 4 2 2
                

Sample Output 1

0

Explanation of Sample Output 1

Team 3 has lost two of its three games, and team 4 has tied one and won one, which gives 4 points to team 4. Even if team 3 wins its final game, it cannot have more points than team 4, and thus, will not be champion.

Sample Input 2

3
4
1 3 5 7
3 4 8 0
2 4 2 2
1 2 5 5
                

Sample Output 2

9

Explanation of Sample Output 2

After the following, we know Team 1 has 1 point, Team 2 has 2 points, Team 3 has 6 points and Team 4 has 1 point.

There are two remaining games (team 3 plays team 2; team 1 plays team 4). Teams 1, 2 or 4 cannot achieve 6 points, since even if they win their final games, their final point totals will be 4, 5 and 4 respectively. Thus, out of the 9 possible outcomes (2 matches with 3 different possible results per match), team 3 will be the champion in all 9 outcomes.

Hint (Click to reveal)

This problem was the third question from the 2013 Senior CCC competition. You can visit that problem page on the CCC Grader to grade your own solution.

My C++ solution (Dynamic Programming) is shown below. A strong understanding of Dynamic Programming is recommended to understand this solution.

#include 
#include 
#include 
using namespace std;


// We make a system to store the state of the tournament in a vector.
// First number the 6 games 0, 1, 2, 3, 4 and 5.
// Below shows which teams correspond to each game number.
// For example, in game 0, team 1 plays team 2.
//      0    1    2    3    4    5
//      1-2  1-3  1-4  2-3  2-4  3-4
// We use a integer vector of size 6 to store what has happened so far 
// in each of the games. We use 0 to indicate that a game hasn't happened yet,
// 1 to indicate that the first team won, 2 to indicate that the second team won,
// and 3 to indicate a tie. 

int t, g;

// findA and findB are lookup functions that return the first and second teams
// that played each game. 


int findA(int a){
    if(a == 0) return 1;
    if(a == 1) return 1;
    if(a == 2) return 1;
    if(a == 3) return 2;
    if(a == 4) return 2;
    if(a == 5) return 3;

}
int findB(int a){
    if(a == 0) return 2;
    if(a == 1) return 3;
    if(a == 2) return 4;
    if(a == 3) return 3;
    if(a == 4) return 4;
    if(a == 5) return 4;
}

// function returns 1 if the favourite team won under the input configuration.

int score(vector<int> games){
    int teams[5] = {0, 0, 0, 0, 0};
    for(int i = 0 ; i < 6; i++){
        int a = findA(i);
        int b = findB(i);
        if(games[i] == 1){
            teams[a] += 3;
        }
        else if(games[i] == 2){
            teams[a] += 0;
            teams[b] += 3;
        }
        else if (games[i] == 3){
            teams[b] += 1;
            teams[a] += 1;
        }
    }
    int myTeamScore = teams[t];
    int tru = 1;
    for(int i = 1; i < 5; i++){
        if(i != t and teams[i] >= myTeamScore){
            tru = 0;
        }
    }

    return(tru);
}

// The main recursive function. Take the starting state of the tournament.
// If all games have finished, see if the favourite team has won,
// then return 1.
// If not all games have finished, simulate all 3 possibilities of the game
// by calling the recursive function with the new state of the tournament.
// Return the sum of these three possibilities.

int dp(vector<int> games){

    int zeros = count(games.begin(), games.end(), 0);
    if(zeros == 0){
        int win = score(games);

        return(win);
    }
    else{

        int i = 0;
        int nextGame = 0;
        while(games[nextGame] != 0){
            nextGame++;
        }
        games[nextGame] = 1;
        int p1 = dp(games);
        games[nextGame] = 2;
        int p2 = dp(games);
        games[nextGame] = 3;
        int p3 = dp(games);

        return(p1+p2+p3);
    }
}

// Takes the inputs, converts the initial tournament state to the 
// system used by the recursive function,
// then call the recursive function.

int main() {
    cin >> t >> g;
    int initGames [6] = {0, 0 , 0, 0, 0, 0};
    int t1, t2, s1, s2;
    for(int i = 0; i < g; i++){
        cin >> t1 >> t2 >> s1 >> s2;
        int gameNum = 0;
        if(t1 == 1){
            if(t2 == 2) gameNum = 0;
            if(t2 == 3) gameNum = 1;
            if(t2 == 4) gameNum = 2;
        }
        else if(t1 == 2){
            if(t2 == 3) gameNum = 3;
            else gameNum = 4;
        }
        else gameNum = 5;
        if(s1 > s2) initGames[gameNum] = 1;
        else if(s1 == s2) initGames[gameNum] = 3;
        else initGames[gameNum] = 2;
    }
    vector<int> initGame;
    for(int i = 0; i < 6; i++){
        initGame.push_back(initGames[i]);
    }

    cout << dp(initGame) << endl;
}
                

You have been asked by a parental unit to do your chores. Each chore takes a certain amount of time, but you may not have enough time to do all of your chores, since you can only complete one chore at a time. You can do the chores in any order that you wish. What is the largest amount of chores you can complete in the given amount of time?

Input Specification

The first line of input consists of an integer 𝑇 (0 ≤ 𝑇 ≤ 100000), which is the total number of minutes you have available to complete your chores.

The second line of input consists of an integer 𝐶 (0 ≤ 𝐶 ≤ 100), which is the total number of chores that you may choose from. The next 𝐶 lines contain the (positive integer) number of minutes required to do each of these chores. You can assume that each chore will take at most 100000 minutes.

Output Specification

The output will be the maximum number of chores that can be completed in time 𝑇.

Sample Input

6
3
3
6
3

Sample Output

2

This problem was the fourth question from the 2013 Junior CCC competition. You can visit that question on the CCC Grader to grade your own solution.

My Python Solution is shown below.

t = int(input(""))                  # how much time you have
c = int(input(""))                  # how many chores

availableChores = []                # stores times of available chores

for i in range(c):
    availableChores.append(int(input("")))

availableChores.sort()              # sorts the times of available chores in increasing order


                    # now, we go through the list of available chores, keeping track of how much time
                    # has passed and counting how many chores we've done. 


elapsedTime = 0                     # how much time has passed so far. This starts at zero.
choresFinished = 0                  # counter for number of chores finished

for chore in availableChores:       # for each chore in availableChores, 
    elapsedTime += chore            # do a chore
    if elapsedTime > t:             # if we're out of time, stop doing chores
        break;
    choresFinished += 1             # count if we've completed a chore without running out of time

print(choresFinished)
                    
                    

You have a few minutes before your class starts, and you decide to compare the heights of your classmates. You don't have an accurate measuring device, so you just compare relative heights between two people: you stand two people back-to-back, and determine which one of the two is taller. Conveniently, none of your classmates are the same height, and you always compare correctly (i.e., you never make a mistake in your comparisons). After you have done all of your comparisons, you would like to determine who the tallest person is between two particular classmates.

Input Specification

The first line contains two integers 𝑁 and 𝑀 separated by one space. 𝑁, the number of people in the class, is an integer with 1 ≤ 𝑁 ≤ 1000000. 𝑀, the number of comparisons that have already been done, is an integer with 1 ≤ 𝑀 ≤ 10000000. Each of the next 𝑀 lines contains two distinct integers 𝑥 and 𝑦 (1 ≤ 𝑥, 𝑦 ≤ 𝑁) separated by a space, indicating that person number 𝑥 was determined to be taller than person number 𝑦. Finally, the last line contains two distinct integers 𝑝 and 𝑞 (1 ≤ 𝑝, 𝑞 ≤ 𝑁) separated by one space: your goal is to determine, if possible, whether person 𝑝 is taller than person 𝑞. Note that it may be the case that neither 𝑝 nor 𝑞 occur in the input concerning measurements between classmates, and each measurement between any two particular people will be recorded exactly once.

Output Specification

The output is one line, containing one of three possible strings: yes (if 𝑝 is taller than 𝑞), no (if 𝑞 is taller than 𝑝), unknown (if there is not enough information to determine the relative heights of 𝑝 and 𝑞).

Sample Input

10 3
8 4
3 8
4 2
3 2
                

Sample Output

yes

Explanation of Sample Output

The input tells us that 3 is taller than 8, 8 is taller than 4, and 4 is taller than 2. Therefore, 3 is taller than 2.

This problem was the fourth question from the 2013 Senior CCC competition. You can visit that problem page on the CCC Grader to grade your own solution.

Consider the measurements as a directed graph, and for each measurement, an edge points from the taller student to the shorter student. We can run BFS or DFS on the graph, and if there exists a path from one student to another, than the first student is taller than the second. Then, we run BFS or DFS again but reversed to find if the first student is shorter. If none of these two cases result, then there's not enough information.

My C++ solution (BFS) is shown below.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int n, m; 
    cin >> n >> m;
    vector<vector<int>> adj (n+1);


    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(b);

    }

    vector<int> current;
    vector<int> next;
    vector<bool> visited (n+1);

    cin >> a >> b;

    current.push_back(a);
    visited[a] = true;

    bool found = false;
    while(!found and current.size() > 0){
        for(auto x : current){
            for(auto y : adj[x]){
                if(!visited[y]){
                    next.push_back(y);
                }
                if(y == b){
                    found = true;
                    break;
                }
            }
            visited[x] = true;
        }
        current = next;
        next.clear();
    }

    if(found){
        cout << "yes" << endl;
    }
    else{
        current.clear();
        next.clear();
        vector<bool> temp (n+1);
        visited = temp;


        current.push_back(b);

        visited[b] = true;



        while(!found and current.size() > 0){
            for(auto x : current){
                for(auto y : adj[x]){
                    if(!visited[y]){
                        next.push_back(y);
                    }
                    if(y == a){
                        found = true;
                        break;
                    }
                }
                visited[x] = true;
            }
            current = next;
            next.clear();
        }

        if(found){
            cout << "no" << endl;
        }
        else{
            cout << "unknown" << endl;
        }

    }


}
                

You and your friend have come up with a way to send messages back and forth. Your friend can encode a message to you by writing down a positive integer 𝑁 and a symbol. You can decode that message by writing out that symbol 𝑁 times in a row on one line. Given a message that your friend has encoded, decode it.

Input Specification

The first line of input contains 𝐿, the number of lines in the message.

The next 𝐿 lines each contain one positive integer less than 80, followed by one space, followed by a (non-space) character.

Output Specification

The output should be 𝐿 lines long. Each line should contain the decoding of the corresponding line of the input. Specifically, if line 𝑖+1 of the input contained 𝑁 x, then line 𝑖 of the output should contain just the character x printed 𝑁 times.

Sample Input

4
9 +
3 -
12 A
2 X

Sample Output

+++++++++
---
AAAAAAAAAAAA
XX

This problem was the second question from the 2019 Junior CCC competition. You can visit that question on the CCC Grader to grade your own solution.

My Python Solution is shown below.

a = int(input(""))
for i in range(a):
    n, c = input("").split()
    n = int(n)
    s = ""
    for j in range(n):
        s = s + c  //makes string s contain n characters c. You can actually write s = n*c in python, but 
                   //similar functionality may not be available in other languages. 
    print(s)
                    

This week, we look at graph theory, particularly the Breadth-First Search (BFS) Algorithm.

There is a genre of fiction called choose your own adventure books. These books allow the reader to make choices for the characters which alters the outcome of the story. For example, after reading the first page of a book, the reader may be asked a choice, such as "Do you pick up the rock?" If the reader answers "yes", they are directed to continue reading on page 47, and if they choose "no", they are directed to continue reading on page 18. On each of those pages, they have further choices, and so on, throughout the book. Some pages do not have any choices, and thus these are the "ending" pages of that version of the story. There may be many such ending pages in the book, some of which are good (e.g., the hero finds treasure) and others which are not (e.g., the hero finds a leftover sandwich from 2001).

You are the editor of one of these books, and you must examine two features of the choose your own adventure book:

1. Ensure that every page can be reached – otherwise, there is no reason to pay to print a page which no one can ever read;
2. Find the shortest path, so that readers will know what the shortest amount of time they need to finish one version of the story.

Given a description of the book, examine these two features.

Input Specification

The first line of input contains 𝑁 (1 ≤ 𝑁 ≤ 10000), the number of pages in the book. Each of the next 𝑁 lines contain an integer 𝑀𝑖 (1 ≤ 𝑖 ≤ 𝑁; 0 ≤ 𝑀𝑖 ≤ 𝑁), which is the number of different options from page 𝑖, followed by 𝑀𝑖 space-separated integers in the range from 1 to 𝑁, corresponding to each of the pages to go to next from page 𝑖. It will also be the case 𝑀₁ + 𝑀₂ + ⋯ + 𝑀_N is at most 10000.

Output Specification

The output will be two lines. The first line will contain Y if all pages are reachable, and N otherwise. The last line will contain a non-negative integer 𝐾, which is the shortest path a reader can take while reading this book. There will always be a finite shortest path.

Sample Input

3
2 2 3
0
1 1
                

Sample Output

Y
2

Explanation of Sample Output

Every page is reachable, since from page 1, we can reach pages 2 and 3. The shortest path is the path 1→2, which contains two pages.

This problem was the fifth question from the 2018 Junior CCC competition. You can visit that problem page on the CCC Grader to grade your own solution.

My C++ solution (BFS) is shown below.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int n; cin >> n;
    vector<vector<int>> adj; // stores adjacency list of graph
    adj.push_back({}); // to simplify, we correct the index numbers so they match the page numbers

    vector<int> zeros;

    int m0, mj;
    for(int i = 1; i <= n; i++){
        cin >> m0;
        adj.push_back({});
        if(m0 == 0){
            zeros.push_back(i);
        }
        for(int j = 0; j < m0; j++){
            cin >> mj;
            adj[i].push_back(mj);
        }
    }

    vector<int> visited (n+1);
    visited[0] = 1;
    visited[1] = 1;

    vector<int> current; //current and next will be used for the BFS
    vector<int> next;

    current.push_back(1);
    int distance = 2;

    while(!current.empty()){ //Main BFS algorithm is here. Learn the BFS algorithm at:
                // https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
        for(auto page : current){
            for(auto nextPage : adj[page]){
                if(visited[nextPage] == 0){
                    next.push_back(nextPage);
                    visited[nextPage] = distance;
                }
            }
        }
        distance += 1;
        current = next;
        next.clear();
    }

    bool allVisited = true; // Check whether all pages are visited
    for(int i = 1; i <= n; i++){
        if(visited[i] == 0){
            allVisited = false;
            break;
        }
    }

    int shortestPath = 2147000000;
    for(auto endPage : zeros){ // Look through all ending pages for the shortest path.
        if(visited[endPage] != 0){
            shortestPath = min(shortestPath, visited[endPage]);
        }
        
    }

    if(allVisited){
        cout << "Y" << endl;
    }
    else{
        cout << "N" << endl;
    }

    cout << shortestPath << endl;

}
                

Magic Squares are square arrays of numbers that have the interesting property that the numbers in each column, and in each row, all add up to the same total.

Given a 4×4 square of numbers, determine if it is magic square.

Input Specification

The input consists of four lines, each line having 4 space-separated integers.

Output Specification

Output either magic if the input is a magic square, or not magic if the input is not a magic square.

Sample Input

16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1

Sample Output

magic

Explanation for Sample Output

Notice that each row adds up to 34, and each column also adds up to 34.

This problem was the second question from the 2016 Junior CCC competition. Visit that page on the CCC Grader to grade your own solution.

A Java solution by Mr. Miskew is shown below.

import java.util.Scanner;
/*
    * https://cemc.uwaterloo.ca/contests/computing/2016/stage%201/juniorEn.pdf
*/

public class CCCJ2MagicSquare {

    public static void main(String[] args) {
        
        System.out.println(magicSquares());
    }
    
    public static String magicSquares() {
        
        //int[][] arr = {{16, 3, 2, 13}, {5, 10, 11, 8}, {9, 6, 7, 12}, {4, 15, 14, 1}};
        int[][] arr = {{5, 10, 1, 3}, {10, 4, 2, 3}, {1, 2, 8, 5}, {3, 3, 5, 0}};
            
        Scanner s = new Scanner(System.in);
        
        //for (int r = 0; r < 4; r = r + 1) 
        //	for (int c = 0; c < 4; c = c + 1)
        //		arr[r][c] = s.nextInt();
        
        int total = arr[0][0] + arr[0][1] + arr[0][2] + arr[0][3];
        
        //Check row sums
        for (int r = 1; r < 4; r = r + 1) {
            
            int t = 0;
            for (int c = 0; c < 4; c = c + 1)
                t = t + arr[r][c];
            
            if (t != total)
                return "not magic";
        }
        
        //Check column sums
        for (int c = 0; c < 4; c = c + 1) {
            
            int t = 0;
            for (int r = 0; r < 4; r = r + 1)
                t = t + arr[r][c];
            if (t != total)
                return "not magic";
        }
        
        return "magic";
    }
}
                    

In the country of Voronoi, there are N villages, located at distinct points on a straight road. Each of these villages will be represented by an integer position along this road. Each village defines its neighbourhood as all points along the road which are closer to it than to any other village. A point which is equally close to two distinct villages A and B is in the neighbourhood of A and also in the neighbourhood of B. Each neighbourhood has a size which is the difference between the minimum (leftmost) point in its neighbourhood and the maximum (rightmost) point in its neighbourhood. The neighbourhoods of the leftmost and rightmost villages are defined to be of infinite size, while all other neighbourhoods are finite in size. Determine the smallest size of any of the neighbourhoods (with exactly 1 digit after the decimal point).

Input Specification

The first line will contain the number N (3≤N≤100), the number of villages. On the next N lines there will be one integer per line, where the ith line contains the integer V_i , the position of the i^th village (−1000000000≤V_i≤1000000000). All villages are at distinct positions.

Output Specification

Output the smallest neighbourhood size with exactly one digit after the decimal point.

Sample Input

5
16
0
10
4
15

Sample Output

3.0

Explanation of Sample Output

The neighbourhoods around 0 and 16 are infinite. The neighbourhood around 4 is 5 units (2 to the left, and 3 to the right). The neighbourhood around 10 is 5.5 units (3 to the left and 2.5 to the right). The neighbourhood around 15 is 3.0 units (2.5 to the left and 0.5 to the right).

This problem was the first question from the 2018 Senior CCC competition. Visit that page on the CCC Grader to score your own solution.

My C++ solution is shown and annotated below.

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

    int num;
    cin >> num;  //number of towns

    cout << fixed;
    
    double towns [num];  // locations of towns (we need this to be a double to avoid
                                        //      automatic conversion to integer values
                                        //      when processing the point between
                                        //      towns, where a decimal may be produced)
    for(int i=0; i < num; i++){
        int k = 0; cin >> k;    // inputs locations of towns and stores in array
        towns[i]=k;
    }
    
    sort(towns, towns + num);  // sort the locations of the towns for easier processing
    
    double smallest = 2000000001.0;// stores the smallest neighbourhood found so far.
                                   // We set this to a number greater than the max possible
                                   // for this problem, so we can easily replace it by the smaller
                                   // value when one is found using min().
                                  
                                 
    for(int i = 1; i < num-1; i++){ // Loop over all towns with non-infinite neighbourhoods
        double neighbourhoodSize = 0; 
        neighbourhoodSize += (towns[i] - towns[i-1])/2; // add left half of neighbourhood
        neighbourhoodSize += (towns[i+1] - towns[i])/2; // add right half of neighbourhood
        
        smallest = min(neighbourhoodSize, smallest);// if we've found a smaller neighbourhood,
                                                    // store that neighbourhood size as new smallest
    }

    cout << setprecision(1) << fixed; // round output to 1 decimal place
    cout << smallest << endl; // output answer
    
}
                    

Here's a straightforward warmup question so we can get back into things:

A vote is held after singer A and singer B compete in the final round of a singing competition. Your job is to count the votes and determine the outcome.

Input Specification

The input will be two lines. The first line will contain V (1 ≤ V ≤ 15), the total number of votes. The second line of input will be a sequence of V characters, each of which will be A or B, representing the votes for a particular singer.

Output Specification

The output will be one of three possibilities: A, if there are more A votes than B votes, B if there are more B votes than A votes, and Tie if there is an equal number of A and B votes.

Sample Input

6
ABBABB

Sample Output

B

This problem was the second question from the 2014 Junior CCC competition. Visit that page on the CCC Grader to score your own solution.

My python 3 solution is shown below.

length = int(input(""))
    a = 0
    b = 0
    votes = input("")
    for i in range(len(votes)):
        if votes[i] == 'A':
            a += 1
    b = length - a
    if a > b:
        print("A")
    elif b > a:
        print("B")
    else:
        print("Tie")
                    

You are hosting a party and do not have room to invite all of your friends. You use the following unemotional mathematical method to determine which friends to invite.

Number your friends 1,2,…,K and place them in a list in this order. Then perform m rounds. In each round, use a number to determine which friends to remove from the ordered list.

The rounds will use numbers r₁,r₂,…,r_m. In round i, remove all the remaining people in positions that are multiples of r_i (that is, r_i,2r_i,3r_i,…) The beginning of the list is position 1.

Please output the numbers of the friends that remain after this removal process.

Input Specification

The first line of input contains the integer K (1 ≤ K ≤ 100). The second line of input contains the integer m (1 ≤ m ≤ 10), which is the number of rounds of removal. The next m lines each contain one integer. The i^th of these lines (1 ≤ i ≤ m) contains r_i (2 ≤ ri ≤ 100) indicating that every person at a position which is multiple of r_i should be removed.

Output Specification

The output will be the list of people still invited, one person per line, in increasing order.

Sample Input

10
2
2
3

Sample Output

1
3
7
9

Explanation of Sample Output

Initially, our list of invitees is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. There will be two rounds of removals. After the first round of removals, we remove the even positions (i.e., every second position), which causes our list of invitees to be {1, 3, 5, 7, 9}. After the second round of removals, we remove every 3rd remaining invitee: thus, we keep 1 and 3, remove 5 and keep 7 and 9, which leaves us with an invitee list of {1, 3, 7, 9}.

This problem was the first question from the 2014 Senior CCC competition. Visit that page on the CCC Grader to score your own solution.

My C++ solution is shown below.

#include <iostream>

int main() {

    using namespace std;
    int K = 0;   // n = number of friends
    cin >> K;
    
    int m = 0;   // m = number of rounds
    cin >> m;
    
    int round [m];   // stores rounds to remove
    
    for(int i = 0; i < m; i++){
        cin >> round[i];
    }
    
    int tests [K];   // stores the status of friends
    
    for(int i = 0; i < K; i++){
        
        tests[i] = 1;  // start by marking friends 1 for all invited
        
    }
    
    for(int i = 0; i < m; i++){  // repeat the following for all of the removal rounds
        int counter = 0;                // start a counter at zero
        for(int k = 0; k < K; k++){
            if(tests[k] != 0){              // If the friend hasn't been removed already,
                counter += 1;               // Increment the counter by 1
                if(counter%round[i] == 0){  // If counter is divisible by desired multiple,
                    tests[k] = 0;           // Remove the friend by marking him 0
                }
            }
        }
    }
    
    for(int i = 0; i < K; i++){
        if(tests[i] != 0){
            cout << i+1 << endl;  // Print all the friends still invited
        }
    }
}