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

Подробнее о новшествах — дальше в посте.

Надеюсь, новые функции обрадуют вас также, как мы радовались на каждом стендапе, обсуждая свимлейн «Реакции» на доске.

Реакции на комментарии для всех

Реакции — простой способ быстро ответить на комментарий в YouTrack. Пользователи любят эмодзи за то, что ими можно заменить слово или даже целое предложение — с реакциями можно не писать лишние комментарии при обсуждении задачи.
Чтобы случайно не пропустить важную реакцию, в центре уведомлений есть список недавних реакций на ваши комментарии, оттуда же можно сразу открыть нужную задачу.

YouTrack — это все-таки таск-менеджер, а не мессенджер, поэтому мы решили начать с небольшого набора эмодзи. Мы будем развивать библиотеку в соответствии с мнением пользователей, поэтому обязательно делитесь с нами своими впечатлениями.

Режим перевода интерфейса из контекста для иноязычных пользователей

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

Мы стараемся максимально упростить процесс локализации интерфейса для тех, кто хочет внести свой вклад. В режиме перевода из контекста YouTrack подсвечивает все элементы интерфейса, которые еще не переведены, и вы можете предлагать свои варианты прямо в приложении. После того как JetBrains одобрит ваш перевод, он будет виден всем, кто использует YouTrack на этом языке.

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

Тонкие настройки доступа к полям в задачах для администраторов

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

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

В YouTrack 2020.1 администратор может открывать доступ для просмотра и обновлению каждого поля в отдельности. Более того, теперь администраторы проекта могут создать одну выделенную группу пользователей, которые могут видеть определенные поля, и другую — тех, кто может их обновлять. Вместо написания сложных рабочих процессов просто используйте новые настройки полей для неординарных случаев распределения ролей между командами.

Улучшенная интеграция с VCS и TeamCity для разработчиков

Расширены возможности интеграции YouTrack с TeamCity, Upsource и системами контроля версий, такими как GitHub.

Общие настройки интеграции с VCS для нескольких проектов

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

Обработка связанных задач

Интеграция между YouTrack и TeamCity теперь позволяет точнее выбирать, какие задачи соответствуют определенному билду. В рамках интеграции с TeamCity задачи, которые упоминаются в изменениях VCS, включенных в билд, рассматриваются как «связанные» с этим билдом. Когда билд обрабатывается, связанные задачи в статусе “Завершена”, обновляются соответствующим номером сборки. Теперь можно указать условие, которое будет определять, какие связанные задачи следует обновлять.

Поддержка Swagger

Еще одно улучшение, связанное с разработкой: в YouTrack 2020.1 появился встроенный Swagger Open API 3.0 файл. С его помощью можно использовать REST API для интеграции вашего приложения с YouTrack. На этой странице GitHub можно найти совместимые инструменты генерации кода для вашей среды выполнения.

Разрешение «Применить команду без уведомлений»

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

Подробнее о новой версии читайте на сайте.

Открытые лекции

1. «Что такое операционная система и как она работает», Кирилл Кринкин

2. «LaTeX: краткое введение в качественную типографику», Александр Смаль

3. «Программирование музыки на Sonic Pi», Владимир Красильщик

4. «Введение в язык программирования Go», Марат Хабибуллин

5. «Жадная гипотеза для задачи о надстроке», Александр Куликов

6. «Введение в язык программирования Rust», Алексей Кладов

7. «Введение в статистическое моделирование с помощью языка программирования Stan», Александр Сухочев

8. «Классические и новые задачи комбинаторики», Андрей Михайлович Райгородский

9. «Случайные графы», Андрей Михайлович Райгородский

10. «Вероятность и алгебра в комбинаторике», Андрей Михайлович Райгородский

Все открытые лекции CS центра

Видеокурсы

Если не знаете, с чего начать, почитайте материал Яндекс.Академии: мы рассказали ребятам про 10 наших самых популярных видеокурсов.

Все выложенные курсы CS центра

«Эффект обеззараживания основан на прямом губительном воздействии ультрафиолетовых лучей в спектре с длиной волны 200—300 нм и максимумом бактерицидного действия 260 нм … ультрафиолетовые лучи могут воздействовать не только на обычные бактерии, но и на споровые организмы и вирусы» — Справочник химика [1].

Подробную информацию об использовании ультрафиолетового излучения для обеззараживания можно найти в [2].

Профессиональные бактерицидные установки стоят недешево и предназначенные для них лампы в обычный патрон не вкрутишь. В этой статье пойдёт речь об изготовлении и применении недорогой бактерицидной лампы со стандартным патроном Е27 или Е14 с питанием от сети 220В на основе УФ лампы с цоколем 2G7 или G11 и электронного балласта б/у энергосберегающей лампы.

Меры предосторожности при использовании УФ-лампы.

1. Воздействие ультрафиолетового излучения на кожу приводит к ожогам разной степени, может вызывать рак кожи. При облучении глаз вызывает ожог роговицы. Ультрафиолет коротковолнового диапазона (100—280 нм) может проникать до сетчатки глаза. Обработка помещений должна проводиться только без людей!
2. При работе УФ ламп образуется озон, обладающий высокой токсичностью. После обработки помещение необходимо проветрить. Это не относится к УФ лампам из увиоливого стекла, не генерирующим озон по причине поглощения стеклом спектра излучения, создающего молекулы озона.
3. Многие полимеры, используемые в товарах широкого потребления, деградируют под действием УФ-света. Не рекомендуется надолго оставлять изделия из полимеров вблизи работающих УФ ламп.

В зависимости от соотношения мощностей УФ лампы и электронного балласта, возможны 3 варианта:

1. Если мощность лампы и балласта совпадают, задача проста: подключить лампу к балласту и прикрепить к корпусу.
2. Если мощность лампы больше мощности балласта, если повезёт, работать будет, но не на полную мощность, а в соответствии с мощностью балласта. Балласт ограничивает выходной ток, поэтому подключение ламп избыточной мощности не выведет его из строя.
3. Если мощность лампы меньше — требуется вмешательство в конструкцию балласта с целью уменьшения мощности. Об этом — следующий раздел.

Устройство и работа электронных балластов.

На эту тему написано немало статей. Рассмотрим первую схему из статьи «Схемы, устройство и работа энергосберегающих ламп» [3].

Рисунок 1: cхема электронного балласта лампы.

Из всех элементов схемы нас интересуют:

1. Лампа. На схеме обозначены её катоды LMP1, LMP2. Сюда будем подсоединять УФ-лампу.
2. Пусковой конденсатор С3. Во время запуска, напряжение на конденсаторе C3 достигает порядка 600В. Если колба энергосберегающей лампы была повреждена, вероятен выход из строя конденсатора C3 и транзисторов. Поэтому, при использовании балласта от неисправной лампы, необходимо проверить их исправность. Да и все остальные детали желательно проверить до первого включения.
3. Терморезистор RT1 с положительным температурным коэффициентом сопротивления, также называемый позистором или PTC. Устанавливается в некоторых лампах. Он предотвращает перенапряжение на выходе преобразователя: в момент поджига лампы он холодный и протекающий через него ток разогревает катоды лампы, чтобы облегчить запуск, снизить износ, потом PTC нагревается, увеличивает своё сопротивление и не препятствует дальнейшей работе лампы.
4. Предохранитель F1, необходимый для обеспечения пожаробезопасности.
5. Выходной дроссель L1. Ограничивает ток через лампу.
6. Трансформатор обратной связи TR1. Намотан на ферритовом кольце и является насыщающимся. От его параметров зависит частота генерации, а от неё — индуктивное сопротивление дросселя и ток через лампу.

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

