Добрый день.

26-го марта в 10:00 (московское время) стартует Отборочный Раунд 2 чемпионата Технокубок 2016. Раунд будет длиться два часа, участникам будут предложены 5 задач. По его результатам лучшие 150 участников (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке http://mirror.codeforces.com/contests/649. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 100 минут).

Зарегистрироваться на Отборочный Раунд 2 →
Для зарегистрированных участников олимпиады

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

• короткое описание формата
• полное описание формата

Напоминаем, что регистрация на олимпиаду еще открыта. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

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

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD 1: Раунд будет рейтинговым для всех участников олимпиады "Технокубок", то есть как для официальных участников раунда, так и участников вне конкурса.

UPD 2: Дорешивание доступно в Тренировках: 2016 Технокубок: Отборочный Раунд 2.

24-го марта в 09:00 (московское время) стартовал Ознакомительный Раунд 2. Его продолжительность составит двое суток, его результаты не будут как-либо влиять на прохождение в следующие этапы. Его единственная цель — дать вам возможность ознакомиться с платформой Codeforces и её тестирующей системой. Приглашаем вас принять в нём участие! Для участия перейдите по ссылке http://mirror.codeforces.com/contests/647. Раунд будет содержать несколько несложных ознакомительных задач и будет открыт для официальных участников Технокубка.

Раунд продлится 48 часов, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Ознакомительный раунд, как и все предстоящие раунды, требует отдельной регистрации, она будет открыта на протяжении всего раунда.

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

Напоминаем, что еще открыта регистрация на олимпиаду для школьников Технокубок. Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces в этом году впервые проводит Технокубок — первую совместную олимпиаду по программированию для школьников. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы.

Зарегистрироваться на олимпиаду!

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Первый отборочный раунд уже состоялся, а второй начнется 26 марта (суббота) в 10:00.

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

648A - Наибольший подъем

Для решения данной задачи насчитаем высоту каждой горы и сохраним ее в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдем заданную матрицу, и если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звездочке, обновим высоту j-й горы: h[j] = max(h[j], n - i). Осталось просто проитерироваться по столбцам от 0 до m — 2 включительно, и, если текущий столбец равен j, обновить величину максимального подъема или максимального спуска величиной |h[j + 1] - h[j]|.

int n, m;
int h[N];
char c;

void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c;
			if (c == '*') {
				h[j] = max(h[j], n - i);
			}
		}
	}
	int maxU = 0, maxD = 0;
	for (int i = 0; i < m - 1; i++) {
		int diff = h[i + 1] - h[i];
		if (diff > 0) {
			maxU = max(maxU, diff);
		} else {
			maxD = max(maxD, -diff);
		}
	}
	cout << maxU << ' ' << maxD << endl;
}

648B - Собери стол

Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним ее в переменную len (len = sum / n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберем части ножек переменной i от 0 до n - 1 включительно и будем выводить в ответ пары вида (a[i], len - a[i]).

int n, len, sum;
int a[N];

int main() {
	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		cin >> a[i];
		sum += a[i];
	}   	
	len = sum / n;
	sort(a, a + 2 * n);
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ' << len - a[i] << endl;
	}
}

648C - Путь Робота

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

int n, m, sx, sy;
char a[N][N];   

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char dir[] = {'U', 'D', 'L', 'R'}; 

void solve() 
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'S') {
				sx = i, sy = j;
			}
		}
	}
	a[sx][sy] = '*';
	int px = -1, py = -1;
        while (true) {
    	    bool wasMove = false;
    	    for (int i = 0; i < 4; i++) {
    		int nx = sx + dx[i];
    		int ny = sy + dy[i];
    		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
    			continue;
    		}
    		if (a[nx][ny] != '*') {
    			continue;
    		}
    		if (nx == px && ny == py) {
    			continue;    		
    		}
    		a[nx][ny] = '.';
    		px = sx, py = sy;
    		sx = nx, sy = ny;    		
    		cout << dir[i];	
    		wasMove = true;
    		break;
            }         
            if(wasMove) {
           	break;
            }
        }
    puts("");
}

648D - Собачки и миски

Если представить каждую миску в виде отрезка [u_j - t_j, u_j + t_j], то i-я собачка сможет покушать из j миски, если u_j - t_j ≤ x_i ≤ u_j + t_j.

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

Легко видеть, что такая жадность приводит к оптимальному ответу:

