Всем привет!

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

UPD Пишу на указателях.

Привет всем!

Недавно нашёл эти классные сборники и решил поделится со всеми.

UPD Обратно не пашут. Новые.

UPD-2 2008-2014: https://www.dropbox.com/sh/bs23ye9u97ck9oi/AAAPcy0zkJUovixoCfPsxHY7a?dl=0

UPD-3 https://drive.google.com/drive/folders/1eV9-ExIqBifNM-U5p1lc93Pb-8ooHm0V?usp=sharing

Привет, CF!

Я думаю многие из вас, в частности участники IOI, затрудняются найти хорошие, понятные разборы задач IOI, поэтому я решил создать блог где мы будем публиковать задачу, решать её и переходить к следующей (как на AOPS).

Позвольте мне начать — IOI 2006 Б. Пирамида.

Name	CF Handle	Country	Previous IOIs
Román Castellarin	ponysalvaje	Аргентина	2013 2014
Ariel Nowik	ariel.nowik	Аргентина	Не участвовал(-а)
Martin Mirakyan	Martin97	Армения	Не участвовал(-а)
Mushegh Shahinyan	MyLeg	Армения	2014
Albert Gevorgyan	albertg	Армения	Не участвовал(-а)
Eduard Grigoryan	edogrigqv2	Армения	2010, 2011, 2013, 2014
Florian Leimgruber	fleimgruber	Австрия	2014
Gary Ye	GaryYe	Австрия	2013 , 2014
Peter Ralbovsky	peto159	Австрия	2013, 2014
Simon Lehner-Dittenberger		Австрия	Не участвовал(-а)
Nur Muhammad Shafiullah	LamePrince	Бангладеш	2012
Hasib Al Muhaimin	hasib	Бангладеш	2013 2014
Labib Rashid	Labib666	Бангладеш	2013 2014
Imran Hasan	SkullKnight	Бангладеш	Не участвовал(-а)
Nikita Sazanovich	Nik_Storm_2010	Беларусь	Не участвовал(-а)
Alex Vistyazh	netman	Беларусь	2014
Barbara Kuskova	kuskova	Беларусь	2014
Ilya Medyanikov	Ferathorn	Беларусь	Не участвовал(-а)
Mattéo Couplet	mcouplet	Бельгия	Не участвовал(-а)
Damien Galant	damien_g	Бельгия	2014
Robin Jadoul		Бельгия	Не участвовал(-а)
Nico Ekkart	nicoekkart	Бельгия	Не участвовал(-а)
Marcelo Zeballos	marcelozeballos	Боливия	Не участвовал(-а)
Ronaldo Franco Jaldin	rony	Боливия	2014
Arthur Pratti Dadalto	arthurpd	Бразилия	2014
Mateus Bezrutchka	m_bezrutchka	Бразилия	2014
Lucca Morais de Arruda Siaudzionis	luccasiau	Бразилия	Не участвовал(-а)
Murilo Corato Zanarella	murilocz	Бразилия	Не участвовал(-а)
Hristo Venev	mustrumr	Болгария	2012 ,2013 , 2014
Encho Mishinev	Enchom	Болгария	2013 2014
Daniel Atanasov		Болгария	Не участвовал(-а)
Kristian Tsaklev	krisits	Болгария	Не участвовал(-а)
Farbod Yadegarian	FarbodY	Канада	Не участвовал(-а)
Yikuan (Timothy) Li	FatalEagle	Канада	2014
Ben Zhang	Kuroba	Канада	2014
Jacob Jackson	zxqfl	Канада	2014
Yanyi Liu	lyy	Китай	Не участвовал(-а)
Xiaochen Lu	Ruchiose	Китай	Не участвовал(-а)
Yuhao Du	jqdai0815	Китай	Не участвовал(-а)
Hengjie Zhang	zhj	Китай	Не участвовал(-а)
Juan Sebastian Chaves	Chaves	Колумбия	2014
Domagoj Bradac	DBradac	Хорватия	Не участвовал(-а)
Tonko Sabolcec	tonkosi	Хорватия	Не участвовал(-а)
Mihael Liskij	Mihaell	Хорватия	Не участвовал(-а)
Ivan Lazaric	IvL	Хорватия	2013
Alexander Bestard Rivera	bestard	Куба	Не участвовал(-а)
Michael Gonzáles	Mjgonzales	Доминиканская Республика	Не участвовал(-а)
Manuel David Sánchez Suero	tecnomaster999	Доминиканская Республика	Не участвовал(-а)
Alejandra Martínez Jiménez	alejandra_244	Доминиканская Республика	Не участвовал(-а)
Sami Kalliomäki	Scintillo	Финляндия	2012, 2013 , 2014
Tuukka Korhonen	Laakeri	Финляндия	Не участвовал(-а)
Henrik Lievonen	Hennkka	Финляндия	2013, 2014
Kalle Luopajärvi	kllp	Финляндия	2013 , 2014
Alexander Tskhovrebov	alexandre	Грузия	Не участвовал(-а)
Georgy Skhirtladze	gskhirtladze	Грузия	2014
Elene Machaidze	emachaidze	Грузия	2014
Giorgi Kldiashvili	GiorgiKldiashvili	Грузия	Не участвовал(-а)
Aristofanis Rontogiannis	mentalist	Греция	2014
Panagiotis Kostopanagiotis	infinity	Греция	2013
Konstantinos Agiannis		Греция	Не участвовал(-а)
Emanuel Mihalainas		Греция	Не участвовал(-а)
Tanay Kothari	Tanay1998	Индия	Не участвовал(-а)
Malvika Raj Joshi	a0666	Индия	2014
Arjun P	Superty	Индия	Не участвовал(-а)
Kushagra Juneja		Индия	Не участвовал(-а)
Muhammad Ayaz Dzulfikar	ayaze	Индонезия	Не участвовал(-а)
Michael Wibawa	M_W	Индонезия	Не участвовал(-а)
Agus Sentosa Hermawan	aguss787	Индонезия	Не участвовал(-а)
Stacia Edina Johanna		Индонезия	Не участвовал(-а)
Francesco Milizia	fram	Италия	2014
Marco Donadoni	mark03	Италия	Не участвовал(-а)
Filippo Baroni	Delfad0r	Италия	Не участвовал(-а)
Peiman Jabbarzade	JeBeK	Иран	Не участвовал(-а)
Ali Haghani	Haghani	Иран	Не участвовал(-а)
Ali Bahjati	LiTi	Иран	Не участвовал(-а)
Amir Keivan Mohtashami	matrix	Иран	Не участвовал(-а)
Sami Daoud	daoudsammy1	Иордания	Не участвовал(-а)
Aleksejs Zajakins	Alex_2oo8	Латвия	2014
Kristaps Čivkulis	how_to_become_purple	Латвия	2014
Ingus Jānis Pretkalniņš	Ingus	Латвия	2014
Aleksejs Popovs	popoffka	Latvia	2011, 2012 , 2013 , 2014
Azret Kenzhaliev	Azret	Кыргызстан	Не участвовал(-а)
Kadyrbek Narmamatov	SEFI2	Кыргызстан	2014
Erkin Matkaziev	Erkin97	Кыргызстан	2014
Zarlyk Jusubaliev	heavenly_phoenix	Кыргызстан	Не участвовал(-а)
Kliment Serafimov		Македония	2012 2013 2014
Hristijan Gjorshevski		Македония	Не участвовал(-а)
Mihail Denkovski		Македония	Не участвовал(-а)
Juan Carlos Sigler Priego	Juanito98	Мексика	Не участвовал(-а)
Carlos Galeana Hernandez	charlyhlms	Мексика	Не участвовал(-а)
Angel David Ortega Ramirez	blak_dragon	Мексика	Не участвовал(-а)
Emmanuel Antonio Cuevas	EmmanuelAC	Мексика	Не участвовал(-а)
Marcel Bezdrighin	please_delete_account	Молдавия	2014
Mihail Tarigradschi	ThatMathGuy	Молдавия	Не участвовал(-а)
Chihai Mihai	mihaiI	Молдавия	Не участвовал(-а)
Motroi Valeriu	fake_delete_account	Молдавия	Не участвовал(-а)
Dejan Todorovic	dejo	Черногория	2014
Velibor Dosljak	nnMan	Черногория	Не участвовал(-а)
Maciej Hołubowicz	znirzej	Польша	Не участвовал(-а)
Jarosław Kwiecień	yarek	Польша	2014
Przemysław Jakub Kozłowski		Польша	Не участвовал(-а)
Konrad Jan Paluszek		Польша	Не участвовал(-а)
Gonçalo Paredes	gonP	Португалия	2014
José Correia	jrcc	Португалия	Не участвовал(-а)
João Lago	joaolago	Португалия	Не участвовал(-а)
Fábio Colaço	fabioiuri	Португалия	Не участвовал(-а)
Hanpil Kang	Konijntje	Республика Корея	Не участвовал(-а)
Jaehyun Koo	ko_osaga	Республика Корея	Не участвовал(-а)
Jeehak Yoon	HYPERHYPERHYPERCUBELOVER	Республика Корея	2014
Seunghyun Joe	ainta	Республика Корея	2014
Alexandru Velea	alex.velea	Румыния	2014
Rares Buhai	rares.buhai	Румыния	2012 , 2013 , 2014
Andrei Popa	AndreiNet	Румыния	Не участвовал(-а)
Valentin Harsan	valih10	Румыния	Не участвовал(-а)
Михаил Ипатов	LHiC	Россия	Не участвовал(-а)
Владислав Макеев	V--o_o--V	Россия	Не участвовал(-а)
Михаил Путилин	SpyCheese	Россия	Не участвовал(-а)
Николай Будин	budalnik	Россия	Не участвовал(-а)
Marko Stanković	MeinKraft	Сербия	2013 , 2014
Dimitrije Erdeljan	dd__	Сербия	2013 , 2014
Dušan Živanović	zDule98	Сербия	Не участвовал(-а)
Nikola Jovanović	randomusername	Сербия	Не участвовал(-а)
Teo Por Loong		Сингапур	No Participation
Feng Jiahai		Сингапур	2014
Pang Wen Yuen	pwypeanut	Сингапур	Не участвовал(-а)
Howe Choong Yin		Сингапур	Не участвовал(-а)
Eduard Batmendijn	Baklazan	Словакия	2012 , 2013 , 2014
Bui Truc Lam		Словакия	2014
Pavel Madaj		Словакия	No Participation
Samuel Sládek	samo98	Словакия	Не участвовал(-а)
David Wärn		Швеция	No Participation
Aleksandar Abas	Alex7	Сирия	2014
Joud Zouzou	RedNextCentury	Сирия	2014
Besher Massri	besher	Сирия	Не участвовал(-а)
Mohammad Dwik	Bug	Сирия	Не участвовал(-а)
Pochang Chen	johnchen902	Тайвань	2014
Po Jui Chen	a00012025	Тайвань	Не участвовал(-а)
Mekhrubon Turaev	Ximera	Таджикистан	2013,2014
Nodir Daminov	Nodir.Daminov	Таджикистан	Не участвовал(-а)
Doro Umarov	Alnair	Таджикистан	2013,2014
Suhaylii Bakhoduri	Suhaylee	Таджикистан	Не участвовал(-а)
Muhammed İkbal Kazar	ikbal	Турция	Не участвовал(-а)
Muhammed Emin Ayar	EMINAYAR	Турция	2014
Abdullah Enes ÖNCÜ	enesoncu	Турция	2014
Kayacan Vesek	KayacanV	Турция	Не участвовал(-а)
Bayram Berdiyev	bayram	Туркменистан	2014
Silap Aliyev	accidentallygivenfuck	Туркменистан	2013 2014
Allanur Shiriyev	Allanur	Туркменистан	Не участвовал(-а)
Gunesh Purchekov		Туркменистан	Не участвовал(-а)
Moakher Mohamed	moakhey	Тунис	Не участвовал(-а)
Shevchenko Ilya	Scorpy	Украина	2013 2014
Aslandukov Matvey	BigBag	Украина	Не участвовал(-а)
Kachur Roman	Maestr0	Украина	Не участвовал(-а)
Mikhno Mark	AllCatsAreBeautiful	Украина	Не участвовал(-а)
Rowan Lee	Rowan.Lee	Великобритания	Не участвовал(-а)
Daniel Chiu	waterfalls	США	Не участвовал(-а)
Demi Guo	DemiGuo	США	Не участвовал(-а)
Alexander Wei	yummy	США	Не участвовал(-а)
Andrew He	ecnerwala	США	2014
Andrew Li	ParanoidAndroid	Узбекистан	Не участвовал(-а)
Raif Akhmedshin	RaifAkhmedshin	Узбекистан	Не участвовал(-а)
Abdulla Axmadaliyev	a1549a	Узбекистан	Не участвовал(-а)
Ulugbek Sobirov	BEK97	Узбекистан	Не участвовал(-а)
Nguyen Tien Trung Kien	kien_coi_1997	Вьетнам	2014
Pham Van Hanh	I_love_tigersugar	Вьетнам	Не участвовал(-а)
Nguyen Viet Dung	toilanvd_HSGS	Вьетнам	Не участвовал(-а)
Phan Duc Nhat Minh	minh141198	Вьетнам	Не участвовал(-а)

