e-olymp 662. Налог

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

«Курс валюты Зимбабве опустился накануне до рекордно низкого уровня — $1.2$ млрд. зимбабвийских долларов за один доллар США»
(Новости от $07.06.2009$ )

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

Один из налогов на доходы составляет $1$. Напишите программу, которая по введенному числу $D$ (величине дохода гражданина) вычислит этот налог.

При этом применяются следующие правила округления:

  1. Если налог выражается целым числом, то он не округляется.
  2. Если налог выражается дробным числом, то он округляется в сторону большего целого (в пользу государства).

Входные данные
Вводится одно число $D$ (натуральное,$10^{5}⩽D<10^{200}$ ) – величина дохода гражданина.
Выходные данные
Выведите одно натуральное число – величину налога.
Тесты

Входные данные Выходные данные
12345600
123456
158874554
1588746
1000001
10001
555555
5556

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

Решение задачи
Так как у нас по условию $10^{200}$ нам нужно использовать String, ибо в long такое число не поместится. Поэтому, есть строка, каждый символ которой, это цифра. Округляем по условию, то есть если последние два символа — нули, то просто выдаем подстроку, без последних двух символов ( s.substring(0, s.length() - 2) ). В любом случае, нужно округлять вверх, для этого, к третей с конца цифре добавляем один. Если цифра была $9$, то она станет $0$, а к следующей по возрастанию цифре применим такое-же действие. Если текущая цифра последняя, то нужно добавить перед ней еще единицу.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 7340. Поле-чудес

Задача

Петрик і Марічка захопились грою поле-чудес: Марічка записує слово, що складається з великих англійських букв, а Петрик старається розпізнати його, причому відгадана буква відкривається на всіх позиціях, де вона міститься. За яку найменшу кількість ходів Петрик зможе відгадати задане слово.

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані Вихідні дані
[latex]GOOGLE[/latex] [latex]4[/latex]
[latex]ALBUS[/latex] [latex]5[/latex]
[latex]OOO[/latex] [latex]1[/latex]

Код програми

Рішення завдання

Створимо місце для слова і прочитаємо його,далі для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква..

Код програми з множиною

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

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

Задача

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, 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

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

Решение

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

Ссылки

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

e-olymp 1119. Пирамида из символов

Задача

Вася хочет напечатать на принтере пирамиду из какого-то символа высоты $h$. Напишите программу, которая поможет ему в этом, не забывая, что программа должна быть «экономически выгодной», т.е печатать наименьшее количество символов.

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

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

В одной строке задан сначала символ, при помощи которого должна быть напечатана пирамида, а затем через пробел натуральное число, задающее высоту пирамиды $h (h ≤ 50)$.

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

В первой сроке выведите общее количество напечатанных «печатных» символов а ниже саму пирамиду.

Тесты

Входные данные Выходные данные
A 3 12
A
AAA
AAAAA
M 9 117
M
MMM
MMMMM
MMMMMMM
MMMMMMMMM
MMMMMMMMMMM
MMMMMMMMMMMMM
MMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMM

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

Решение

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

Ссылки

e-olymp
Ideone

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

Задача

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

Универсальные идентификаторы ресурсов (или 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

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

Решение

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

Ссылки

Ideone
решение e-olymp

Шифровка

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

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

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

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

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

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

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

Решение

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

AL6

Условие

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

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

$latex ({([])})$

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

Yes.

Код

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

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

АА14

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

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

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

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

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

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

Код

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

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

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

e-olymp 2165. Лишние пробелы

Задача

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

  • он находится в самом начале строки, до самого первого слова;
  • он находится в конце строки, после самого последнего слова;
  • несколько пробелов расположены между двумя словами (проще говоря, если слова разделены более чем одним пробелом, тогда все пробелы кроме одного — лишние).

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

Дана строка s. Строка содержит только латинские буквы и пробелы.

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

Строка без лишних пробелов.

Тесты

Входные данные Выходные данные
1 «Alexandr      Sergeevich   Pushkin» «Alexandr Sergeevich Pushkin»
2 «JohnSnow» «JohnSnow»
3 » Mr    Charlie       Chaplin » «Mr Charlie Chaplin»
4 «Mechnikov    University» «Mechnikov University»
5 «Daenerys          Targaryen» «Daenerys Targaryen»

Код

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

Решение

Вводим строку s, которая содержит латинские буквы и пробелы. Используем метод replaceAll()  для удаления лишних пробелов. Чтоб не удалить последний оставшийся пробел используем regex " +", " " . «Прочитать» его по-русски можно так: " +"  — выделить 1 или больше пробелов до символа, не являющимся пробелом и " "  — заменить выделенную последовательность на 1 пробел. Проверяем символы на концах строки на наличие пробела. Перезаписываем подстроку без пробелов в строку s.

Затем выводим полученную строку.

АА14

Задача

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

Тесты

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

Решение

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

Пояснения

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