Блог пользователя Azret

Автор Azret, история, 9 лет назад, По-русски

Всем привет!

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

Автор Azret, история, 9 лет назад, По-русски

Привет всем!

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

Автор Azret, история, 9 лет назад, перевод, По-русски

Привет, CF!

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор Azret, история, 9 лет назад, По-русски
Add Participant View Participants
Name CF Handle Country Previous IOIs
Román Castellarin ponysalvaje Аргентина 2013 2014
Ariel Nowik ariel.nowik Аргентина Не участвовал(-а)
Martin Mirakyan Martin97 Армения Не участвовал(-а)
Mushegh Shahinyan MyLeg Армения 2014 S
Albert Gevorgyan albertg Армения Не участвовал(-а)
Eduard Grigoryan edogrigqv2 Армения 2010, 2011, 2013, 2014 S
Florian Leimgruber fleimgruber Австрия 2014 B
Gary Ye GaryYe Австрия 2013 B, 2014 B
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 S
Barbara Kuskova kuskova Беларусь 2014 B
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 S
Mateus Bezrutchka m_bezrutchka Бразилия 2014 S
Lucca Morais de Arruda Siaudzionis luccasiau Бразилия Не участвовал(-а)
Murilo Corato Zanarella murilocz Бразилия Не участвовал(-а)
Hristo Venev mustrumr Болгария 2012 S ,2013 G, 2014 G
Encho Mishinev Enchom Болгария 2013 S 2014 G
Daniel Atanasov Болгария Не участвовал(-а)
Kristian Tsaklev krisits Болгария Не участвовал(-а)
Farbod Yadegarian FarbodY Канада Не участвовал(-а)
Yikuan (Timothy) Li FatalEagle Канада 2014 B
Ben Zhang Kuroba Канада 2014
Jacob Jackson zxqfl Канада 2014 G
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 B
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 B, 2014 S
Tuukka Korhonen Laakeri Финляндия Не участвовал(-а)
Henrik Lievonen Hennkka Финляндия 2013, 2014 B
Kalle Luopajärvi kllp Финляндия 2013 B, 2014 S
Alexander Tskhovrebov alexandre Грузия Не участвовал(-а)
Georgy Skhirtladze gskhirtladze Грузия 2014 B
Elene Machaidze emachaidze Грузия 2014 B
Giorgi Kldiashvili GiorgiKldiashvili Грузия Не участвовал(-а)
Aristofanis Rontogiannis mentalist Греция 2014 B
Panagiotis Kostopanagiotis infinity Греция 2013
Konstantinos Agiannis Греция Не участвовал(-а)
Emanuel Mihalainas Греция Не участвовал(-а)
Tanay Kothari Tanay1998 Индия Не участвовал(-а)
Malvika Raj Joshi a0666 Индия 2014 S
Arjun P Superty Индия Не участвовал(-а)
Kushagra Juneja Индия Не участвовал(-а)
Muhammad Ayaz Dzulfikar ayaze Индонезия Не участвовал(-а)
Michael Wibawa M_W Индонезия Не участвовал(-а)
Agus Sentosa Hermawan aguss787 Индонезия Не участвовал(-а)
Stacia Edina Johanna Индонезия Не участвовал(-а)
Francesco Milizia fram Италия 2014 S
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 S
Kristaps Čivkulis how_to_become_purple Латвия 2014 S
Ingus Jānis Pretkalniņš Ingus Латвия 2014
Aleksejs Popovs popoffka Latvia 2011, 2012 B, 2013 B, 2014 S
Azret Kenzhaliev Azret Кыргызстан Не участвовал(-а)
Kadyrbek Narmamatov SEFI2 Кыргызстан 2014
Erkin Matkaziev Erkin97 Кыргызстан 2014
Zarlyk Jusubaliev heavenly_phoenix Кыргызстан Не участвовал(-а)
Kliment Serafimov Македония 2012 2013 2014 B
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 G
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 G
Seunghyun Joe ainta Республика Корея 2014 S
Alexandru Velea alex.velea Румыния 2014 S
Rares Buhai rares.buhai Румыния 2012 G, 2013 G, 2014 G
Andrei Popa AndreiNet Румыния Не участвовал(-а)
Valentin Harsan valih10 Румыния Не участвовал(-а)
Михаил Ипатов LHiC Россия Не участвовал(-а)
Владислав Макеев V--o_o--V Россия Не участвовал(-а)
Михаил Путилин SpyCheese Россия Не участвовал(-а)
Николай Будин budalnik Россия Не участвовал(-а)
Marko Stanković MeinKraft Сербия 2013 S, 2014 S
Dimitrije Erdeljan dd__ Сербия 2013 B, 2014 S
Dušan Živanović zDule98 Сербия Не участвовал(-а)
Nikola Jovanović randomusername Сербия Не участвовал(-а)
Teo Por Loong Сингапур No Participation
Feng Jiahai Сингапур 2014 G
Pang Wen Yuen pwypeanut Сингапур Не участвовал(-а)
Howe Choong Yin Сингапур Не участвовал(-а)
Eduard Batmendijn Baklazan Словакия 2012 G, 2013 G, 2014 S
Bui Truc Lam Словакия 2014 S
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 S
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 S
Abdullah Enes ÖNCÜ enesoncu Турция 2014 B
Kayacan Vesek KayacanV Турция Не участвовал(-а)
Bayram Berdiyev bayram Туркменистан 2014
Silap Aliyev accidentallygivenfuck Туркменистан 2013 2014
Allanur Shiriyev Allanur Туркменистан Не участвовал(-а)
Gunesh Purchekov Туркменистан Не участвовал(-а)
Moakher Mohamed moakhey Тунис Не участвовал(-а)
Shevchenko Ilya Scorpy Украина 2013 B 2014 S
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 G
Andrew Li ParanoidAndroid Узбекистан Не участвовал(-а)
Raif Akhmedshin RaifAkhmedshin Узбекистан Не участвовал(-а)
Abdulla Axmadaliyev a1549a Узбекистан Не участвовал(-а)
Ulugbek Sobirov BEK97 Узбекистан Не участвовал(-а)
Nguyen Tien Trung Kien kien_coi_1997 Вьетнам 2014 B
Pham Van Hanh I_love_tigersugar Вьетнам Не участвовал(-а)
Nguyen Viet Dung toilanvd_HSGS Вьетнам Не участвовал(-а)
Phan Duc Nhat Minh minh141198 Вьетнам Не участвовал(-а)

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +156
  • Проголосовать: не нравится