Можете писать в комментарии имена участвующих. :)

Поздравляю всех кто прошёл на IOI 2015! :)

Доброго времени суток!

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

Собственно вопрос: Существует ли общая схема построения доказательства жадных алгоритмов и решений ДП?

Заранее спасибо. :)

Доброго времени суток!

Помогите, пожалуйста, решить задачу.

Доброго времени суток!

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

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

Задача A.

Разбор от Alex_2oo8.

Всегда существует оптимальное решение следующего вида — разобьем всю последовательность на отрезочки и сначала заберем все числа из первого отрезочка (внутри отрезочка берем числа в обратном порядке), потом из второго отрезочка и так далее. К примеру, если мы разбили последовательность на отрезки вот так: [a₁ a₂ a₃][a₄ a₅][a₆ a₇ a₈ a₉], то забирать числа будем в порядке a₃, a₂, a₁, a₅, a₄, a₉, a₈, a₇, a₆. Доказывать это сейчас не буду.

Дальше получается довольно простое ДП: f(k) -  -  максимальная сумма, которую можно получить убрав префикс длины k. Переход будет такой:

• f(k) = f(k - 1) + a_k + 1, если последний отрезочек будет длины 1;

• , если последний отрезочек — [j, k].

• Замечаем, что второй переход можно записать вот так:

, где S — префиксные суммы и получаем константный переход.

Задача C.

Решение от Azret.

После долгих размышлений я увидел закономерность. Итог:

int s[][5] = {
    {1, 2, 3, 4, 5},
    {4, 5, 1, 2, 3},
    {2, 3, 4, 5, 1},
    {5, 1, 2, 3, 4},
    {3, 4, 5, 1, 2},
};
int main() {
    freopen(NAME".in", "r", stdin);
    freopen(NAME".out", "w", stdout);

    int n, i, j, m, a[111][111];

    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i ++)
        for(j = 0; j < m; j ++)
            a[i][j] = s[i % 5][j % 5];

    for(i = 0; i < n; i ++){
        for(j = 0; j < m; j ++)
            printf("%d ", a[i][j]);
        printf("\n");
    }

    return 0;
}

Задача D.

Разбор от heavenly_phoenix.

Код.

Задача E.

Разбор от SEFI2.

Простая динамика, не требует объяснения.

int main(){
    cnt [0] = 1;
    for (i =  1; n >= i ; i++){
        cnt[i] += cnt[i - 1];cnt[i]%=md;
        for (j =  i - 1; j>=1 ; j--){if(a[j] > a[j + 1])break;cnt[i] += cnt[j - 1];cnt[i]%=md;}
        for (j =  i - 1; j>=1 ; j--){if(a[j] < a[j + 1])break;cnt[i] += cnt[j - 1];cnt[i]%=md;}
        long long inter = 0;
        for (j =  i - 1; j>=1 ; j--){
            if(a[j] != a[j + 1])break;
            inter += cnt[j - 1];
        }
        cnt [i] -= inter;
        cnt [i] = (cnt[i] + md) % md;
    }
    cout << cnt[ n ] << endl;
 
    return 0;
}

Задача G.

Разбор от Azret.

Простой жадный алгоритм. На каждом этапе будем уравнивать предыдущий уровень с текущим пока это возможно. Если в конце остались лишние кубики (обозначим их как OST), то ответом будет текущая высота стены + OST / N.

Для лучшего понимания выкладываю код.

Задача I.

Разбор от heavenly_phoenix.

Код.

Задача L.

Разбор от pva701.

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

• Т.е можем разбить весь массив на непересекающиеся подряд идущие отрезки. если запрос был просто на массиве — нам нужно было выбрать максимальный из этих отрезков.

• Посчитаем для каждого i, такой максимальный индекс f[i] (f[i] >= i), что отрезок [i..f[i]] удовлетворяет условию.

• Теперь, когда приходит запрос, начнем в l, перейдем в f[l] + 1, затем в f[f[l] + 1] + 1, и т.д, т.е будем прыгать на элемент после правой границы отрезка [i..f[i]], сохраняя максимум среди длин всех отрезков, по которым прошли. рано или поздно наступит следующее: либо мы просто придем в r (вернее, на следующий после r) — тогда все, максимум найден, либо следующий прыжок из i будет за правую границу, т.е f[i] > r, отметим, что в этом случае a[i] будет больше либо равен всех элементов на суффиксе [i..r]. тогда начнем ту же самую процедуру с r (мы так же заранее для всех j посчитали массив g[j] — минимальный индекс, такой что [g[j]..j] удовлетворяет условию). рано или поздно, g[j] станет меньше, чем l. тогда a[j] = a[i], т.к. если бы они были неравны, то мы могли перейти из j не за l (g[j] был бы больше l), т.к. a[i] был бы больше a[j] (как мы ранее отметили). Т.е. остается один отрезок, который нельзя никак уже разбить [i..j], учитываем его в нашем ответе.

