Автор |
Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 18-04-2010 20:54 |
|
|
Potyczki Algorytmiczne 2010
Algorithmic Engagements (Potyczki Algorytmiczne) – щорічне змагання з програмування, що проводиться фірмою Advanced Digital Broadcast Polska та факультетом математики, інформатики та механіки Варшавського університету.
Терміни проведення
Змагання розпочнеться 20 квітня та триватиме до 15 травня 2010 року.
20-28 квітня відбудеться 6 онлайн-раундів, 20 переможців яких (в загальному заліку Україна + Польща) прийматимуть участь у фінальному раунді, що відбудеться 15 травня 2010 року у штаб-квартирі ADB Polska в місті Zielona Góra (Польща).
Організатори беруть на себе усі витрати на поїздку трьох найкращих учасників з України. |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
Опубліковано 21-04-2010 02:30 |
|
|
Кожен з шести онлайн-раундів починається з моменту публікації завдань на сайті змагання та триває 36 або 60 годин.
Я так розумію, що власне раунди мають тривалість на добу меншу, ніж вказано у новині. Нелогічно ж, що раунди перекриваються... |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 21-04-2010 10:44 |
|
|
Так, раунди перетинаються!
Наприклад сьогодніз 12:00 і до 24:00 (по CET) можна приймати участь у першому і другому раунді, аналогічно і наступні, тільки останні мають більше вікно. |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
Опубліковано 21-04-2010 19:10 |
|
|
Так, я бачу. Ніколи раніше з таким цікавим розкладом не стикався просто |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 22-04-2010 07:10 |
|
|
Правила точно як в реальному житті: Всі проекти поперекривалися, дедлайни підходять один за другим, а ти ще нічого не зробив
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
kilotaras
Користувач
Повідомлень: 17
Звідки: ЛНУ
Зареєстрований: 22.11.07 |
Опубліковано 22-04-2010 08:04 |
|
|
Така порада. Обов'язково спробуйте скомпілювати програму під g++ |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 22-04-2010 10:43 |
|
|
kilotaras написав:
Така порада. Обов'язково спробуйте скомпілювати програму під g++
А що таке? Розкажи свою історію. |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 22-04-2010 10:48 |
|
|
Хочу відразу відмітити, що система оцінки задачі тут досить дивна. Нахай на задачу маємо К груп тестів, кожна група має свій бал (можливо і 0), у кожній групі є від одного до декількох тестів.
Здається система така, якщо із групи не пройшов хоч один тест, то за групу вам дадуть 0 балів, якщо всі тести із групи успішні, то відповідно дадуть скільки вартувала та група.
Сумарний бал це сума отриманих балів по всім групам.
Якось перемішано ІОІ та АСМ.
Змінив(ла) webmaster, 22-04-2010 10:48 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 22-04-2010 11:00 |
|
|
Розбір першого туру.
Сьогодні вночі завершився перший тур і мене задача набрала 10 болів (100%), тому я вважаю, що я зробив її правильно і маю повне моральне право написати як я її робив.
Умова.
Дано N (N < 1000 000) чисел, це циклічний масив, тобто після останнього елементу знову слідує перший і т.д.
Ми можемо вибрати будь який із цього масиву початковим елементом і від нього (в любому напрямку) пройти до кінця цей масив, якщо він буде незростаючим, то потрібно видати відповідь "TAK" (латинськими літерами) в інакшому випадку "NIE".
Ну значить будемо так і робити. Спочатку вибрати який підходячий початковий елемент, можливо пару їх, і просто пробігти у дві сторони (вперед і назад) і подивитись чи є наш масив незростаючим.
Вибрати початковий елемент можна двома способами або найменший, або найбільший, суті не міняє, тільки потім шукати потрібно або незростаючу або неспадаючу послідовність.
Це все просто, навіть занадто.
Але проблема у тому, що таких початкових елементів може бути декілька (багато), от тільки тут здається потрібно у цій задачі подумати. Нам потрібно вибрати такий початковий елемент, який є "крайнім" у серії із таких самих елементів. Наприклад для послідовності "1221", варто взяти першу двійку. Звісно якщо шукати у зворотньому напрямку послідовність, то ... . Щойно придумав, що можна просто реверснути нашу послідовність і знову застосувати до неї вже готовий алгоритм.
Сподіваюсь не дуже заплутано "видрукувався".
Ну тут має бути все зрозуміло, бо задача проста і варінтів може бути багато.
А який Ваш розв'язок? |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
kilotaras
Користувач
Повідомлень: 17
Звідки: ЛНУ
Зареєстрований: 22.11.07 |
Опубліковано 22-04-2010 13:12 |
|
|
Можна зробити так. Запишем то все в чергу. Одразу порахуєм кількість неправильних пар підряд(a[i]>a[i+1])
наприклад:
1 2 2 1 - 1(остання пара)
6 5 6 5-(2 пари 6 5)
тоді викидаємо елемент спочатку, дивимось, чи він утворював пару(відповідно зменшуєм каунтер)_ і докидуєм в кінець, якщо він утворить пару, то збільшуєм каунтер. Якщо каунтер 0, то відповідь існує.
Потім реверс і ще раз, то що зверху.
А моя студія, чогось не матюкалась, на відсутній algorithm в темплейті(напевно тому, що він був десь там включений) і "error: 'reverse' was not declared in this scope" |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 22-04-2010 13:37 |
|
|
коли ти сабмітиш, то не відбувається тестування на всіх тестах, а тільки на нульовому (0) і він звісно варутує 0 балів, тобто тестують на першому тесті.
правда здається там їх декілька таких і вони рандомом вибирають, бо я мав дві відправки одна протестована на тесті 0, а інша на тесті 0а.
це до того, що ти мав побачити результат, якщо ні, то дай знати про деталі |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
Опубліковано 22-04-2010 14:28 |
|
|
Сумарний бал це сума отриманих балів по всім групам.
Якось перемішано ІОІ та АСМ.
Групи тестів використовуються і на ІОІ-змаганнях. В цьому змаганні їх іноді теж використовують для відсіювання тупих розвязків.
В даному випадку очевидно, що вони служать для того, щоб розвязки, які виводять тупо ТАК, тупо НІ або випадкову відповідь не набирали бали
Про задачу
int c1 = 0, c2 = 0;
for (int i =0 ; i < n; i++)
{
c1 += a[i] > a[(i+1)%n];
c2 += a[i] < a[(i+1)%n];
}
puts(c1 <= 1 || c2 <= 1 ? "TAK" : "NIE");
думаю коментарі тут зайві |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
Опубліковано 22-04-2010 17:52 |
|
|
alt написав:
Про задачу
int c1 = 0, c2 = 0;
for (int i =0 ; i < n; i++)
{
c1 += a > a[(i+1)%n];
c2 += a[i] < a[(i+1)%n];
}
puts(c1 <= 1 || c2 <= 1 ? "TAK" : "NIE"
думаю коментарі тут зайві
Угу. Я так само робив. Тільки в мене кінцева умова виглядає як
if (ans1*ans2=ans1) or (ans1*ans2=ans2) then
[i]З.І. глянув свої сорси, які в системі - виявляється, я все ж не повірив в себе і здав "простіший" варіант, бо боявся десь загнатись в такому, як в мене на локалці висить кінцевим (я його, виявляється, так і не здав).
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 25-04-2010 00:07 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
MoRZe
Користувач
Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09 |
Опубліковано 22-04-2010 18:11 |
|
|
В мене пише, що 2/10
Щойно скачав тести і сів провіряти.
Програма видає правильні відповіді.
До речі
Для чого використовувати масиви?
Зберігаємо перший елемент, зчитуємо числа(якщо воно більше за попереднє, то збільшуємо один з каунтерів на одиницю, якщо менше , то збільшуємо інший.)
Провіряємо перший елемент з останнім.
якщо хочаб один з каунтерів=0 або 1, то ТАК інакше NIE
_______47____
Змінив(ла) MoRZe, 22-04-2010 18:11 |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
Опубліковано 22-04-2010 18:20 |
|
|
Для чого використовувати масиви?
Просто звичка - спочатку зчитати все, а потім вже обробляти |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
MoRZe
Користувач
Повідомлень: 141
Звідки: LNU
Зареєстрований: 05.12.09 |
Опубліковано 22-04-2010 19:47 |
|
|
Як завжди забув що в FPC integer займає 2 байти, а не 4, як в мене
Через це тільки 2/10
_______47____ |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
Опубліковано 22-04-2010 23:49 |
|
|
До уваги "сішників"
%lld для інт64, здається, не працює |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
Опубліковано 23-04-2010 00:18 |
|
|
alt написав:
До уваги "сішників"
%lld для інт64, здається, не працює
Звідки такий висновок? Пробував на тріальній задачі, все ніби нормально |
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
alt
Користувач
Повідомлень: 29
Звідки: УжНУ, ІТФ, КСМ
Зареєстрований: 30.04.07 |
Опубліковано 23-04-2010 00:48 |
|
|
DixonD написав:
alt написав:
До уваги "сішників"
%lld для інт64, здається, не працює
Звідки такий висновок? Пробував на тріальній задачі, все ніби нормально
Надіслав розвязок на задачу Fragments - WA, хоча локально все працює. Написав свій sprintf(s, "%lld", n) окремою процедуром - АС
Хоча зараз такий код працює нормально
#include <stdio.h>
int main()
{
long long n = 1000000000000000LL, n2;
char s[100];
sprintf(s, "%lld", n);
sscanf(s, "%lld", &n2);
if (n != n2)
while (1);
return 0;
}
|
|
Автор |
RE: Potyczki Algorytmiczne 2010 |
webmaster
Головний Адміністратор
Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 23-04-2010 01:18 |
|
|
Вже є результати.
У мене пройшли дві задачі, тобто сумарно за другий раунд маю 20 балів, а разом маю 30 балів.
Стосовно lld, то у мене у задачі про гриби було таке виведення:
Зараз напишу розбір. |
|