ES242. Data Structures and Algorithms I. Week 01 Lab
ES242. Data Structures and Algorithms I.
Lab 01
Theme: Practice problems to get used to C syntax.
Learn C syntax:
More practice problems:
- Try the first problem in any Codechef/Codeforces contest.
Print all non-negative integers less than or equal to \(N\) in descending order.
Constraints
- \(1 \leq N \leq 100\)
- \(N\) is an integer.
Input
The input is given from Standard Input in the following format:
Output
Print \(X\) lines, where \(X\) is the number of non-negative integers less than or equal to \(N\). For each \(i = 1, 2, \ldots, X\), the \(i\)-th line should contain the \(i\)-th greatest non-negative integer less than or equal to N.
Sample I/O
Sample Input
Expected Output
You are standing at the origin of a number line. You want to make it to a treasure chest at coordinate \(X\).
There is a guard at coordinate \(Y\), who will block you if you encounter him on the way.
However, there is a magic phrase written on a paper which is kept at coordinate \(Z\). If you pick up that paper, then you can whisper the magic phrase to the guard, who will then let you go.
Determine whether you can reach the goal. If you can, find the minimum total distance you need to travel to do so.
Constraints
- \(−1000 \leq X,Y,Z \leq 1000\)
- \(X, Y, Z\) are distinct, and none of them is \(0\).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
If you can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.
Sample I/O
Sample Input
Sample Output
You can go straight to the goal.
Sample Input
Sample Output
The goal is beyond the guard. You can get there by first picking up the magic phrase and then getting past the guard.
Sample Input
Sample Output
Write a simulation for the Game of Trust when played by an always cheat player for R rounds.
Input Format
The first line of the input contains a number T, which is the number of test cases.
The next 2T lines contain T test cases. Each test case is two lines. The first line is the value R and the second line is R space-separated integers. The i-th integer on the second line is 1 if the other player cooperated in the i-th round, and 0 otherwise.
Output Format
For each test case, print two space-separated integers on a new line. The first integer is the total number of coins earned by the always cheat player, while the second integer is the total number of coins earned by the other player. Note that you have to output the net balance. DO NOT output anything else!
Sample I/O
Sample Input
Expected Output
Rock Paper Scissors is a game between two players. Each game contains many rounds; in each round, the players each simultaneously choose one of Rock, Paper, or Scissors using a hand shape. Then, a winner for that round is selected: Rock defeats Scissors, Scissors defeats Paper, and Paper defeats Rock. If both players choose the same shape, the round instead ends in a draw.
You are preparing for your first big RPS match. Someone has tipped you off with a strategy guide against your opponent on the first match, which consists of many rounds. The strategy guide can be interpreted as follows:
- The first column of the i-th row is what your opponent is going to play in the i-th round: A for Rock, B for Paper, and C for Scissors.
- The second column of the i-th row is what you should play in response in the i-th round: X for Rock, Y for Paper, and Z for Scissors.
Winning every time would be suspicious, so the responses must have been carefully chosen.
Your total score is the sum of your scores for each round. The score for a single round is the score for the shape you selected (1 for Rock, 2 for Paper, and 3 for Scissors) plus the score for the outcome of the round (0 if you lost, 3 if the round was a draw, and 6 if you won).
Your task is to calculate the score you would get if you were to follow the strategy guide.
Input Format
The first line of the input is a number N, which is the total number of rounds. The next N lines contain two space separated characters. The first character is one of A or B or C, and the second character is one of X or Y or Z.
Output Format
The output shound be a single integer, your total score across all rounds based on the strategy guide.
Sample I/O
Sample Input
Expected Output
This strategy guide predicts and recommends the following:
- In the first round, your opponent will choose Rock (A), and you should choose Paper (Y). This ends in a win for you with a score of 8 (2 because you chose Paper + 6 because you won).
- In the second round, your opponent will choose Paper (B), and you should choose Rock (X). This ends in a loss for you with a score of 1 (1 + 0).
- The third round is a draw with both players choosing Scissors, giving you a score of 3 + 3 = 6.
In this example, if you were to follow the strategy guide, you would get a total score of 15 (8 + 1 + 6).
\(p(x)\) is a polynomial whose coefficients are either 0 or 1.
You are given the value of \(p(2)\) and a number \(d\).
Return YES if the coefficient of \(x^d\) in \(p(x)\) is 1 and NO otherwise.
Input Format
The first line of the input contains a number T, which is the number of test cases.
The next 2T lines contain T test cases. Each test case is two lines. The first line is the value of p(2) and the second line is the value of d.
It is guaranteed that p(2) will be at most 10^9 and d will be at most the degree of p(x).
Output Format
For each test case, print a single integer on a new line, which is YES or NO depending on if the coefficient of x^d in p(x) is 1 or 0. DO NOT output anything else!
Sample I/O
Sample Input
Expected Output
Watch this video and write a program to validate the mechanics of the card trick shown.
In other words, your program should take as input a sequence of cards, with the promise that the number of red cards is equal to the number of black cards, and then “perform” the trick as shown in the video, and verify that the final claim about the number of red cards in the red pile being equal to the number of black cards in the black pile is, in fact, true.
Implement the Stable Marriage algorithm discussed in class. You can practice on this Codechef problem.