e-olymp 2820. Перемещение коня

06/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

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

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]a[/latex]—[latex]h[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]—[latex]8[/latex]), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»

Тест

Пример входных данных	Пример выходных данных
[latex]e2[/latex] [latex]e4[/latex]	Путь от [latex]e2[/latex] к [latex]e4[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]b2[/latex]	Путь от [latex]a1[/latex] к [latex]b2[/latex] занимает [latex]4[/latex] шагов.
[latex]b2[/latex] [latex]c3[/latex]	Путь от [latex]b2[/latex] к [latex]c3[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]h8[/latex]	Путь от [latex]a1[/latex] к [latex]h8[/latex] занимает [latex]6[/latex] шагов.
[latex]a1[/latex] [latex]h7[/latex]	Путь от [latex]a1[/latex] к [latex]h7[/latex] занимает [latex]5[/latex] шагов.
[latex]h8[/latex] [latex]a1[/latex]	Путь от [latex]h8[/latex] к [latex]a1[/latex] занимает [latex]6[/latex] шагов.
[latex]b1[/latex] [latex]c3[/latex]	Путь от [latex]b1[/latex] к [latex]c3[/latex] занимает [latex]1[/latex] шагов.
[latex]f6[/latex] f[latex]6[/latex]	Путь от [latex]f6[/latex] к [latex]f6[/latex] занимает [latex]0[/latex] шагов.

Решение

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

class Main {

    public static class Pair <T1, T2> {
        public T1 fst;
        public T2 snd;

        public Pair(T1 t1, T2 t2) {

            this.fst = t1;
            this.snd = t2;
        }
    }

    public static void main(String[] args) 
 {
        char a, b;
        int nx, ny, tx, ty;
        int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
        int my[] = {2, -2, 2, -2, 1, -1, 1, -1};
        int A[][] = new int[8][8];
        Scanner s = new Scanner(System.in);
        String str;
        while (s.hasNextLine()) {
            String line = s.nextLine();
            Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");
            Matcher m = p.matcher(line);
            m.find();
            a = m.group(1).toCharArray()[0];
            ny = Integer.parseInt(m.group(2));
            b = m.group(3).toCharArray()[0];
            ty = Integer.parseInt(m.group(4));
            nx = a - 'a';
            ny--;
            tx = b - 'a';
            ty--;
            A[nx][ny] = 0;
            Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
            q.add(new Pair<Integer, Integer>(nx, ny));
            while (!q.isEmpty()) {
                Pair<Integer, Integer> c = q.peek();
                int x = c.fst, y = c.snd;
                if (x == tx && y == ty) break;
                q.remove();
                for (int i = 0; i < 8; i++) {
                    if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                        q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));
                        A[x + mx[i]][y + my[i]] = A[x][y] + 1;
                    }
                }
            }
            System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

