Johnny designed a magic square (square of numbers with the same sum for all rows, columns and diagonals i.e. both the main diagonal – meaning the diagonal that leads from the top-left corner towards bottom-right corner – and the antidiagonal – meaning the diagonal that leads from top-right corner towards bottom-left corner). Write a program to test it.
Write a program that will check if the given square is magic (i.e. has the same sum for all rows, columns and diagonals).
Continue reading “Magic Square – IEEXtreme 8.0”
Minka is very smart kid who recently started learning computer programming.
His coach gave him a cyclic array A having N numbers, and he has to perform Q operations on this array.
In each operation the coach would provide him with a number X. After each operation, every element of the cyclic array would be replaced by the sum of itself and the element lying X positions behind it in the cyclic array. All these replacements take place simultaneously.
For example, if the cyclic array was [a, b, c, d], then after the operation with X = 1, the new array would be [a+d, b+a, c+b, d+c].
He needs to output the sum of the elements of the final array modulus 10^9+7.
He made a program for it but it’s not very efficient. You know he is a beginner, so he wants you to make an efficient program for this task because he doesn’t want to disappoint his coach.
Continue reading “Sum It Up – IEEXtreme 8.0”
The game “Back to Square 1” is played on a board that has n squares in a row and n-1 probabilities. Players take turns playing. On their first turn, a player advances to square 1.After the first turn, if a player is on square i , the player advances to square i + 1 with probability p(i) , and returns to square 1 with probability 1-p(i) .The player is finished upon reaching square n .
Write a program that determines the expected number of turns needed for a player to reach the final square.For example, consider the board below with n = 3 and p(1) = 0.5 and p(2) = 0.25. A player moves to square 1 on their first turn. With probability p(1) , they move to square 2 on their second turn, but with probability 1- p(1) , they remain on square 1. If they were lucky and made it to square 2 on their second turn, they advance to square 3 on their third turn with probability p(2) , but they would go back to square 1 with probability 1- p(2) . Thus, a really lucky player could finish is 3 turns. However, on average, it would take 13 turns for a player to make it to square 3.
Continue reading “Back to Square 1 – IEEEXtreme 8.0”
Recurrence relations are an important tool for the computer scientist. Many algorithms, particularly those that use divide and conquer, have time complexities best modeled by recurrence relations. A recurrence relation allows us to recursively define a sequence of values by defining the nth value in terms of certain of its predecessors.
Many natural functions, such as factorials and the Fibonacci sequence, can easily be expressed as recurrences. The function of interest for this problem is described below.
Let |An| denote the number of digits in the decimal representation of An. Given any numberA0, we define a sequence using the following recurrence:
Ai = |Ai-1| for i > 0
The goal of this problem is to determine the smallest positive i such that Ai = Ai-1.
Continue reading “Digit Fun! – IEEEXtreme 9.0”