e-olymp 263. Три единицы

27/12/2018 by Карина Миловская

Задача

Вычислить количество последовательностей длины $n,$ состоящих только из нулей и единиц, в которых не встречается три единицы подряд.

Входные данные

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

Выходные данные

Вывести количество искомых последовательностей по модулю $12345.$

Тесты

Входные данные	Выходные данные
$1$	$2$
$4$	$0$
$263$	$10159$
$10000$	$8872$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int MAX = 100010;
	static int f[] = new int[MAX];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		f[1] = 2; 
		f[2] = 4; 
		f[3] = 7;
		for(int i = 4; i <= n; i++) {
			f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
		}
		System.out.println(f[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static int MAX = 100010;

static int f[] = new int[MAX];

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

f[1] = 2;

f[2] = 4;

f[3] = 7;

for(int i = 4; i <= n; i++) {

f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

}

System.out.println(f[n]);

}

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 47. Паркет из треугольников

27/12/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex] m [/latex] на [latex] n [/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex] a [/latex] на паркетину [latex] b [/latex].

Входные данные

Во входном файле в первой сроке через пробел заданы значения [latex]m[/latex], [latex]n[/latex] [latex]\left ( 1\leqslant n,m\leqslant 100 \right )[/latex], а во второй — [latex] a [/latex] и [latex] b [/latex].

Выходные данные

Искомое количество шагов

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
3	5 4 15 22	3
5	3 2 6 12	2

Код 1

import java.util.*;
import java.lang.*;
import java.io.*;


class Main
{
	public static void swap(int A, int B) {
		int C = A;
		A = B;
		B = C;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int vertSize;
		int horSize;
    	int firstNumber;
    	int lastNumber;
    	Scanner in = new Scanner(System.in);
    	horSize = in.nextInt();
		vertSize = in.nextInt();
		firstNumber = in.nextInt();
		lastNumber= in.nextInt();
    	if (firstNumber > lastNumber){
    		int C = firstNumber;
			firstNumber = lastNumber;
			lastNumber = C;
    	} 
    //вычисление координат
    	int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    	int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    	int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    	int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    	int[] Search= new int[2 * horSize];
    	Search[firstNumberx - 1] = 0;
    	int step = 1;
    	for (int i = firstNumberx - 2; i >= 0; i--){
        	Search[i] = step++;
    	}
    	step = 1;
    	for (int i = firstNumberx; i < 2 * horSize; i++){
        	Search[i] = step++;
    	}
    	//сравнение по у
    	for (int j = firstNumbery; j < lastNumbery; j++) {
        	for (int i = 1; i < 2 * horSize; i += 2) {
            	Search[i - 1] = Search[i] + 1;
            	Search[i] += 2;
            //определение значения на предпоследнем элементе
            	if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                	Search[i - 2] = Search[i];
            	}
        	}
    	}
    System.out.println(Search[lastNumberx - 1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap(int A, int B) {

int C = A;

A = B;

B = C;

}

public static void main (String[] args) throws java.lang.Exception

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

Scanner in = new Scanner(System.in);

horSize = in.nextInt();

vertSize = in.nextInt();

firstNumber = in.nextInt();

lastNumber= in.nextInt();

if (firstNumber > lastNumber){

int C = firstNumber;

firstNumber = lastNumber;

lastNumber = C;

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int[] Search= new int[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определение значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

System.out.println(Search[lastNumberx - 1]);

}

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Следующим шагом будет определение позиции [latex]firstNumber [/latex] и [latex]lastNumber[/latex]. Положим, что [latex]x[/latex] — это позиция в строке, а [latex]y[/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем массив, переменные в котором будет иметь тип [latex]int[/latex] , а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex]int[/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции [latex]Search[firstNumberx — 1][/latex] стояло количество шагов, совершенных в ходе решения.

Код 2

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long m, n, a, b;
		Scanner in = new Scanner(System.in);
		m = in.nextLong();
		n = in.nextLong();
		a = in.nextLong();
		b = in.nextLong();
    	long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;
    	long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);
    	long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;
    	long k = dm > 0? 1: -1;
    	a += 2*k*o*(m - 1);
    	System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

long m, n, a, b;

Scanner in = new Scanner(System.in);

m = in.nextLong();

n = in.nextLong();

a = in.nextLong();

b = in.nextLong();

long dm = ((a + 1)/2 - 1) %m - ((b + 1)/2 - 1) % m;

long dn = (a - 1)/(2 * m) - (b - 1)/(2 * m);

long o = dm * dn < 0? Math.min(Math.abs(dm), Math.abs(dn)) : 0;

long k = dm > 0? 1: -1;

a += 2*k*o*(m - 1);

System.out.print( ((a + b) % 2 == 0? 0: Math.max(a, b) % 2 == 0? 1: -1) + 2*(Math.abs(dm) + Math.abs(dn) - o));

}

Ссылки

Задача на e-olymp

Код_1 задачи на ideone

Код_2 задачи на ideone

e-olymp 1489. Шоколад

27/12/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленькихшоколадных долек — прямоугольников $2 \cdot 1$.

Петя делит шоколадку на две части, разламывая ее вдоль некоторой прямой, параллельной одному из краев шоколадки. Ни Петя, ни Маша не любят ломаные дольки, поэтому Петя хочет разломать шоколадку так, чтобы ни одна долька не была повреждена.

Помогите Пете поделиться шоколадкой с Машей.

Входные данные

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

Выходные данные

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные	Выходные данные
2 3 1 1 2 3 3 2	Yes
5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13	No
4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7	Yes

Код решения

import java.io.InputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Resolver(System.in, System.out).solve();
    }

    public static class Resolver {

        private Scanner scanner;
        private PrintWriter writer;

        public Resolver(InputStream is, OutputStream os) {
            this.scanner = new Scanner(is);
            this.writer = new PrintWriter(os);
        }

        public void solve() {
            int rowCount = scanner.nextInt();
            int columnCount = scanner.nextInt();
            int[][] chocolate = new int[rowCount][columnCount];
            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();
            }
            check(chocolate, rowCount, columnCount);
            writer.flush(); writer.close();
        }

        private void check(int[][] chocolate, int rowCount, int columnCount) {
            if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");
            else writer.println("No");
        }
        private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < rowCount - 1; i++) {
                boolean okRow = true;
                for (int j = 0; j < columnCount; j++) {
                    if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; }
                }
                if (okRow) return true;
            }
            return false;
        }
        private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {
            for (int i = 0; i < columnCount - 1; i++) {
                boolean okColumn = true;
                for (int j = 0; j < rowCount; j++) {
                    if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; }
                }
                if (okColumn) return true;
            }
            return false;
        }
    }
}