В документе «Electronic Lamp Ballast Design» [4] приведена методика расчёта электронных балластов при разработке с нуля. При переделке готовых электронных балластов пригодятся формулы:

1. Формула (1) на с. 3 — зависимость индуктивного сопротивления от частоты.
2. Формула (3) на с. 3, и ненумерованная чуть ниже, связывающие индуктивность дросселя и ток через лампу.
3. Формула (16) на с.8, определяющая частоту генерации.
4. Формула (18) на с.10, связывающая ток протекающий через лампу с числом витков первичной обмотки и периметром сердечника трансформатора обратной связи. Ток протекающий через лампу равен току первичной обмотки.

   Из этих формул следует, что ток через лампу обратно пропорционален числу витков первичной обмотки трансформатора обратной связи. Чтобы уменьшить ток, нужно домотать больше витков. А увеличивать ток нежелательно — могут не выдержать транзисторы и другие детали.

5. Формула (6) на с.7 — напряжение на вторичной обмотке трансформатора обратной связи, которое не должно превышать максимальное напряжение базы транзистора.
6. Лучше добавить обратные диоды в базовые цепи транзисторов, чтобы они не вышли из строя от превышения напряжения базы после домотки трансформатора. Это, вероятно, было причиной неудачи с первым вариантом доработанного балласта: он сгорел с бабахом. Обуглились все резисторы в цепях баз, пробило транзисторы. Дешевая китайская схема, значит, была рассчитана впритык. Шунтирование эмиттерных переходов обратными диодами, которые показаны на схеме красным цветом, предотвратит пробой.

Методика переделки электронных балластов под любую нужную мощность (в меньшую сторону)

1. Определение тока. Измерьте напряжение U на штатной колбе б/у лампы, мощность которой P1 указана на корпусе. Ток I1 = P1 / U1. Если колба б/у лампы неисправна, примем допущение, что напряжение U1 на старой и новой U2 лампах примерно равны U1 = U2. Ток УФ-лампы I2 = P2 / U2. Соотношение токов I1/I2 определяет изменение числа витков первичной обмотки трансформатора обратной связи.
2. Домотка первичной обмотки трансформатора обратной связи. Посчитайте количество витков первичной обмотки Np. Нужно домотать N = Np * (I1/I2 — 1) витков.
3. Добавление обратных диодов в базовые цепи транзисторов. Напряжение и ток диодов малы, поэтому годятся почти любые быстрые диоды. Например, UF4007 или аналогичные, из других б/у балластов.
4. Добавление терморезистора (если его не было) параллельно пусковому конденсатору.
5. Добавление предохранителя F1 (если его не было). Номинальный ток предохранителя Iпр = 2P / Uсети выбирается по расчетному току нагрузки с учетом пусковых токов. Можно брать из других б/у балластов такой же или большей мощности.
6. Испытание. Проводить в защитных очках.
   1. Временно подключить УФ-лампу. При первом включении подсоединить лампу накаливания мощностью 60-100 Вт последовательно с фазой питающей сети для предотвращения выхода из строя балласта в случае допущенных ошибок.
   2. Кратковременно включить питание без добавочной лампы, измерить ток, сравнить с рассчитанным.
   3. Сравнить реальную мощность на лампе с номинальной.
   4. Если номинальная мощность превышена на 2Вт и более, домотать ещё 1 виток первичной обмотки трансформатора обратной связи и повторить этот пункт.

Методика изготовления бактерицидной лампы

