9 weeks ago

John 910

Hyderabad

Question 1

The Chernobyl disaster happened on April 26, 1986, at the No. 4 reactor of the Chernobyl Nuclear Power Plant. In terms of both cost and casualties, it is one of the most devastating nuclear disasters in history.

After the tragedy, scientists retrieved a large number of important documents from the site, which contained nuclear power emission data in N rows and M columns. This information represented the powers emitted by N nuclear reactor on an hourly basis during M hours. Because these records were handwritten, scientists intend to scan them using optical character scanners to turn numbers into machine encoded text. However, some of the numbers are illegible owing to catastrophic damage.

Scientists opted to reconstruct the missing data by using the rest of the data from that column. Can you help them with a program that detects the minimum number in a column and replaces it with the document's damaged space that is indicated as -1.

Illustrate this scenario by reading the input from STDIN and the output from STDOUT, Do not write arbitrary strings while reading the input or while printing, as these contribute to the standard output.

Constraints:

1 ≤ N ≤ 10,00,000

-1 represents the damaged space. It should not be considered as minimum value

Input Format:

• The first line of input contains N and M, where N is the number of nuclear reactors and M is the number of hours.
• The next N lines of input contain M integers, each separated by a single white space.

Output Format:

The output of N rows with M integers in row separated by space and replace -1 with the minimum of that column.

Sample Input 1:

 4   4

 2   4   6  -1

-1   4   5   6

 7   5   8   3

 4   3   6   7 

Sample Output 1:

2   4   6   3

2   4   5   6

7   5   8   3

4   3   6   7

Explanation 1:

From the Sample Input 1, we have the following data structure:

Question 2

Harry wants to sell lottery tickets and earn money out of it. In his basic research, he found that most lottery tickets follow some logic in deciding the winning ticket number. He studied many algorithms for the same and finally decided on the algorithm.

Every day he provides 2 numbers as an input to the algorithm which is N and K, where N is the number of prime numbers to be used for the algorithm and K is a single digit odd number,

Algorithm Winning TicketNumber (N.K):

Step 1: Create a list L of first N prime numbers that end with digit K and include 2 and 5 in that list.

Step 2: Find the sum of all the numbers S of L

Step 3: Print the sum S as the winning ticket number for that day.

Please write a program to implement WinningTicketNumber algorithm by accepting N and K values.

Read the input from STDIN and write the output to STDOUT, You should not write arbitrary strings while reading the input and while printing as these contribute to the standard output.

Constraints:

1<N<1000, K=1,3,7,9

Input Format:

The first line of the input contains N and K.

Output Format:

A single line of output consists of sum S which is the winning ticket number for that day.

Sample Input 1:

57

Sample Output 1:

182

Explanation 1:

Here, N=5 So the list will be 2, 5, 7, 17, 37, 47, and 67.

So the sum of all the numbers listed will be 2 5 7 17 37 47 67 = 182 which is printed as the winning ticket number.

Sample Input 2:

103

Sample Output 2:

677

Explanation 2:

Here, N=5, So the list will be  2, 5, 3, 13, 23, 43, 53, 73, 83, 103, 113, and 163.

So the sum of all the numbers listed will be 2 5 3 13 23 43 53 73 83 103 113 163 = 677.

8 months ago

Shikhar Mehrotra 480

Chennai

Q2)
Quick Solution
Since we are given small N <= 1000 . we could just iterate over all the values by fixing the rightmost digit as K and check whether it is prime or not and if it is prime we append that to list only till the list size is less than N and then find the sum of the list + 2 + 5.
To check whether number is prime we could precompute using Sieve of Eratosthenes
Pseudo Code

p=0
while(size of list L is less than N)
{

number=p*10+K
if(number is prime)
{
append number to L
}
p=p+1
}

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 1

Analysis

The problem can be simply solved if we first precompute the minimum value (excluding -1) from each column. We can then iterate through the matrix and then update the value at each damaged position as the minimum value in the column through the precomputed values.

PseudoCode

column_min = [inf]*M
for col from 1 to M:
     for row from 1 to N:
           if(matrix[row][col]!=-1):
                column_min[col]=min(column_min[col],matrix[row][col])

for col from 1 to M:
     for row from 1 to N:
           if(matrix[row][col]==-1):
                matrix
[row][col] = column_min[col]

return matrix