Java → Разбор Chandelier 1
05 май
Всем привет! Так как месяц java еще не закончился, решил сделать разбор на эту задачу, так как она очень красиво решается использованием полиморфизма...
Для чего вообще нужен полиморфизм? по большей части для того, чтобы избавиться от не нужных проверок... В нашей задаче мы имеем два типа элементов: это простой элемент и кольцо... Для каждого из них нам необходимо посчитать необходимый минимальный стек и, если для каждого элемента проверять является ли он точечным элементом или кольцом, это будет занимать больше времени... Да и выглядеть в коде это будет не очень красиво...
Для начала, определим основной интерфейс:
interface Item{
public abstract int getStackSize();
public abstract String getText();
}
Как видим любой унаследованный класс должен будет реализовывать два метода:
- getStackSize() - должен возвращать минимальный размер стека, необходимый для построения элемента.
- getText() - должен выдавать итоговую строку - порядок выполнения.
В нашей программе будут два класса, наследующиеся от Item класса. Это PointItem и RingItem.
Класс для точечного элемента PointItem очень прост... Его метод getStackSize() всегда возвращает 1, так элемент там только один, а getText() возвращает соответственно "а".
Теперь рассмотрим класс RingItem:
Во-первых, в классе есть три переменных:
1. int size - количество элементов в кольце.
2. Item[] items - элементы лежащие в кольце.
3. int offset - номер элемента, с которого надо начинать строить кольцо для оптимального использования стека.
Во-вторых, класс имеет один конструктор, который принимает количество элементов в нем и парсит входную строку... Кстати, входная строка хранится в классе Main в виде статичных массива символов и поинтера на последний элемент... Почему на последний? Потому что в конце у нас остается 1 элемент и от него проще построить всю структуру... Итак, получаем следующую реализацию конструктора:
public RingItem(int t){
items = new Item[t];
size = t;
for (int i = 0; i < t; i++)
if (Main.input[--Main.pointer] == 'a') items[t-i-1] = new PointItem();
else items[t-i-1] = new RingItem(Main.input[Main.pointer]-'0');
}
Ну и перейдем к основным методам. Во-первых, мы выполняем функцию getStackSize(), где сначала находим рекурсивно стеки всех текущих элементов, а затем обычным перебором находим оптимальный offset. Получается вот такой вот метод:
public int getStackSize() {
int[] stacks = new int[size];
for (int i = 0; i < size; i++)
stacks[i] = items[i].getStackSize();
int min = Integer.MAX_VALUE;
for (int i = 0; i < size; i++){
int k = 0;
for (int j = 0; j < size; j++)
k = Math.max(k, stacks[(i+j)%size]+j);
if (k < min) {min = k; offset = i;}
}
return min;
}
Во-вторых, вызываем метод getText, который для найденного отступа возващает нужную строку... Опять же рекурсивно:
public String getText() {
StringBuffer s = new StringBuffer("");
for (int i = 0; i < size; i++)
s.append(items[(offset+i)%size].getText());
s.append(Integer.toString(size));
return s.toString();
}
В итоге при готовой структуре мы получаем вполне красивый код в Main классе:
public class Main{
public static char[] input;
public static int pointer = 0;
public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("chandelier.in"));
PrintWriter out = new PrintWriter(new File("chandelier.out"));
input = in.readLine().toCharArray();
pointer = input.length;
RingItem item = new RingItem(1);
out.println(item.getStackSize());
String res = item.getText();
out.print(res.substring(0, res.length()-1));
out.close();
}
}