1. Разборка лампы. Подогрейте корпус феном в области шва чтобы пластмасса стала эластичнее, просуньте тупой нож или плоскую отвёртку и отожмите защёлки.
2. Доработка балласта — описана выше, делается при несовпадении мощностей УФ-лампы и балласта.
3. Удаление колбы. Отсоедините выводы колбы от платы балласта. Подогрейте феном клей, которым приклеена колба, и расковыряйте его ножом, чтобы отделить колбу от корпуса.
4. Доработка корпуса и установка УФ-лампы. Конкретные действия зависят от конструкции корпуса. В моём случае оказалось достаточно срезать часть пластика и сделать отверстия для выводов УФ-лампы. После припаивания проводов УФ лампа оказалась достаточно хорошо зафиксирована. Если планируется замена УФ-ламп, установите патрон.
5. Сборка лампы. Проложите прокладку из изолирующего материала между платой и выводами УФ-лампы / патрона и соедините половинки корпуса.

Демонстрация предложенной методики.

Лампа ультрафиолетовая ESL-PL-9/UVCB/2G7/CL (аналог ДКБУ-9) мощностью 9Вт. Напряжение в лампе 60±6В.

Электронный балласт от лампы Happy Light мощностью 15 Вт. Колба неисправна.

I1 = 15 / 60 = 0,25 A
U1 = U2
I2 = 9 / 60 = 0,15 A
N = 4,67 округляется до 5 витков

Измеренное значение мощности 8,08Вт отличается в меньшую сторону от номинальных 9 Вт, что допустимо, т. к. незначительно влияет на эффективность и не снижает надёжность.

Рисунок 2: Крышка корпуса до доработки

Рисунок 3: Трансформатор обратной связи с домотанной первичной обмоткой.

Рисунок 4: Тестовое подключение УФ-лампы к балласту.

Рисунок 5: Подключение щупов осциллографа.

Рисунок 6: Осциллограммы тока и напряжения.

Рисунок 7: Осциллограмма мощности.

Рисунок 8: Доработанная крышка корпуса с установленной УФ-лампой

Рисунок 9: Окончательное подключение УФ-лампы к балласту.

Рисунок 10: Готовая лампа.

Рисунок 11: Работающая лампа.

Привет! Меня зовут Александр Курилкин, и я веду курс по алгоритмам в «ШАД Helper». В этом посте я разберу несколько задач из вступительных экзаменов прошлых лет, чтобы вы смогли увидеть, что вас ждет, и понять, чему мы сможем вас научить на нашем курсе. Надеюсь, что вы разделяете мою любовь к интересным задачам по алгоритмам и получите искреннее удовольствие от прочтения этого поста! Итак, приступим…

28.05.2016, №4

Даны

отрезков

. Назовем индексом вложенности отрезка

количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложенности, превышающим 1000. Ограничение по времени —

, по дополнительной памяти —

.

Решение

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

$$

, и "отрезок закрылся", которое происходит в момент времени

$$

. Отсортируем все события по их моменту времени и начнем обрабатывать их в таком порядке. Когда отрезок открывается, нужно увеличить счетчик открытых отрезков на 1. Когда открылся очередной отрезок, а счетчик открытых отрезков уже был больше или равен 1000, казалось бы, мы уже решили задачу — очередной отрезок содержится в 1000 уже открытых ранее. Но все не так просто — какие-то из открытых ранее отрезков могли закрыться раньше, чем закроется наш текущий отрезок, который мы рассматриваем как кандидат на ответ. Чтобы решить эту проблему, давайте поддерживать отсортированное мультимножество (std::multiset в C++), в котором будем хранить координаты концов открытых отрезков. На самом деле, хранить все концы в нем не обязательно — достаточно лишь 1000 максимальных. Теперь, чтобы проверить, что текущий отрезок и правда подходит нам, нужно проверить, что в мультимножестве *set.begin(), то есть минимальный (среди 1000 максимальных) конец не левее конца текущего отрезка. Если это правда, то мы нашли подходящий отрезок и задача решена! Если нет, то увы, придется продолжать обрабатывать события раньше. Если отрезок закрылся, то нужно уменьшить счетчик открытых отрезков и удалить из мультимножества его конец. Если все события обработаны, а подходящий отрезок не обнаружен, то его и нет!

