e-olymp 3966. An ardent collector of butterflies

01/09/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует 2000000000 видов бабочек.

Чтобы не запутаться, Андрей Сергеевич присвоил каждому виду уникальный номер. Нумерация бабочек всегда начинается с единицы.

Теперь он хочет знать, есть ли бабочка с видом K в его коллекции, или же её придётся добывать, затрачивая уйму сил и денег.

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

В первой строке входного файла содержится единственное число N (1 ≤ N≤ 100000) — количество видов бабочек в коллекции Андрея Сергеевича.

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

Все виды бабочек в коллекции имеют различные номера.

В третьей строке файла записано число M (1≤ M≤ 100000) — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел M чисел — номера видов бабочек, наличие которых необходимо проверить.

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите «YES«, если бабочка с данным номером содержится в коллекции, и «NO» — в противном случае.

Тесты:

№	Входные данные	Выходные данные:
1	7 10 47 50 63 89 90 99 4 84 33 10 82	NO NO YES NO
2	10 1 4 7 11 12 43 44 67 344 355 5 1 2 4 44 45	YES NO YES YES NO

Код на Java:

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

class Main {
	public static boolean find(int search, int[] arr, int len) {
		boolean ret = false;
		int fst = 0;
		int lst = len - 1;
		while (fst <= lst) {
			int mid = (fst + lst) / 2;
			if (search == arr[mid]) {
				ret = true;
				break;
			} else if (search < arr[mid]) {
				lst = mid - 1;
			} else {
				fst = mid + 1;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int len = scan.nextInt();
		int[] arr = new int[len];
		int i;
		for (i = 0; i < len; i++) {
			arr[i] = scan.nextInt();
		}
		int num = scan.nextInt();
		int search;
		for (i = 0; i < num; i++) {
			search = scan.nextInt();
			System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Алгоритм:

Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:

Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
int[] arr = new int[len];
int i;
for (i = 0; i < len; i++) {
	arr[i] = scan.nextInt();
}
int num = scan.nextInt();

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

int search;
for (i = 0; i < num; i++) {
	search = scan.nextInt();
	System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
}

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Суть алгоритма бинарного поиска: искомый элемент сравнивается с элементом в середине диапазона. При совпадении поиск считаем оконченным. Если совпадения нет, то, в зависимости от различия, поиск продолжается в «левой» или «правой» половине текущего диапазона. Если оказалось, что очередной диапазон имеет «нулевую» длину, это означает, что искомого элемента в исходном массиве нет. Примечание: алгоритм требует упорядоченности исходного массива по возрастанию или убыванию.

public static boolean find(int search, int[] arr, int len) {
	boolean ret = false;
	int fst = 0;
	int lst = len - 1;
	while (fst <= lst) {
		int mid = (fst + lst) / 2;
		if (search == arr[mid]) {
			ret = true;
			break;
		} else if (search < arr[mid]) {
			lst = mid - 1;
		} else {
			fst = mid + 1;
		}
	}
	return ret;
}

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 6127. The queue of unlimited size

31/08/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

Программа должна вывести значение первого элемента, не удаляя его из очереди.

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты:

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

Код на Java:

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

class Main {
	public static class Node {
		public int value;
		public Node next;
		
		public Node() {
			value = 0;
			next = null;
		}
		public Node(int newValue, Node newNext) {
			value = newValue;
			next = newNext;
		}
	}
	
	public static class Queue {
		private int size;
		private Node first;
		private Node last;
		
		public Queue() {
			size = 0;
			first = null;
			last = null;
		}
		
		public void push(int v) {
			Node newNode = new Node(v, null);
			if (size == 0) {
				first = last = newNode;
			} else {
				last.next = newNode;
				last = newNode;
			}
			size++;
		}
		public boolean pop() {
			boolean ret = false;
			if (size > 0) {
				int val = first.value;
				first = first.next;
				size--;
				System.out.println(val);
				ret = true;
			}
			return ret;
		}
		public boolean front() {
			boolean ret = false;
			if (size > 0) {
				System.out.println(first.value);
				ret = true;
			}
			return ret;
		}
		public int getSize() {
			return size;
		}
		public void clear() {
			first = null;
			last = null;
			size = 0;
		}
	}
	public static void main(String[] args) {
		Queue q = new Queue();
		String s;
		int n;
		Scanner scan = new Scanner(System.in);
		while ((s = scan.next()) != null) {
			switch(s) {
				case "size": System.out.println(q.getSize()); break;
				case "push":
					n = scan.nextInt();
					q.push(n);
					System.out.println("ok");
					break;
				case "pop":
					if (q.pop() == false) {
						System.out.println("error");
					}
					break;
				case "front":
					if (q.front() == false) {
						System.out.println("error");
					}
					break;
				case "clear":
					q.clear();
					System.out.println("ok");
					break;
				case "exit":
					System.out.println("bye");
					return;
				default: break;
			}
		}
	}
}

100

101

102

103

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static class Node {

public int value;

public Node next;

public Node() {

value = 0;

next = null;

}

public Node(int newValue, Node newNext) {

value = newValue;

next = newNext;

}

public static class Queue {

private int size;

private Node first;

private Node last;

public Queue() {

size = 0;

first = null;

last = null;

}

public void push(int v) {

Node newNode = new Node(v, null);

if (size == 0) {

first = last = newNode;

} else {

last.next = newNode;

last = newNode;

}

size++;

}

public boolean pop() {

boolean ret = false;

if (size > 0) {

int val = first.value;

first = first.next;

size--;

System.out.println(val);

ret = true;

}

return ret;

}

public boolean front() {

boolean ret = false;

if (size > 0) {

System.out.println(first.value);

ret = true;

}

return ret;

}

public int getSize() {

return size;

}

public void clear() {

first = null;

last = null;

size = 0;

}

public static void main(String[] args) {

Queue q = new Queue();

String s;

int n;

Scanner scan = new Scanner(System.in);

while ((s = scan.next()) != null) {

switch(s) {

case "size": System.out.println(q.getSize()); break;

case "push":

n = scan.nextInt();

q.push(n);

System.out.println("ok");

break;

case "pop":

if (q.pop() == false) {

System.out.println("error");

}

break;

case "front":

if (q.front() == false) {

System.out.println("error");

}

break;

case "clear":

q.clear();

System.out.println("ok");

break;

case "exit":

System.out.println("bye");

return;

default: break;

}

Алгоритм:

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Для этого соответствующие методы делаем логическими.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

Quaternion

09/07/2016 by Владислав Козачков

Условие

Кватернионы (от лат. quaterni, по четыре) — система гиперкомплексных чисел, образующая векторное пространство размерностью четыре над полем вещественных чисел. Обычно обозначаются символом $H$ . Предложены Уильямом Гамильтоном в 1843 году.
Кватернионы удобны для описания изометрий трёх- и четырёхмерного евклидовых пространств, и поэтому получили широкое распространение в механике. Также их используют в вычислительной математике, например, при создании трёхмерной графики.
Источник: Кватернионы — Википедия.

Код на Java:

Описание класса:

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

class Quaternion {
	private double a;
	private double b;
	private double c;
	private double d;
	
	public Quaternion() {
		a = 0;
		b = 0;
		c = 0;
		d = 0;
	}
	public Quaternion(double a) {
		this.a = a;
		b = 0;
		c = 0;
		d = 0;
	}
	public Quaternion(double a, double b, double c, double d) {
		this.a = a;
		this.b = b;
		this.c = c;
		this.d = d;
	}
	
	public Quaternion conjug() {
		return new Quaternion(a, -b, -c, -d);
	}
	public double abs() {
		return Math.sqrt(a * a  + b * b + c * c + d * d);
	}
	public Quaternion inverse() throws ArithmeticException {
		return Quaternion.divide(this.conjug(), this.abs() * this.abs());
	}
	public boolean isZero() {
		return (a == 0 && b == 0 && c == 0 && d == 0);
	}
	
	public static Quaternion sum(Quaternion a, Quaternion b) {
		return new Quaternion(a.a + b.a, a.b + b.b, a.c + b.c, a.d + b.d);
	}
	public static Quaternion sub(Quaternion a, Quaternion b) {
		return new Quaternion(a.a - b.a, a.b - b.b, a.c - b.c, a.d - b.d);
	}
	public static Quaternion mul(Quaternion a, double mult) {
		return new Quaternion(a.a * mult, a.b * mult, a.c * mult, a.d * mult);
	}
	public static Quaternion mul(Quaternion a, Quaternion b) {
		return new Quaternion(a.a * b.a - a.b * b.b - a.c * b.c - a.d * b.d,
							  a.a * b.b + a.b * b.a + a.c * b.d - a.d * b.c,
							  a.a * b.c - a.b * b.d + a.c * b.a + a.d * b.b,
							  a.a * b.d + a.b * b.c - a.c * b.b + a.d * b.a);
	}
	public static Quaternion divide(Quaternion a, double divider) throws ArithmeticException {
		if (divider == 0) throw new ArithmeticException("Zero divider");
		return new Quaternion(a.a / divider, a.b / divider, a.c / divider, a.d / divider);
	}
	public static Quaternion divide(Quaternion a, Quaternion b) throws ArithmeticException {
		if (b.isZero()) throw new ArithmeticException("Zero divider");
		return Quaternion.mul(a, b.inverse());
	}
	
	public String toString() {
		return new String(a +
						  ((b < 0)? " - " : " + ") + Math.abs(b) + "*i" +
						  ((c < 0)? " - " : " + ") + Math.abs(c) + "*j" +
						  ((d < 0)? " - " : " + ") + Math.abs(d) + "*k\n");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Quaternion {

private double a;

private double b;

private double c;

private double d;

public Quaternion() {

a = 0;

b = 0;

c = 0;

d = 0;

}

public Quaternion(double a) {

this.a = a;

b = 0;

c = 0;

d = 0;

}

public Quaternion(double a, double b, double c, double d) {

this.a = a;

this.b = b;

this.c = c;

this.d = d;

}

public Quaternion conjug() {

return new Quaternion(a, -b, -c, -d);

}

public double abs() {

return Math.sqrt(a * a + b * b + c * c + d * d);

}

public Quaternion inverse() throws ArithmeticException {

return Quaternion.divide(this.conjug(), this.abs() * this.abs());

}

public boolean isZero() {

return (a == 0 && b == 0 && c == 0 && d == 0);

}

public static Quaternion sum(Quaternion a, Quaternion b) {

return new Quaternion(a.a + b.a, a.b + b.b, a.c + b.c, a.d + b.d);

}

public static Quaternion sub(Quaternion a, Quaternion b) {

return new Quaternion(a.a - b.a, a.b - b.b, a.c - b.c, a.d - b.d);

}

public static Quaternion mul(Quaternion a, double mult) {

return new Quaternion(a.a * mult, a.b * mult, a.c * mult, a.d * mult);

}

public static Quaternion mul(Quaternion a, Quaternion b) {

return new Quaternion(a.a * b.a - a.b * b.b - a.c * b.c - a.d * b.d,

a.a * b.b + a.b * b.a + a.c * b.d - a.d * b.c,

a.a * b.c - a.b * b.d + a.c * b.a + a.d * b.b,

a.a * b.d + a.b * b.c - a.c * b.b + a.d * b.a);

}

public static Quaternion divide(Quaternion a, double divider) throws ArithmeticException {

if (divider == 0) throw new ArithmeticException("Zero divider");

return new Quaternion(a.a / divider, a.b / divider, a.c / divider, a.d / divider);

}

public static Quaternion divide(Quaternion a, Quaternion b) throws ArithmeticException {

if (b.isZero()) throw new ArithmeticException("Zero divider");

return Quaternion.mul(a, b.inverse());

}

public String toString() {

return new String(a +

((b < 0)? " - " : " + ") + Math.abs(b) + "*i" +

((c < 0)? " - " : " + ") + Math.abs(c) + "*j" +

((d < 0)? " - " : " + ") + Math.abs(d) + "*k\n");

}

Стандартное определение

Кватернионы можно определить как формальную сумму a + bi + cj + dk, где a, b, c, d — вещественные числа, а i, j, k — мнимые единицы со следующим свойством: i² = j² = k² = ijk = −1.
Таким образом, таблица умножения базисных кватернионов — 1, i, j, k — выглядит так:

×	1	i	j	k
1	1	i	j	k
i	i	-1	k	-j
j	j	-k	-1	i
k	k	j	-1	-1

Сопряжение

Для кватерниона q сопряжённым называется:
$conj(q) = a - bi - cj - dk$

Модуль

Так же, как и для комплексных чисел,
$abs(q) = sqrt(q*conj(q)) = sqrt(a^2 + b^2 + c^2 + d^2)$
называется модулем q.

Обращение умножения (деление)

Кватернион, обратный по умножению к q, вычисляется так:
$q^-1 = conj(q)/abs(q)^2$ .

Основная программа:

class Main {
	public static void main (String[] args) {
		Quaternion qt1 = new Quaternion();
		Quaternion qt2 = new Quaternion(5);
		Quaternion qt3 = new Quaternion(1, 2, 3, 4);
		Quaternion qt4 = new Quaternion(0.1, 1.4, -2.5, -1.7);
		if (!qt1.isZero()) {
			System.out.print(Quaternion.sum(qt3, qt4));
		} else {
			System.out.print(Quaternion.mul(qt3, qt4));
		}
		do {
			qt2 = Quaternion.sub(qt2, qt3);
			System.out.print(qt2);
			System.out.print(qt2.conjug());
			System.out.print(qt2.inverse());
		} while (qt2.isZero());
		try {
			System.out.print(Quaternion.divide(qt3, qt4));
		} catch (ArithmeticException e) {
			System.out.print(e.getMessage());
		}
		System.out.print(Quaternion.mul(qt3, 17.2));
	}
}

class Main {

public static void main (String[] args) {

Quaternion qt1 = new Quaternion();

Quaternion qt2 = new Quaternion(5);

Quaternion qt3 = new Quaternion(1, 2, 3, 4);

Quaternion qt4 = new Quaternion(0.1, 1.4, -2.5, -1.7);

if (!qt1.isZero()) {

System.out.print(Quaternion.sum(qt3, qt4));

} else {

System.out.print(Quaternion.mul(qt3, qt4));

}

do {

qt2 = Quaternion.sub(qt2, qt3);

System.out.print(qt2);

System.out.print(qt2.conjug());

System.out.print(qt2.inverse());

} while (qt2.isZero());

try {

System.out.print(Quaternion.divide(qt3, qt4));

} catch (ArithmeticException e) {

System.out.print(e.getMessage());

}

System.out.print(Quaternion.mul(qt3, 17.2));

}

Ход выполнения

При выполнении происходит проверка функций класса: логических, арифметических, построения объектов, производных от исходного (таких, как сопряженное и обратное значение), функции строкового отображения объекта.

Вывод программы:

11.600000000000001 + 6.5*i + 6.8*j - 10.499999999999998*k

4.0 - 2.0*i - 3.0*j - 4.0*k

4.0 + 2.0*i + 3.0*j + 4.0*k

0.08888888888888888 + 0.04444444444444444*i + 0.06666666666666665*j + 0.08888888888888888*k

-1.026102610261026 - 0.5490549054905489*i - 0.5580558055805579*j + 1.017101710171017*k

17.2 + 34.4*i + 51.599999999999994*j + 68.8*k

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

Layout change

07/07/2016 by Владислав Козачков

Условие

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

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

На вход подается некоторая строка текста, который нужно изменить.

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

Вывести исходную строку текста, «перепечатанную» в другой раскладке.

Примечание: Данная программа работает с русской и английской раскладкой клавиатуры. Весь текст, в какой бы из этих расскладок не был введен, перепечатывается в другой раскладке: русский — в английский, английский — в русский.

Тесты :

Ввод	Вывод
Руддщб цщкдв!	Hello, world!
Ghbdtn? vbh!	Привет, мир!
Шэь пдфв ещ ыуу нщг	I’m glad to see you
Rfr ltkf&	Как дела?
ащк (ште ш = 0ж ш Б тж ш++)	for (int i = 0; i < n; i++)

Код на Java:

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

class Main {
	public static void main (String[] args) {
		String eng = "qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,@#$^&\"№;:?";
		String rus = "йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?\"№;:?@#$^&";
		Scanner scan = new Scanner(System.in);
		String word = new String();
		word = scan.nextLine();
		StringBuffer word1 = new StringBuffer();
		for (int i = 0; i < word.length(); i++) {
			int k = rus.indexOf(word.charAt(i));
			if (k != -1) {
				word1.append(eng.charAt(k));
			} else {
				word1.append(word.charAt(i));
			}
		}
		word = word1.toString();
		System.out.print(word);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

String eng = "qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,@#$^&\"№;:?";

String rus = "йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?\"№;:?@#$^&";

Scanner scan = new Scanner(System.in);

String word = new String();

word = scan.nextLine();

StringBuffer word1 = new StringBuffer();

for (int i = 0; i < word.length(); i++) {

int k = rus.indexOf(word.charAt(i));

if (k != -1) {

word1.append(eng.charAt(k));

} else {

word1.append(word.charAt(i));

}

word = word1.toString();

System.out.print(word);

}

Алгоритм:

В памяти хранятся строки соответствия. Каждому символу одной строки соответствует символ другой строки на той же позиции, но соответствующий символ — из другой раскладки.

String eng = "qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,@#$^&\"№;:?";
String rus = "йцукенгшщзхъфывапролджэячсмитьбю.ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ,qwertyuiop[]asdfghjkl;'zxcvbnm,./QWERTYUIOP{}ASDFGHJKL:\"ZXCVBNM<>?\"№;:?@#$^&";

Вводим строку, которую требуется заменить. Измененный вариант будет записываться в другой, временной строке.

String word = new String();
word = scan.nextLine();
StringBuffer word1 = new StringBuffer();

String word = new String();

word = scan.nextLine();

StringBuffer word1 = new StringBuffer();

Далее проходим по всей введенной строке. Если некоторый текущий символ можно заменить, записываем измененный символ. Если нет, то записываем исходный.

for (int i = 0; i < word.length(); i++) {
	int k = rus.indexOf(word.charAt(i));
	if (k != -1) {
		word1.append(eng.charAt(k));
	} else {
		word1.append(word.charAt(i));
	}
}

for (int i = 0; i < word.length(); i++) {

int k = rus.indexOf(word.charAt(i));

if (k != -1) {

word1.append(eng.charAt(k));

} else {

word1.append(word.charAt(i));

}

А в конце переписываем исходную строку и выводим ее:

word = word1.toString();
System.out.print(word);

word = word1.toString();

System.out.print(word);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 19. The degree of symmetry

07/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Степенью симметрии натурального числа назовём количество пар его десятичных цифр, в которых цифры совпадают и расположены симметрично относительно середины десятичной записи этого числа. Если некоторая цифра стоит посередине десятичной записи, её тоже нужно учитывать в паре с ней самой. Найти степень симметрии числа [latex]n[/latex].

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

Одно натуральное число [latex]n < 2\cdot10^9.[/latex]

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

Вывести степень симметрии числа [latex]n[/latex].

Тесты:

Ввод	Вывод
123322	2
100	1
1010	0
1234321	4
1234567891	1

Код на Java:

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

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int i = 0;
		int j = 0;
		int num[] = new int[10];
		if (n == 0) {
			num[0] = 0;
		} else {
			while (n > 0) {
				num[j] = n % 10;
				n /= 10;
				j++;
			}
			j--;
		}
		int count = 0;
		while (i <= j) {
			if (num[i] == num[j]) count++;
			i++;
			j--;
		}
		System.out.print(count);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

int i = 0;

int j = 0;

int num[] = new int[10];

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

}

Алгоритм:

Вначале считываем число. Затем раскладываем его по цифрам внутри массива (в обратном порядке, но для нашей задачи порядок цифр значения не имеет):

if (n == 0) {
	num[0] = 0;
} else {
	while (n > 0) {
		num[j] = n % 10;
		n /= 10;
		j++;
	}
	j--;
}

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

Затем подсчитываем собственно степень симметрии, двигаясь внутри массива от крайних цифр к центру, а после выводим результат:

int count = 0;
while (i <= j) {
	if (num[i] == num[j]) count++;
	i++;
	j--;
}
System.out.print(count);

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 5082. Degrees of vertices

06/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

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

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

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

Выведите $N$ чисел – степени всех вершин.

Тесты :

Ввод	Вывод
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 1
3 0 1 0 1 1 1 0 1 0	1 4 1
5 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1	6 1 6 1 6
5 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1	1 3 4 3 3
5 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0	4 1 4 1 4
5 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0	3 3 2 1 1

Код на Java:

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N;
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		String strout = new String();
		for (int i = 0; i < N; i++) {
			int counter = 0;
			int x;
			for (int j = 0; j < N; j++) {
				x = scan.nextInt();
				if (x > 0) counter += (i == j? 2 : 1);
			}
			strout += counter + " ";
		}
		System.out.print(strout);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int N;

Scanner scan = new Scanner(System.in);

N = scan.nextInt();

String strout = new String();

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

int counter = 0;

int x;

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

x = scan.nextInt();

if (x > 0) counter += (i == j? 2 : 1);

}

strout += counter + " ";

}

System.out.print(strout);

}

Алгоритм:

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной $counter$ , изначально $0$ . По очереди считываем все ее элементы и, если текущий элемент равен $1$ , то прибавляем степени $2$ , если элемент принадлежит главной диагонали (так как тогда это ребро является петлей, а при подсчете степени ребро-петля учитывается дважды), иначе прибавляем $1$ . Формируем строку-результат и выводим её.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 109. Numeration

05/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Для нумерации $M$ страниц книги использовали $N$ цифр. По заданному $N$ вывести $M$ или $0$ , если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число $N$ . В книге не более $1001$ страницы.

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

Искомое количество страниц.

Тесты :

N	8	21	22	113	999	1001
M	8	15	0	61	369	0

Код на Java:

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

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = 1;
		while (true) {
			if (m < 10) {	//1 digit
				n -= 1;
			} else if (m < 100) {	//2 digits
				n -= 2;
			} else if (m < 1000) {	//3 digits
				n -= 3;
			} else {	//4 digits
				n -= 4;
			}
			if (n < 0) {
				m = 0;
			}
			if (n <= 0) {
				break;
			}
			m++;
		}
		System.out.print(m);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

int m = 1;

while (true) {

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

if (n < 0) {

m = 0;

}

if (n <= 0) {

break;

}

m++;

}

System.out.print(m);

}

Ход решения:

Принимаем исходное количество страниц $M$ как 1.
В зависимости от $M$ , вычитаем необходимое количество цифр из $N$ :

if (m < 10) {	//1 digit
	n -= 1;
} else if (m < 100) {	//2 digits
	n -= 2;
} else if (m < 1000) {	//3 digits
	n -= 3;
} else {	//4 digits
	n -= 4;
}

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

Далее проверяем условие выхода. Если при этом мы получили отрицательное значение $N$ , значит, исходное его значение также было неверным, тогда количеству страниц присваиваем 0:

if (n < 0) {
	m = 0;
}
if (n <= 0) {
	break;
}

if (n < 0) {

m = 0;

}

if (n <= 0) {

break;

}

Выйдя из цикла, выводим $M$ :

System.out.print(m);

28	System.out.print(m);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 4. Two circles

01/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Определить количество точек пересечения двух окружностей.

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

Шесть чисел: x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 — их радиусы. Все числа — действительные, не превышают 10⁹, заданы не более чем с тремя знаками после запятой.

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

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Тесты:

X₁	Y₁	R₁	X₂	Y₂	R₂	N
0	0	5	5	0	1	2
0	0	5	0	0	6	1
0	1	6	0	3	6	2

Код на Java:

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		double x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();
		double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();
		double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		double rads = r1 + r2;
		if (range == 0 && r1 == r2) {
			System.out.print(-1);
		}
		else if (range == rads || range + r1 == r2 || range + r2 == r1) {
			System.out.print(1);
		}
		else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
			System.out.print(0);
		}
		else {
			System.out.print(2);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

double x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();

double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

double rads = r1 + r2;

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

else {

System.out.print(2);

}

Ход решения:

Высчитываем расстояние между центрами окружностей по формуле: $Range$ = $\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}$ . Вычисление в одну строку:

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

1	double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

Далее рассчитываем суму радиусов окружностей.
Если центры совпадают (Range = 0) и длины радиусов равны, значит, совпадают и окружности:

if (range == 0 && r1 == r2) {
	System.out.print(-1);
}

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

Если расстояние между окружностями равно сумме радиусов, окружности имеют одну общую точку, касаясь друг друга снаружи. Также одна из окружностей может лежать внутри другой и касаться ее изнутри:

else if (range == rads || range + r1 == r2 || range + r2 == r1) {
	System.out.print(1);
}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

Если расстояние между окружностями превышает сумму радиусов, это значит, что они не пересекаются. Также одна окружность может лежать внутри другой, но не касаться ее:

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
	System.out.print(0);
}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

В остальных случаях окружности пересекаются и имеют две общие точки:

else {
	System.out.print(2);
}

else {

System.out.print(2);

}

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olymp 57. Butterfly-orderly

30/06/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Школьники, идя из дому в школу или наоборот – со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.

Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами $X_1$ , $Y_1$ , бабочка перелетала в точку с координатами $X_2$ , $Y_2$ , $Z_2$ , расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.

Какую оптическую силу $D$ имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты $X_1$ , $Y_1$ , обертки от конфетки. Во второй – 3 числа: координаты $X_2$ , $Y_2$ , $Z_2$ бабочки в момент сжигания обертки.

Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз $D$ , вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

Тесты:

$X_1$	$Y_1$	$X_2$	$Y_2$	$Z_2$	$D$
10	20	10	20	100	0.010
10	30	10	30	50	0.020
10	30	20	40	110	0.009

Код на Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int x1 = scan.nextInt(), y1 = scan.nextInt();
        int x2 = scan.nextInt(), y2 = scan.nextInt(), z2 = scan.nextInt();
        double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);
        System.out.print(D);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner scan = new Scanner(System.in);

int x1 = scan.nextInt(), y1 = scan.nextInt();

int x2 = scan.nextInt(), y2 = scan.nextInt(), z2 = scan.nextInt();

double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

System.out.print(D);

}

Ход решения:

Вычисляем оптическую силу линзы D по формуле $D = \frac{1}{f}$ , где f – расстояние между бабочкой и обёрткой. вычисляем его по формуле: $f$ = $\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2+Z_2^2}$ . Вычисление в одну строку:

double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

1	double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

Далее выводим на экран:

System.out.print(D);

1	System.out.print(D);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com