Prison Transfer [Codeforces Round #244 (Div. 2)] Problem B

B. Prison Transfer

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The prison of your city has n prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer c of the prisoners to a prison located in another city.

For this reason, he made the n prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.

Then, the mayor told you to choose the c prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,

• The chosen c prisoners has to form a contiguous segment of prisoners.
• Any of the chosen prisoner's crime level should not be greater then t. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer.

Find the number of ways you can choose the c prisoners.

Input

The first line of input will contain three space separated integers n (1 ≤ n ≤ 2·105), t (0 ≤ t ≤ 109) and c (1 ≤ c ≤ n). The next line will contain n space separated integers, the ith integer is the severity ith prisoner's crime. The value of crime severities will be non-negative and will not exceed 109.

Output

Print a single integer — the number of ways you can choose the c prisoners.

Sample test(s)

input

4 3 3
2 3 1 1

output

2

input

1 1 1
2

output

0

input

11 4 2
2 2 0 7 3 2 2 4 9 1 4

output

6

My Solution [ Java ] :

→ Source

import java.util.Scanner;

public class PrisonTransfer {
    public static void main(String[] args){
       Scanner s = new Scanner(System.in);
       int n = s.nextInt();
       int t = s.nextInt();
       int c = s.nextInt();
       
       int con = 0;
       int w=0;
       
       int temp=0;
       for(int i=0;i<n;++i){
          temp = s.nextInt();
          if(temp<=t){
              con++;
              if(con==c){
                  w++;
                  con-=1;
              }
          }else
              con=0;
       }
       System.out.println(w);
    }
}

Password Check [Codeforces Coder-Strike 2014 - Qualification Round] Problem A

A. Password Check

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have probably registered on Internet sites many times. And each time you should enter your invented password. Usually the registration form automatically checks the password's crypt resistance. If the user's password isn't complex enough, a message is displayed. Today your task is to implement such an automatic check.

Web-developers of the company Q assume that a password is complex enough, if it meets all of the following conditions:

• the password length is at least 5 characters;
• the password contains at least one large English letter;
• the password contains at least one small English letter;
• the password contains at least one digit.

You are given a password. Please implement the automatic check of its complexity for company Q.

Input

The first line contains a non-empty sequence of characters (at most 100 characters). Each character is either a large English letter, or a small English letter, or a digit, or one of characters: "!", "?", ".", ",", "_".

Output

If the password is complex enough, print message "Correct" (without the quotes), otherwise print message "Too weak" (without the quotes).

Sample test(s)

input

abacaba

output

Too weak

input

X12345

output

Too weak

input

CONTEST_is_STARTED!!11

output

Correct

→ Source

import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class PasswordCheck {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        
        if(s.length()<5){
            System.out.println("Too weak");
            System.exit(0);
        }
        int l=0,ss=0,d=0;
        
        Pattern p = Pattern.compile("[0-9]+");
        Matcher m = p.matcher(s);
        if(m.find()){
            d++;
        }
        p=Pattern.compile("[A-Z]+");
        m=p.matcher(s);
        if(m.find()){
            l++;
        }
        p=Pattern.compile("[a-z]+");
        m=p.matcher(s);
        if(m.find()){
            ss++;
        }
        
        if(l==0||ss==0||d==0){
            System.out.println("Too weak");
            System.exit(0);
        }
        System.out.println("Correct");
    }
}

Sereja and Mirroring : Codeforces Round #243 (Div. 2) Problem B

B. Sereja and Mirroring

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's assume that we are given a matrix b of size x × y, let's determine the operation of mirroring matrix b. The mirroring of matrix b is a2x × y matrix c which has the following properties:

• the upper half of matrix c (rows with numbers from 1 to x) exactly matches b;
• the lower half of matrix c (rows with numbers from x + 1 to 2x) is symmetric to the upper one; the symmetry line is the line that separates two halves (the line that goes in the middle, between rows x and x + 1).

Sereja has an n × m matrix a. He wants to find such matrix b, that it can be transformed into matrix a, if we'll perform on it several(possibly zero) mirrorings. What minimum number of rows can such matrix contain?

Input

The first line contains two integers, n and m (1 ≤ n, m ≤ 100). Each of the next n lines contains m integers — the elements of matrix a. The i-th line contains integers ai1, ai2, ..., aim (0 ≤ aij ≤ 1) — the i-th row of the matrix a.

Output

In the single line, print the answer to the problem — the minimum number of rows of matrix b.

Sample test(s)

input

4 3
0 0 1
1 1 0
1 1 0
0 0 1

output

2

input

3 3
0 0 0
0 0 0
0 0 0

output

3

input

8 1
0
1
1
0
0
1
1
0

output

2

Note

In the first test sample the answer is a 2 × 3 matrix b:

001
110

If we perform a mirroring operation with this matrix, we get the matrix a that is given in the input:

001
110
110
001

→ Source

import java.util.Scanner;

public class SerejaAndMirroring {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int rows = scan.nextInt();
        int columns = scan.nextInt();

        if (rows % 2 == 1) {
            System.out.println(rows);
            System.exit(0);
        }
        if (rows == 1) {
            System.out.println(rows);
            System.exit(0);
        }
        int result = 0;

        int[][] mat = new int[rows + 1][columns + 1];
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= columns; ++j) {
                mat[i][j] = scan.nextInt();
            }
        }
        int m = 0;

        while (rows % 2 == 0) {
            for (int i = 1; i <= rows / 2 && m != 1; ++i) {
                for (int j = 1; j <= columns; ++j) {
                    if (mat[i][j] != mat[rows - i + 1][j]) {
                        m = 1;
                        break;
                    }
                }
            }
            if (m == 1) {
                break;
            } else {
                rows /= 2;
            }
        }
            System.out.println(rows);
    }
}