import java.io.InputStream;

import java.io.OutputStream;

import java.io.PrintWriter;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

new Resolver(System.in, System.out).solve();

}

public static class Resolver {

private Scanner scanner;

private PrintWriter writer;

public Resolver(InputStream is, OutputStream os) {

this.scanner = new Scanner(is);

this.writer = new PrintWriter(os);

}

public void solve() {

int rowCount = scanner.nextInt();

int columnCount = scanner.nextInt();

int[][] chocolate = new int[rowCount][columnCount];

for (int i = 0; i < rowCount; i++) {

for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt();

}

check(chocolate, rowCount, columnCount);

writer.flush(); writer.close();

}

private void check(int[][] chocolate, int rowCount, int columnCount) {

if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes");

else writer.println("No");

}

private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) {

for (int i = 0; i < rowCount - 1; i++) {

boolean okRow = true;

for (int j = 0; j < columnCount; j++) {

if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; }

}

if (okRow) return true;

}

return false;

}

private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) {

for (int i = 0; i < columnCount - 1; i++) {

boolean okColumn = true;

for (int j = 0; j < rowCount; j++) {

if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; }

}

if (okColumn) return true;

}

return false;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true и false в обратном случае.Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа boolean. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Ссылка на E-olymp
Ссылка на решение

e-olymp 936. Формулы Крамера

27/12/2018 by Иван Василевский

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
$\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}$
Входные данные
Первая строка содержит коэффициенты первого уравнения, а вторая строка содержит коэффициенты второго. Все входные числа разделены одним пробелом и не превышают по модулю $100$.
Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.
Тесты