class Main {

public static class Pair <T1, T2> {

public T1 fst;

public T2 snd;

public Pair(T1 t1, T2 t2) {

this.fst = t1;

this.snd = t2;

}

public static void main(String[] args)

{

char a, b;

int nx, ny, tx, ty;

int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};

int my[] = {2, -2, 2, -2, 1, -1, 1, -1};

int A[][] = new int[8][8];

Scanner s = new Scanner(System.in);

String str;

while (s.hasNextLine()) {

String line = s.nextLine();

Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");

Matcher m = p.matcher(line);

m.find();

a = m.group(1).toCharArray()[0];

ny = Integer.parseInt(m.group(2));

b = m.group(3).toCharArray()[0];

ty = Integer.parseInt(m.group(4));

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();

q.add(new Pair<Integer, Integer>(nx, ny));

while (!q.isEmpty()) {

Pair<Integer, Integer> c = q.peek();

int x = c.fst, y = c.snd;

if (x == tx && y == ty) break;

q.remove();

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

if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные aи b типа char, где a и b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых a, ny — координата одной клетки и b, ty — координата другой клетки. nx — цифровая координата, которую мы получаем из буквы, отнимая от a. Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.

e-olymp 5072. Подсчет количества ребер

06/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

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

Входной файл содержит число [latex]n(1 \leq n \leq 100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Тест

№	Значения	Результат
1	3 0 1 1 1 0 1 0 1 1	6

Решение

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

class Main
{
	public static void main (String[] args)
	{
		int n;
    	Scanner sc =new Scanner(System.in);
    	n=sc.nextInt();
 		int k, l=0;
    	for(int i=0;i<n;i++){
        	for(int j=0; j<n; j++){
            	k=sc.nextInt();
            	if (k>0)
            	l++;
    		}
    	}
 		System.out.println(l);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

int n;

Scanner sc =new Scanner(System.in);

n=sc.nextInt();

int k, l=0;

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

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

k=sc.nextInt();

if (k>0)

l++;

}

System.out.println(l);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n типа int. Чтобы найти количество ребер в графе, вводим в двух циклах каждый элемент матрицы смежности и если значение больше нуля, то увеличиваем сумму.

MS13. Решение квадратных уравнений

04/07/2017 by Присяжный Михаил

Постановка задачи
Каждая четвёрка чисел входного потока представляет собой квадратное уравнение в такой форме [latex]ax^2+bx+c=d.[/latex] Выпишите через запятую решения этих уравнений (если это возможно).

Входные данные:
значения переменных

Выходные данные:
корни [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex] и нет корней

Тесты

№	Входной поток чисел	Корни уравнений
1	2 -3 4 1 0 13 10 0	нет корней;
2	2 -0.5 2.2 0 5 0 -25 0	нет корней; -2.23607, 2.23607;
3	1 3 -4 -1 2 -7 11 0	-3.79128784747792, 0.7912878474779199; нет корней;

Решение

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

class Ideone
{
	public static void main (String[] args)
	{
		double a, b, c, d, D;
		double x1,x2,x3;
		Scanner s =new Scanner(System.in);
		while(s.hasNext()){
			a= s.nextInt();
			b= s.nextInt();
			c= s.nextInt();
			d= s.nextInt();
			D=b*b-4*a*(c-d);
			if(D>0)
			{
				x1=(-b-Math.sqrt(D))/(2*a);
				x2=(-b+Math.sqrt(D))/(2*a);
				System.out.println(x1+", "+x2+"; ");
			}
			else if(D==0)
			{
				x3=(-b)/(2*a);
				System.out.println(x3+"; ");
			}
			else System.out.println("no roots"+"; ");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

double a, b, c, d, D;

double x1,x2,x3;

Scanner s =new Scanner(System.in);

while(s.hasNext()){

a= s.nextInt();

b= s.nextInt();

c= s.nextInt();

d= s.nextInt();

D=b*b-4*a*(c-d);

if(D>0)

{

x1=(-b-Math.sqrt(D))/(2*a);

x2=(-b+Math.sqrt(D))/(2*a);

System.out.println(x1+", "+x2+"; ");

}

else if(D==0)

{

x3=(-b)/(2*a);

System.out.println(x3+"; ");

}

else System.out.println("no roots"+"; ");

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменные a, b, c, d, D, x1, x2, x3 типа double, где a, b, c, d — коефициенты квадратического уравнения, D — дискриминант, а x1, x2, x3 — корни. Создаем цикл while, в котором производится решение квадратического уравнения. В нем проверяем, если дискриминант больше нуля, выводим корни x1 и x2. Если дискриминант равен нулю, то находим x3, иначе, если дискриминант отрицателен — не имеем корней (no roots).

Ю 4.17

03/07/2017 by Присяжный Михаил

Постановка задачи

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<x_{i}>a_{i+1}[/latex].

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

№	Количество значений	Значения	Результат
1	6	2 4 6 1 3 7 5	2
2	7	3 1 6 2 8 5 7	2, 4
3	10	2 5 8 3 5 6 9 7 1 4	2, 6

Решение

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

class Ideone
{
	public static void main (String[] args)
	{
		int n;
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		double[] x = new double[n];
		for(int i=0; i<n; i++){
			x[i]=s.nextInt();
		}
		for(int j=1; j<=(n-2); j++){
			if((x[j]>x[j+1])&&(x[j]>x[j-1])){
				System.out.println(j + " ");
			}	
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

int n;

Scanner s = new Scanner(System.in);

n = s.nextInt();

double[] x = new double[n];

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

x[i]=s.nextInt();

}

for(int j=1; j<=(n-2); j++){

if((x[j]>x[j+1])&&(x[j]>x[j-1])){

System.out.println(j + " ");

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.

e-olymp 7365

03/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

Количество учеников [latex]n[/latex] и их веса

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

Количество пирожков и пакетов молока

Тесты

№	Кол-во учеников	Вес учеников	Кол-во пирожков	Кол-во пакетов молока
1	3	23 24 25	3	1
2	6	11 15 26 27 22 30	5	1
3	7	21 30 30 27 21 22 30	4	1

Решение

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

class Main {
    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int p = 0; 
        int n, k; 
        double m, u, w;
        n = s.nextInt();
        m = 0.2;
        u = 0.9;
        for (int i = 0; i < n; i++) {
            w = s.nextDouble();
            if (w < 30) p++;
        }
        k = (int) Math.ceil(p * m / u);
        System.out.println(k + " " + p);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

int p = 0;

int n, k;

double m, u, w;

n = s.nextInt();

m = 0.2;

u = 0.9;

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

w = s.nextDouble();

if (w < 30) p++;

}

k = (int) Math.ceil(p * m / u);

System.out.println(k + " " + p);

}

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

Ссылка на проверку решения задачи на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные типа int для учеников n и пирожков p и упаковок молока k. Для определения количества дополнительных пакетов молока и пирожков, используем цикл for, в котором, проверяем, присутствуют ли в наших учениках те, вес которых ниже 30 кг weight<30. Если вес ученика ниже 30 кг weight<30, то даем ему пирожок p++ и прибавляем 200 мл молока. На экран выводим количество пирожков и количество пакетов молока для заданного количества учеников с заданным весом.

Mif 5

02/07/2017 by Присяжный Михаил

Постановка задачи

Даны действительные числа [latex]x, y, z[/latex]. Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.

Входные данные: действительные числа [latex]x, y, z.[/latex]

Выходные данные: Максимальное значение (Highest value), количество максимальных значений (Count of highest values), минимальное значение (Lowest value), количество минимальных значений (Count of lowest values)

Тесты

	Входные данные	Выходные данные
№	[latex]x, y, z[/latex]	Максимум	Количество максимумов	Минимум	Количество минимумов
1	10	20	1	10	2
2	10
3	20

Решение

import java.util.Scanner;

 class Task2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        float number;
        float max = 0;
        float min = 0;
        int countMax = 0;
        int countMin = 0;

        for (int x = 0; x < 3; x++) {
            number = input.nextInt();

            if (x == 0 || number > max) {
                countMax = 1;
                max = number;
            } else if (number == max) {
                countMax++;
            }
            if (x == 0 || number < min) {
                countMin = 1;
                min = number;
            } else if (number == min) {
                countMin++;
            }
        }

        System.out.println("Highest value: " + max);

        System.out.println("Count of highest values: " + countMax);

        System.out.println("Lowest value: " + min);

        System.out.println("Count of lowest values: " + countMin);
    }
}

import java.util.Scanner;

class Task2 {

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

float number;

float max = 0;

float min = 0;

int countMax = 0;

int countMin = 0;

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

number = input.nextInt();

if (x == 0 || number > max) {

countMax = 1;

max = number;

} else if (number == max) {

countMax++;

}

if (x == 0 || number < min) {

countMin = 1;

min = number;

} else if (number == min) {

countMin++;

}

System.out.println("Highest value: " + max);

System.out.println("Count of highest values: " + countMax);

System.out.println("Lowest value: " + min);

System.out.println("Count of lowest values: " + countMin);

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для нахождения нахождения найбольшего max и найменьшего min значений используем цикл for. Если текущее число больше максимального, то ставим счетчик countMax на 1 и сохраняем новое максимальное значение max. Если последующее число равно текущему максимальному max, то увеличиваем счетчик countMax. Аналогично и для поиска найменьшего min значения.

ML13. Площадь равностороннего треугольника

02/07/2017 by Присяжный Михаил

Постановка задачи

Дана сторона равностороннего треугольника. Найти площадь этого треугольника.

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

Сторона равностороннего треугольника [latex]a[/latex]

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

Площадь равностороннего треугольника [latex]S[/latex]

Тесты

№	Входные данные	Выходные данные
1	4	6.928
2	3	3.897
3	6	15.588

Ссылка на результат теста на wolframalpha.com

Решение

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

class Ideone
{
	public static void main (String[] args)
	{
		double a, S;
		Scanner in = new Scanner(System.in);
		a = in.nextInt();
		S = (Math.sqrt(3)/4)*a*a;
		System.out.println(S);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

double a, S;

Scanner in = new Scanner(System.in);

a = in.nextInt();

S = (Math.sqrt(3)/4)*a*a;

System.out.println(S);

}

Для проверки работы программы можно воспользоваться онлайн компилятором Ideone.com

Описание решения

Для нахождения площади равностороннего треугольника будем использовать формулу [latex]S = \frac{a^2\sqrt{3}}{4}[/latex]. Чтобы найти корень, используем функцию Math.sqrt(). На экран выводим площадь треугольника.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Присяжный Михаил

e-olymp 2820. Перемещение коня

e-olymp 5072. Подсчет количества ребер

MS13. Решение квадратных уравнений

Ю 4.17

e-olymp 7365

Mif 5

ML13. Площадь равностороннего треугольника