Задачу I решали так: Запишем строку в виде a...ab...b Если количество букв будет равным и будет равно k, то получаемое значение на выходе k^2 Найдем первый квадрат не превосходящий n. Добавляя буквы (a) в конец строки (не более двух раз),сдвигая их влево и пересчитывая текущее значение — найдем удовлетворяющую нас строку.

Задача D:

Если n%2=1 ans=n*(n-1)*3+1;

Если n%2=0 ans=(n-1)*(n-1)*3+1;

код:

#include<stdio.h>

main()
 {
  freopen("forbidden-triples.in","r",stdin);
  freopen("forbidden-triples.out","w",stdout);
  long long n; scanf("%lld",&n);
  if (n % 2 == 1) printf("%lld\n",((n-1)*(n))*3+1); else 
                  printf("%lld\n",((n-1)*(n-1))*3+1);
 };

#include<cstdio>
#define T freopen("covering-game."
int main(){
T"in","r",stdin);T"out","w",stdout);
int n,i=0;scanf("%d",&n);
while(i<3)puts(((n/2+1)%3==i++)?"Yes":"No");
}

1. Прочитать и понять условие.
2. Заметить, что за каждый ход остаток от деления количества непомеченных вершин в дереве на 3 меняется на 1. Поэтому то, какой игрок проиграет, однозначно определяется в зависимости от остатка от деления на 3.

Видимо, это тест, в котором нету ни одного удаления символа и цикл повторяется ровно 20 раз :(

Если что самые выносящие тесты это буква I и буква П повернутые на . Это вроде 46 и 49.

А что, правда никто кроме меня не заинтересовался, как кто решал H? Не нашел про нее вопросов, кроме этого.

Задача C.
С последними цифрами понятно: надо просто посчитать все по модулю 10.
С первыми цифрами зашло следующее: храним числа в long long, как только оно становится больше 10^18, делим его на 10^18. Первая цифра всегда корректная получается. Доказывать не умеем.

Задача F.
Генерируем простые числа до 2*10^6. Затем проделаем некое подобие решета: для каждого из этих простых чисел p[i] пройдемся по отрезку [A,B] с шагом p[i] (это работает где-то за N*log(N), где N — длина отрезка), и отметим, какое из чисел на этом отрезке делится на p[i] (все делители сохраняем в векторы).
Теперь для каждого числа из отрезка [A,B] мы знаем все простые делители, меньшие 2*10^6. Если есть простой делитель, больший 2*10^6, то он только один и входит в разложение в первой степени. Будем делить, пока можно, каждое из чисел отрезка на его уже найденные делители. Если в конце получилась не единица, то это еще один простой делитель данного числа из отрезка.
Теперь мы знаем все простые делители всех чисел из [A,B], и можно посчитать по определению функцию Эйлера и вывести ответ.

P.S. Возможно, это решение не совсем такое, как предполагалось авторами, т.к. пришлось немного пооптимайзить.

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

curlog = i * log(a), а не curlog += log(a)

Тут

при N > 5 ответ всегда ноль

Для n>5 ответ всегда равен 0. А для пяти чисел пишем полный перебор.

Я думаю для начала разбить на 3 случая: // обозначим первый отрезок за 'а' второй за 'b' 1 случай: Если отрезки a и b параллельны осям координат то 1. если они равны можно вывести 2 случайных числа желательно взять их по модулю больше 1000 2. если они не равны можно выводить "NO" т.к у двух треугольников будет одинаковая высота но разные основания => две одинаковые площади быть не могут.

2 случай: Если две прямые перпендикулярны тогда сравним площади треугольников 0,5 * |a| * h1 = 0.5 * |b| * h2 |a| * h1 == |b| * h2

вместо h1 напишем 1 получим h2 = |a|/|b| к координате X (от прямой параллельной оси ОУ) добавим h1 (т.е 1). А к У другой прямой добавим h2 получим координаты точки.

3 случай: две параллельные прямые не лежащие на 1ой прямой точка лежит между прямыми значит 0.5*a*h1 = 0.5*b*h2 h2 = x — h1; h1 = (a * x) / (a + b) а дальше аналогично

Дописать не успели в чём-то описался видимо пока писал исправить не успел WA 15 тест

Забыл дописать в конце проверку на NO, ва9. Добавил, градиентный спуск зашел.

Это был XXXIII чемпионат СПбГУ. Если хочется отдельный монитор.

Перебор и пихать. Вот есть код. Правда от Dmitry_Egorov и после долгого пихания, так что мало что понятно.

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

Теперь мы уже нашли координаты для двух точек. Найдем массив “кандидатов” на остальные точки. Как будем это делать? Просто переберем все расстояния d1 до первой точки и d2 до второй точки и проверим, что такая конфигурация возможна.

Теперь уже у нас есть координаты двух точек и массивы возможных положений остальных точек. Будем искать оставшиеся точки в порядке увеличения индекса в массиве кандидатов. При этом, в кандидатах будем поддерживать только тех, которых мы можем взять в нашем шаге рекурсии. То есть, если мы берем точку, то мы перебираем имеющихся кандидатов и выкидываем тех, которые уже не подходят. Имеется в виду, что если у нас есть уже координаты для первых x точек и мы проверяем какого-то кандидата, то мы должны убедиться что в списке допустимых расстояний есть все расстояния от кандидата до уже имеющихся точек. Эта часть у меня была реализована за C*x*log(D), где C – количество кандидатов, x – количество уже поставленных точек, D – количество различных расстояний во входных данных.

Локально такое решение работало довольно быстро, но на сервере сначала получало ТЛ. Тогда я сделал random_shuffle() входных расстояний и получил более дальний ТЛ :) Добавил srand(time(0)) и получился ОК :)

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

Мы захардкодили все возможные расположения точек (для n <= 6 таких расположений 22 штуки), а потом проверяли все расположения для данного n, для каждого расположения проверяли все перестановки точек, а потом смотрели, подходит ли инпут под данное расположение.

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

Если есть точка, лежащая только на одной прямой, то выкинули, потом добавим в случайное место. Итого на всех прямых лежит по хотя бы три точки, и каждая точка лежит на хотя бы двух прямых. Несложно понять, что единственная картинка которая бывает (ну или ее подкартинки) — это четыре прямые, на которых лежат по три точки, каждая точка лежит на двух прямых. Такая делается руками.

Мы генерили набор случайных точек с координатами от 1 до 8 и проверяли, подходит ли он под инпут. Если не подходит, то генерим заново. Если за 1.9 секунд не нашли ответа, то выводим "NO". Такое решение не находит ответа для 6 точек на 1 прямой, так что это отдельно рассмотрели. Еще у нас на один тест ответ находило в зависимсти от randseed, так что мы на всякий случай его тоже руками вбили.