Russian Code Cup — по следам отборочного раунда

14 мая прошёл отборочный раунд Russian Code Cup 2017. По традиции выкладываем разбор задач и подводим итоги.

A. Маленькие числа
B. Новая клавиатура
C. Складывание фигуры
D. Остроугольные треугольники
E. Объединение массивов
F. Два поддерева

В раунде участвовали 603 человека: приблизительно по 200 лучших программистов с каждого квалификационного раунда. По результатам отборочного раунда мы взяли в финал 55 участников.

Все шесть задач отборочного раунда не смог решить ни один участник. С пятью задачами справились 15 человек. С четырьмя — еще 55 участников.

Трое лучших:

  1. На первом месте со значительным отрывом от преследователей (15 минут) оказался Ипатов Михаил из Костромы.
  2. Второе место занял Тихомиров Михаил из Москвы.
  3. На третьем месте — Пышкин Игорь из Санкт-Петербурга.

Кроме того, в топ-10 попали:

  1. Митричев Петр, Цюрих, Швейцария
  2. Геннадий Короткевич, Санкт-Петербург, Россия
  3. Александр Останин, Долгопрудный, Россия
  4. Ершов Станислав, Санкт-Петербург, Россия
  5. Djokic Nikola
  6. Данилюк Алексей, Одинцово, Россия
  7. Du Yuhao, Пекин, Китай

Всех участников и рейтинговую таблицу раунда можно найти здесь.

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

A. Маленькие числа

Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт

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

Сначала он написал в тетрадке числа a и b, после чего решил, что будет последовательно производить с ними одну из трёх операций:

  • Поделить оба числа на какой-то из их общих делителей;
  • Поделить a на один из его делителей g, а b умножить на g;
  • Поделить b на один из его делителей g, а a умножить на g.

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

Так как Влад ещё маленький, ему нравятся числа поменьше, потому он стремится минимизировать сумму чисел, написанных в тетрадке. Сам он не справляется. Помогите Владу определить, какую минимальную сумму чисел возможно получить такими операциями, и приведите пример пары чисел, которая может получиться в итоге.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 500).

Каждый тест описывается следующим образом: в единственной строке описания теста содержатся два числа a и b (1 ≤ a, b ≤ 109) — любимые числа Влада.

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

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

Если ответов несколько, то разрешается вывести любой из них.

Примеры

Входные данные
2
4 5
4 6

Выходные данные
1 5
2 3

Разбор задачи

Для начала разложим числа a и b на простые.

Теперь заметим, что если какое-то простое число p входит в произведение ab в степени выше первой, то мы можем либо сразу поделить оба числа на число p, либо если же одно из чисел не делится на p, то перенесём в него множитель p из другого числа, после чего поделим на p.

Очевидно, что чётность вхождения простых чисел в произведение ab не меняется во всех операциях. Тогда давайте оставим все простые в первой степени. Остались числа p1, p2, …, pn. Давайте назовём произведение всех этих простых чисел d, d ≤ ab. Утверждается, что этих простых не может быть больше 14. Если 1 ≤ a, b ≤ 109, то произведение ab ≤ 1018, а произведение первых 15 простых чисел превышает 1018). Теперь заметим, что конечный ответ — пара чисел (x, y) таких, что xy = d. Из этого следует, что второй элемент пары определяется однозначно по первому. Переберём всевозможные делители d за число x за O(2n), и выберем наилучшую пару.

B. Новая клавиатура

Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт

Петя купил новую клавиатуру. Она поддерживает n раскладок. В каждой раскладке можно набирать некоторое подмножество строчных букв латинского алфавита. Пронумеруем раскладки от 1 до n.

Петя хочет набрать некоторое сообщение, состоящее из m строчных букв латинского алфавита. Исходно активна первая раскладка. Петя может производить следующие действия:

  • Переключить раскладку. Тогда, если текущая раскладка имела номер i, новая раскладка будет иметь номер i mod n + 1, где mod — операция взятия остатка по модулю. Если предыдущим действием Петя также переключал раскладку, это действие займет b миллисекунд, иначе это действие займет a миллисекунд.
  • Набрать символ. Петя может добавить в конец текущего сообщения любую букву, содержащуюся в текущей раскладке. На это действие он потратит c миллисекунд.

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

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

В первой строке содержатся четыре целых числа n, a, b и c — количество раскладок у клавиатуры, и количество миллисекунд, необходимых для совершения переключения раскладки и набора символа (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 109, 1 ≤ c ≤ 109).

В следующих n строках содержится описание раскладок. Каждая раскладка описывается непустой строкой, в которой каждая строчная буква латинского алфавита встречается не более одного раза — подмножество букв, которые можно набрать в этой раскладке. Буквы в этой строке упорядочены в алфавитном порядке.

В последней строке содержится строка s — сообщение, которое хочет набрать Петя (длина строки s от 1 до 2 000). Строка s состоит из строчных латинских букв.

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

Выведите единственное целое число — минимальное количество миллисекунд, необходимое, чтобы набрать сообщение. Выведите  - 1, если набрать сообщение невозможно.

Примеры

Входные данные
5 3 2 1
abc
d
e
f
def
abcdef

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

Входные данные
1 1 1 1
a
z

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

Разбор задачи

Используем для решения метод динамического программирования. Состояние — d[i][j][k], где i — флаг, обозначающий тип предыдущего действия (0, если это было переключение раскладки, и 1, если это был набор символа), j — номер текущей раскладки, и k — количество набранных символов. Значение — минимальное время, необходимое, чтобы достичь этого состояния.

Переберем k. Для фиксированного k переберем j от 1 до n два раза. Обновим d[0][j % n + 1][k] = min(d[0][j % n + 1][k], min(d[0][j][k] + b, d[1][j][k] + a)). Перебрать j от 1 до n два раза нужно потому, что после набора k-го символа может быть включена раскладка с номером большим, чем раскладка, в которой будет набран следующий символ, и будет необходимо произвести переключение раскладок по циклу до нужной. После этого переберем j еще раз и обновим значения для k + 1. Если в j-й раскладке есть k-й символ сообщения, d[1][j][k + 1] = min(d[0][j][k], d[1][j][k]) + c.

В конце ответ равняется min(d[1][j][m]), где m = length(s), по всем j от 1 до n.

C. Складывание фигуры

Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт

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

Аккуратно вырезав ее из тетради, он сложил ее пополам вдоль линии клетчатой сетки (по горизонтали или по вертикали — он точно не запомнил), а также нарисовал копию сложенной фигуры в тетради. И не зря! Петя потерял фигуру, и все что у него осталось — копия сложенной фигуры, нарисованная в тетради. Теперь он хочет восстановить исходную фигуру.

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

Рассмотрим второй пример теста из условия. В нем сложенная фигура предславляет собой букву «П», а исходная фигура состоит из 12 клеток. Один из возможных вариантов исходной фигуры представлен на рисунке (сгиб происходит по прямой y = 3):

image

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 200).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится два целых числа n, k — количество закрашенных клеток, из которых состоит сложенная фигура Васи и количество клеток в исходной фигуре (1 ≤ n < k ≤ 105).

В каждой из следующих n строк содержатся два числа xi, yi — координатылевого нижнего угла i-й закрашенной клетки ( - 108 ≤ xi, yi ≤ 108). Гарантируется, что все закрашенные клетки различны и образуют связную фигуру.

Гарантируется, что сумма k во всех тестах одних входных данных не превосходит 105.

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

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

В первой строке выведите линию сгиба, а в k следующих строках по два целых числа (x’i, y’i) — координаты клеток связной фигуры, которую можно сложить пополам по выведенной линии сгиба, чтобы получить фигуру во входных данных.

Линия сгиба должна быть выведена одним из 4 способов:

  • L num — сгиб производится по прямой x = num, левая часть накладывается поверх правой;
  • R num — сгиб производится по прямой x = num, правая часть накладывается поверх левой;
  • U num — сгиб производится по прямой y = num, верхняя часть накладывается поверх нижней;
  • D num — сгиб производится по прямой y = num, нижняя часть накладывается поверх верхней.

