Telerik Software Academy
Problem 1 – Ship Damage
Inside the sea (a standard Cartesian /rectangular/
coordinate system) we are given a ship S
(a rectangle whose sides are parallel to the coordinate axes), a
horizontal line H (the horizon) and
three catapults, given as coordinates C1,
C2 and C3 that will be used to fire
the ship. When the attack starts, each catapult hits a projectile exactly into
the positions that are symmetrical to C1,
C2 and C3 with respect to the horizon
H. When a projectile hits some of
the corners of the ship, it causes a damage of 25%, when it hits some of the
sides of the ship, the damage caused is 50% and when it hits the internal body
of the ship, the damage is 100%. When the projectile hit outside of the ship,
there is no damage. The total damage is sum of the separate damages and can
exceed 100%.
At the figure below a sea, a ship S, a line H, three points C1,
C2 and C3 and their hit positions
are shown:
Your task is to write a program that
calculates the total damage caused after the attack over the ship.
Input
The input data should be read from the
console.
There will be exactly 11 lines holding the integer numbers SX1, SY1,
SX2, SY2, H, CX1, CY1, CX2,
CY2, CX3, and CY3. The ship S
is given by any two of its opposite corners and is non-empty (has positive
width and height). The line H is
given by its vertical offset. The points C1, C2
and C3 are given as couples of coordinates and cannot overap
each other.
The input data will always be valid and in
the format described. There is no need to check it explicitly.
Output
The output data should be printed on the
console.
The output should consist of a single line
holding the total damage given as percentage.
Constraints
·
The numbers SX1, SY1, SX2,
SY2, H, CX1, CY1, CX2, CY2,
CX3, and CY3 are all integers between
-100 000 and 100 000, inclusive.
·
Allowed work time for your program: 0.1 seconds.
·
Allowed memory: 16 MB.
Examples
Input
|
Output
|
Input
|
Output
|
|
-11
6
-6
3
1
-9
-3
-12
-4
-6
-1
|
125%
|
-6
6
-11
3
1
-9
-4
-11
-1
2
2
|
75%
|
using System; class ShipDamage { static void Main() { int sX1 = int.Parse(Console.ReadLine()); int sY1 = int.Parse(Console.ReadLine()); int sX2 = int.Parse(Console.ReadLine()); int sY2 = int.Parse(Console.ReadLine()); if (sX1 > sX2) { int temp = sX2; sX2 = sX1; sX1 = temp; } if (sY1 > sY2) { int temp = sY2; sY2 = sY1; sY1 = temp; } int h = int.Parse(Console.ReadLine()); int hits = 0; int[,] cPoints = new int [3,2]; for (int i = 0; i < 3; i++) { cPoints[i, 0] = int.Parse(Console.ReadLine()); cPoints[i, 1] = int.Parse(Console.ReadLine()); cPoints[i, 1] = h + (h - cPoints[i, 1]); if ((cPoints[i, 0] == sX1) || (cPoints[i, 0] == sX2)) { if ((cPoints[i, 1] == sY1) || (cPoints[i, 1] == sY2)) { hits += 25; } else if ((cPoints[i, 1] > sY1) && (cPoints[i, 1] < sY2)) { hits += 50; } } else if ((cPoints[i, 0] > sX1) && (cPoints[i, 0] < sX2)) { if ((cPoints[i, 1] == sY1) || (cPoints[i, 1] == sY2)) { hits += 50; } else if ((cPoints[i, 1] > sY1) && (cPoints[i, 1] < sY2)) { hits += 100; } } } Console.WriteLine("{0}%", hits); } }
Problem 2 – Tribonacci
The Tribonacci sequence is a sequence in
which every next element is made by the sum of the previous three elements from
the sequence.
Write a computer program that finds the Nth element of the
Tribonacci sequence, if you are given the first three elements of the sequence
and the number N. Mathematically
said: with given T1, T2 and T3 – you must find
Tn.
Input
The input data should be read from the
console.
The values of the first three Tribonacci
elements will be given on the first three input lines.
The number N will be on the fourth line. This is the number of the consecutive
element of the sequence that must be found by your program.
The input data will always be valid and in
the format described. There is no need to check it explicitly.
Output
The output data should be printed on the
console.
At the only output line you must print the Nth element of the given
Tribonacci sequence.
Constraints
·
The values of the first three
elements of the sequence will be integers between -2 000 000 000 and 2 000 000
000.
·
The number N will be a positive integer between 1 and 15 000, inclusive.
·
Allowed working time for your program: 0.25 seconds.
·
Allowed memory: 16 MB.
Examples
Input example
|
Output example
|
1
1
1
4
|
3
|
2
3
4
10
|
335
|
using System; using System.Numerics; class Tribonacci { static void Main() { BigInteger firstElement = BigInteger.Parse(Console.ReadLine()); BigInteger secondElement = BigInteger.Parse(Console.ReadLine()); BigInteger thirdElement = BigInteger.Parse(Console.ReadLine()); int n = int.Parse(Console.ReadLine()); BigInteger temp = 0; for (int i = 0; i < n - 3; i++) { temp = thirdElement; thirdElement += firstElement + secondElement; firstElement = secondElement; secondElement = temp; } Console.WriteLine(thirdElement); } }
Problem 3 – Fir Tree
Christmas Eve is coming so even programmers
got to prepare!
In the spirit of the event your task is to
write a program that prints a fir tree to the console.
The format of the tree is shown in the
examples bellow.
Input
The input data should be read from the
console.
On the only input line you have an integer
number N, showing the height of the
tree.
The input data will always be valid and in
the format described. There is no need to check it explicitly.
Output
The output data should be printed on the
console.
You must print the fir tree on the console.
Each row contains only characters "." (point) or "*" (asterisk).
The first row should have exactly one
"*" in the middle (that is the top of the tree) and each of the next lines
two more.
The last line should have exactly one
asterisk in the middle, showing the stem of the tree.
Constraints
·
The number N is a positive integer between 4 and 100, inclusive.
·
Allowed working time for your program: 0.25 seconds.
·
Allowed memory: 16 MB.
Examples
Input example
|
Output example
|
5
|
...*...
..***..
.*****.
*******
...*...
|
9
|
.......*.......
......***......
.....*****.....
....*******....
...*********...
..***********..
.*************.
***************
.......*.......
|
using System; class FirTree { static void Main() { int n = int.Parse(Console.ReadLine()); for (int i = 0; i < n-1; i++) { Console.Write(new String ('.', n - i - 2)); Console.Write(new String ('*', i*2 + 1)); Console.WriteLine(new String('.', n - i - 2)); } Console.Write(new String('.', n - 2)); Console.Write("*"); Console.WriteLine(new String('.', n - 2)); } }
Problem 4 – We All Love Bits!
One of the things the programmers love the
most is bitwise operations. The "bitwise guy" is a synonym for a
programmer that loves bits more than everything else in programming. Mitko is a
"bitwise guy". He invented a new bitwise algorithm. The algorithm
takes one positive integer number P,
makes magic with it and returns a new positive integer number. He also defined
a new number P̃ which represents the number P in binary numeral system with
inverted bits. All zeros in P are
ones in P̃ and all ones in P are zeros in P̃. For example if we have P = 9 (which is 1001 in
binary numeral system) its inverted number P̃ will be equal to 6 (which is 110
in binary numeral system). But that’s not all! He invented another number P̈, which represents reversed number P in binary numeral system. For example
if we have P = 11 (which is 1011 in binary numeral system) its reversed number P̈
is equal to 13 (which is 1101 in binary numeral system). The Mitko's magical
algorithm takes a number P and
transforms it to a new number Pnew
using the following bitwise transformation: Pnew = (P ^ P̃) & P̈.
Your
task is to write a program that transforms a sequence of N positive integer numbers using Mitko's algorithm.
Input
The input data should be read from the
console.
At the first input line there will be one positive
integer – the number N.
At each of the next N lines there will be one positive integer – the consequent number
that must be converted using Mitko's algorithm.
The input data will always be valid and in
the format described. There is no need to check it explicitly.
Output
The output data should be printed on the
console.
The output must consist of N lines, containing the transformed
numbers for each number from the input.
Constraints
·
The number N will be positive integer number between 1 and 20 000, inclusive.
·
Each of the N numbers will be positive integer
numbers between 1 and 2 147 483 647, inclusive.
·
Allowed working time for your program: 0.20 seconds.
·
Allowed memory: 16 MB.
Examples
Input example
|
Output example
|
1
2
|
1
|
2
19
248
|
25
31
|
using System; using System.Text; class WeAllLoveBits { static void Main() { int n = int.Parse(Console.ReadLine()); int p1 = 0; int p2 = 0; int [] pResults = new int [n]; for (int i = 0; i < n; i++) { pResults[i] = int.Parse(Console.ReadLine()); p2 = 0; long level = 1; int maskOfOnes = 1; int pShifted = pResults[i]; while (pResults[i] >= level) { maskOfOnes = (maskOfOnes << 1) | 1; p2 = (p2<<1) | (pShifted & 1); pShifted >>= 1; level <<= 1; } p1 = (~pResults[i]) & maskOfOnes; pResults[i] = (pResults[i] ^ p1) & p2; } for (int i = 0; i < n; i++) { Console.WriteLine(pResults[i]); } } }
Problem 5 – Pillars
You are given a list
of 8 bytes (positive integers in the
range [0…255]) n0, n1, …, n7. These numbers represent a square grid
consisting of 8 lines and 8 columns. Each cell of the grid could
either be empty or full. The first line is represented by the bits of n0, the second – by the bits
of n1 and so on, and the
last line is represented by the bits of n7.
Each bit with value 1 denotes a full cell and each bit with value 0 denotes an
empty cell. The lines are numbered from the first (top) to the last (bottom)
with the numbers 0, 1, …, 7. The columns
are numbered from right to left with the indices 0, 1, …, 7. The figure shows a square grid and its representation
by a sequence of 8 numbers n0, n1, …, n7:
7
|
6
|
5
|
4
|
3
|
2
|
1
|
0
|
||
0
|
n0 = 0
|
||||||||
1
|
■
|
n1 = 64
|
|||||||
2
|
n2 = 0
|
||||||||
3
|
■
|
n3 = 8
|
|||||||
4
|
n4 = 0
|
||||||||
5
|
■
|
■
|
n5 = 12
|
||||||
6
|
■
|
■
|
■
|
n6 = 224
|
|||||
7
|
n7 = 0
|
We are allowed to put a vertical pillar
over any of the columns in the grid. Pillars split the grid into two sides
(left and right) and the column holding the pillar is ignored. Write a program that
finds the leftmost column where the pillar can be put so that the full cells on
the left side and on the right side are equal number. For example at the figure
if we put the pillar at column 5, it will split the grid into two sides and
both sides will have exactly 3 full cells.
Input
The input data should be read from the
console.
There will be exactly 8 lines each holding
the integer numbers n0, n1, …, n7.
The input data will always be valid and in
the format described. There is no need to check it explicitly.
Output
The output data should be printed on the
console.
If a pillar splitting the grid into two
vertical sides each holding the same number of full cells exists, print its column
index on the first line and the number of full cells in each of the sides. If
multiple pillars can do the job, print only the leftmost. If no such pillar exists,
print the string "No" on the console (just one line holding the word
"No").
Constraints
·
The numbers n0, n1,
…, n7 are positive
integers in the range [0…255].
·
Allowed work time for your program: 0.25 seconds.
·
Allowed memory: 16 MB.
Examples
Input Example
|
Output Example
|
0
64
0
8
0
12
224
0
|
5
3
|
3
0
0
0
0
0
0
0
|
No
|
using System; class Pillars { static void Main() { byte[] rows = new byte[8]; for (int i = 0; i < 8; i++) { rows[i] = byte.Parse(Console.ReadLine()); } ushort leftBytes = 0; ushort rightBytes = 0; sbyte pillar = 7; do { leftBytes = 0; rightBytes = 0; for (int i = 0; i < 8; i++) { byte currentRow = rows[i]; if (currentRow != 0) { for (int j = 0; j < 8; j++) { if (j < pillar) { if ((currentRow & 1) == 1) { rightBytes++; } } else if (j > pillar) { if ((currentRow & 1) == 1) { leftBytes++; } } currentRow >>= 1; } } } pillar--; } while ((pillar >= 0) && (leftBytes != rightBytes)); if (leftBytes == rightBytes) { Console.WriteLine(pillar+1); Console.WriteLine(leftBytes); } else { Console.WriteLine("No"); } } }
Няма коментари:
Публикуване на коментар