e-olymp 1080. Анаграмматическое расстояние

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

Задача

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно $6$, так как нужно удалить все буквы. (Любое слово, в том числе и пустая строка, являются анаграммой само к себе.)

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

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

В первой строке задано положительное целое число $N$ (не превышающее $60000$), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего $2N$ последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

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

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

Тесты

Входные данные	Выходные данные
4 crocus succor dares seared empty smell lemon	Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
3 dog god cat dog dragon fly	Case #1: 0 Case #2: 6 Case #3: 9
1 cow	Case #1: 3
1 memory moratory	Case #1: 6

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main (String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int ABC_SIZE = 26;
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int[] counters = new int[ABC_SIZE];
			String firstWord = br.readLine();
			for (int j = 0; j < firstWord.length(); j++) {
				counters[firstWord.charAt(j) - 'a']++;
			}
			String secondWord = br.readLine();
			for (int j = 0; j < secondWord.length(); j++) {
				counters[secondWord.charAt(j) - 'a']--;
			}
			int matchingLetters = 0;
			for (int k = 0; k < ABC_SIZE; k++) {
				matchingLetters += Math.abs(counters[k]);
			}
			System.out.println("Case #" + (i + 1) + ":  " + matchingLetters);
		}
		
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

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

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

final int ABC_SIZE = 26;

int n = Integer.parseInt(br.readLine());

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

int[] counters = new int[ABC_SIZE];

String firstWord = br.readLine();

for (int j = 0; j < firstWord.length(); j++) {

counters[firstWord.charAt(j) - 'a']++;

}

String secondWord = br.readLine();

for (int j = 0; j < secondWord.length(); j++) {

counters[secondWord.charAt(j) - 'a']--;

}

int matchingLetters = 0;

for (int k = 0; k < ABC_SIZE; k++) {

matchingLetters += Math.abs(counters[k]);

}

System.out.println("Case #" + (i + 1) + ": " + matchingLetters);

}

Решение

Создадим массив на $26$ элементов, соответствующих буквам латинского алфавита. Для каждой буквы первого слова будем увеличивать на $1$ соответствующий ей элемент, а для каждой буквы второго слова — уменьшать. В конце, полученные значения будут указывать на то, сколько в первом слове «лишних» букв по сравнению со вторым (и наоборот, в случае отрицательных значений). Сумма абсолютных значений элементов массива и будет являться анаграмматическим расстоянием для указанных слов.

Ссылки

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

e-olymp 2371. Черный квадрат

25/12/2018 by Саша Рябова

Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

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

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

Первая строка содержит четыре целых числа: $m$,$n$,$s$ и $k$.
$(1 \leq m,n \leq 5000, 1 \leq s \leq \min(m,n), 1 \leq k \leq m).$
Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

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

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

Тесты

Входные данные	Выходные данные
$3$ $4$ $2$ $3$ ..**	Unique
$4$ $4$ $2$ $3$ ..	Impossible
$3$ $5$ $2$ $2$ .**..	Ambiguous
$2$ $8$ $1$ $2$ ……*.	Unique

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int k = sc.nextInt();
        String stripe = sc.next();
        int number_of_stars = 0;
        boolean end_of_stars = false;
        boolean sec_seq = false;
        String result = new String();
        for (int i = 0; !sec_seq && i < stripe.length(); i++){
            if ('*' == stripe.charAt(i)) {
                if (end_of_stars == true) sec_seq = true;
                else number_of_stars++;
            }
            else {
                if (end_of_stars == false && number_of_stars != 0){
                    end_of_stars = true;
                }
            }
        }
        if (sec_seq == true) result = "Impossible";
        else {
            if (number_of_stars == 0) {
                if (s > k-1 && s > m-k) result = "Impossible";
                else {
                    if (n > s) result = "Ambiguous";
                    else {
                        if ((s > m - k && k - 1 == s) || (s > k - 1 && m - k == s)){
                            result = "Unique";
                        }
                        else result = "Ambiguous";
                    }
                }
            }
            else {
                if (number_of_stars != s) result = "Impossible";
                else {
                    if (m == s || s == 1 || k == 1 || k == m) result = "Unique";
                    else result = "Ambiguous";
                }
            }
        }
        System.out.print(result);
    }
    
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int s = sc.nextInt();

int k = sc.nextInt();

String stripe = sc.next();

int number_of_stars = 0;

boolean end_of_stars = false;

boolean sec_seq = false;

String result = new String();

