Сьома лекція четвертого сезону відбудеться 6 грудня о 18 годині у 265 аудиторії головного корпусу університету імені Івана Франка.
Лекцію ведуть: Igor та LeBron.
Тема: Елементарна комбінаторика.
На порядку денному:
- Біноміальні коефіцієнти.
- Перестановки та розміщення.
- Комбінації та розміщення з повтореннями.
- Побудова лексикографічно наступної перестановки.
- Числа Каталана.
Це взагалі не стосується цієї лекції. Я дуже довго роблю задачу і не можу зрозуміти що нетак. Задача 1207 з acm.lviv.ua. Вона в мене падає по часу на 59 тесті. Вот сорс
#include
#include
#include
using namespace std;
int N,K,cK;
int SI=0;
deque s_in;
int main()
{
scanf(”%d%d”,&N,&K);
cK=K;
int c;
scanf(”%c”,&c);
for(int i=0;i0 && SIs_in[SI+1])
{
s_in.erase(s_in.begin()+SI);
if(SI>0)
–SI;
–K;
}
else
++SI;
}
for(int i=0;i<N-cK;++i)
putchar(s_in[i]);
return 0;
}
Якщо я не помиляюся, складність O(N)
там і інклуді
стдио, дек”ю, иострим
Напишіть тести до задачі, що сьогодні придумав Василь протягом лекції.
А хтось вже придумав як її робити?
Morgan HackProg – тяжко допомогти, не маючи уявлення про те, який в тебе код і алгоритм. В тому, що я бачу тут, кількість відкриваючих дужок не співпадає з кількістю закриваючих, а ще є якась черга, з якої видаляють, але жодного разу не додають.
З того коду, який я бачу, найбільше проблем може бути з видаленням з деку.
http://www.cplusplus.com/reference/deque/deque/erase/ , http://en.wikipedia.org/wiki/Double-ended_queue – отут багато цікавого написано. Суть в тому, що видалення з середини деку (з вище поданого коду я не зрозумів, чи видалення там буває десь з середини, чи тільки біля краю) працює далеко не за константний час – залежно від конкретної реалізації дека в певній мові програмування, в нас буде або повільний RA-ітератор, або повільне видалення.
Деякі лінки, про які було згадано на лекції:
http://en.wikipedia.org/wiki/Binomial_coefficient
http://e-maxx.ru/algo/binomial_coeff
http://en.wikipedia.org/wiki/Catalan_number
http://e-maxx.ru/algo/catalan_numbers
http://oeis.org/A000108
http://informatics.mccme.ru/moodle/course/view.php?id=21 – отут є багато елементарних задач з комбінаторики. На справжніх контестах такі задачі дуже рідко виникають як самостійні повноцінні завдання, але часто виникають як підзадачі серйозніших задач.
http://acmp.ru/index.asp?main=tasks – багато цікавих задач в розділі “комбінаторика”. http://acmp.ru/index.asp?main=task&id_task=158 , http://acmp.ru/index.asp?main=task&id_task=192 – мають пряме відношення до матеріалу лекції.
Також комбінаторні задачі можна шукати на Codeforces за тегом Комбінаторика: http://codeforces.ru/problemset/tags/combinatorics
Узагальнане задача про вибори:
http://en.wikipedia.org/wiki/Bertrand’s_ballot_theorem
Відповідна задача з Тімуса:
http://acm.timus.ru/problem.aspx?space=1&num=1619
1619 не іде теорема Балота, або я не розумію, що вважати за p, а що за q. якщо вираховувати варіанти? що менший вийде в лідери то він буде виходити з рівності p і q. Можна невеличку підказку)