• Если самая левая собачка может покушать, то нет смысла ей не кушать, поскольку этим мы убираем одну миску и ухудшим ответ на единицу;
• Рассмотрим те миски из которых может покушать самая левая собачка. Все эти миски будут доступны и остальным собачкам кроме тех у которых правая граница находится слишком далеко влево. Таким образом, если мы хотим взять какую-либо миску (а мы уже поняли из пункта 1, что это стоит сделать), то выгоднее будет взять миску с самым левым правым концом, так мы не ухудшим выбор для собачек справа.

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

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

Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).

const int N = 200200;

int n, m;
int x[N];
int u[N], t[N];

bool read() {
	if (!(cin >> n >> m)) return false;
	forn(i, n) assert(scanf("%d", &x[i]) == 1);
	forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2);
	return true;
}

pti segs[N];

void solve() {
	forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]);

	sort(x, x + n);
	sort(segs, segs + m);

	int ans = 0;
	multiset<int> z;
	for (int i = 0, j = 0; i < n; ) {
		if (j < m && segs[j].x <= x[i]) {
			z.insert(segs[j].y);
			j++;
		} else {
			auto it = z.lower_bound(x[i]);
			i++;
			if (it != z.end()) {
				ans++;
				z.erase(it);
			}
		}
	}
	cout << ans << endl;
}

648E - Собери число

Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа a_i этот остаток станет равный остатку от деления на k числа r·10^l_i + a_i (l_i — количество цифр в записи числа a_i).

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

Все описанное выше позволяет нам построить граф на k вершинах (от 0 до k - 1, соответственно остаткам), ребра в котором определяются числами a_i: из вершины v в вершину длины l_i, означающее, что с помощью дописывания l_i цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые a_i в этом графе будут соответствовать одним и тем же ребрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество ребер не будет превышать 10k².

Теперь все, что от нас требуется — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие ребра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, которую можно решить алгоритмом Дейкстры за O(k²). Однако, в силу специфичности задачи, решение алгоритмом Форда-Беллмана (с правильными отсечениями, конечно) так же проходит все тесты, хоть в теории и имеет столь большие O(k³).

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

    for (int i = 0; i < n; ++i) {
        int x;
        assert(scanf("%d", &x) == 1);
        any[x % k][length(x)] = x;
    }

    p10[0] = 1;
    for (int i = 0; i + 1 < P; ++i)
        p10[i + 1] = (p10[i] * 10) % k;

    for (int i = 0; i <= k; ++i) {
        d[i] = int(1e9);
        p[i] = -1;
        used[i] = false;
    }

    d[k] = 0;
    while (true) {
        int v = -1;
        for (int i = 0; i <= k; ++i)
            if (!used[i] && (v == -1 || d[v] > d[i]))
                v = i;
        if (v == -1)
            break;   
        if (v == 0)
            break;
        used[v] = true;
        for (int r = 0; r < k; ++r)
            for (int l = 0; l < P; ++l)
                if (any[r][l] != -1) {
                    int to = (v * p10[l] + r) % k;
                    if (d[to] > d[v] + l) {
                        d[to] = d[v] + l;
                        p[to] = v;
                        w[to] = any[r][l];
                        used[to] = false;
                    }
                }               
    }   

    if (p[0] == -1) {
        puts("NO");
    } else {
        puts("YES");
        vector <int> res;
        int v = 0;
        do {
            res.push_back(w[v]);
            v = p[v];
        } while (v != k);

        reverse(res.begin(), res.end());
        for (auto x: res)
            printf("%d", x);
    }

Добрый день.

23-го марта в 18:00 (московское время) стартует Отборочный Раунд 1 чемпионата Технокубок 2016. Раунд будет длиться два часа, участникам будут предложены 5 задач. По его результатам лучшие 150 участников (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке http://mirror.codeforces.com/contests/648. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 20 минут).

Зарегистрироваться на Отборочный Раунд 1 →
Для зарегистрированных участников олимпиады

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

• короткое описание формата
• полное описание формата

Напоминаем, что регистрация на олимпиаду еще открыта. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Второй отборочный раунд будет открыт для всех тех, кто не прошел в финальный этап из первого отборочного раунда. Причина (не участие или недостаточный результат) — не важна. Второй отборочный раунд состоится 26 марта 10:00-12:00.

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD 1: Раунд будет являться рейтинговым соревнованием, то есть на основании его результатов будут пересчитаны рейтинги участников.

UPD 2: Соревнование закончено, спасибо за участие! Поздравляем топ-150 с приглашением в Финал олимпиады. Скоро вам будет отослано письмо с формой участника, пожалуйста, не задерживайте с заполнением.

UPD 3: В силу ряда причин дорешивать задачи можно в Тренировках: 2016 Технокубок: Отборочный Раунд 1, приношу извинения за некоторое неудобство.

Добрый день.

21-го марта в 17:00 (московское время) стартует Ознакомительный Раунд 1. Его продолжительность составит двое суток, его результаты не будут как-либо влиять на прохождение в следующие этапы. Его единственная цель — дать вам возможность ознакомиться с платформой Codeforces и её тестирующей системой. Приглашаем вас принять в нём участие! Для участия перейдите по ссылке http://mirror.codeforces.com/contests/646. Раунд будет содержать несколько несложных ознакомительных задач и будет открыт для официальных участников Технокубка.

Раунд продлится 48 часов, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Ознакомительный раунд, как и все предстоящие раунды, требует отдельной регистрации, она будет открыта на протяжении всего раунда.

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

Напоминаем, что еще открыта регистрация на олимпиаду для школьников Технокубок. Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces в этом году впервые проводит Технокубок — первую совместную олимпиаду по программированию для школьников. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы.

Зарегистрироваться на олимпиаду!

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда). Отборочные раунды состоятся:

• первый отборочный раунд: 23 марта 18:00-20:00
• второй отборочный раунд: 26 марта 10:00-12:00

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

В 16:00 (московское время) 4 марта 2016 г. Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces запускает Технокубок — первую совместную олимпиаду по программированию для школьников. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы.

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

Организаторы олимпиады

Московский физико-технический институт

Московский Государственный Технический Университет им. Н. Э. Баумана

IT.Mail.Ru

Codeforces

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

Этапы соревнования

Ознакомительные раунды
21 марта 00:00 — 23 марта 17:00, 24 марта 00:00 — 26 марта 11:00

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

**Отборочный (онлайн) этап **
23 марта 18:00 — 20:00, 26 марта 10:00 — 12:00

Пользователи могут участвовать как и в первом, так и во втором онлайн-раунде. Лучшие 150 участников каждого из онлайн-раундов будут приглашены к участию в заключительном этапе, но не более 45% от общего числа участников раунда. До 5 апреля приглашенные в заключительный этап должны подтвердить желание и возможность участия в нем. В случае отсутствия подтверждения, жюри может пригласить следующего участника по результатам соответствующего онлайн-раунда.

Заключительный (очный) этап в МГТУ им. Н. Э. Баумана и МФТИ
17 апреля

Заключительный этап будет проходить очно на площадках вузов. Участники, прошедшие онлайн-этап, побывают в лучших технических вузах страны и смогут получить ответы на вопросы по поводу поступления. Награждение пройдет в тот же день в офисе Mail.Ru Group, для победителей и призеров будет организован трансфер с площадок вузов. Победители и призеры олимпиады познакомятся со специалистами крупнейшей IT-компании в России, а также узнают про возможности карьерного роста в IT-сфере для абитуриентов МФТИ и МГТУ им. Н. Э. Баумана. Проживание и проезд осуществляется за счет участников. При наличии возможности по решению Оргкомитета возможна частичная оплата расходов на проживание. Для остальных мы подберем рекомендации по проживанию за невысокую цену близ площадок вузов.

Призы

Дополнительные баллы в МФТИ и МГТУ им. Н. Э. Баумана:

• Победителям (диплом I степени) — 8 баллов
• Призерам (диплом II, III степени) — 6 баллов

Всего будут награждены не более трети участников заключительного этапа.

Ценные призы:

• 1 место iPad mini 2 + Технокубок
• 2 место iPod nano
• 3 место iPod shuffle

Регистрация начнется в 16:00 (московское время) 4 марта на сайте: https://it.mail.ru/technocup/

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

Олимпиада проходит по правилам раундов Codeforces.

Чемпионат Технокубок входит в число инициатив Mail.Ru Group, направленных на развитие российской IT-отрасли и объединённых ресурсом It.Mail.Ru. Платформа It.Mail.Ru создана для тех, кто увлекается IT и стремится профессионально развиваться в этой сфере. Проект объединяет чемпионаты Russian AI Cup, Russian Code Cup и Russian Developers Cup, образовательные проекты Технопарк в МГТУ им. Баумана, Техносфера в МГУ им. М.В. Ломоносова и Технотрек в МФТИ. Кроме того, на It.Mail.Ru можно с помощью тестов проверить свои знания по популярным языкам программирования, узнать важные новости из мира IT, посетить или посмотреть трансляции с профильных мероприятий и лекции на IT-тематику.

*Дополнительные баллы могут получить учащиеся 8 – 11-х классов образовательных учреждений. Действие льготы — 4 года.