Автор Azret, 9 лет назад, По-русски

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

Автор Azret, 9 лет назад, По-русски

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

Автор Azret, история, 9 лет назад, По-русски

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

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

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

Задача A.

Разбор от Alex_2oo8.

Всегда существует оптимальное решение следующего вида — разобьем всю последовательность на отрезочки и сначала заберем все числа из первого отрезочка (внутри отрезочка берем числа в обратном порядке), потом из второго отрезочка и так далее. К примеру, если мы разбили последовательность на отрезки вот так: [a1a2a3][a4a5][a6a7a8a9], то забирать числа будем в порядке a3, a2, a1, a5, a4, a9, a8, a7, a6. Доказывать это сейчас не буду.

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

  • f(k) = f(k - 1) + ak + 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. Напоминаю, что все числа в этой последовательности в возрастающем порядке.

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

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

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

fi = max(fj, f0) + 1, где j — такая максимальная позиция, что ai - aj ≥ len. Если такой позиции нет, то j = 0. Найти такое j можно бинарным поиском.

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

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

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

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

Решение от izban.

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор Azret, 9 лет назад, По-русски

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

Задача А.

Реализация.

Задача B.

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

Задача С.

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

  • Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано xi людей в лучшем ответе.
  • Города лучше всего захватывать в порядке ai - xi (очевидно).
  • В одном из лучших ответов города надо захватывать в порядке ai. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и ai > aj, то xj = 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. Код решения может не совпадать с идеей, так как был взят от другого пользователя.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор Azret, 10 лет назад, По-русски

Привет всем!

"Где я могу найти задачи и решения 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 по этому вопросу.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится