Paving the Way to Competitive Programming Nov 06, 2024
Problem A. Coins Time limit 2000 ms Mem limit 262144 kB
In Berland, there are two types of coins, having denominations of 2 and k burles.
Your task is to determine whether it is possible to represent n burles in coins, i. e. whether
there exist non-negative integers x and y such that 2 ⋅ x + k ⋅ y = n.
Input
The first line contains a single integer t (1 ≤ t ≤ 104 ) — the number of test cases.
The only line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 1018 ; k = 2).
Output
For each test case, print YES if it is possible to represent n burles in coins; otherwise, print NO. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).
Examples Input Output
4 YES 5 3 YES 6 1 NO 7 4 YES 8 8
Note
In the first test case, you can take one coin with denomination 2 and one coin with denomination k = 3.
In the second test case, you can take three coins with denomination 2. Alternatively, you can take six coins with denomination k = 1.
In the third test case, there is no way to represent 7 burles.
Page 1 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
In the fourth test case, you can take one coin with denomination k = 8.
Page 2 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
Problem B. Full Pyramid
Time limit 1000 ms Mem limit 524288 kB
Given an integer N , print a full pyramid of asterisks.
A full pyramid of asterisks of size N has N lines of asterisks. The first line has 1 asterisk, the second line has 2 asterisks, the third line has 3 asterisks and so on. Each asterisk has a space between them. The asterisks in each line are centered to make it look like a pyramid.
Here is a full pyramid of asterisks of size 4:
1 * 2 * * 3 * * * 4 * * * *
Input The input will contain an integer N (1 ≤ N ≤ 100).
Output Print the full pyramid of asterisks of the given size.
Do not print any space after the last asterisk in each line.
Sample
Input Output
3 * * * * * *
Page 3 of 13 - Mr. Bean used to have a lot of problems packing his suitcase for holiday. So he is very careful for this coming holiday. He is more serious this time because he is going to meet his fiance and he is also keeping frequent communication with you as a programmer friend to have suggestions. He gets confused when he buys a gift box for his fiance because he can’t decide whether it will fit in his suitcase or not. Sometimes a box doesn’t fit in his suitcase in one orientation and after rotating the box to a different orientation it fits in the suitcase. This type of behavior makes him puzzled. So to make things much simpler he bought another suitcase having same length, width and height, which is 20 inches. This measurement is taken from inside of the box. So a box which has length, width and height of 20 inches will just fit in this suitcase. He also decided to buy only rectangular shaped boxes and keep a measuring tape in his pocket. Whenever he chooses one gift box, which must be rectangular shaped, he quickly measures the length, width and height of the box. But still he can’t decide whether it will fit in his suitcase or not. Now he needs your help. Please write a program for him which calculates whether a rectangular box fits in his suitcase or not provided the length, width and height of the box. Note that, sides of the box must be parallel to the sides of the suitcase.
Input Input starts with an integer T (T ≤ 100), which indicates the number of test cases. Each of the next T line contains three integers L, W and H (1 ≤ L, W, H ≤ 50) denoting the length, width and height of a rectangular shaped box.
Output For each test case, output a single line. If the box fits in the suitcase in any orientation having the sides of the box is parallel to the sides of the suitcase, this line will be ‘Case #: good’, otherwise it will be ‘Case #: bad’. In your output # will be replaced by the case number. Please see the sample input and sample output for exact format.
Sample Input 2 20 20 20 1 2 21
Sample Output Case 1: good Case 2: bad Paving the Way to Competitive Programming Nov 06, 2024
Problem D. Jump Year
Time limit 1000 ms Mem limit 262144 kB
Description
You live on a weird planet inside a weird galaxy. A year x on that planet is a jump year if and only if at least one of the following conditions is satisfied:
x is divisible by A, but is not divisible by B .
x is divisible by C .
Given four integers N , A, B , and C . Determine whether year N on that planet is a jump year or not!
Constraints
1 ≤ N , A, B, C ≤ 200 000
Input
N A B C
Output
One line containing YES if year N on that planet is a jump year, or NO otherwise.
Sample
Input Output
132 11 13 7 YES
Explanation of Sample 1
Year 132 is a jump year because it is divisible by 11 and is not divisible by 13.
Sample
Input Output
60 6 4 9 NO
Sample Page 5 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
Input Output
2000 4 100 400 YES
Explanation of Sample 3
Year 2000 is a jump year because it is divisible by 400.
Sample
Input Output
30 3 4 5 YES
Page 6 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
Problem E. Taxi Time limit 3000 ms Mem limit 262144 kB Input file stdin Output file stdout
After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are
separated by a space, si is the number of children in the i-th group.
Output
Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.
Examples Input Output
5 4 1 2 4 3 3
Input Output
8 5 2 3 4 4 2 1 3 1
Note Page 7 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
In the first test we can sort the children into four cars like this:
the third group (consisting of four children),
the fourth group (consisting of three children), the fifth group (consisting of three children), the first and the second group (consisting of one and two children, correspondingly).
There are other ways to sort the groups into four cars.
Page 8 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
Problem F. Strong Passwords
Time limit 1000 ms Mem limit 262144 kB
Mitu had been using the
password mitu1997qt on all her online accounts. And sure enough, her accounts got hacked. She has come crying to you. But you are merely a privacy enthusiast, not a hacker yourself to hack her accounts back. All you can do is suggest her a strong password, so that her new accounts do not get hacked.
By your definition, a strong password should be no lesser than 12 characters. And, for ease- of-use, passwords should not be longer than 24 characters. In a strong password, there should be at least 1 lowercase ASCII letter (a,b,..,z), at least 1 uppercase ASCII letter (A,B,..,Z), at least 2 ASCII digits (0,1,..,9) and at least 2 special characters from these six &!@._% ASCII special characters. There should be no other characters in the password, other than lowercase and uppercase ASCII letters, ASCII digits and the six mentioned ASCII special characters. There should definitely not be any spaces in the password.
Page 9 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
For example, Mitu@1997 is not a strong password because the length is only 9 and there is only one special character. &strongpassword! is also not a strong password because there is no uppercase letter in there, nor any digits.
Will you please suggest Mitu a strong password?
Input There is no input for this problem.
Output Output a single line containing the password.
The password should be no lesser than 12 characters and no more than 24 characters. And the password must be strong as per the definition stated above.
Page 10 of 13 - Some operators checks about the relationship between two values and these operators are called rela- tional operators. Given two numerical values your job is just to find out the relationship between them that is (i) First one is greater than the second (ii) First one is less than the second or (iii) First and second one is equal.
Input First line of the input file is an integer t (t < 15) which denotes how many sets of inputs are there. Each of the next t lines contain two integers a and b (|a|, |b| < 1000000001).
Output For each line of input produce one line of output. This line contains any one of the relational operators ‘>’, ‘<’ or ‘=’, which indicates the relation that is appropriate for the given two numbers.
Sample Input 3 10 20 20 10 10 10
Sample Output < > = Paving the Way to Competitive Programming Nov 06, 2024
Problem H. Distinct Numbers
Time limit 1000 ms Mem limit 524288 kB
You are given a list of n integers, and your task is to calculate the number of distinct values in the list.
Input
The first input line has an integer n: the number of values.
The second line has n integers x1 , x2 , … , xn .
Output
Print one integers: the number of distinct values.
Constraints
1 ≤ n ≤ 2 ⋅ 105 1 ≤ xi ≤ 109
Example
Input Output
5 2 2 3 2 2 3
Page 12 of 13 - Paving the Way to Competitive Programming Nov 06, 2024
Problem I. Again Twenty Five!
Time limit 500 ms Mem limit 65536 kB
The HR manager was disappointed again. The last applicant failed the interview the same way as 24 previous ones. "Do I give such a hard task?" — the HR manager thought. "Just raise number 5 to the power of n and get last two digits of the number. Yes, of course, n can be rather big, and one cannot find the power using a calculator, but we need people who are able to think, not just follow the instructions."
Could you pass the interview in the machine vision company in IT City?
Input
The only line of the input contains a single integer n (2 ≤ n ≤ 2·10
18) — the power in which
you need to raise number 5.
Output
Output the last two digits of 5n without spaces between them.
