Розбір задач третього кваліфікаційного раунду Russian Code Cup 2014

    
 
У суботу 24 травня відбувся третій кваліфікаційний раунд RCC 2014. На участь в раунді зареєструвалося 5483 особи, взяло участь більше 1500, з них хоча б одне рішення прислали 893 учасника.
 
Прищенко Богдан (LeBron), студент Львівського національного університету ім. Івана Франка, першим на 2:25 хвилині вирішив завдання А (Трикутники). Задачу В (Орігамі) на 4:44 хвилині першого вирішив Юлдашев Марат (snowbear), задачу С (Митя і граф) першим на 10:34 хвилині вирішив Ахмедов Максим (Zlobober), правильне рішення завдання D (Призи) на 26:45 хвилині надіслав Копеліович Сергій (Burunduk1), а останню задачу E (крипостійкість ключі) швидше за всіх вирішив Пономарьов Павло (pperm) на 54:38 хвилині.
 
За підсумками 3 кваліфікаційного раунду не було жодної дискваліфікації за списування, а 200 кращих спортивних програмістів перейшли у відбірковий раунд.
 
Учасники, які не пройшли кваліфікацію протягом минулих трьох кваліфікаційних раундів, ще мають можливість пройти у відбірковий раунд, взявши участь в четвертому кваліфікаційному раунді, що відбудеться 1 червня в 13:00 за московським часом.
 
Нагадуємо, для того, щоб взяти участь в Russian Code Cup, потрібно зареєструватися на сайті (реєстрація буде відкрита до початку останнього кваліфікаційного раунду).
 
Ще напередодні третього раунду ми оновили версії компіляторів майже всіх мов програмування, що використовуються в RCC. Додали можливість відправляти рішення на C + +11 під GNU C + + (Visual C + + 2013 і так підтримує C + +11) і додали Java 8 (Java 7 теж поки залишається). Актуальні версії компіляторів і рядки компіляції ви можете переглянути на сторінці з правилами чемпіонату < www.russiancodecup.ru/rules/ >.
 
 Завдання А. Трикутники .
Ідея: Андрій Станкевич.
Реалізація: Анна Малова.
Розбір: Анна Малова.
 
У задачі потрібно визначити кількість трикутників кожного типу, які можна скласти з чотирьох відрізків.
 
Переберемо всі можливі трійки відрізків. З трьох відрізків можна скласти трикутник, якщо виконано нерівність трикутника, тобто сума будь-яких двох сторін більше довжини третьої сторони.
 
Розглянемо відрізки a, b, c в порядку зростання довжини. Якщо виконано рівність c2 = a2 + b2, то трикутник є прямокутним, якщо c2 < a2 + b2 — гострокутним, і якщо c2> a2 + b2 — тупоугольного
 
 Завдання B. Орігамі .
Ідея: Георгій Корнєєв.
Реалізація: Микола Ведерников.
Розбір: Микола Ведерников.
 
У задачі потрібно перевірити, чи існує в прямокутнику a на b подпрямоугольнік площею S, у якого сторони паралельні вихідним.
 
Для цього переберемо все x-подільники числа S і перевіримо, чи є x ≤ a і S / x ≤ b. Якщо існує хоча б одна така пара x і S / x, задовольняють обмеженням, то рішення існує.
 
Час роботи на один тестовий випадок O (sqrt (S)).
 
 Завдання C. Митя і граф .
Ідея: Журі.
Реалізація: Виталик Аксьонов.
Розбір: Виталик Аксьонов.
 
Перше спостереження полягає в наступному: граф повинен бути реберним кактусом. Якщо він не вийшов таким, то обов'язково знайдеться парний цикл. Раз це кактус, то кількість циклів одно m — (n — 1). А так як кожен цикл містить в собі мінімум 3 вершини, то 3 · (m — (n — 1)) ≤ m. Звідси отримуємо, що максимальне число ребер дорівнює 3 · (n — 1) / 2.
 
При непарних n це млин, тобто набір циклів довжини 3, пересічних по 1 вершині, а при непарних n майже те ж саме, але ще одна висяча вершина з'єднана ребром з будь-якої іншої.
 
 Завдання D. Призи .
Ідея: Виталик Аксьонов.
Реалізація: Виталик Аксьонов.
Розбір: Виталик Аксьонов.
 
Ми знаємо, що кількості цукерок, виданих учасникам, повинні спадати залежно від номера групи. Нескладно переконатися, що будь-яке задовольняє розбиття цукерок можна представити таким способом:
 
У першій групі діти отримують n цукерок, у другій — n-1 цукерок, ..., в останній — 1 цукерку. Далі ми можемо додавати по одній цукерці всім дітям на префіксі груп. Це означає, що ми можемо вибрати число p і збільшити ai на одиницю для будь-якого i ≤ p.
 
Так як ми вибрали початковий розподіл, то із загального числа цукерок можна відразу відняти n · a1 +… +1 · an. Нескладно помітити, що операція розподілу віднімає bp = a1 +… + ap. Тобто нам треба перевірити, чи можемо ми уявити d у вигляді якоїсь суми b1, ..., bn, а це стандартна задача про рюкзак.
 
Час роботи O (nd).
 
 Завдання Е. крипостійкість ключі .
Ідея: Віталій Дем'янюк.
Реалізація: Віталій Дем'янюк.
Розбір: Віталій Дем'янюк.
 
Дано безліч чисел a1, a2, ..., an. Його замкнули щодо операцій НСД та НСК. Потрібно з'ясувати, чи належить задане число v замкнутій безлічі S.
 
Уявімо v у вигляді p1q1p2q2… pkqk, qi> 0, де p1, p2, ..., pk — прості числа. Щоб v належало S, необхідно, щоб для кожного i, 1 ≤ i ≤ k існувало j, 1 ≤ j ≤ n, таке, що piqi | aj і piqi +1 ∤ aj. Цей факт випливає з того, що ми можемо будь-яке число представити у вигляді НОК (НОД (...), НСД (...), ..., НОД (...)), так як min (a, max ( b, c)) = max (min (a, b), min (a, c)) і max (a, min (b, c)) = min (max (a, b), max (a, c) ). Покладемо ci рівним найбільшому загальному дільнику чисел aj, таких що piqi | aj. Якщо все ci ділять v, то v належить S. Воно може бути отримано як найменше спільне кратне всіх ci. В іншому випадку v не належить S (це випливає з властивостей операцій НСД та НСК).
 
Час роботи O (nk + sqrt (v)), де k — кількість простих дільників числа v.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.