Задачи второго этапа конкурса IT-Planet 13/14

8 minutes read in Archive

Итак, разработчикам на Java было предоставлено 5 задач на решение. Код писался для версии Java 7. Файл с исходным кодом отправлялся на сервер, для последующей проверки.

Инструкция по участию во втором отборочном этапе

Задача 1. Observatory

Ограничение времени: 5 с

С распределением после университета вам не повезло, и вы работаете лаборантом в астрономической обсерватории где ваша задача состоит в том, чтобы считать количество метеоров, которые попали в объектив телескопа. Телескоп оснащен цифровой матрицей и вы анализируете картинку в формате PNG. Вам надоело считать метеоры на экране монитора, так-как это занимает много времени и вас постоянно клонит в сон от такой работы. Вы твердо решили автоматизировать этот процесс. Тем более, что метеоры в этой части света особенные. На картинке они всегда оставляют след шириной в один пиксел и их следы никогда не пересекаются.

На стандартный ввод вы получаете путь к картинке неизвестного размера в формате png. Фон картинки черного цвета. На картинке следы метеоров (белые отрезки) переменной длины толщиной в 1 пиксель. Известно, что отрезки никогда не пересекаются, и минимальное расстояние между ними 3 пиксела. Ваша задача выдать на стандартный вывод количество отрезков на картинке.

Для тестов можно использовать картинку:

Sample Image

Ответ: 12

Задача 2. Spy Network

Ограничение времени: 1 с

В недавно обнаруженной шпионской сети было перехвачено закодированное сообщение. Известно, что для расшифровки сообщений агенты сети использовали определенный Java-класс, в котором, среди прочего, существует метод, декодирующий сообщение и возвращающий поток-ответ (объект класса, реализующего InputStream). Чтобы сбить с верного следа, расшифрованное сообщение передается потоком-ответом не напрямую, а в описании какого-то исключения. Точно не известно, откуда и в какой форме вызывается это исключение.

На стандартный ввод программе подаются построчно следующие параметры (в соответствующем порядке): полное имя класса-дешифратора, закодированное сообщение, пароль и число-код.

В классе-дешифраторе найдите метод, удовлетворяющий следующим правилам:

Необходимо вызывать найденный метод и распечатать сообщение в стандартный вывод

Время доступа к сети ограничено, так что необходимо отфильтровать все фальшивые методы в классе-дешифраторе. Мы точно знаем, что только один метод удовлетворяет всем перечисленным выше условиям. Вызовите этот метод. Вы получите экземпляр класса “Ответ”

Один из методов экземпляра класса “Ответ” при любых входных параметрах выбросит исключение типа IOException с сообщением ненулевой длины. Эти данные и будут расшифрованным сообщением. Как обычно при работе с потоками, метод close() должен всегда вызываться последним.

Распечатайте сообщение на стандартный вывод. Для тестирования решения положите example.jar в classpath и используйте данные из примера.

ВНИМАНИЕ! Описание публичного класса должно быть первым в файле-решении

Задача 3. Annotation processor

Ограничение времени: 3 с

Работа производится в дефолтном пакете.

Файл решения должен иметь имя ConstructorProcessor.java

  1. В ConstructorProcessor.java создать value-аннотацию Constructor, принимающую в качестве значения массив строк String[], по умолчанию массив нулевой длины. Пользователь будет использовать @Constructor для проверки наличия конструктора с заданными типами параметров.

Пример использования аннотации:

@Constructor({"String", "int"})
public class Test { 
    // ... 
}

подразумевает наличие конструктора Test(String s, int i)

  1. В ConstructorProcessor.java создать публичный класс ConstructorProcessor, который является процессором аннотаций (наследуется от AbstractProcessor). ConstructorProcessor будет работать с SourceVersion.RELEASE_7 и только с созданной на первом шаге аннотацией Constructor. Процессор будет подключаться во время компиляции, в частности во время проверки задания.

Процессор проверяет, присутствует ли конструктор с заданными типами параметров в проаннотированном классе. Если конструктор с заданными в аннотации типами отсутствует, процессор сообщает компилятору об ошибке. Наличие других конструкторов не является ошибкой. Простые и полные имена типов считаются одинаковыми, так как по сути представляют одно и то же с точностью до импорта (например, java.lang.String и String). Аннотация @Constructor со значением по умолчанию ("") соответствует конструктору без параметров.

Пример 1:

@Constructor({"String", "int"})
class Test {
public Test(String str) {}
public Test(String str, int i, char c) {}
}

Компилятор с процессором ConstructorProcessor выдаст ошибку компиляции, так как конструктор с типами String и int отсутствует.

Пример 2:

@Constructor({"java.lang.String", "int"})
class Test {
public Test(String str, int i) {}
}

Здесь ошибки компиляции не будет.

Задача 4. Twitter

Ограничение времени: 60 с