Входные данные	Выходные данные
5 8 1 -3 6 15	-1.000 2.000
5 5 5 2 3 5	-2.000 3.000
1 2 3 3 3 3	-1.000 2.000
25 15 16 11 12 13	-0.022 1.104

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        double matrix[][] = new double[3][2];
        for (int i = 0; i < 2; ++i){
            String[] params1 = bufferedReader.readLine().split(" ");
            for (int j = 0; j < 3; ++j){
                matrix[j][i] = Float.parseFloat(params1[j]);
            }
        }
        double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];
        double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];
        System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

double matrix[][] = new double[3][2];

for (int i = 0; i < 2; ++i){

String[] params1 = bufferedReader.readLine().split(" ");

for (int j = 0; j < 3; ++j){

matrix[j][i] = Float.parseFloat(params1[j]);

}

double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];

double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];

double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];

System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);

}

Решение задачи
Создаем матрицу размером $3$ на $2$, так как у нас $3$ переменных в $2$ уравнениях. Создаем циклы для заполнения нашей матрицы. Дальше по формуле Камера перемножаем переменные. Выводим на экран ответы с точностью до $0.001$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 922. Сдвинь элементы

27/12/2018 by Иван Василевский

Условие задачи
Задан массив целых чисел длины $n$. Сдвинуть элементы массива вправо циклически на $1$ шаг.
Входные данные
В первой строке задано количество элементов массива $n$$(n ≤ 100)$ . Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает $100$.
Выходные данные
В одной строке вывести $n$ чисел — новые значения элементов массива.
Тесты

Входные данные	Выходные данные
4 1 2 3 4 5	4 1 2 3
6 3 3 3 3 3 1	1 3 3 3 3 3
2 1 2	2 1

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        int number;
        number = Integer.parseInt(params1[0]);
        int arr[] = new int[number];
        String[] params2 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < number; i++)
        {
            arr[i] = Integer.parseInt(params2[i]);
        }
        int last = arr[number - 1];
        for (int i = number - 1; i > 0; i--)
        {
            arr[i] = arr[i - 1];
        }
        arr[0] = last;
        for (int i = 0; i < number; i++)
        {
            System.out.print(arr[i]);
            System.out.print(' ');
        }
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int number;

number = Integer.parseInt(params1[0]);

int arr[] = new int[number];

String[] params2 = bufferedReader.readLine().split(" ");

for (int i = 0; i < number; i++)

{

arr[i] = Integer.parseInt(params2[i]);

}

int last = arr[number - 1];

for (int i = number - 1; i > 0; i--)

{

arr[i] = arr[i - 1];

}

arr[0] = last;

for (int i = 0; i < number; i++)

{

System.out.print(arr[i]);

System.out.print(' ');

}

Решение задачи
Создаем динамический массив, размером в number элементов. Создаем переменную last, в которой записан последний элемент массива. Создаём цикл, в котором меняется каждый элемент массива с предыдущим. Кладем на $1$ место (точнее $0$ место) бывший последний элемент массива.
Выводим массив.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 930. Номер мобильного телефона

26/12/2018 by Томас Пасенченко

Задача

Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.

Входные данные

В единственной строке задан номер мобильного телефона.

Выходные данные

В первой строке вывести количество отсутствующих в номере цифр. Во второй строке в порядке возрастания вывести отсутствующие цифры, разделенные пробелом.

Тесты

Входные данные	Выходные данные
0631562976	2 4 8
2139087	3 4 5 6
1111111111	9 0 2 3 4 5 6 7 8 9
7	9 0 1 2 3 4 5 6 8 9
4848	8 0 1 2 3 5 6 7 9
0921234567	1 8
6723545	4 0 1 8 9
9867453210	0
+38 (037) 123-4-765	1 9

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main (String[] args) throws Exception{
		int code;
		int count = 0;
		int n[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while ((code = br.read()) != -1) {
			if (code >= 48 && code <= 57) n[code - 48]++;
		}
		for (int i = 0; i < 10; i++) {
        	if (n[i] == 0) count++;
		}
		System.out.println(count);
		for (int i = 0; i < 10; i++) {
			if (n[i] == 0) System.out.print(i + " ");
		}
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

public static void main (String[] args) throws Exception{

int code;

int count = 0;

int n[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

while ((code = br.read()) != -1) {

if (code >= 48 && code <= 57) n[code - 48]++;

}

for (int i = 0; i < 10; i++) {

if (n[i] == 0) count++;

}

System.out.println(count);

for (int i = 0; i < 10; i++) {

if (n[i] == 0) System.out.print(i + " ");

}

Решение

Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp

e-olymp 2812. Уголок

26/12/2018 by Георгий Мартынюк

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

Входные данные

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.

Выходные данные

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные	Выходные данные
2 2 .. ..	4
2 3 ..X .X.	1
5 4 …. X.XX …. X..X ..XX	12

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int x, y;
        x = Integer.parseInt(params1[0]);
        y = Integer.parseInt(params1[1]);
        boolean mas[][] = new boolean[x][y];
        for (int i = 0; i < x; ++i){
            String[] params2 = bufferedReader.readLine().split(" ");
            for (int j = 0; j < y; ++j){
                char buff;
                buff = params2[0].charAt(j);
                if (buff == '.') mas[i][j] = true; 
                else mas[i][j] = false;
            }
            System.out.print("\n");
        }
        int sum = 0;
        for (int i = 0; i < x; ++i){
            for (int j = 0; j < y; ++j){
                if (mas[i][j]){
                    if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1])  ++sum;
                    if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1])  ++sum; 
                    if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1])  ++sum; 
                    if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1])  ++sum; 
                }
            }
        }
        System.out.print(sum);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int x, y;