У пытливого читателя при прочтении мог возникнуть вопрос: почему достаточно хранить лишь 1000 концов? Вдруг может быть такое, что удалится какой-то из этих 1000 максимальных концов, а открыто было больше 1000 отрезков, и придется откуда-то взять конец, чтобы заменить им только что удаленный? На самом деле такого быть не может, ведь если мы удалили какой-то из 1000 максимальных концов, значит, мы закрыли отрезок с таким концом, а до этого закрыли и все отрезки с концами левее нашего, а значит, заменять в мультимножестве удаленный конец нечем.

Вот и все, задача решена. Мы потратили

$$

времени на сортировку событий,

$$

времени на операции с мультимножеством концов отрезков и O(n) на все остальное. Таким образом, время работы:

$$

. Памяти мы уж точно потратили не больше

$$

.

25.05.2019, №4

Дан массив вещественных чисел

. Предложите алгоритм, находящий для каждого элемента

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

. Ограничение по времени

, по дополнительной памяти —

.

Решение

Будем идти по массиву справа налево и поддерживать стек пар

$$

пройденных чисел. Начнем с самого правого элемента (для него ответ

$$

), добавим в стек

$$

, пойдем левее. Пусть мы хотим обработать очередное число с индексом

$$

. Тогда какие числа, пройденные ранее, не представляют для нас никакого интереса в плане определения ближайшего справа в два раза больше как для нашего числа, так и для чисел левее? Это те числа, которые находятся между нашим и ближайшим большим справа. И правда, зачем они нам в будущем, если у нас уже есть число левее, большее них? А вот ближайшее большее справа нам еще может пригодиться. Поэтому давайте удалять из стека верхние элементы, пока их значения меньше или равны нашему. Как только у верхушки стека значение стало больше, пора остановиться и добавить на вершину стека

$$

. Хорошо, со стеком мы поработали, но как теперь определить индекс ближайшего справа в два раза большего числа? Заметим, что числа в стеке отсортированы (сверху вниз) по значению и по расстоянию до

$$

. Тогда достаточно двоичным поиском в стеке (да, для этого потребуется индексация стека, поэтому давайте вместо стека использовать std::vector) найти наименьшее значение, большее или равное

$$

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

$$

.

Хорошо, задачу мы решили, но какова асимптотика алгоритма? Каждый элемент добавится и удалится из стека всего один раз, поэтому на все добавления и удаления в стек мы потратим O(n), а еще придется сделать

$$

двоичных поисков, что займет

$$

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

$$

.

10.06.12, №5
В множестве из

человек каждый может знать или не знать другого (если

знает

, отсюда не следует, что

знает

). Все знакомства заданы булевой матрицей

. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени —

, сложность по памяти —

.

Решение

Для определенности пусть

$$

, если

$$

-й человек знает

$$

-го человека, и 0 иначе.

Тогда заметим, что если

$$

, то

$$

-й человек точно не может быть знаменитостью, ведь он кого-то знает, а вот

$$

-й может, а если

$$

, то

$$

-й человек точно не может быть знаменитостью, ведь

$$

-й его не знает.

Это дает нам следующий алгоритм: пусть изначально первый человек — наш кандидат в знаменитости. Давайте начнем идти по первой строке матрицы вправо, пока не встретим 1, скажем, в столбце

$$

. Тогда все люди, соответствующие пройденным столбцам (где был записан 0), точно не могут быть знаменитостями, а человек, соответствующий первой строке, тоже не может быть знаменитостью, поскольку он кого-то знает (а именно, человека, соответствующего строке

$$

). Тогда

$$

-й человек — наш кандидат в знаменитости, и начнем такой же процесс с клетки матрицы

$$

. Если на пути нам встретится 1, то обновим кандидатата, и так далее, пока мы можем идти вправо. Осталось проверить, действительно ли является ли наш последний кандидат знаменитостью. Для этого проверим, что в столбце, соответствующем ему, все единицы (кроме клетки на главной диагонали), это значит, что его все знают, а в его строке все нули, то есть он никого не знает. Пока мы шли по матрице, мы двигались только вправо, а значит, потратили

