Сап, анон, проходил недавно тест входной в Яндексе, так и не разобрался с задачами, пишу на Java, вот сами задачи:выставлю одну, остальные буду скидывать в тредA. Граф подстрокОграничение времени 6 секундОграничение памяти 128MbВвод стандартный ввод или input.txtВывод стандартный вывод или output.txtАнтон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об автоматической генерации текстов Антон должен построить граф подстрок существующих текстов. Антон берет все имеющиеся у него слова и действует следующим образом: слово S=s1s2…sn−1sn образует n−2 слова длины 3: w1=s1s2s3, w2=s2s3s4, w3=s3s4s5 …wn−2=sn−2sn−1sn; если для какого-то из слов wi еще нет вершины в графе, то она создается; для каждой пары слов (wi,wi+1) добавляется ориентированное ребро веса 1, или увеличивается вес существующего ребра на 1. Таким образом получается граф G с v вершинами и e ориентированными ребрами. Между некоторыми вершинами может быть несколько дуг (от a к b и от b к a). По заданному набору слов помогите Антону найти количество вершин в графе и вывести ориентированные ребра между вершинами. Формат вводаВ первой строке записано одно целое число T (1≤T≤40000) — количество слов, имеющихся у Антона. В каждой из T следующих строк записано одно слово Si (4≤|Si|≤30). Все слова состоят из строчных букв английского алфавита.Формат выводаВ первой строке выведите количество вершин v в графе G. Во второй строке выведите количество пар вершин e, между которыми есть ориентированные ребра. В каждой из следующих e строк выведите слово ws, соответствующее началу ребра, затем слово wf, соответствующее концу ребра, и вес ориентированного ребра из вершины ws в wf. Ребра вы можете перечислить в произвольном порядке. Пример 1Ввод Вывод 2aaaaaaaaaaaaaaaabbbaaabbba 67aaa aaa 10aaa aab 2aab abb 2abb bbb 2bbb bba 2bba baa 1baa aaa 1 Пример 2Ввод Вывод 2ababbaba 22aba bab 1bab aba 1 Пример 3Ввод Вывод 1qwertyqwertyqwertyqwertyqwerty 66qwe wer 5wer ert 5ert rty 5rty tyq 4tyq yqw 4yqw qwe 4//////////////////////////////////////////////////////////////
Не думаю, что тут имеют место какие-то хитрые оптимизации. Мне тяжело было переварить условие, но решение, кажется, довольно прямолинейно. Ходим по каждому слову сдвигающимся окном в 3 символа, запоминаем текущее и предыдущее слово. Имеем ассоциативный массив (хэш или дерево), в котором каждой паре ставится в соответствие счечтик, инкрементирующийся для каждой новой пары. Осталось учесть симметрию, то есть, например, парам (aaa, bbb) и (bbb, aaa) должно ставиться в соответствие единственное значение счетчика; для этого, кажется, достаточно сортировать пары в лексиграфическом порядке. Позже попробую написать код не ливай с доски.
>>1439426 (OP)Для питона совсем простая задача, для других языков будет сложнее. Создаём список слов,{'aaa', 'aab'}Словарь рёбер{('aaa', 'aab') : 2, ('aaa', 'aaa') : 10}дальше одним циклом заполняем словарь слов, потом вторым циклом словарь рёбер. Можно в один проход, но это сложнее, некрасиво и наверно даже дольше работать будет.Вывод результата тоже очень простой. В других языках эти базовые конструкции могут быть сложнее.Можно поупражняться на пример красивого оформления этого дела. Может кому интересно.
Вот еще задачка, но она попроще: Телефонные номераОграничение времени 3 секундыОграничение памяти 256MbВвод стандартный ввод или input.txtВывод стандартный вывод или output.txtЕсть база данных телефонных номеров. Необходимо для каждого номера определить страну, оператора, а также привести номер в определённый формат. Существует список шаблонов, которым может удовлетворять номер. Он имеет вид: NUMBER - COUNTRY OPERATOR NUMBER – шаблон номера, формат ниже COUNTRY – названия страны, последовательности символов латинского алфавита OPERATOR – названия оператора, последовательности символов латинского алфавита и цифр Номер в шаблоне задаётся в следующем виде: +COUNTRY_CODE (OPERATOR_CODE) PERSONAL_NUMBER COUNTRY_CODE – код страны, от одной до трёх цифр, первая цифра не может быть нулём OPERATOR_CODE – код оператора, от двух до четырёх цифр PERSONAL_NUMBER – шаблон номера абонента внутри оператора, строка длиной от пяти до девяти символов. Символом может быть цифра от 0 до 9 или символ X. Символ X означает, что на данной позиции может быть любая цифра от 0 до 9. Справа от символа X не может стоять цифра Все номера телефонов в текущей базе данных содержатся в полном формате (все цифры присутствуют), но, в отличие от формата выше: могут отсутствовать знак + и скобки могут отсутствовать или быть в любом месте номера пробелы и знак-разделитель дефис не содержат больше никакой информации (имени абонента, оператора и т.п.) Гарантируется, что для каждого номера существует ровно один шаблон, которому он удовлетворяет, и все шаблоны не пересекаются. Формат вводаПервая строка содержит число N (1≤N≤1000) – количество номеров в базе данных. Далее следует N строк – номера телефонов по одному номеру в строке. Длина строки не превосходит 100 символов. Следующая строка содержит число M (1≤M≤1000) – количество шаблонов. Далее M строк – шаблоны в формате, описанном выше. Длина шаблона не превосходит 100 символов. Формат выводаВыведите N строк, в каждой номер в новом формате в том порядке, в котором они указаны во входе.Пример 1Ввод Вывод 428-49-5-123-45-6787544456789+28 (495) 123 45 56875-(29)-1234563+875 (29) 1XXXXX - Atlantis MythCell+875 (44) 4XXXXX - Atlantis MobTelecom+28 (495) XXXXXXX - ElDorado GoldLine +28 (495) 1234567 - ElDorado GoldLine+875 (44) 456789 - Atlantis MobTelecom+28 (495) 1234556 - ElDorado GoldLine+875 (29) 123456 - Atlantis MythCell
>>1439456В виде скрина и прямо сюда, но без форматирования. На тестовых значениях вывод один в один с ними, порядок рёбер тот же, я думаю, они тоже на питоне делали. Это питон-3.inp_sentences = []with open ('input.txt') as inp: n_words = int(inp.readline().strip()) for i in range(n_words): inp_sentences.append(inp.readline().strip())set_words = set()dict_edges = {}for sentence in inp_sentences: for i in range(len(sentence) - 2): set_words.add(sentence[i : i+3])for sentence in inp_sentences: for i in range(len(sentence) - 3): word1 = sentence[i : i+3] word2 = sentence[i+1 : i+4] dict_edges[(word1, word2)] = dict_edges.get((word1, word2), 0) + 1print (len(set_words))print (len(dict_edges))for (edge1, edge2), num in dict_edges.items(): print ("{} {} {}".format(edge1, edge2, num))
>>1439478В строках 24-25 должно быть word1, word2. На функциональность переименование не влияет никак, это по смыслу переменные названы неправильно.
>>1439489Ты сейчас что-ли решаешь? Ну могу ещё какую-нибудь сделать, те же телефоны.А какую ошибку выдаёт? Ты пробелы все поставил как надо? Это питон ведь. И именно питон-3, а не питон-2
Тоже решал эти задачи, только на c++. Сами задачи не сильно сложные кроме последней , сложно выдрачить свой алгоритм, что бы они прошли все тест. Например, с задачей "Телефонные номера" тестов 100 написал, все работало корректно, но в контекста выдавал WA на 7мом тесте, какой они туда input грузят не понятно
Хотел решить первую задачу на C++, но не процедурно в main, а красиво. Как же это выматывает.http://ideone.com/8vYyeG
>>1439522>>1439524А жаль, что кончился. Хотелось бы в лице анона на стажировочку в яндекс отобраться. А так не интересно.Решение с телефонами:https://www.codepile.net/pile/dmd65JMz
>>1439545Решение на питоне сверху (оно вообще правильное?) написано процедурно в виде скрипта. Я мог бы на C++ решить в несколько циклов for в main и у меня бы получилось бы не сильно длиннее.
>>1439532Да, но сомневаюсь что он тебе поможет. Могу описать свои попытки решения.Граф подстрокЧерез префиксное дерево, хотя уверен можно придумать куда лучше решениеТелефонные номера.при первом вводе данных, полностью очищал шаблоны и номера от всего кроме цифр (скобочек, пробелом, плюсов и т.д.), и записывал в соответствующие массивы (массив номеров и массив шаблонов). И отдельно сохранял не модифицированные шаблоны в отдельный массив. После этого сравнивал чистый номер с каждым чистым шаблоном, там где наибольшее совпадение тот и верный шаблон. ну и остается только вставить нужный номер вместо ХХХХХ в шаблон с не модифицированными шаблонами.ПроизведениеЕсть алгоритм перебора сочетаний из N по K, через битовые сдвиги, работает намного быстрее чем обычный перебор, им я перебрал итераторы в массиве и проверял сумму. Но при отправке выдавало PE, хотя локально все работало.
>>1439567Пока ноль, тоже ошибка ответа. Они ловят какие-то изъёбистые случаи, но ты даже примерно не поймёшь, на чём они ловят. Это самое противное в таких тестах.
>>1439426 (OP)>Ограничение времени 6 секунд>Ограничение времени 3 секундыНа чем? на i7 или на p2? Ору с такой конкретики.>>1439511>собирается в яндекс>долбоеб из поста просто скопировал без табуляций? Бля, как же я ору.
>>1439824Сразу видно маньку, которая НИКОГДА не решала алгоритмические задачи, но пиздящую о мвоей охуенности.
>>1439426 (OP)>Антон стажируется в группе обработки комментариев и отзывов>aaaaaaaaaaaaa>aaabbbaaabbbaКекнул
>>1439974Сам яндекс может быть, но яндекс-стажировки может быть и интересны. Да и джуниорский опыт в таком бренде тоже плюс в карму.
Яндексокуколды здесь? Обьясните, опущи, вот это как вообще понимать? 416 заблокированных элементов на странице, вы там не охуели в своем рекламном агентстве? Вы чем-нибудь кроме впаривания малвари вообще занимаетесь? Зачем вам нужны работники со знанием алгоритмов, машоба итд? Стильно, модно, молодежно? У вас же гитхаб беднее, чем у любого студента-индуса. Все это не нужно чтобы впаривать малварь.
>>1439985Ты сломал Хуяндекс---Ошибка 404Вы попали на несуществующую страницу.Вероятно, это произошло из-за опечатки или неправильной раскладки клавиатуры.Если вы прошли сюда по ссылке, поделитесь ею с нами, пожалуйста.
>>1440053>Ты сломал ХуяндексЯ удалил часть строки с моим акком. Дело не в этом, а в количестве заблоченного говна. Ну доколе, правда?