• Последний шаг — все вот эти переходы (f[i], g[j]) предподсчитаем в массив двоичных подъемов, и будем делать наши прыжки за log N.

Асимптотика —

Задача J.

Разбор от netman.

Сначала очень просто можно узнать, какое максимальное число вхождений у нас может быть. Просто возьмем и посчитаем, какое максимальное кол-во вхождений какой-нибудь буквы мы имеем. Назовем это кол-во вхождений need.

Давайте научимся проверять какую-нибудь длину len. Проверять длину len — значит узнать, есть ли у нас такая подстрока длины len, что она имеет need непересекающихся вхождений.

Это можно делать за используя полиноминальные хэши. Посчитаем хэш всех подстрок длины len. Выпишем такие пары (hash, position) — хэш подстроки и позиция подстроки. Теперь давайте для каждого уникального hash выпишем все его position в возрастающем порядке. Теперь, зная все position для фиксированного hash не составляет труда посчитать максимальную подпоследовательность из этих позиций, что разница между соседними элементами подпоследовательности больше либо равна len (это условие нужно, потому что мы ищем непересекающиеся вхождения). Это можно легко подсчитать используя ДП:

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

Теперь можно просто считать следующее ДП:

f_i — максимальная длина подпоследовательности из префикса a длины i. Понятно, что f₀ = 0.

Подсчет данного ДП ведется так:

f_i = max(f_j, f₀) + 1, где j — такая максимальная позиция, что a_i - a_j ≥ len. Если такой позиции нет, то j = 0. Найти такое j можно бинарным поиском.

Как говорилось выше: давайте для каждого уникального hash выпишем все его позиции и запустим на них вышеописанное ДП. И возьмем максимум среди всех результатов запуска ДП. Это и будет максимальное кол-во непересекающихся вхождений строки, имеющей длину len. Теперь легко проверить подходит длина len или нет.

Также надо заметить, что если подходит длина len, то и длина len — 1 тоже подходит, значит можно использовать бинарный поиск, чтобы найти максимальное len, которое подходит.

Итоговая асимптотика решения:

Для лучшего понимания выкладываю код.

Решение от izban.

Есть решение проще.

Сначала найдем need. Теперь фиксируем первую букву ответа (26 вариантов), и перебираем длину ответа, добавляя новый символ — суммарно будет сделано не больше n операций для каждой буквы. Итого, решение за 26n. Код.

P.S. Осталось немного, отписывайтесь.

Доброго времени суток!

Задача А.

Реализация.

Задача B.

Ладей можно было расставлять по диагоналям.

Задача С.

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

• Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано x_i людей в лучшем ответе.
• Города лучше всего захватывать в порядке a_i - x_i (очевидно).
• В одном из лучших ответов города надо захватывать в порядке a_i. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и a_i > a_j, то x_j = 0 (зачем нам кого-то нанимать, если можно весь город захватить бесплатно). "Перекинем" часть закупок из i-того города в j-тый. Противоречие. (см. пункт 5))
• Пусть теперь в последнем городе мы закупили солдат больше, чем надо для победы (а в каком-то меньше (иначе мы уже потратили не меньше денег, чем в построенном ответе)). Перекинем одного из закупленных солдат в какой-то город, в котором не закупили всех. Тогда мы всё равно присоединим последний город.
• Каждая операция, описанная в решении не увеличивает число потраченных денег и перекидывает покупки в более дешёвые города, то есть проблем с зацикливанием нет.

Решение.

Задача D.

Решение от heavenly_phoenix.

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

Задача Е.

Решение от Anuar.

Обозначения:

• А — множество столбиков на которые Петя может закинуть кольца
• B — множество столбиков на которые Петя может закинуть кольца
• C — множество столбиков на которые и Петя и Вася могут закинуть кольца

