e-olymp 9407. Слияние строк

03/12/2020 by Даниил Кулык

Задача

Имеются две строки $A$ и $B$.

Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.

Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.

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

Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.

Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.

Гарантируется, что обе строки содержат только строчные латинские буквы.

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

Выведите одну строку $C$.

Тесты

№	Входные данные	Выходные данные
1.	compressing single	compressingle
2.	can you	canyou
3.	compressiondoneright doner	compressiondoneright
4.	details tail	details
5.	essential code	essentialcode

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static boolean check(StringBuilder a, StringBuilder b) {
		if(a.length()==b.length()) {
			for(int i = 0; i < a.length(); i++) {
				if(a.charAt(i) != b.charAt(i)) return false;
			}
		}
	return true;
	}
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m, z;
		StringBuilder a = new StringBuilder();
		StringBuilder b = new StringBuilder();
		StringBuilder c = new StringBuilder();
		Scanner in = new Scanner(System.in);
    	a.append( in.nextLine());
    	b.append( in.nextLine());
    	StringBuilder d = new StringBuilder(b);
    	n = b.length();
    	m = a.length();
    	c = new StringBuilder(a.substring(m - n, m));
    	if(a.toString().contains(b.toString()) != true) {
        	for (int i = 1; i<=n && check(b,c) != true; i++) {
            	b.delete(n - i,m);
            	c.delete(0, 1);
        	}
        	z = c.length();
        	d.delete(0,z);
        	System.out.print(a);
        	System.out.print(d);
    	}
    	else System.out.print(a);
    	System.exit(0);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static boolean check(StringBuilder a, StringBuilder b) {

if(a.length()==b.length()) {

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

if(a.charAt(i) != b.charAt(i)) return false;

}

return true;

}

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

{

int n, m, z;

StringBuilder a = new StringBuilder();

StringBuilder b = new StringBuilder();

StringBuilder c = new StringBuilder();

Scanner in = new Scanner(System.in);

a.append( in.nextLine());

b.append( in.nextLine());

StringBuilder d = new StringBuilder(b);

n = b.length();

m = a.length();

c = new StringBuilder(a.substring(m - n, m));

if(a.toString().contains(b.toString()) != true) {

for (int i = 1; i<=n && check(b,c) != true; i++) {

b.delete(n - i,m);

c.delete(0, 1);

}

z = c.length();

d.delete(0,z);

System.out.print(a);

System.out.print(d);

}

else System.out.print(a);

System.exit(0);

}

Решение

В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.

Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией contains(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 4764. Степени вершин

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

Задача

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

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

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

Выведите [latex]n[/latex] чисел — степени всех вершин.

Тесты

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

Код задачи

import java.util.*;
public class Main
{
  public static void main(String[] args)

  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    //массив, в котором содержатся степени вершин
    int deg[] = new int[n];
    //Чтение матрицы смежности
    //и если есть ребро, то увеличиваем степень на 1
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j < n; j++)

		 {
			int value = in.nextInt();
			if (value == 1)
    		{
    			deg[i]++;
    		}
		 }
    }
    //вывод результата
    for(int i = 0; i < n; i++)
    {
      System.out.println(deg[i]);     
    }
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

//массив, в котором содержатся степени вершин

int deg[] = new int[n];

//Чтение матрицы смежности

//и если есть ребро, то увеличиваем степень на 1

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

{

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

{

int value = in.nextInt();

if (value == 1)

{

deg[i]++;

}

//вывод результата

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

{

System.out.println(deg[i]);

}

Решение

В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]

Ссылки

Задача на e-olymp

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

e-olymp 44. Единицы

27/12/2018 by Валерия Ларикова

Задача

В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

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

Тесты

#	Входные данные	Выходные данные
1	7	6
2	22	10
3	90	13
4	157	16
5	985	21

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
 
class Main
{
	public static int max = 5001;
	static int [] x = new int[max];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k;
		x[1] = 1;
		x[2] = 2;
		for (int i = 3; i <= n; i++) {
			x[i] = x[i-1]+1;
			for (int j = 2; j <= Math.sqrt(n); j++) {
				if(i % j == 0) {
					k = x[j] + x[i/j];
					if( k < x[i]) x[i] = x[j] + x[i/j];
				}
			}
		}
		System.out.println(x[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

public static int max = 5001;

static int [] x = new int[max];

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k;

x[1] = 1;

x[2] = 2;

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

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

for (int j = 2; j <= Math.sqrt(n); j++) {

if(i % j == 0) {

k = x[j] + x[i/j];

if( k < x[i]) x[i] = x[j] + x[i/j];

}

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

}

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

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

java@Cat

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

Tag Archives: поиск

e-olymp 9407. Слияние строк

Задача

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

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

Тесты

Код

Решение

Ссылки

e-olymp 4764. Степени вершин

Задача

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

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

Тесты

Код задачи

Решение

Ссылки

e-olymp 44. Единицы

Задача

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

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

Тесты

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

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

Ссылки