Все x’i, y’i, а также координата линии сгиба по модулю не должны превышать 109. Гарантируется, что такая фигура существует. Если существует несколько подходящих ответов, разрешается вывести любой из них.

Примеры

Входные данные
2
7 14
0 0
0 1
0 2
1 2
2 2
2 1
2 0
7 12
0 0
0 1
0 2
1 2
2 2
2 1
2 0

Выходные данные
L 0
0 0
0 1
0 2
1 2
2 0
2 1
2 2
-1 0
-1 1
-1 2
-2 2
-3 2
-3 1
-3 0
U 3
0 0
0 1
0 2
1 2
2 2
2 1
2 0
0 3
1 3
2 3
0 4
2 4

Разбор задачи

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

Возьмём любую из клеток сложенной фигуры с минимальной координатой по оси OX — клетку (xi, yi). За линию сгиба возьмём вертикальную прямую x = xi, касающуюся этой клетки. Теперь слева нужно восстановить k – n клеток первоначальной фигуры, чтобы после накладывания левой части вдоль линии сгиба на правую получилась сложенная фигура из входных данных. Так как k – n ≤ n (иначе после сгиба стало бы больше n клеток), достаточно выделить из сложенной фигуры k – n клеток, образующих связную фигуру, содержащую клетку (xi, yi). Это можно сделать простым обходом в глубину.

D. Остроугольные треугольники

Ограничение по времени — 4 секунды
Ограничение по памяти — 256 мегабайт

Совсем недавно московский десятиклассник Дмитрий Захаров обогнал всех в построении множества точек в d-мерном пространстве, таких что все треугольники с вершинами в этих точках остроугольные.

Таня решила померяться силами с Дмитрием. Разумеется, она планирует использовать компьютер. Для начала она хочет решить следующую задачу. Дано n точек на плоскости, требуется найти количество остроугольных треугольников с вершинами в этих точках. Треугольник называется остроугольным, если все его углы строго меньше 90 градусов.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 666).

Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся число n (3 ≤ n ≤ 2000) — количество точек.

В следующих n строках содержатся по два числа xi, yi ( - 109 ≤ x, y ≤ 109) — координаты точек. Гарантируется, что все точки в одном тесте различные.

Суммарное количество точек по всем тестам одних входных данных не превосходит 2000.

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

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

Примеры

Входные данные
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3

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

Разбор задачи

Для подсчёта остроугольных треугольников достаточно из общего количества треугольников вычесть количество прямоугольных и тупоугольных треугольников. Будем считать три точки на одной прямой вырожденным тупоугольным треугольником.

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

Заметим: количество прямоугольных и тупоугольных треугольников равно количеству прямых и тупых углов с вершинами в заданных точках.

Осталось посчитать количество углов не меньше 90 градусов с вершинами в заданных точках. Переберём угловую точку и отсортируем по углу относительно данной все остальные точки. Воспользуемся методом двух указателей. Переберём вторую точку, которая будет образовывать угол. Для подсчета количества подходящих третьих точек достаточно заметить, что все точки, которые образуют угол не меньше 90 градусов с двумя другими точками, лежат на отрезке в отсортированном порядке и что отрезок сдвигается только в сторону увеличения угла.

Время работы решения: O(n2log(n)).

E. Объединение массивов

Ограничение по времени — 4 секунды
Ограничение по памяти — 256 мегабайт

Рассмотрим два массива натуральных чисел A = [a1, a2, …, an] и B = [b1, b2, …, bm]. Будем называть их k-объединением лексикографически минимальный массив чисел R длиной k, который разбивается на две непустые подпоследовательности, первая из которых является подпоследовательностью массива A, а вторая — подпоследовательностью массива B.

Формально говоря, необходимо найти лексикографически минимальный массив R = [r1, r2, …, rk], для которого существуют непустые наборы индексов 1 ≤ i1, 1 < i1, 2 < … < i1, t ≤ n и 1 < j1, 1 < j1, 2 < … < j1, k - t ≤ m в исходных массивах, а также наборы индексов 1 ≤ i2, 1 < i2, 2 < … < i2, t ≤ k и 1 ≤ j2, 1 < j2, 1 < … < j2, k - t ≤ k, такие что:

  • Для любых 1 ≤ p ≤ t, 1 ≤ q ≤ k - t выполнено i2, p ≠ j2, q;
  • Для любого 1 ≤ p ≤ t выполнено ai1, p = ri1, p;
  • Для любого 1 ≤ p ≤ k - t выполнено bj1, p= rj1, p.

Например, если A = [1, 2, 1, 3, 1, 2, 1], B = [1, 2, 3, 1], а k = 9, то их k-объеднением будет R = [1, 1, 1, 1, 2, 1, 2, 3, 1] (подпоследовательность из первого массива — [1, 1, 1, 2, 1], подпоследовательность из второго массива — [1, 2, 3, 1]).

По двум данным массивам A и B, а также числу k найдите их k-объединение R.

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

В первой строке ввода содержится число n — размер массива A (1 ≤ n ≤ 3000).

Во второй строке содержится n чисел ai — массив A (1 ≤ ai ≤ 3000).

В третьей строке содержится число m — размер массива B (1 ≤ m ≤ 3000).

Во четвертой строке содержится m чисел bi — массив B (1 ≤ bi ≤ 3000).

В последней строке содержится число k (2 ≤ k ≤ n + m).

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

Выведите k-объединение заданных во входном файле массивов.

Примеры

Входные данные
7
1 2 1 3 1 2 1
4
1 2 3 1
9

Выходные данные
1 1 1 1 2 1 2 3 1

Разбор задачи

Приведём два решения этой задачи: за O(k2•log(k)) и O(k2).

Решение за O(k2•log(k))

Разобьём решение задачи на три пункта:

  1. Для каждого массива X (A или B) и каждой длины 1 ≤ length ≤ |X| найдём minSubsequenceX[length] — лексикографически минимальную подпоследовательность X длины length.
  2. Переберём длину подпоследовательности в первом массиве — 1 ≤ t ≤ min(k – 1, |A|). Если 1 ≤ k – t ≤ |B|, возьмём minSubsequenceA[t] и minSubsequenceB[k – t], их надо объединить.
  3. Объединим две подпоследовательности в одну, получив тем самым лексикографически минимальную подпоследовательность длины k, обновим ответ.