x = Integer.parseInt(params1[0]);

y = Integer.parseInt(params1[1]);

boolean mas[][] = new boolean[x][y];

for (int i = 0; i < x; ++i){

String[] params2 = bufferedReader.readLine().split(" ");

for (int j = 0; j < y; ++j){

char buff;

buff = params2[0].charAt(j);

if (buff == '.') mas[i][j] = true;

else mas[i][j] = false;

}

System.out.print("\n");

}

int sum = 0;

for (int i = 0; i < x; ++i){

for (int j = 0; j < y; ++j){

if (mas[i][j]){

if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1]) ++sum;

if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1]) ++sum;

}

System.out.print(sum);

}

Решение

Для решения данной задачи создаем динамический массив типа [latex]bool[/latex] [latex]x[/latex] на [latex]y[/latex]. Заполняем соответствующий элемент значением [latex]true[/latex], когда вводится «.» и значением [latex]false[/latex] в противном случае. Далее увеличиваем значение количества уголков на , если существуют не пустые клетки.

Ссылки

e-olymp
Ideone

A302. Количество различных цифр числа в его десятичной записи

26/12/2018 by Андрей Лисовой

Задача

Дано натуральное число $N$. Сколько различных цифр встречается в его десятичной записи?

Вводные данные

Натуральное число $N$.

Выходные данные

Количество различных цифр.

Тесты

Входные данные	Выходные данные
$1234$	$4$
$100$	$2$
$1234567890$	$10$
$3333$	$1$
$11112222$	$2$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[] folder = new int[10];
    	long N = in.nextLong();
    	while(N != 0) {
        	folder[(int)N % 10]++;
        	N /= 10;
    	}
    	int sum = 0;
    	for (int i = 0; i < 10; i++)
        	if(folder[i] != 0) sum++;
        System.out.print(sum);	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int[] folder = new int[10];

long N = in.nextLong();

while(N != 0) {

folder[(int)N % 10]++;

N /= 10;

}

int sum = 0;

for (int i = 0; i < 10; i++)

if(folder[i] != 0) sum++;

System.out.print(sum);

}

Решение задачи

Для решения задачи создадим массив folder в котором будем хранить количество встреч для различных цифр десятичной записи в соответствующих позициях массива. Находим цифры числа $N$($N \mod 10$ последняя цифра числа, затем $N / 10$). Увеличиваем на $1$ значения соответствующей позиции массива(цифра числа равна индексу массива). Для определения количества различных цифр делаем цикл и проверяем ненулевые значения массива folder. Задача решена.

Ссылки

Условие задачи(стр. 126).
Код решения на ideone.com

e-olymp 4557. Одинокий король

26/12/2018 by Андрей Лисовой

Задача

Позиция короля на шахматной доске

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.

Определите, побывал ли король дважды на одном и том же поле за свои $n$ ходов.

Возможные ходы короля

Вводные данные

В первой строке задано общее число ходов короля $n$ $(0 \leq n \leq 1000)$. В последующих $n$ строках заданы направления перемещения короля: строка под номером $i+1$ задаёт направление перемещения короля на $i$-ом ходу.