Вам, как программисту одной из секретных служб министерства национальной безопасности предстоит решить задачу анализа twitter-сообщений с привязкой местности. Для отладки вы будете использовать существующий архив всех твитов с геолокацией за несколько месяцев в формате XML, кодировка UTF-8. Файл оказался слишком велик и был сжат с помощью gzip. XML в архиве корректный, но некоторые отдельные твиты слегка повреждёны: теги могут быть не закрыты, или не содержать данных. Такие записи нужно игнорировать.

Архив представляет собой дамп реальных твитов, которые выдаёт api твиттера, json перекодирован в xml и сжат. Координаты задаются действительными числами, десятичный разделитель – точка.

Формат файла с данными: В файле содержатся строки с твитами, содержащими те же поля, что и json, который отдаёт api твиттера. Каждый твит ограничен тегами <tweet></tweet>

Геоданные и текст находятся в соответствующих элементах:

<tweet>
...<geo><coordinates>Долгота</coordinates><coordinates>Широта</coordinates></geo><text>Текст</text>...
</tweet>

Всё остальное – прочая информация, имеющая отношение к твиту, автору твита и так далее для решения задачи она не важна.

Пример XML – smaller.xml.gz Задача: Выделить из архива твиты, содержащие хотя бы одно ключевое слово и которые были сделаны в области прямоугольника, заданного двумя точками x0, y0 и x1, y1. -360 < x < 360, -360 < y < 360. Вывести текст найденных твитов на стандартный вывод. Порядок вывода должен соответствовать порядку следования твитов в XML файле. ВНИМАНИЕ! Описание публичного класса должно быть первым в файле-решении Формат входных данных На стандартный ввод программе подаются построчно следующие параметры (в соответствующем порядке): путь_к_архиву в формате операционной системы c:\opt\java для windows или /opt/java для unix Координаты прямоугольника ограничивающего область поиска х0 у0 х1 у1 количество_записей_которые_нужно_найти минимум 0, максимум 20 ключевое_слово_1 ключевое_слово_2 … ключевое_слово_n Ключевых слов может и не быть, в таком случае выводятся все записи с координатами попадающими в прямоугольник Максимальное количество ключевых слов: 20 Максимальное количество записей в файле 4 000 000 Формат результата Вывести текст найденных твитов на стандартный вывод. Порядок вывода должен соответствовать порядку следования твитов в XML файле.

Пример:

Входные данные Результат работы
/home/user/smaller.xml.gz -360 -360 360 360 10 good i wonder where my vendor get her hair from. it’s really good hair thou ., iwanna find out her source that way i can go straight to thm. remember the good days when we used to swim and then get the yummy de stafford pic n mix sweets @ellisrobynborer @rosiesluman

Примечания

Пример работает с файлом smaller.xml.gz

Задача 5. Bags repackaging

Ограничение времени: 1 с

В этой задаче требуется перепаковать набор сумок.

Есть n сумок.

Все сумки различны: каждая покрашена в свой уникальный цвет.

Каждая сумка довольно вместительна, но сама по себе занимает мало места. На практике это означает, что в любую сумку можно положить все остальные сумки вместе взятые.

Сумки могут лежать одна в другой либо непосредственно, либо внутри других сумок, также лежащих внутри.

Попробуем дать формальное определение этих понятий. Будем говорить, что сумка u лежит непосредственно в сумке v, если, открыв сумку v, можно извлечь из неё сумку u, не открывая никакие другие сумки.

Смущает, что сама v тоже может в чём-то находиться. Будем говорить, что сумка u находится где-то внутри сумки v, если либо u лежит непосредственно в v, либо u лежит непосредственно в какой-то сумке w, которая находится где-то внутри сумки v.

Каждая сумка может лежать непосредственно не более чем в одной сумке.

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

Никакая сумка не может находиться где-то внутри самой себя.

Будем называть конфигурацией сумок информацию для каждой сумки о том, лежит ли она непосредственно в какой-то другой сумке, и если лежит, то в какой именно.

Определим две операции, которые можно делать с конфигурацией сумок.

out u v

Достать сумку u, которая лежит непосредственно в сумке v, из сумки v, которая находится снаружи.

in u v

Положить сумку u, которая находится снаружи, в сумку v, которая также находится снаружи.

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

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

ВНИМАНИЕ! Описание публичного класса должно быть первым в файле-решении

Формат входных данных

В первой строке ввода задано целое число n – количество сумок 1

Во второй строке задана исходная конфигурация сумок,

а в третьей – требуемая конфигурация.

Описание каждой конфигурации сумок состоит из n целых чисел: * в какой сумке лежит непосредственно первая, вторая, … , n-я сумка.

Сумки нумеруются целыми числами от 1 до n.

Если какая-то сумка находится снаружи, соответствующее число равно нулю.

Гарантируется, что обе конфигурации сумок корректны.

Формат результата

В первой строке выведите целое число k – количество операций.

Следующие k строк должны описывать сами операции в порядке их произведения.

Следуйте формату, указанному в условии.

Если возможных ответов несколько, можно вывести любой из них.

Пример:

Example

← DuckDuckGo: Right Search Engine ASUS Zenbook Prime UX32VD →