for (int i = 0; !sec_seq && i < stripe.length(); i++){

if ('*' == stripe.charAt(i)) {

if (end_of_stars == true) sec_seq = true;

else number_of_stars++;

}

else {

if (end_of_stars == false && number_of_stars != 0){

end_of_stars = true;

}

if (sec_seq == true) result = "Impossible";

else {

if (number_of_stars == 0) {

if (s > k-1 && s > m-k) result = "Impossible";

else {

if (n > s) result = "Ambiguous";

else {

if ((s > m - k && k - 1 == s) || (s > k - 1 && m - k == s)){

result = "Unique";

}

else result = "Ambiguous";

}

else {

if (number_of_stars != s) result = "Impossible";

else {

if (m == s || s == 1 || k == 1 || k == m) result = "Unique";

else result = "Ambiguous";

}

System.out.print(result);

}

Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов $*$. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

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

Ссылки

Текст задачи на e-olymp

e-olymp 3020. Семь решений в процентах

25/12/2017 by Даниил Андреев

Задача

Семь решений в процентах

Универсальные идентификаторы ресурсов (или URI) являются строками, например, такие как http://icpc.baylor.edu/icpc/, MAILTO: foo@bar.org, ftp://127.0.0.1/pub/linux, или даже просто readme.txt, что, как правило, используется для идентификации ресурсов в Интернете или на локальном компьютере. Некоторые символы зарезервированы в URI, и если зарезервированный символ является частью идентификатора, то он должен быть процент-закодирован, заменив его знаком процента, за которым следуют две шестнадцатеричные цифры, представляющие ASCII код символа. Таблица семи зарезервированные символы и их кодировка приведена ниже. Ваша задача написать программу, которая может выполнять процент-кодирование заданной строки символов.

Символ	Кодировка
» » (space)	%20
«!» (exclamation point)	%21
«$»(dollar sign)	%24
«%» (percent sign)	%25
«(» (left parenthesis)	%28
«)» (right parenthesis)	%29
«*» (asterisk)	%2a

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

Входные данные состоят из одной или нескольких строк, каждая из 1-79 символов в отдельной строке, а затем строки, содержащей только «#», что свидетельствует об окончании ввода. Символ «#» используется только как маркер окончания входных данных и не содержится в других местах во входных данных. Строка может содержать пробелы, но не в начале или в конце строки, и никогда не содержит двух или более последовательных пробелов.

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

Для каждой строки, полученной на входе, заменить каждое вхождение зарезервированного символа в таблице, приведённой выше, на его процент-кодирование, точно так, как это показано в примере, и вывести результирующую строку в отдельной строке. Ещё раз отметим, что процент-кодирование для символа «*» «%2a» (со строчной «а»), а не «%2A» (с прописной буквой «A»).

Тесты

Входные данные	Выходные данные
Happy Joy Joy! http://icpc.baylor.edu/icpc/ plain_vanilla (**) ? the 7% solution #	Happy%20Joy%20Joy%21 http://icpc.baylor.edu/icpc/ plain_vanilla %28%2a%2a%29 ? the%207%25%20solution

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

import java.util.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		String S;
		boolean loop = scan.hasNextLine(); 
		
		while (loop){
			S = scan.nextLine();
			if (S.equals("#"))	break;
			else{	
				S = S.replace ("%", "%25");
				S = S.replace (" ", "%20");
				S = S.replace ("!", "%21");
				S = S.replace ("$", "%24");
				S = S.replace ("(", "%28");
				S = S.replace (")", "%29");
				S = S.replace ("*", "%2a");
				System.out.println(S);
			}
		}
	}
}

import java.util.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

String S;

boolean loop = scan.hasNextLine();

while (loop){

S = scan.nextLine();

if (S.equals("#")) break;

else{

S = S.replace ("%", "%25");

S = S.replace (" ", "%20");

S = S.replace ("!", "%21");

S = S.replace ("$", "%24");

S = S.replace ("(", "%28");

S = S.replace (")", "%29");

S = S.replace ("*", "%2a");

System.out.println(S);

}

Решение

Создаем цикл в котором с помощью метода replace начиная с «%» (т.к. он будет использоваться в последующих кодировках) заменяем символы на их кодировку в ASCII и печатаем измененную строку. В начале каждого цикла проверяем является ли строка «#».

Ссылки

Ideone
решение e-olymp

АА14

03/07/2017 by Шостак Дмитрий

Задача

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

Тесты

№	Входная строка	Строка на выходе
1	22.11.11	2211.11
2	java.mazurok.com	javamazurok.com
3	Suspect	The dot was not found.

Решение

class StringLab
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		String mainString;
		
		mainString = input.next();
		StringBuilder changedString = new StringBuilder(mainString);
		
		int dotIndex = changedString.indexOf(".");
		
		if (dotIndex == -1) System.out.println("The dot was not found."); 
		else 
		{
			changedString.deleteCharAt(dotIndex);
			System.out.println(changedString);
		}
	}
}

class StringLab

{

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

{

Scanner input = new Scanner(System.in);

String mainString;

mainString = input.next();

StringBuilder changedString = new StringBuilder(mainString);

int dotIndex = changedString.indexOf(".");

if (dotIndex == -1) System.out.println("The dot was not found.");

else

{

changedString.deleteCharAt(dotIndex);

System.out.println(changedString);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Для редактирования строки mainString , используем класс обертку StringBuilder. Находим индекс первого вхождения точки в строке и записываем его в переменную dotIndex , после чего выполняем проверку, нашла ли функция indexOf() точку в строке. Если нет, выводим соответствующее сообщение. Иначе же выполняем удаление символа из строки по индексу с помощью функции deleteCharAt() и выводим результат в консоль.

java@Cat

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

Tag Archives: работа со строками

e-olymp 1080. Анаграмматическое расстояние

Задача

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

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

Тесты

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

Решение

Ссылки

e-olymp 2371. Черный квадрат

Условие

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

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

Тесты

Код задачи

Решение

Ссылки

e-olymp 3020. Семь решений в процентах

Задача

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

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

Тесты

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

Решение

Ссылки

АА14

Задача

Тесты

Решение

Пояснения