$$

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

$$

времени. Итого:

$$

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

$$

. Полное решение!

Это были задачи, требующие смекалки и совсем небольшого знания алгоритмов, а теперь немного алгоритмической жести!

2019, онлайн-контест, задача D

Минимальное остовное дерево, часть 2
Ограничение времени: 2 секунды
Ограничение памяти: 256Mb

Вам дан неориентированный взвешенный граф с

вершинами и

рёбрами. Требуется выполнить

запросов вида «уменьшить вес ребра номер

на 1». После каждого запроса вам нужно вывести вес минимального остовного дерева в графе.

Остовное дерево графа — это подграф, содержащий все вершины графа и являющийся деревом. Остовное дерево называется минимальным, если сумма весов входящих в него рёбер минимально возможная.

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

Формат ввода

В первой строке входного файла содержатся два целых числа

и

— количество вершин и рёбер графа соответственно (

. В следующих

строках содержится по три целых числа

,

,

. Это значит, что в графе есть ребро веса

, соединяющее вершины

и

(

).

В следующей строке содержится целое число

— количество запросов (

). В следующих

строках содержится по одному целому числу

(

). Это значит, что требуется уменьшить на единицу вес ребра

. Рёбра нумеруются с единицы в порядке следования во входном файле.

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

Выведите

чисел, разделённых пробелами или переводами строки — веса минимального остовного дерева после выполнения каждого запроса.

Решение

Для начала давайте поймем, как решать задачу, если бы ограничения были поменьше или наши руки были посильнее 99% поступающих в ШАД. Для начала построим минимальное остовное дерево.

Пускай приходит запрос "уменьшить ребро между

$$

и

$$

", и новый вес ребра стал

$$

. Тогда если в дереве на пути между

$$

и

$$

есть ребро весом больше

$$

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

$$

, иначе бы остов не был минимальным, так как на пути в остове между вершинами ребра

$$

и

$$

было ребро веса

$$

, а наше ребро было веса

$$

, а значит, выгодно заменить бо́льшее ребро на наше), то нужно удалить его из остова и добавить вместо него наше, уменьшив тем самым вес минимального остовного дерева на 1. Это называется критерий Тарьяна минимальности остовного дерева. Осталось понять, как находить максимальное ребро на пути, удалять ребро из дерева и соединять два дерева ребром. Это можно делать либо наивно за

$$

, что не позволит нам решить задачу, уложившись в ограничения по времени, либо за

$$

с помощью структуры данных link-cut tree, написание которой у вас займет больше времени, чем сам контест (и это в лучшем случае). Поэтому будем искать другое оптимальное решение.

Так как веса бывают всего лишь от 1 до 10, давайте поддерживать 10 остовов (они могут быть лесами, не обязательно деревьями). В

$$

-м остове будут только ребра весом

$$

. Каждый остов построим алгоритмом Краскала. Для этого есть две причины: он просто пишется, и СНМы (системы непересекающихся множеств) для каждого остова, оставшиеся после него, нам еще понадобятся в будущем. Кроме того, можно заметить, что при построении таким образом первый остов будет подмножеством второго, второй третьего, и так далее.

Пусть вес ребра

$$

уменьшился на 1 и стал

$$

. Попытаемся добавить его в

$$

-й остов. Для начала с помощью СНМ проверим, лежат ли в

$$

-м остове

$$

и

$$

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

$$

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

$$

и

$$

в СНМе

$$

-го остова, заодно уменьшив вес минимального остовного дерева на 1. Если же

$$

и

$$

лежат в одной компоненте связности в

$$

-м остове, то между ними есть путь по ребрам с весом

$$

, и уменьшение веса нашего ребра не принесет никакой пользы.

Задачу решили, пишется не очень сложно, а что там по времени и памяти?

$$

на запрос и даже если писать совсем не заботясь о времени, то

$$

на препроцессинг. В ограничения должно уложиться, Accepted 🙂

Друзья здравствуйте, всем здоровья, берегите себя, антисептики — наше ВСЁ!

Сегодня попробуем рассмотреть московские электробусы по мотивам статьи в журнале «За рулем» в части используемых литий-титанатных батарей (Li4Ti5O12 или LTO), их стоимости и перспектив эксплуатации, также попробуем разобраться, почему литий-титанат не подходит для промышленных решений в ИБП.

После нашей статьи «Li-Ion технологии: удельная стоимость снижается быстрее прогнозов» вызвал интерес литий-титанат как «не автомобильный» литий. На мой взгляд LTO как раз и является самым что ни на есть тяговыми батареями, которые совершенно не подходят для работы в качестве аккумуляторных батарей в ИБП и телекоме. Почему? Давайте разберемся под катом, структуру статьи условно разделим на три части:

1. Что такое электробус и почему LTO?
2. Химия-химия…., все батарейки одинаковые? В чем отличие LTO, LpTO и LFP
3. Стоимость литий-ионных решений на данном этапе: мировые данные и примерные коэффициенты на рынке РФ

Что такое электробус и почему LTO?

Для начала разберемся в статье и «выудим» нужные нам данные

• используемые LTO-батареи, точнее АКБ+BMS производства китайской Microvast,INC Однако ВИКИ утверждает, что в Китае лишь завод по производству батарей, головная компания — Хьюстон, штат Техас, USA
• Электробусы поставляют КАМАЗ и ЛИАЗ, кузова разные, но силовая установка одна и та же
• декларируется 7 лет работы или 15 тысяч циклов, однако в буклете производителя указано витиевато «более 12 тысяч циклов». А вот вышеупомянутый ВИКИ утверждает, что количество циклов для этого типа батарей-от 2 до 7 тысяч циклов. Разберемся ниже по тексту, однако скажу, что в научных статьях именно для Microvast указывают лишь >2000 циклов для LpTO
• Вот тут не состыковка с буклетом китайцев, они утверждают, что начало эксплуатации электробусов в Китае — 2011 год, то есть в прошлом году уже прошло 9 лет, вопрос где статистика?
  

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

• Стоимость энергетической установки — 9,5 млн. рублей (удорожание электробуса, запомним пока цифру)
• Масса батарей на крыше автобуса — 1,8-2 тонны (тут тоже не стыковка, снаряженная масса для электробуса — это и электродвигатели, и обвязка, и контроллеры батарей, и конечно сами батареи)
• Емкость батареи — 77кВт*ч, однако сам производитель пишет о 60/80кВт*ч

  

Таким образом на основе статьи имеем:

1. Удельная масса батарей — 10,3 кВт*ч/кг массы батарей (pack)
2. Удельная стоимость батарей (за вычетом 1/3 зарядной станции -55,2 т.рублей/ Вт*ч/кг (pack)
3. Кузов автобуса рассчитан производителем на 12 лет эксплуатации, расчетная замена батарей — через 7 лет за счет города, учитывая невысокий (предположительно) уровень службы эксплуатации Мосгортранс и желание «побыстрее» зарядить батарею в ущерб сроку службы батарей — получаем средний цикл эксплуатации батареи — порядка 7 тысяч циклов. Если брать по 10 циклов в день — то срок службы батарей электробуса вряд ли превысит 3 года или 10,5 тысяч циклов (2 года гарантии — предполагаю — плюс год послегарантийного обслуживания)

фото c сайта www.zr.ru

… на этом пока все, продолжение следует.

UPD: С чего начнём следующую — химическую — часть:

Внешний вид LpTO батарейной сборки от Microvast, Китай. Возможно, именно они установлены на электробусах в Москве.