Чтобы найти minSubsequenceX[length] для каждого length, сделаем вот что:

  • Посчитаем next[i][c], в котором будет храниться следующее после i вхождение символа c в X.
  • Посчитаем firstSymbol[length][i] — первый символ лексикографически минимальной подпоследовательности массива X[i..|X| – 1] длиной length. Для этого заметим следующее:
    • Если j1 = next[i][1] существует, то firstSymbol[1][i], firstSymbol[2][i],… firstSymbol[|X| – j1][i] начинаются с 1;
    • Если j2 = next[i][2] существует, то firstSymbol[|X| – j1 + 1][i], …, firstSymbol[|X| – j2][i] начинаются с 2;
    • Если j|alphabet| = next[i][|alphabet| существует, то firstSymbol[max(|X| – j1, |X| – j2, …, |X| – j|alphabet| - 1) + 1][i], …, firstSymbol[|X| – j|alphabet|][i] начинаются с |alphabet|.
      где alphabet — максимальное возможное число в массиве X.
  • Посчитав firstSymbol[length][i], можно восстановить лексикографически минимальную подпоследовательность X для каждой длины итеративно по одной букве.

Этот пункт работает за O(|X|2).

Найдя две лексикографически минимальные подпоследовательности SA и SB, их надо объединить в одну лексикографически минимальную длиной k. Будем двигаться по подпоследовательностям двумя указателями p1 и p2. Если SAp1 ≠ SBp2, то двигаем указатель, стоящий на меньшем числе. Если SAp1 = SBp2, двоичным поиском найдём наибольший общий префикс SA[p1..|SA|] и SB[p2..|SB|] и сравним следующие числа. Для сравнения подотрезков SA и SB можно использовать хеши.

Этот пункт работает за O((|SA| + |SB|)•log(max(|SA|, |SB|))) = O(k•log(k)).

Итого, суммируя все три пункта, получаем асимптотику O(|A|2 + |B|2 + k2•log(k)) = O(k2•log(k)).

Решение за O(k2)

Назовём массив A нулевым, а массив B — первым. Будем строить ответ по одному элементу. Также станем поддерживать вспомогательное значение dp[i][j], где i — номер массива (0 или 1), а j — индекс в этом массиве. dp[i][j] равно минимальному индексу в массиве 1 – i, с которого можно продолжать строить ответ, если в массиве i мы остановимся на индексе j.

На t-й из k итераций построения ответа будем находить минимальный элемент, такой, что, добавив его в ответ, последовательность можно закончить, т. е. что оставшихся элементов хотя бы k – t – 1. Также нужно учесть, что обе подпоследовательности обоих массивов, из которых строится ответ, должны быть непустые.

После добавления найденного элемента v в ответ за O(|A| + |B|) обновим значения dp. Для этого будем пользоваться посчитанным в предыдущем решении массивом next.

F. Два поддерева

Ограничение по времени — 4 секунды
Ограничение по памяти — 256 мегабайт

Рассмотрим подвешенное дерево. Рассмотрим вершину v, имеющую в поддереве хотя бы одну вершину на расстоянии k от v. Будем называть k-поддеревом вершины v дерево, полученное из поддерева вершины v удалением всех вершин, расстояние от которых до v больше k. Например, на иллюстрации ниже красным отмечено 2-поддерево вершины 3.

image

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

image

Дано подвешенное дерево. Требуется определить наибольшее k такое, что у него есть два одинаковых k-поддерева, корни которых различны. Эти поддеревья могут пересекаться.

На рисунке приведены деревья из примеров.

image

В первом примере корни одинаковых 1-поддеревьев — это вершины 2 и 3.

Во втором примере корни одинаковых 3-поддеревьев — это вершины 1 и 4.

В третьем примере корни одинаковых 0-поддеревьев — это вершины 1 и 2.

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

В первой строке задано число t — количество тестов (1 ≤ t ≤ 104).

Каждый из t тестов описывается следующим образом: в первой строке задано число n — количество вершин (2 ≤ n ≤ 105).

Далее следует n строк. В i-й из них задано число cnti — количество детей вершины i, а далее следуют cnti чисел — номера детей вершины i. Вершины нумеруются с единицы. Корнем дерева является вершина 1. Гарантируется, что заданный граф является деревом с корнем в 1.

Сумма n по всем тестам в одних входных данных не превосходит 2·105.

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

Для каждого теста выведите на отдельной строке максимальное k такое, что существует два одинаковых k-поддерева с разными корнями.

Примеры

Входные данные
3
5
2 2 3
1 4
1 5
0
0
8
1 2
2 3 4
0
1 5
2 6 7
0
1 8
0
2
1 2
0

Выходные данные
1
3
0

Разбор задачи

По условию в k-поддереве обязательно есть вершины на глубине k. Временно отменим это требование.

Рассмотрим все k-поддеревья для некоторого k. Их можно разбить на классы эквивалентности. Каждой вершине поставим в соответствие ck[v] — метку класса эквивалентности, которому принадлежит её k-поддерево.

При k = 0 все c0[v] равны, так как 0-поддерево любой вершины — это она сама.

При k = 1 c1[v] равно количеству детей вершины.

Научимся по массивам ck[v] и cm[v] строить массив ck + m[v]. Для начала поставим в соответствие каждой вершине v массив arrk + m[v], который будет однозначно задавать класс эквивалентности её k + m — поддерева. Пусть u1, …, us — потомки вершины v на расстоянии k в порядке обхода dfs. Тогда поставим в соответствие вершине v массив arrk + m[v] = ck[v], cm[u1], …, cm[us]. То есть k + m — поддерево вершины задаётся k-поддеревом вершины и m-поддеревьями нижней части k-поддерева. Ниже приведена иллюстрация для k = 3 и m = 1.

image

Чтобы получить для каждой вершины список её потомков на расстоянии k, запустим поиск в глубину от корня. Будем поддерживать в стеке путь до корня и каждую вершину класть в массив для её предка на расстоянии k.

Чтобы преобразовать массивы arrk + m[v] в числа ck + m[v], можно захешировать их, использовать бор или unordered_map из массива в номер. Время работы будет O(n), поскольку каждая вершина встречается в списках arr только один раз.

Имея массив ck[v], можно легко проверить, что существует два одинаковых k-поддерева. Для этого найдём две вершины с одинаковым ck, при этом нужно рассматривать только вершины, у которых есть потомки на расстоянии k от неё (это то требование, которое мы отменили в начале).

Чтобы найти максимальное k, посчитаем c1[v], c2[v], …, c2t[v] (2t — максимальная степень двойки, не превосходящая n). После этого используем аналог двоичных подъёмов по k: начнём с k = 0 и по очереди попытаемся прибавить к нему 2t, 2t – 1, …, 20.

Время работы решения: O(nlog(n)).

Планы на будущее

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

А напоследок делимся с вами одной из идей: возможно, в следующем году мы сделаем специальные номинации вроде «Лучший в языке». Тогда, например, обладатель лучшего решения на С++ получит отдельный приз. Что скажете?

ссылка на оригинал статьи https://habrahabr.ru/post/329476/

Как геймерам подарили право на ошибку — рождение и смерть карт памяти в игровых консолях

Привет, Гиктаймс! Не думай о секундах свысока, попивая сок классифицируя игровые консоли, потому что грань между nextgen, current-gen и классикой постоянно смещается. Но есть один критерий, который разделил консоли на периоды «тогда» и «сейчас» — карты памяти. Вспоминаем, как накопители для сохранений игр сначала стали «паспортом консольного геймера», а затем умерли, и родились заново в новейших игровых консолях.

«…а ещё у игровых машин в прошлом была такая штука, как карта памяти, внучок. Поразительная была техника! Проходишь, бывало, игру, и всё, чего ты в ней добился, остаётся с тобой в крохотном чипе памяти, меньше ладошки! Мы так удивлялись, когда поняли, что играть можно не залпом, да и без тетради с записанными паролями уровней под рукой…».


Не забуду мать родную А вот попробуете потом на старости лет объяснить внукам, которые даже HDD в глаза не видел, что у вас изображено

Но внуки будут недоумённо хлопать глазами в ответ, потому что для них даже «однокнопочные» QTE, авторегенерация здоровья, укрытия и чекпоинты на каждом шагу будут казаться слишком жёсткими условиями игры. Да и как объяснить человеку, что набором сохранений на 1-мегабайтной медлительной микросхеме мы дорожили больше, чем сотнями «достижений» уровня «сделать выстрел» в новой эпохе? Эмоции эмоциями, но время вернуться к конкретике: сегодня мы поговорим, какие консоли впервые примерили карты памяти, какие похоронили этот стандарт, и вспомним, какими были «игровые флэшки» до того, как первые USB Flash стали шагать по планете.

Сохранения игр в классических консолях — эпоха «превозмогателей»

Возможности сохранения в классических консолях не было не потому, что разработчики превозносили мастерство игроков или ждали, чтобы их игры проходили «за один присест» — просто тяжёлые времена были. Мало того, что разработка игр велась на ассемблере и напоминала скорее программирование микроконтроллеров, чем современный игрострой, так ещё и дефицит ресурсов был настолько заметен, что недостаток быстродействия в разрешении Full HD у этой вашей Xbox One — скорее ворчание пресытившихся девелоперов, чем непосильная тяжесть разработки.


Чаще всего возможность сохранения в клонах NES встречалась в обучающих картриджах

Ведь даже ёмкость картриджей в эпоху 8-битных консолях измерялась десятками килобайт (хотя «картриджи индивидуальной архитектуры» в той же NES были популярны), а о хранилище игрового состояния разработчики и вовсе не помышляли. В первую очередь, по финансовым соображениям — за внедрение энергозависимой памяти в лицензионный картридж разработчики платили круглые суммы разработчикам консолей. Вплоть до 16-битной эпохи, то есть, 4 поколения консолей, игр с возможностью сохранения было исчезающее мало. Например, для NES сохранения были доступны разве что в масштабных RPG, наподобие Ultima или Final Fantasy. А на рынке консолей-«клонов» и пиратских носителей — разве что в немногочисленных обучающих картриджах, чтобы от текстовых редакторов был хоть какой-то прок.

Как выкручивались геймеры? Либо держали консоль постоянно включенной (один японский любитель платформеров «мариновал» свою SNES таким образом 20 лет подряд!), либо, задолго до аксиомы Билана, доказывали, что «невозможное возможно». То есть, проходили игры со злосчастными «Continue? 3» или, в лучшем случае, кодами доступа к миссиям.


И сам картридж с батарейкой, и батарейка были дефицитом в 1990-е

В 16-битных консолях сохранения стали чуть меньшей экзотикой, но только если речь идёт о лицензионных картриджах. Потому что у пиратов глаза на лоб лезли от пестроты реализаций сэйвов. В популярной Sega Mega Drive, к примеру, путь сохранение выгружалось либо сходным с загрузкой следующего ROM способом, либо маппер просто переключал банк памяти и считывал код второго уровня взамен первого. А ещё, помимо конфигурации «SRAM + батарейка», встречались варианты с энергонезависимой serial EEPROM или FRAM… В общем, «не повторяйте это дома на пиратской фабрике». Вот пираты и не повторяли.

Сохранения там, где их не должно было быть: флоппи-дисковод для NES и «грабберы» игрового состояния с картриджей

Нельзя сказать, что сами разработчики консолей боготворили картриджи — просто с устоявшимся форматом носителей ROM некоторое время носились, как с чемоданом без ручки. В современном мире нечто подобное происходит с Blu-ray.

До того, как совпали звёзды (рекламные бюджеты Sony совпали с постепенным удешевлением Compact Disk как носителя) и пришла PlayStation, мейнстримными накопителями были картриджи, а создатели консолей робко внедряли новые форматы и «ломали зубы» о привычки аудитории.

Nintendo не была исключением, но создатели супер-популярной NES поначалу продвигали не дорогостоящие CD, а гораздо более доступные-привычные по десктопным компьютерам дискеты. Так на свет появился Famicom Disk System — флоппи-аддон для NES/Dendy. В разъём для картриджей подключался RAM-адаптер с собственной ОЗУ для хранения программы и спрайтов, контроллером дисковода и микросхемой-звуковым синтезатором, а в роли накопителей выступали двусторонние дискеты общим объёмом 112 Кбайт. Не так-то много, но первоначальный объём картриджа для NES составлял 48 Кбайт.


Попытки подружить NES с дискетами к успеху не привели

Вдобавок, уже в 1986 году, на момент выхода аксессуара, картриджи были в 10 раз дороже дискет, а «киллер-фичей» стала возможность за «копейки» записать новую игру на старый флоппи-диск в фирменном киоске Nintendo. Такого для консолей не предлагал никто!
Таким образом, сохранения игр на перезаписываемом носителе наконец перестали быть проблемой. Но дискеты постоянно выходили из строя (плохая защита от загрязнений), «эксклюзивы» для немногочисленных владельцев консолей с поддержкой floppy не окупались, а защиту DRM «спиратили» до того, как Nintendo презентовали новый тип накопителей за пределами Японии. В общем, игры с поддержкой сохранений портировали на картриджи «с батарейкой», а идея играть в старые игры по-новому не прижилась.

Зато уже в XXI веке для ретро-геймеров на свет появились чудо-машины, которые умели штамповать «быстрые сохранения» в реальном времени для игр с картриджей! Например, Nakitek Game Saver для SNES, который подключался как посредник между консолью и картриджем и элементарным образом позволял сохранять/загружать игровой процесс, или снижать скорость игры (чтобы её было легче пройти, очевидно же!). Базовая версия хранила сэйвы в реальном времени, в версии Plus игровой прогресс хранился во внутренней памяти, покуда был заряд в шести AA-батарейках, или пока был подключен блок питания от аксессуара.
Никакого вам «играй как задумано », но это неплохой компромисс для тех, кому охота играть не на ПК и эмуляторе, но и не проходить игру одним махом.


Nakitek Game Saver — «железный хак» для того, чтобы сохранять и загружать игры с картриджей в произвольном месте

Но всё это — новодел, а в эпоху царствования 8- и 16-битных консолей сохранения игр остались экзотикой. Но с таким положением дел всё же можно было жить, потому что игры были ориентированы на молодёжь, у которой хватало усидчивости и свободного времени на прохождение игр, да и вариативность классических игр почти всегда укладывалась в пароли к новым уровням, которые и были «сэйвами» в тетрадях заядлых игроков.

Только богатые могут позволить себе сохраняться

Первая домашняя консоль с поддержкой карт памяти была не совсем домашней и не совсем консолью — «24-битная» Neo-Geo образца 1990 года стала переделкой игрового автомата для домашнего использования. Супер-технологичная и неприлично дорогая консоль базировалась на комплектующих игрового автомата, и массовой не стала. Но задала новую моду — состоятельные ребята проходили игры дома, а потом блистали своими достижениями в местных игровых клубах.


Это сегодня дизайн Neo-Geo смущает игроков, а на заре 1990-х это была элитнейшая консоль!

Оригинальные карты памяти ёмкостью 2 Кбайт при 18 ячейках для сохранения сами по себе были достижением, а «тюнингованные» варианты сторонних производителей насчитывали 64 Кбайт и до 156 ячеек! С технической точки зрения карта представляла собой модуль SRAM с литиевым аккумулятором в комплекте. О быстродействии судить сложно, потому что в природе не существует «бенчмарков» для консольных карт памяти.
Дело было за малым — превратить карты памяти из аксессуара элитных консолей в массовое явление.


Так выглядела первая карта памяти в игровых приставках

Карты памяти — лучшие друзья компакт-дисков

Массовое хождение карт памяти в консолях совпало с расцветом игр на компакт-дисках. Долго ли, коротко ли, рекламой, процессорной архитектурой и ласковым отношением к разработчикам среди консолей «лихих девяностых» самой успешной консолью поколения стала Sony PlayStation.

Главное, что принесли с собой Sony в консольный игропром — стандартизацию. Одинаковые носители игр — стандартные компакт-диски ёмкостью 700 Мбайт. Никаких обходных путей и картриджей, как это было в раннюю эпоху! Нормальный язык C «здорового человека» взамен борьбы с ассемблером в разработке игр. И единообразные карты памяти вместо зоопарка вариантов сохранений в той же NES или Sega Mega Drive.

Вряд ли можно назвать карту памяти PS1 изысканной — 128 Кбайт энергонезависимой последовательной памяти (EEPROM), разделенных на 15 блоков + проприетарная файловая система. Впрочем, для девяностых годов это был неплохой вариант накопителя небольшой ёмкости, который будет постоянно перезаписываться. И 8-битный 8-пиновый последовательный порт, сходный по архитектуре с SPI и работающий на частоте 250 кГц. Кстати, примерно такие же интерфейсы Sony использовали и для геймпадов.


Ох, сколько мы вместе прошли, сколько повидали…

И ведь не скажешь, что 15 блоков памяти геймерам хватало с избытком — большинство игр довольствовались одной ячейкой, но даже нафаршированный чемпионатами, моделями авто и вариантами тюнинга автосимулятор Gran Turismo съедал от 5 блоков и больше (особенно страдали любители сохранять повтор гонки). А пошаговая стратегия Civilization II употребляла 2/3 ёмкости карты, то есть, 10 блоков на любом этапе прохождения! На такой случай существовали неоригинальные карты памяти с джампером, которым можно было переключить «страницы» по 15 блоков каждая. Но это уже совсем другая история…

Что любопытно, ровесница дебютной PlayStation, Nintendo 64, довольствовалась классическим уже сочетанием карт памяти (32 Кбайт/123 ячейки) с картриджами — носители для игр были по соотношению ёмкости и цены уже не впечатляли, но загрузка в такой конфигурации проходила намного быстрее и надёжнее, чем капризы оптического привода в консоли Sony.

Начало двухтысячных — эпоха расцвета карт памяти в консолях

Карты памяти окончательно перестали быть диковинкой с приходом шестого поколения консолей — Sony PlayStation 2, Microsoft Xbox, Sega Dreamcast и Nintendo Gamecube стали, пожалуй, последними консолями с жёсткой привязкой к физическому носителю игр (CD/DVD). А заодно и последними мейнстрим-консолями, которые полагались на карты памяти как основной источник хранения информации до конца своей конвейерной жизни.


Карта памяти для Sega Dreamcast сегодня выглядит дитём любви пейджера и тамагочи…

Самым изобретательным среди всех производителей оказалась Sega. Карты памяти VMU (Visual Memory Unit) мало того, что устанавливались не в корпус консоли, а в геймпад, так ещё и представляли собой подобие пейджера, на котором вспыхивали мини-игры или вспомогательная информация (патроны/здоровье в Resident Evil, например).

Впрочем, с технической точки зрения карты Sega были «пастгеном» и вмещали всего 128 Кбайт, тогда как для PlayStation 2, Xbox и GameCube стандартом стали 8-мегабайтные накопители, причём даже деление на «блоки» отошло в прошлое — объём сохранений стал измеряться килобайтами. И наконец появилась поддержка ECC, с которой карты памяти прибавили в долговечности.


… но мини-игры и перенос элементов UI на экран в геймпаде впечатляют и сегодня

А вопрос долговечности стоял более остро, ведь архитектура карт тоже изменились — теперь они полагались на современную NAND-флэш память, а вместо «самопальной» файловой системы использовали FAT (то есть, кормили Microsoft и её Xboxот души).

А ещё приятно, что «на пике формы» карты памяти наконец стали сравнительно быстрыми накопителями. Например, в последовательных операциях карта памяти PlayStation 2 разгонялась аж до 10 Мбит/с! Правда, в произвольном чтении/записи магия исчезала и быстродействие иной раз снижалось до 40 Кбит/с. А впрочем, какая разница — контроллер памяти в PS2 всё равно не позволял считывать данные на пределе возможностей памяти. Не расширяла полёт инженерной фантазии и поддержка legacy-карт эпохи PSOne в PlayStation 2.

Консоли современного типа — дорога сквозь SATA-II в облака

С анонсом консолей Xbox 360 и PlayStation 3 состоялась «кровопролитная» война форматов — Microsoft продвигала стандарт HD-DVD, Sony выступала за распространение Blu-ray. В итоге всех победили… жёсткие диски, которые мимоходом умертвили и карты памяти как явление в игровых приставках седьмого поколения.
То есть, никто не мешал владельцам PS3 прикупить переходник стоимостью $60 для импорта сохранений с PlayStation 1 и 2, но в действительности большинство геймеров смирились с «утратой» и взамен играли в старые игры на старых консолях. На Xbox 360 импорт сохранений со старой консоли был ещё более хлопотным и, мягко говоря, недокументированным.

Взамен началась временная «пляска» с затратами на покупку игр на Blu-ray дисках (первые консоли комплектовались HDD ёмкостью всего лишь 20 до 60 Гбайт!), а по мере того, как игры становились «тяжелее», пользователи осваивали замену стандартных бестолковых HDD более современными вариантам. PlayStation 3 к таким манипуляциям абсолютно лояльна, а вот владельцы Xbox 360 учились «правильно готовить» покупные HDD, чтобы консоль опознала диски и была в состоянии с ними взаимодействовать.

Со сменой поколений в PlayStation 4 и Xbox One мало что изменилось — разве что Xbox капитулировал и обзавёлся поддержкой Blu-ray, а оптические приводы ныне выглядят архаизмом. И, наконец, прогресс в играх почти всегда копируется в облачное хранилище и привязан к учётной записи игрока, а не просто находится на HDD. А экспорт и импорт сохранений теперь можно совершать на обычные USB-флэшки. Правда, без входа в свою учётную запись, вряд ли вы сможете поделиться с другом своими игровыми достижениями.
Реализация накопителей даже в самых современных консолях далека от идеала — и PlayStation 4, и Xbox One взаимодействуют с накопителями в рамках архаичного стандарта SATA-II образца 2004 года.


Эпоха картриджей и «болванок» сменилась компьютерно-ноутбучной традицией апгрейда HDD/SSD

Такая конфигурация настолько «унылая», что апгрейдить в ней, казалось бы, нечего? Но мы уже проверяли, есть ли смысл устанавливать SSD в компьютеры с поддержкой старых версий SATA, и да — смысл есть!
Причём в случае с Xbox One производительность у внешнего накопителя USB 3.0 окажется выше, чем у внутреннего в рамках SATA-II! Чудны дела твои, Microsoft AMD! А ведь это идея — сравнить быстродействие игр в Xbox One посредством USB 3.0 между флагманской флэшкой (HyperX Savage, например), не менее флагманским SSD (внезапно, HyperX Savage) и бюджетным SSD, чтобы нащупать «потолок производительности» при замене накопителей в новых консолях! *записывает в блокнот*
PlayStation 4, к слову, тоже оснащена быстрыми портами USB, но вот установить игры на внешний накопитель уже не позволяет.


Xbox One способен загружать игры с накопителя USB 3.0 проворнее, чем с интегрированного HDD, ограниченного скоростными пределами SATA-II

Портативные консоли — новое пристанище карт памяти

«Младшие братья» настольных игровых приставок развивались иначе. Sony PlayStation Portable полагалась на проприетарные диски UMD для игр и карту памяти MemoryStick для мультимедийного контента и сохранений. Правда, всю конвейерную жизнь PSP пираты «перетягивали одеяло» на себя и переназначали карту памяти как накопитель для загрузки игр.

В консоли PS Vita сохранения находятся на карте памяти PlayStation Vita card и дублируются в облачном хранилище. Можно сколько угодно ругать Sony за проприетарные форматы накопителей, но хотя бы работоспособный способ бэкапа сохранений в новой консоли есть.


О мёртвых — либо хорошо, либо ничего (кроме правды), но оригинальные накопители PS Vita популярности ей уж точно не прибавили

А вот у Nintendo с самого начала была какая-то тактика, и она её придерживалась. Заключалась тактика в том, что портативная консоль — вещь личная, а значит, никаких переносных карт памяти в ней быть не должно. За сохранения в консолях Gameboy игры сохранялись на энергонезависимую память картриджа, а в новейшей Nintendo Switch прогресс игры оседает строго на внутреннем накопителе. Причём в текущих прошивках невозможно даже сделать резервную копию или отправить сохранения в «облако»!


Nintendo Switch — последняя надежда любителей качественных портативных консолей

Но «окирпичивание» Switch — редкость, а дефицит внутренней памяти для установки игр — уже данность. Можно полагаться на проприетарные ROM-карты памяти Nintendo с играми, но всё это полумеры, и самая современная портативная консоль уже сейчас неспособна вместить в себя новые игры без внешнего накопителя. Nintendo заявляет поддержку накопителей microSDXC U1, то есть, реализовать потенциал недорогих и быстрых карт памяти можно уже сейчас. Оптимальными, пожалуй, будут карты памяти ёмкостью 128 Гбайт — сегодня карты памяти, которые выжмут из Nintendo Switch максимум скорости (Kingston SDC10G2, например), оценены в среднем в 3500 рублей.


Не факт, что Switch раскроет потенциал UHS-I U3, а вот карты microSDXC UHS-I U1 этой консоли отчаянно необходимы

Было, да прошло

Жаль, что эпоха компьютерных клубов, игр по локальной сети и одной карты памяти на компанию друзей миновала. Грустно видеть, что сегодня почти все игры комплектуются очень лояльно расставленными чекпоинтами и другими видами «попустительства» ленивым геймерам. Но виноваты в этом не консоли, и не карты памяти — просто мир стал быстрее, а в игры теперь играют не только молодые и горячие энтузиасты. Давайте просто радоваться тому, что консоли стали быстрее, от выбора игр разбегаются глаза, а за вожделенными новинками больше не нужно стоять в очереди в ларёк с картриджами или у прилавка на рынке. Хороших вам игр и быстрого железа!

Всем компьютерным энтузиастам, которые прочли статью и не прониклись, о чём таком горюют консольщики, мы дарим скидку в размере 10% на модули HyperX Fury DDR4 (в любом цвете). Скидка действует в «Юлмарте» до 29 мая 2017 по промокоду HXCOLOUR. Ударим апгрейдом ПК по консольной унификации!


Подписывайтесь и оставайтесь с нами — будет интересно!

Для получения дополнительной информации о продукции Kingston и HyperX обращайтесь на официальный сайт компании. В выборе своего комплекта HyperX поможет страничка с наглядным пособием.
ссылка на оригинал статьи https://geektimes.ru/post/289411/

Биолог из Колумбии едва не сел в тюрьму на 8 лет из-за публикации тезисов чужой статьи на Scribd

Колумбийский аспирант-биолог Диего Гомес (Diego Gómez) шесть лет назад решил опубликовать тезисы к чужой статье, материалы которой ему понравились. Он сделал тезисы, решив поделиться ими с другими людьми на сервисе публикации различных документов Scribd. Вскоре после размещения публикации администрация сервиса поменяла правила, предложив незарегистрированным пользователям оплачивать $5 за загрузку любого материала.

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

Сфера интересов Диего достаточно широка. Он изучает биоразнообразие региона, разрабатывая методы, позволяющие сохранить находящиеся под угрозой вымирания виды животных и растений из Южной Америки. Также колумбиец старается пополнять свои знания в указанной сфере, но вот беда — большинство качественных научных работ доступны лишь за деньги в специализированных научных журналах.

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

С течением времени Гомес начал более активно работать в Cети, где есть большое количество публикаций по интересующей его тематике, плюс сеть дает возможность связываться с коллегами. Иногда аспиранту попадаются и открытые публикации, которые выкладываются в сеть учеными, которые понимают, что научная литература должна находиться в свободном доступе. Если пользоваться такими статьями, нужно лишь выполнять обычные обязательства — указывать источник со всеми необходимыми деталями.

В 2011-м году Гомесу попалась очень ценная для него публикация. Аспирант, недолго думая, составил тезисы и выложил их на Scribd, надеясь, что эти материалы пригодятся его коллегам. Но другой ученый, автор самой статьи, решил, что колумбийский аспирант хочет получить деньги, выдавая чужую публикацию за свою и подал иск в суд. Автор, о котором идет речь — американец. А между Колумбией и США действует специальное соглашение, которое позволяет наказывать нарушителей авторского права, даже в том случае, если нарушитель из другой страны.

Гомесу повезло в том, что за его защиту в суде взялась юридическое объединение Fundación Karisma. Эта организация постаралась доказать невиновность Гомеса, в чем и преуспела. Стоит отметить, что в Колумбии нет развернутого закона об авторском праве. Там действует устаревший закон о правах авторов. Этот закон и связанные с ним документы появились более 20 лет назад. Они оговаривают ряд специфических ситуаций, которые очень редко встречаются в наше время, а к интернету и вовсе неприменимы. Тем не менее, часть этих законов была использована в суде против Гомеса.

К счастью для него, адвокаты сумели доказать, что при выкладывании тезисов статьи у Гомеса не было злого умысла. Кроме того, есть еще один важный нюанс — тем же юристам удалось доказать, что автору публикации не был нанесён ущерб. Как уже говорилось выше, материал был выложен изначально на Scribd, когда там еще не требовалось платить деньги за загрузку материала.


Аспирант Колумбийского университета Диего Гомес

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

Стоит отметить, что публикация, которую использовал Гомес для создания тезисов, была опубликована еще в 2006 году. Колумбийский аспирант, в свою очередь, выложил материал на Scribd в 2011 году. По мнению юристов организации Fundación Karisma, тот факт, что кто-то, опубликовавший работу еще в начале 2000-х считает, что этот материал может использоваться в коммерческих целях, показывает нам несостоятельность того механизма обмена научными материалами, который существует сегодня. Основная проблема — это закон об авторском праве, который многие считают препятствием на пути к дальнейшему развитию науки. Необходимо реформировать законодательство, как международное, так и локальное, для того, чтобы исключить негативное влияние законов на науку и ее развитие.
ссылка на оригинал статьи https://geektimes.ru/post/289519/

Security Week 21: BlueDoom защищает от WannaCry, криптолокер угрожает медтехнике, субтитры – новый вектор атаки

Благотворительный марафон сливов ShadowBrokers продолжает приносить плоды. Вслед за WannaCry в Сеть ворвался еще один червь, под завязку накачанный эксплойтами. Один семпл забрел к хорватам из местного CERT, и получил имя EternalRocks, второй такой же попался Heimdal Security и был назван не менее пафосно – BlueDoom. На целевую машину они заходили точно так же, как WannaСry, через порт 445.

Новый червяк любопытен большим числом интегрированных в него эксплойтов: он использует EternalBlue, EternalChampion, EternalRomance, EternalSynergy, ArchiTouch, SMBTouch, и DoublePulsar – все это благодаря доброте ShadowBrokers.

Заразив машину, EternalRocks на протяжении суток не делает ничего (видимо, на случай попадания запуска в песочнице – авторы полагают, что исследователи не будут так долго ждать, пока пойманная особь задергается), а потом стучится на сервер управления через сеть Tor. Но ничего особо вредоносного, помимо эксплойт-пака для дальнейшего распространения, сервер ему так ни разу и не прислал, чем изрядно озадачил исследователей.

Тайну раскрыл сам автор, разместив на командном сервере сообщение, гласящее, что пугаться нечего, его червь – никакая не рансомварь, а очень даже полезный самоходный «файрволл», закрывающий порт 445 у своих жертв. Вместе с тем автор прекратил кампанию, отключив на сервере отправку эксплойт-пака. Похоже, пристальное внимание исследователей ему не понравилось. А чего он ждал? Люди не очень-то любят, когда их пытаются осчастливить насильно.

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

Siemens и Bayer готовят антиWannaCry-патчи для медицинской техники

Новость. Казалось бы, в чем тут сенсация – патчи это же всегда хорошо. Однако ведь интересно получилось: оказывается, немало медицинской техники работает Windows, подключено к Интернету и смотрит в Интернет по SMB. Удобно это, видимо, для обслуживания. Мало ли, новую прошивку закинуть, логи глянуть или еще что. И до поры такой подход казался вендорам безопасным. МРТ-аппарат ведь не будет открывать подозрительные аттачи в письме, и на левые сайты не полезет.

Но WannaCry относится к полузабытой породе зловредов – это сетевой червь, использующий для распространения сетевой эксплойт, и достаточно просто слушать 445, чтобы заразиться. При этом никто вроде бы не сообщал о том, что модный троянец где-то вывел из строя медицинскую аппаратуру, но, учитывая технологию его распространения, это просто неизбежно. Тем более что мы знаем, как неохотно и неторопливо IoT-вендоры выпускают патчи. Так что, если они зашевелились – повод был, и повод серьезный.

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

Разработан вектор атаки через субтитры

Новость. Исследование. Давайте уже отдохнем от WannaCry и глянем, что еще в мире происходит. Check Point Software выявили новый оригинальный вектор атаки на пользователей. Казалось бы, чем может быть опасен файл с субтитрами для фильма? Это же текст! Но нет, практически все популярные видеоплееры и медиацентры имеют уязвимости, позволяющие запускать на системе произвольный код, подсунув правильно сконструированные субтитры.

Это очередное подтверждение тезиса, что уязвимостей нет там, где их не ищут. Стоило поискать – и в одном только VLC их нашлось сразу четыре. Эксперты выкатили небольшой список дырявых приложений, пригодных для такого типа атаки. Среди них: VLC, Kodi, Stremio и Popcorn Time, упомянуты и Smart TV. Во всех случаях злоумышленник получает полный контроль над системой жертвы.

Самое обидное, что рискуют даже те, кто никогда не смотрит фильмы с субтитрами. Многие видеоплееры автоматически ищут и загружают субтитры к проигрываемому фильму, также не составляет труда приложить вредоносный файл к раздаче на торренте. Технические подробности компания не сообщает ввиду масштабности проблемы – слишком много уязвимого софта, слишком много пользователей под угрозой (у одного лишь VLC более 170 миллионов загрузок). Впрочем, все упомянутые в новости проигрыватели уже получили патчи, так что обновляйтесь.

Древности

«Twin-351»

Вирус-«спутник»: при запуске .EXE-файла создает файл-«спутник», имеющий имя запускаемого файла и расширение .COM (например, XCOPY.EXE – XCOPY.COM), и записывает в него свою копию. При запуске любого файла из командной строки сначала ищутся .COM-файлы, а только затем – .EXE. В результате первым будет запущен .COM-файл, содержащий вирус. Вирус, в свою очередь, инсталлирует свою TSR-копию и запускает файл .EXE.

Реализует довольно оригинальный «стелс»-механизм: устанавливает у файла- «спутника» атрибут hidden, перехватывает int 21h и обрабатывает функцию FindNext таким образом, что на экран не выдаются файлы, имеющие атрибут hidden. В результате .COM-файлы, содержащие тело вируса, не видны ни при использовании команды DIR, ни при работе в Norton Commander’е.

Цитата по книге «Компьютерные вирусы в MS-DOS» Евгения Касперского. 1992 год. Страницa 85.

Disclaimer: Данная колонка отражает лишь частное мнение ее автора. Оно может совпадать с позицией компании «Лаборатория Касперского», а может и не совпадать. Тут уж как повезет.
ссылка на оригинал статьи https://habrahabr.ru/post/329570/

Mobile Dimension разработал «планшет для консультантов торгового зала» по заказу М.Видео

image

В рамках проекта «Сделка здесь и сейчас!» команды технических специалистов М.Видео и Mobile Dimension разработали планшеты для консультантов торгового зала.

О компании
М.Видео – лидирующая российская розничная сеть, специализирующаяся на продаже электроники и бытовой техники в России. М.Видео является одной из крупнейших европейских компаний в этом сегменте. В 1 квартале 2017 года сеть насчитывала 399 магазинов в 165 городах России.

Задача перед Mobile Dimension
Не так-то просто быть продавцом-консультантом в М.Видео. Даже если ты настоящий эксперт с ярко выраженным энциклопедическим складом ума и феноменальной памятью, запомнить огромный ассортимент магазина – от блендеров до плазменных панелей, от мобильных чехлов до холодильников, насчитывающий около 20 000 наименований техники, сложно. А теперь представьте, что для каждого товара есть целый набор аксессуаров, и у каждого – свои технические характеристики, свои преимущества и недостатки. И это еще не все сложности: покупатель не просто ждет квалифицированный ответ, он ждёт его мгновенно, здесь и сейчас. И ведь покупатель – не один, покупателей много.
К счастью, в этом мире есть мобильные технологии и Mobile Dimension. Благодаря слаженной совместной работе технических команд Mobile Dimension и М.Видео у продавцов магазинов сети появился свой персональный электронный консультант, который знает все и получает данные онлайн. Причем не только об ассортименте в целом и каждом товаре в отдельности, но и немного о покупателе.

На старте задача звучала предельно четко: повысить объем продаж за счет внедрения «планшета для консультантов торгового зала» на 3%. По факту первых встреч и обсуждений стало очевидно, что планшет должен способствовать не только повышению эффективности продаж, но и росту up- и cross-sales. А еще он должен быть интегрирован в программу лояльности и уметь предложить покупателю дополнительную мотивацию приобретать больше товаров и увеличить свой средний чек. Для полного понимания функционала были проведены встречи с десятками консультантов, а также проанализирован процесс продаж в условиях реальных магазинов.
Каждый консультант магазина, взяв в руки планшет с нашим приложением, должен получить:

  • Исчерпывающую информацию о товарном ассортименте магазина и сети в целом
  • Полную информацию о технических характеристиках каждого продукта
  • Возможность сравнить аналогичные товары
  • Исчерпывающую информацию обо всех аксессуарах и сопутствующих товарах к каждому продукту
  • Доступ к профилю клиента и бонусному счету в программе лояльности «М.Видео — Бонус»
  • Возможность в несколько кликов зарегистрировать покупателя в системе лояльности
  • Информацию о действующих скидках и акциях в магазине

Сложно? Да! Но для нас нет невыполнимых задач.

Решение Mobile Dimension
С целью реализации проекта на стороне Mobile Dimension была выделена проектная группа в составе 11 человек, включая четырех back-end разработчиков, трех тестировщиков, двух мобильных разработчиков и двух UX/UI-дизайнеров. Для повышения динамики работы группа технических специалистов Mobile Dimension работала непосредственно в головном офисе М.Видео бок-о-бок с проектной командой со стороны заказчика по методологии Agile-Scrum. Решение было реализовано на платформе UWP для целевых устройств — планшетов на базе Windows 10.

Удобный каталог товаров

image

image

  • Полный каталог товаров
  • Исчерпывающая информация о товарах
  • Характеристики
  • Наличие в магазине

Александр, старший бэк-енд разработчик Mobile Dimension:
В рамках back-end разработки был использован классический стек технологий, включая Java 8, Spring и Hibernate. Чтобы сделать дальнейшее развитие бизнес-логики решения модульным, гибким и легким, мы применили микро-сервисную архитектуру, построенную на Docker. Каждый сервис получился максимально изолированным благодаря API Gateway, проксирующему вызовы от приложения к сервисам, при необходимости агрегируя данные. Если сервис А нуждается в данных сервиса В, то он не забирает их напрямую, а использует выделенный маршрутизатор. С одной стороны, это несколько усложнило код, с другой – каждый сервис стал работать практически в изолированном окружении. Это позволяет легко писать unit-тесты уровня сервиса без мокирования. Такая ситуация позволяет ещё на этапе сборки понять, нарушили ли систему нововведения, и, таким образом, сэкономить время. Если сервис обращается к базе данных, то перед тестом происходит миграция относящихся к этому тесту данных, и, при необходимости, эти данные сразу вставляются в код.
Так как все запросы принимает на себя Gateway API, к нему предъявляются повышенные требования по надёжности и производительности. Так как на период ожидания ответов от других сервисов уходило немало времени, мы применяли асинхронную схему взаимодействия, доступную в 8-й версии Java. Для выполнения запросов мы использовали библиотеку AsyncHttpClient, которая используется и в средстве для нагрузочного тестирования gatling. С помощью Swagger у нас всегда была актуальная информация об API нашего приложения, а благодаря MapStruct мы смогли легко модифицировать данные между сервисами.
Немалую часть приложения занимает общение с сервисной платформой — общим API, скрывающим за собой все бизнес-системы типа CRM. По сути, это единственное, что нам приходилось мокировать в тестах.

Быстрый поиск, сравнение и заказ товаров

image

image

  • Сравнение товаров
  • Быстрое оформление покупки

Виктория Шишкина, UX/UI-дизайнер Mobile Dimension:
В чем была главная сложность при создании этого планшетного решения? Нам надо было создать инструмент, интересный не только продавцу, но и покупателю! Корпоративное и пользовательское решение в одном приложении! Это challenge!
Это был проект, который мы создавали бок-о-бок с консультантами магазинов. Мы работали не столько в офисе, сколько «в полях». Мы ездили в магазины М.Видео, общались с продавцами и консультантами, собирали информацию, обсуждали удобство будущего интерфейса. Собранная информация ложилась в основу концептов, которые вновь тестировались в условиях живого общения с конечными пользователями. Мы намеренно выбирали различных специалистов: опытных консультантов и новичков. Посещали разные точки: например, я узнала, что магазины в торговых центрах и отдельностоящие отличаются друг от друга количеством покупателей и целями их визита – и все это нужно было предусмотреть в решении и отразить в дизайне. Для проверки самых безумных идей создавались интерактивные анимации в Principle: сначала мы обсуждали их внутри команды, затем – с командой заказчика, и обязательно — несли показывать продавцам. Одним словом, мы проверяли интерфейсные решения по мере их создания, что помогло вовремя корректировать и совершенствовать интерфейсы, избежать крупных ошибок и больших затрат ресурсов.
Описанные работы проводились в рамках первого этапа, в ходе которого мы собрали воедино, с одной стороны, требования бизнеса, с другой – пожелания продавцов. В основу оформления лег бренд-бук М.Видео и требования Windows. Дизайн разрабатывался с помощью Sketch. Из первых макетов интерактивные прототипы создавали в Marvel App, открывали их на планшете и тестировали пользовательские сценарии. В настоящее время работа над интерфейсом продолжается. Мы получаем новые отзывы, думаем над новыми решениями и стремимся сделать приложение еще более удобным и функциональным.

Программа лояльности
image

  • Информация о покупателе
  • Калькулятор бонусов

Ян Мороз, UWP-разработчики Mobile Dimension:

Выбирать технологию UWP (Universal Windows Platform) необходимо всем компаниям, для которых главной экосистемой является ОС Windows 10. М.Видео — в их числе. UWP позволяет разворачивать созданные приложения не только на мобильных устройствах или планшетах, но и на ПК сотрудников компании. Сохранив и улучшив наследие WPF – MVVM из коробки, богатые средства по разработке, стилизации и расширение контроллов – UWP фокусируется на решении насущной задачи, а именно на разработке приложений, которые при минимальной плате могут разворачиваться на всех типах устройств на ОС Windows 10.
Так совпало, что во время разработки «планшета консультанта» для М.Видео вышло решение Visual Studio 2017, которое также расширило наши возможности работы с UWP. Чего стоит только возможность редактирования разметки приложения в режиме Debug без необходимости перезапуска для просмотра изменений — это значительно ускорило скорость разработки приложения!
С самого начала разработка «планшета консультанта» осуществлялась под определенное разрешение дисплеев устройств, но в тоже самое время закладывалась адаптивность создаваемого UI под другие разрешения. Адаптивная модель, реализованная в UWP, позволила работать «на два фронта»: командой в срок реализовались макеты, предоставленные дизайнерами, а спустя несколько месяцев, когда возникла потребность в разворачивании на мобильных устройствах, буквально за неделю был предоставлен прототип этого же приложения, но под совершенно другое разрешение. Заказчик был доволен и согласился, что под мобильные устройства не требуется переработка UI- компания не потеряла драгоценного времени, а команда не тратила силы на решения, которые в итоге пришлось бы переделывать.
В процессе дальнейшей разработки мы обнаружили приятное нововведение от Microsoft: в отличии от WPF, все контролы, входящие в стандартную библиотеку, практически полностью находятся в открытом доступе, благодаря чему мы имели возможность изменять существующие контролы, а не писать их с нуля в соответствии с потребностями проекта.

Зона покупателя

  • Спидометр бонусов
  • Информация о баллах и бонусах

Александр Ефимов, ведущий инженер по автоматизации тестирования Mobile Dimension:
В рамках проекта в задачи тестировщика входили настройка CI, написание автотестов для frontend (UWP – java+ appium) и backend (java), а также проведение нагрузочного тестирования.
В начале стояла задача настройки CI. Требовались сборки артефактов бекенда и фронтенда, а также автотестов на бекенд. Для этого мы выбрали TeamCity. Сделав конфигурации для сборки артефактов, я занялся конфигурациями для развертывания приложения. В итоге артефакты стали собираться в одной сборке и развертываться несколькими сборками в Docker-контейнеры (Dev, Test, Front Test). Для отладки в dev-сборках и мокирования сторонних сервисов в автотестах также в докер контейнере был выбран Wiremock. Далее была сделана сборка для тестирования всех коммитов, в которой приложение собиралось, развертывалось, тестировалось и, при отсутствии проблем после тестирования, удалялось. Следующим шагом стали конфигурации для релизных артефактов. В них приложение собирается в докер-контейнер для продакшен-сервера и прод-лайк тестового стенда. Хранятся контейнеры в докер-репозитории, обновление продакшен-сервера занимает не более 5 минут, но с учетом двух нод – проходит бесшовно. Фронтенд написан на C#(UWP), собирается на сервере CI с помощью msbuild в конфигурациях х64 и х86.
Теперь о тестировании. Все тест-кейсы и результаты запусков тестов ведутся в TestRail. Автотесты бекенда написаны на java с применением фреймворков – testng, rest-assured, hibernate, spring. Перед каждым запуском очищается тестовая база и маппинги wiremock. Тесты запускаются в несколько потоков параллельно по классам. После выполнения тестов результаты собираются и добавляются в TestRail. В автотестах фронтенда используется другой стек в соответствии с требованиями заказчика, а именно java и junit+cucumber. Сами тесты написаны на скриптовом языке gherkin, они хранятся в TestRail, во время запуска забираются оттуда и прогоняются. Также были использованы spring, hibernate и appium. Для автоматической установки последней сборки приложения были написаны скрипты на powershell.

Отзыв со стороны заказчика

Евгений Джамалов, куратор проекта со стороны М.Видео:
«Планшет консультанта» — это сложный проект сразу по нескольким причинам. Во-первых, из-за многозадачности. В ТЗ был включен обширный функционал для обслуживания множества бизнес-процессов и задач, стоявших перед компанией, а также HR-работа с продавцами. Во-вторых, в определенный момент мы осознали необходимость интеграции разработки с уже существовавшим на тот момент решением m_mobile, которым активно пользовались консультанты в зоне смартфонов и цифровой электроники. Это потребовало постепенной доработки и изменения интерфейса. По сути, мы решали нелегкую и очень интересную задачу интеграции приложений, когда нужно избежать дублирования функций и сохранить для пользователя единый user flow. В-третьих, масштаб, обуславливавший повышенные требования к нагрузкам и безопасности данных.
Команда Mobile Dimension продемонстрировала гибкость, оперативность и полное соответствие профессиональных навыков сложной технической задаче. Выбранный формат работы Agile позволил нам тесно взаимодействовать друг с другом, быстро адаптироваться к изменениям и динамично двигаться к цели. Первоначальная задача по выпуску минимального жизненного функционала выполнена успешно. Теперь перед нами новая цель – как можно быстрее предоставить нашим пользователям полнофункциональное приложение, чтобы продавцы «М.Видео» оперативно сопровождали полный цикл покупателя в розничном магазине — от помощи в выборе техники и совершения покупки до пост-продажного сопровождения.
ссылка на оригинал статьи https://habrahabr.ru/post/329566/