|x| -> размер некоторого множества x Так как они играют оптимально оба вначале кидают по очереди кольца в множество С. После этого они кидают в свои множества (т.е Петя в А, Вася в В).

Их очки можно выразить такой формулой:

• Очки Пети: min( |A| — |C| + ceil(|C| / 2) , ceil(m / 2) )
• Очки Васи: min( |B| — |C| + floor(|C| / 2) , floor(m / 2) )

Код решения

Задача F.

Решение от Na2a.

Перебираем делителей a * b и ищем такие x, y что x * y = a * b && gcd(x, y) == gcd(a, b) обновляем ответ. Делитель a * b = делитель a * делитель b. Работает за (количество делителей a) * (количество делителей b). Решение.

Задача G.

Решение от Zharaskhan.

Сначала отсортируем массив. Берем самый максимальный сосуд, переливаем и разбиваем пока средняя арифметическая сумма будет меньше чем максимальный элемент.

int ans = 0;
for (int i = n; i >= 1; i--) {
    if (double(sum / double(i)) >= double(a[i])) {
        break;
    }
    ans++;
}

Задача H.

Решение от Zharaskhan.

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

pair <string, pair <string, string> > a[n];
map <string, int> cnt;
for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second.first >> a[i].second.second;
    cnt[a[i].first]++;
    cnt[a[i].second.first]++; 
}
for (int i = 1; i <= n; i++) {
    if (cnt[a[i].first] > 1) {
      swap(a[i].first, a[i].second.second);
      swap(a[i].second.first, a[i].second.second);
    }
}
sort(a + 1, a + 1 + n);

Задача I.

Решение от Alex_2oo8.

Сведем задачу к кратчайшему пути в графе. Вершинами графа будут состояния (l1, l2, dir), означающие, что мы находимся на перекрестке прямых l1 и l2 и смотрим в данный момент либо по направлению прямой l1 (dir = 0), либо против него (dir = 1). Также добавим две вершины — старт и финиш.

Ребра будут трех типов:

• Мы можем продолжить движение по прямой до следующего перекрестка. То есть из состояния (l1, l2, dir) в (l1, l3, dir), если пересечение прямых l1 и l3 находится в нужном направлении от пересечения l1 и l2 (или они совпадают). Стоимость таких ребер — 0, так как поворачивать нам не нужно

• Либо на как-то перекрестке мы можем повернуть — то есть добавляем ребро из (l1, l2, dir) в (l2, l1, new_dir), стоимость такого ребра — угол между данными векторами.

• И последний вид ребер — это ребра из старта (достаточно добавить два ребра с ценой 0) и аналогично два ребра в финиш.

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

Задача J.

Решение от SEFI2.

Решение.

Задача K.

Решение от Na2a.

Добавляем по несколько клеток слева, справа, сверху и снизу (я добавил 20 клеток) и отмечаем их '.'. Напишем функцию win(ch) => количество позиций что если в них поставить ch (X или 0), то можно выиграть.

• Если win('X') > 0 то первый игрок может выиграть сразу, следовательно ответ равен win('X').

• Иначе, смотрим win('0'). Если позиций, где второй игрок выиграет, больше одного, то мы проиграем в любом случае. (Мы закроем одну позицию, но следующий ход он выиграет).

• Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.

• Иначе, перебираем клетку куда мы ставим 'X'. Если после того, как мы поставили Х на эту клетку, на поле выигрышных клеток стало больше одного, то увеличиваем ответ.

Функию win(ch) надо реализовать не на всем поле, а на каком то подпрямоугольнике. Решение.

UPD 2. Код решения может не совпадать с идеей, так как был взят от другого пользователя.

Привет всем!

"Где я могу найти задачи и решения IOI ?" — частый и актуальный вопрос, который вы хоть раз себе задавали. Я долго не мог найти для него ответ. Долгие поиски все же навели меня ссылки, которыми хочу с вами поделиться.

http://www.ioinformatics.org/locations/ioi**/contest/ -> Здесь можно найти условия задач и решения в текстовом виде. Вместо звёздочек вписываете последние цифры года ( пример : http://www.ioinformatics.org/locations/ioi13/contest/ ).

http://informatics.mccme.ru/course/view.php?id=31 -> Наверняка вы знали, это так, на всякий случай.

UPD Ещё можно обратиться к yeputons по этому вопросу.