Шифровка

28/11/2017 by Валентин Лавриненко

Условие задачи

Взята с сайта.
Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.
Известно, что Штирлиц шифрует текст следующим образом:

1)Убирает все пробелы и знаки препинания.
2)Заменяет все подряд идущие одинаковые буквы на одну такую букву.
3)Многократно вставляет в произвольное место текста две одинаковых буквы.

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

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

Решение с использованием функционала класса String

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		ArrayList arr = new ArrayList();
		String str,str2;
		String empty = "";
		Scanner input = new Scanner(System.in);
		str = input.nextLine();
		for(int i = 0;i < str.length(); i++)
		{
			str2 = empty;
			str2 += str.charAt(i);
			if(i == str.length()-1)
				arr.add(str2);
			else
			{
				if(str.charAt(i) == str.charAt(i+1))
					i++;
				else arr.add(str2);
			}
		}
		for(int i = 0;i < arr.size();i++)
		{
			System.out.print(arr.get(i));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

ArrayList arr = new ArrayList();

String str,str2;

String empty = "";

Scanner input = new Scanner(System.in);

str = input.nextLine();

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

{

str2 = empty;

str2 += str.charAt(i);

if(i == str.length()-1)

arr.add(str2);

else

{

if(str.charAt(i) == str.charAt(i+1))

i++;

else arr.add(str2);

}

for(int i = 0;i < arr.size();i++)

{

System.out.print(arr.get(i));

}

Решение с использованием функционала структуры данных ArrayList

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		ArrayList arr = new ArrayList();
		Scanner input = new Scanner(System.in);
		String str,str2;
		String empty = "";
		str = input.nextLine();
		for(int i = 0;i<str.length();i++)
		{
			str2 = empty;
			str2 += str.charAt(i);
			arr.add(str2);
		}
		for(int i = 0;i < arr.size(); i++)
		{
			if(i != arr.size()-1)
			{
				if(arr.get(i).equals(arr.get(i+1)))
				{
					arr.remove(i);
					arr.remove(i);
					i--;
				}
			}
		}
		for(int i = 0;i < arr.size();i++)
		{
			System.out.print(arr.get(i));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

ArrayList arr = new ArrayList();

Scanner input = new Scanner(System.in);

String str,str2;

String empty = "";

str = input.nextLine();

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

{

str2 = empty;

str2 += str.charAt(i);

arr.add(str2);

}

for(int i = 0;i < arr.size(); i++)

{

if(i != arr.size()-1)

{

if(arr.get(i).equals(arr.get(i+1)))

{

arr.remove(i);

i--;

}

for(int i = 0;i < arr.size();i++)

{

System.out.print(arr.get(i));

}

Решение

Записываем строку в переменную типа $latex String$. Записываем ее в $latex ArrayList$ посимвольно. В следующем цикле добавляем проверку на индекс текущего элемента чтобы не выйти за пределы списка и проверяем совпадают ли ближайшие 2 символа, если да то удаляем их, если нет то переходим к следующему шагу цикла. По его окончанию выводим элементы списка.
Пример решения со строками на ideone.
Пример решения с списком на ideone.

АА14

21/11/2017 by Валентин Лавриненко

Условие задачи

В заданной строке удалить первый символ ‘.’, который найдется в строке.

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

Строка с точками либо без них.

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

Строка без первой точки.

Код

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		String str = input.nextLine();
		int index = str.indexOf('.');
		if(index>=0)
		{
			String part1 = str.substring(0,str.indexOf('.'));
			String part2 = str.substring(str.indexOf('.')+1,str.length());
			System.out.println(part1+part2);
		} else System.out.println("No dots");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner input = new Scanner(System.in);

String str = input.nextLine();

int index = str.indexOf('.');

if(index>=0)

{

String part1 = str.substring(0,str.indexOf('.'));

String part2 = str.substring(str.indexOf('.')+1,str.length());

System.out.println(part1+part2);

} else System.out.println("No dots");

}

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

Объявляем переменную str и присваиваем ей значение, при помощи метода String.indexOf() находим индекс первого вхождения символа ‘.’ . Разделяем строку на две части: первая до точки, вторая — после. Выводим на экран сумму данных строк.

Работу программы можно увидеть на сайте ideone.

А136л

23/08/2017 by Валентин Лавриненко

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

Даны натуральное число , действительные числа $latex a_1,\cdots,a_n$ . Вычислить: $latex |a_1*a_2*\cdots*a_n|$ .

Тесты


4	5	-3	2	1	—	—	—	—	5.477225575051661
5	2	7	4	3	5	—	—	—	28.982753492378876
3	4	4	0	—	—	—	—	—	0
5	3	8	6	2.8	1.3	—	—	—	22.894541

Код

import java.util.*;
import java.lang.*;
 
class Task4
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		double p=1;
		for(;n>0;n--) 
            p*=input.nextDouble();
		System.out.println(Math.sqrt(Math.abs(p)));
	}
}

import java.util.*;

import java.lang.*;

class Task4

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

double p=1;

for(;n>0;n--)

p*=input.nextDouble();

System.out.println(Math.sqrt(Math.abs(p)));

}

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

Объявляем переменную (количество элементов — это целое число, поэтому используем тип int) и переменную $latex p$ (произведение), она может быть вещественной, поэтому выбираем тип double.

В цикле for считываются элементы $latex a_1,\cdots,a_n$ , где вычисляется их произведение.

После цикла вычисляется корень из модуля произведений элементов.

Посмотреть, как работает программа можно на сайте ideone.
Задача была переделана из данного решения.

Ю4.35

23/08/2017 by Валентин Лавриненко

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

Совместная работа. Известно время $latex t_1,t_2,\cdots,t_n$ , за которое некоторую работу может выполнить каждый из рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)?

Тесты

Количество рабочих n.	Время t каждого рабочего, требуемое для выполнения некоторой работы.	Время совместной работы.
3	5 7 9	2.2
4	7 9 11 23	2.6
4	1 2 3 4	0.5
5	3 1 5 2 3	0.4

Код

import java.util.*;
import java.lang.*;
 
class Task5
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		double workingTime, sum = 0;
		for(;n>0;n--) 
		{
			workingTime=input.nextDouble();
			sum+=1/workingTime;
		}
		System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);
	}
}

import java.util.*;

import java.lang.*;

class Task5

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

double workingTime, sum = 0;

for(;n>0;n--)

{

workingTime=input.nextDouble();

sum+=1/workingTime;

}

System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);

}

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

В данной задаче нам нужно найти время, за которое рабочих выполнят какую-то совместную работу. В задаче не указан общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: $latex \frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\cdots+\frac{1}{t_n}}$ .

В программе используем один цикл for в котором задаем значение переменной workingTime и суммируем объем выполняемой работы за час для каждого шага цикла (для каждого рабочего). После завершения цикла получаем объем работы выполняемой всеми работниками вместе за час. Делим общий объем работы на объем работы за час и получаем искомую величину.

Посмотреть, как работает программа можно на сайте ideone.
Задача была решена на основе данного решения.

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

java@Cat

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

Tag Archives: алгоритмы

Шифровка

Условие задачи

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

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

Решение с использованием функционала класса String

Решение с использованием функционала структуры данных ArrayList

Решение

АА14

Условие задачи

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

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

Код

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

А136л

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

Тесты

Код

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

Ю4.35

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

Тесты

Код

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

e-olymp 3966. An ardent collector of butterflies

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки: