Beautiful Matrix Problem !!!

 PROBLEM 29: Beautiful Matrix

Problem Reference: Codeforces 

You've got a 5 × 5 matrix, consisting of 24 zeroes and a single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the matrix columns by numbers from 1 to 5 from left to right. In one move, you are allowed to apply one of the two following transformations to the matrix:

1. Swap two neighboring matrix rows, that is, rows with indexes i and i + 1 for some integer i (1 ≤ i < 5).
2. Swap two neighboring matrix columns, that is, columns with indexes j and j + 1 for some integer j (1 ≤ j < 5).

You think that a matrix looks beautiful, if the single number one of the matrix is located in its middle (in the cell that is on the intersection of the third row and the third column). Count the minimum number of moves needed to make the matrix beautiful.

Input:

The input consists of five lines, each line contains five integers: the j-th integer in the i-th line of the input represents the element of the matrix that is located on the intersection of the i-th row and the j-th column. It is guaranteed that the matrix consists of 24 zeroes and a single number one.

Output:

Print a single integer — the minimum number of moves needed to make the matrix beautiful.

Solution: 

@author Ajay

1. 
   
2. import java.util.*;
3. public class NewClass {
5. public static void main(String arg[])
6. {
7. Scanner s = new Scanner(System.in);
8. int a[][] = new int[10][10];
9. int t = 0 ,t1 = 0;
10. for(int i = 1 ; i <= 5 ; i++)
11. {
12. for(int j = 1 ; j <= 5 ; j++)
13. {
14. a[i][j] = s.nextInt();
15. }
16. }
18. for(int i = 1 ; i <= 5 ; i++)
19. {
20. for(int j = 1 ; j <= 5 ; j++)
21. {
22. if(a[i][j] == 1)
23. {
24. if(i < 3)
25. t = 3 - i;
26. else
27. t = i - 3;
29. if(j < 3)
30. t1 = 3 - j ;
31. else
32. t1 = j - 3 ;
33. }
34. }
35. }
37. System.out.println(t+t1);
40. }
42. }

The above solution is in java language.

Examples

input

0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

output

3

input

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

output

1

Domino Piling Problem !!!

PROBLEM 28: Domino piling

Problem References: Codeforces 

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

1. Each domino completely covers two squares.

2. No two dominoes overlap.

3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

Input:

In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).

Output:

Output one number — the maximal number of dominoes, which can be placed.

Soution:

1. m , n = input().split()
2. a = (int(m) * int(n)) / 2
3. print(int(a))

The above solution is in python language.

Examples

input

2 4

output

4

input

3 3

output

4

Insomnia cure Problem !!!

 PROBLEM 27: Insomnia cure

Problem reference: Codeforces

«One dragon. Two dragon. Three dragon», — the princess was counting. She had trouble falling asleep, and she got bored of counting lambs when she was nine.

However, just counting dragons was boring as well, so she entertained herself at best she could. Tonight she imagined that all dragons were here to steal her, and she was fighting them off. Every k-th dragon got punched in the face with a frying pan. Every l-th dragon got his tail shut into the balcony door. Every m-th dragon got his paws trampled with sharp heels. Finally, she threatened every n-th dragon to call her mom, and he withdrew in panic.

How many imaginary dragons suffered moral or physical damage tonight, if the princess counted a total of d dragons?

Input:

Input data contains integer numbers k, l, m, n and d, each number in a separate line (1 ≤ k, l, m, n ≤ 10, 1 ≤ d ≤ 105).

Output:

Output the number of damaged dragons.

Solution: 

1. k = int(input())
2. l = int(input())
3. m = int(input())
4. n = int(input())
5. d = int(input())
6. d1 = 0
7. for i in range(1,d+1):
8. if i % k == 0 or i % l == 0 or i % m == 0 or i % n == 0:
9. pass
10. else:
11. d1+=1
13. print(d-d1)

This solution is in python language.

Examples

input

1
2
3
4
12

output

12

input

2
3
4
5
24

output

17

Gravity Flip Problem !!!

 PROBLEM 26: Gravity Flip

Problem reference : Codeforces 

Little Chris is bored during his physics lessons (too easy), so he has built a toy box to keep himself occupied. The box is special, since it has the ability to change gravity.

There are n columns of toy cubes in the box arranged in a line. The i-th column contains ai cubes. At first, the gravity in the box is pulling the cubes downwards. When Chris switches the gravity, it begins to pull all the cubes to the right side of the box. The figure shows the initial and final configurations of the cubes in the box: the cubes that have changed their position are highlighted with orange.