Выходные данные

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами $(x_1, y_1)$ и $(x_2, y_2)$ определяется по формуле: $d=|x_2 — x_1| + |y_2 — y_1|$.

Тесты

Входные данные	Выходные данные
$5\;1\;2\;4\;7\;4$	$4$
$5\;1\;2\;4\;6\;4$	$Ok$ $2$
$8\;3\;3\;7\;7\;5\;5\;3\;3$	$3$
$12\;2\;3\;4\;1\;3\;2\;5\;6\;8\;2\;1\;7$	$10$
$9\;2\;2\;3\;3\;4\;4\;7\;7\;7$	$Ok$ 2

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[][] x = new int[2001][2001];
		int n = in.nextInt();
		int move;
		int xPos=1001, yPos=1001;
		for(int i = 0; i < n; i++) {
			move = in.nextInt();
			if(x[xPos][yPos] == 1) { 
            	System.out.print(i);
            	return;
        	}
        	else x[xPos][yPos]=1;
	        if(move == 1) {
	            xPos--;
	            yPos++;
	        }
	        if(move == 2) {
	            yPos++;
	        }
	        if(move == 3) {
	            xPos++;
	            yPos++;
	        }
	        if(move == 4) {
	            xPos++;
	        }
	        if(move == 5) {
	            xPos++;
	            yPos--;
	        }
	        if(move == 6) {
	            yPos--;
	        }
	        if(move == 7) {
	            xPos--;
	            yPos--;
	        }
	        if(move == 8) {
	            xPos--;
	        }
		}
		System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int[][] x = new int[2001][2001];

int n = in.nextInt();

int move;

int xPos=1001, yPos=1001;

for(int i = 0; i < n; i++) {

move = in.nextInt();

if(x[xPos][yPos] == 1) {

System.out.print(i);

return;

}

else x[xPos][yPos]=1;

if(move == 1) {

xPos--;

yPos++;

}

if(move == 2) {

yPos++;

}

if(move == 3) {

xPos++;

yPos++;

}

if(move == 4) {

xPos++;

}

if(move == 5) {

xPos++;

yPos--;

}

if(move == 6) {

yPos--;

}

if(move == 7) {

xPos--;

yPos--;

}

if(move == 8) {

xPos--;

}

System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));

}

Решение задачи

Создаем массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим $1$, и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 5080. Количество висячих вершин 1

25/12/2018 by Карина Миловская

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $1.$

Входные данные

В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.

Выходные данные

Выведите количество висячих вершин в графе.

Тесты

Входные данные	Выходные данные
$2 \\ 0 \ 1 \\ 1 \ 0$	$2$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$	$0$
$4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$	$4$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$	$1$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int [][] gr = new int [1001][1001]; 
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); 
		int ans = 0; 
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				gr[i][j] =  in.nextInt(); 
			}
		}
		for (int i=0; i<n; i++) {
			int cnt = 0; 
			for (int j=0; j<n; j++) {
				if (gr[i][j] == 1) cnt++;
			}
			if (cnt==1) ans++;
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int [][] gr = new int [1001][1001];

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int ans = 0;

for (int i=0; i<n; i++) {

for (int j=0; j<n; j++) {

gr[i][j] = in.nextInt();

}

for (int i=0; i<n; i++) {

int cnt = 0;

for (int j=0; j<n; j++) {

if (gr[i][j] == 1) cnt++;

}

if (cnt==1) ans++;

}

System.out.println(ans);

}

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

Задача

Входные данные

Выходные данные

Тесты

Код 1

Код 2

Ссылки

Задача

Входные данные

Выходные данные

Код решения

Решение

Ссылки

5 8 1 -3 6 15

-1.000 2.000

5 5 5 2 3 5

-2.000 3.000

1 2 3 3 3 3

-1.000 2.000

25 15 16 11 12 13

-0.022 1.104

4 1 2 3 4 5

4 1 2 3

6 3 3 3 3 3 1

1 3 3 3 3 3

2 1 2

2 1

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

Задача

Вводные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки

Задача

Вводные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

5 8 1
-3 6 15

-1.000
2.000

5 5 5
2 3 5

-2.000
3.000

1 2 3
3 3 3

-1.000
2.000

25 15 16
11 12 13

-0.022
1.104

4
1 2 3 4 5

6
3 3 3 3 3 1

2
1 2