Input:

The first line of input contains an integer n (1 ≤ n ≤ 100), the number of the columns in the box. The next line contains n space-separated integer numbers. The i-th number ai (1 ≤ ai ≤ 100) denotes the number of cubes in the i-th column.

Output:

Output n integer numbers separated by spaces, where the i-th number is the amount of cubes in the i-th column after the gravity switch.

Solution: 

1. n = int(input())
2. l = []
3. l2 = []
4. x = [int(x) for x in input().split()]
5. l.append(x)
6. for i in l:
7. for j in i:
8. l2.append(j)
10. l2.sort()
11. for i in l2:
12. print(i,"",end='')

The above solution is in python language.

Examples

input

4
3 2 1 2

output

1 2 2 3 

input

3
2 3 8

output

2 3 8 

Next Round Problem !!!

 PROBLEM 25: Next Round

Problem Reference : Codeforces 

"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

Input:

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).

Output:

Output the number of participants who advance to the next round.

Solution: 

1. n , k = input().split()
2. b = 0
3. c = [int(x) for x in input().split()]
4. for i in c:
5. if i >= c[int(k)-1] and i > 0 :
6. b = b + 1
8. print(b)

The above solution is in python language.

Examples

input

8 5
10 9 8 7 7 7 5 5

output

6

input

4 2
0 0 0 0

output

0

Team Problem !!!

 PROBLEM 24: Team

Problem Reference : Codeforces 

One day three best friends Petya, Vasya and Tonya decided to form a team and take part in programming contests. Participants are usually offered several problems during programming contests. Long before the start the friends decided that they will implement a problem if at least two of them are sure about the solution. Otherwise, the friends won't write the problem's solution.

This contest offers n problems to the participants. For each problem we know, which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution.

Input:

The first input line contains a single integer n (1 ≤ n ≤ 1000) — the number of problems in the contest. Then n lines contain three integers each, each integer is either 0 or 1. If the first number in the line equals 1, then Petya is sure about the problem's solution, otherwise he isn't sure. The second number shows Vasya's view on the solution, the third number shows Tonya's view. The numbers on the lines are separated by spaces.

Output:

Print a single integer — the number of problems the friends will implement on the contest.

Solution: 

1. n = int(input())
2. k=0
3. for i in range(0,n):
4. a , b , c = input().split()
5. if(int(a) == 1 and int(b) == 1 and int(c) == 1):
6. k = k + 1
7. elif(int(a) == 0 and int(b) == 1 and int(c) == 1):
8. k = k + 1
9. elif(int(a) == 1 and int(b) == 0 and int(c) == 1):
10. k = k + 1
11. elif(int(a) == 1 and int(b) == 1 and int(c) == 0):
12. k = k + 1
13. else:
14. pass
15. print(k)

The above solution is in python language. 

Examples

input

3
1 1 0
1 1 1
1 0 0

output

2

input

2
1 0 0
0 1 1

output

1

Park Lighting Problem !!!

 PROBLEM 23: Park Lighting

Problem Reference : Codeforces 

Due to the coronavirus pandemic, city authorities obligated citizens to keep a social distance. The mayor of the city Semyon wants to light up Gluharniki park so that people could see each other even at night to keep the social distance.

The park is a rectangular table with n$n$ rows and m$m$ columns, where the cells of the table are squares, and the boundaries between the cells are streets. External borders are also streets. Every street has length 1$1$. For example, park with n=m=2$n=m=2$ has 12$12$ streets.

You were assigned to develop a plan for lighting the park. You can put lanterns in the middle of the streets. The lamp lights two squares near it (or only one square if it stands on the border of the park).

Semyon wants to spend the least possible amount of money on lighting but also wants people throughout the park to keep a social distance. So he asks you to find the minimum number of lanterns that are required to light all the squares.

Input:

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases in the input. Then t$t$ test cases follow.

Each test case is a line containing two integers n$n$, m$m$ (1≤n,m≤104$1\le n,m\le {10}^4$) — park sizes.

Output:

Print t$t$ answers to the test cases. Each answer must be a single integer — the minimum number of lanterns that are required to light all the squares.

Solution: 

1. import math
2. t = int(input())
3. i = 0
4. while i < t:
5. i += 1
6. n1,m1 = input().split()
7. n = int(n1)
8. m = int(m1)
9. o = (n*m) / 2
10. print(math.ceil(o))

The above solution is in python language.

Example

input

5
1 1
1 3
2 2
3 3
5 3

output

1
2
2
5
8