Задачі для початківців з сайту http://netoi.org.ua/

Дата: Нд, 26.09.2010, 23:32 | Повідомлення № 1

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Пропоную в даній темі обговорювати оптимальні методи розв’язання задач для початківців, що викладені на сайті http://netoi.org.ua/
На мій погляд чудові задачі для тих, хто тільки починає свій рух в напрямку олімпіадного програмування. До того ж є можливість зразу в он-лайні перевірити задачу.
Формат спілкування в цій темі вільний, головне, без особистих образ і приниження учасників форуму. За проявлену відверту зверхність - бан на місяць.

Ковальчук_Олександр

Дата: Пн, 18.10.2010, 21:01 | Повідомлення № 31

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Щось тема притихла. Спробую оживити

Задача Сlock виявилась однією з найцікавіших в розділі "Для початківців". Як виявляється, описаний Юрієм Яковичем спосіб розв’язку не єдиний, мій учень самостійно знайшов ще один спосіб, який на мій погляд 100% правильний, оскільки по-перше, задача проходить перевірку і набирає 20 із 20 можливих балів, по-друге, якщо вважати розв’язок Юрія Яковича за еталон, який видає правильні результати при будь-яких значеннях аргументу, то програма мого учня також видає такі ж результати, оскільки він написав ще одну програму, яка порівнює результати обох сбособів при всіх можливих значеннях аргументу і підраховує кількість неспівпадаючих резульатів. Але таких не виявилося, хоча й в початкових версія програми були.

Наводжу код запатентованого Владом :) розв’язку:

Code

var
    h, m, rez, x: integer;
begin
    read(h, m);
    if (h mod 2 = 0) and (h <> 12) then x := 65 else x := 64;
    h := h * 5;
    if m > h then
      h := h + 60;
    h := h + (h div 11);
    rez := h - m;
    if rez > x then rez := rez - (x + 1);
    write(rez);
end.

Спробуйте розібратись в ньому самостійно.

Нижче наводжу код мого розв’язку, який також проходить тест на валідність і набирає максимальний бал:

Code

var
    m, h, rez, i1, i2, t: integer;c, c1, c2, k1, k2, k3, p: real;
begin
    read(h, m);
    h := h * 5;
    p := h / 11;
    k1 := h + p;
    rez := trunc(k1 - m);
    k2 := h + m / 12;
    c := 60 - m + k2 + (60 - m + k2) / 12;
    c1 := c + (c - (60 - m + k2)) / 12;
    c2 := c1 + ((c1 - c + (c - (60 - m + k2)) / 12) / 12);
    if m > h then
      rez := trunc(c2);
    write(rez);
end.

Але моя програма відрізняється від попередньої тим, що не всі результати виявляються правильними. Серед всіх можливих результатів є 25 неправильних, але її можна скоригувати, тоді вона показуватиме правильні результати в 100% випадків.

Хочу почути чиїсь коментарі щодо розв’язку і чи зрозумілий він вам? Якщо ні, напишу детальні коментарі через декілька днів.

P.S. На останок приводжу код програми, що звіряє резульати способів Пасіхова і Влада.

Code

var
   h, m, i1, i2, rez, t, kil, x: integer;f: text;
begin
   assign(f, 'file1.txt');
   rewrite(f);
   for i1 := 1 to 12 do
     for i2 := 0 to 60 do
     begin
       begin
         h := i1;
         m := i2;
         write(f, h, ' : ', m, '  -  ');
         if (h mod 2 = 0) and (h <> 12) then x := 65 else x := 64;
         h := h * 5;
         if m > h then
           h := h + 60;
         h := h + (h div 11);
         rez := h - m;
         if rez > x then rez := rez - (x + 1);
         write(f, rez, ' / ');
       end;
       begin
         h := i1;
         m := i2;
         t := 11 * (60 * h + m) mod 720;
         if t <> 0  then  t := 720 - t;
         write(f, t div 11, ' ---');
       end;
       if (t div 11) <> rez then
       begin
         inc(kil);
       end
       else writeln(f, 'результати співпадають');
     end;
   write(f, kil);
   close(f);
end.

alex

Дата: Вт, 19.10.2010, 09:14 | Повідомлення № 32

Активний учасник

Повідомлень: 586

Нагороди: 1

Рейтинг: 17

Quote (Ковальчук_Олександр)

Щось тема притихла. Спробую оживити

Через причини, про які говорилось раніше, це навряд чи це буде успішно.

Bandalak

Дата: Вт, 19.10.2010, 11:17 | Повідомлення № 33

Лідер форуму

Повідомлень: 5840

Нагороди: 42

Рейтинг: 265

Quote (Ковальчук_Олександр)

а останок приводжу код програми, що звіряє резульати способів Пасіхова і Влада.

Програма реалізовує обидва алгоритми і порівнює результати обчислень?

Quote (Ковальчук_Олександр)

ка порівнює результати обох сбособів при всіх можливих значеннях аргументу

Цікаво, як Ви підбирали всі можливі значення аргументу, щоб врахувати всі можливі випадки? Інколи це буває архіскладно!!!

Ковальчук_Олександр

Дата: Вт, 19.10.2010, 14:18 | Повідомлення № 34

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Quote (Bandalak)

Цікаво, як Ви підбирали всі можливі значення аргументу, щоб врахувати всі можливі випадки?

За допомогою циклів (це видно з останньої програми)

for i1 := 1 to 12 do
for i2 := 0 to 60 do

Зовнішній цикл змінює години, внутрішній - хвилини. Спочатку i1 набуває значення 1 і відпрацьовує повністю внутрішній цикл for i2 := 0 to 60 do. Тобто виходить 1 година 1 хвилина, 1 година 2 хвилини і т.д.
Потім i1 набуває значення 2 і знову відпрацьовує внутрішній цикл: 2 година 1 хвилина, 2 година 2 хвилина...
І кожен раз h та m отримують значення i1 та i2 відповідно. Таким чином розглядаються всі можливі значення аргументів.

volodschool2

Дата: Вт, 19.10.2010, 16:57 | Повідомлення № 35

Досвідчений учасник

Повідомлень: 1475

Нагороди: 14

Рейтинг: 339

Quote (Ковальчук_Олександр)

for i2 := 0 to 60 do

Здається, так буде краще:
for i2:=0 to 59 do

pasichov

Дата: Вт, 19.10.2010, 21:00 | Повідомлення № 36

Наполегливий учасник

Повідомлень: 946

Нагороди: 3

Рейтинг: 70

п. Олександре! Прграма вашого учня працює фактично за тим же алгоритмом, просто дещо по-іншому представлені дані, а отже і іншим "способом" ведуться розрахунки (ІМХО), не дуже зручно, але (ІМХО) ПРАВИЛЬНО!!!!

Quote (Ковальчук_Олександр)

Але моя програма відрізняється від попередньої тим, що не всі результати виявляються правильними

А ось тут вже гносіологічна помилка. З теорії надійності алгоритму слідує, що якщо хоч в одному випадку результат неправильний - алгоритм неправильний. Чіпляння "латок", звичайно, може дати правильний результат, але не може його ГАРАНТУВАТИ. На олімпіадах, на жаль, від учасників не вимагається доведення надійності, а будь-який, самий класний набір тестів перевірку на 100% надійність не гарантує. Це породжує масові "правдоподібні" розв"язки, що масово "гуляють" від книжки до книжки, від олімпіади до олімпіади. Знаю випадок, коли учень на Всеукраїнській олімпіаді отримав 100% балів за задачу, а в поїзді, коли їхали додому, сам знайшов контрприклад, коли його алгоритм давав помилковий результат....
А щодо заачі, слід сказати, що вона з книжки Ставровького та Порубльова "Алгоритми і програми", на це є посилання в дистанційному курсі для учителів, де вона описана мною вперше.

Ковальчук_Олександр

Дата: Вт, 26.10.2010, 15:00 | Повідомлення № 37

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Задача Bracket

Дано алгебраїчний вираз з дужками, записаний одним рядком. Вірно чи не вірно в ньому розставлено дужки?
Технічні умови: Програма читає з клавіатури рядок з виразом (не довший за 255 символів) . Програма виводить на екран відповідь в вигляді текстового рядка. Якщо дужки розставлено вірно - друкує слово True, якщо не вірно - Folse
Приклад:
Введення:
(a+b)

Виведення:
True

На мою думку, розв’язок може бути таким (за один прохід):

Code

program vyraz;
var s:string; i,d1,d2,l:byte; rez:boolean;
begin
       read(s);
       d1:=0; d2:=0;
       l:=length(s);
       for i:=1 to length(s) do
       begin
       if s[i]='(' then inc(d1);
       if s[i]=')' then inc(d2);
       end;
       if (d1=d2) and ( (s[1]<>')') and (s[l]<>'(') ) then rez:=true else rez:=false;
       if rez then writeln('True') else writeln('False');
end.

Даний розв’язок базується на таких міркуваннях: якщо кількість відкриваючих і закриваючих дужок однакова і перший символ рядка не починається з ")" та останній символ не закінчується на "(", то дужки розставлені правильно, інакше - не правильно.

alex

Дата: Вт, 26.10.2010, 15:07 | Повідомлення № 38

Активний учасник

Повідомлень: 586

Нагороди: 1

Рейтинг: 17

Quote (pasichov)

В курсі, з якого цей розбір, є ще багато цікавих і, головне КОРИСНИХ розібраних задач. Ми з Олександром Івановичем намагалися його провести позаминулим літом для бажаючих учителів. Таких виявилося небагато. Але (хочеться вірити) все-таки комусь це може бути корисно. Отже, якщо когось цікавлять такі задачі:
1. Зареєструватися в системі http://disted.edu.vn.ua
2. Зайти, як зареєстрований користувач, обрати ПОЗАКЛАСНА РОБОТА. ДИСТАНЦІЙНІ КУРСИ=>Методика розв`язування олімпіадних задач з інформатики (для учителів) (Пасіхов Ю.Я. Олійник О.І.)
Уроки доступні в послідовності вивчення - кожен наступний після вивчення матеріалу попереднього.

Повний розбір задачі для випадку різних типів дужок.

Відредаговано: alex - Вт, 26.10.2010, 15:14

vitert

Дата: Вт, 26.10.2010, 15:20 | Повідомлення № 39

Тут живе...

Повідомлень: 174

Нагороди: 1

Рейтинг: 22

Quote (Ковальчук_Олександр)

()))((() - слідуючи вашим міркуванням дужки розставлені правильно
Найкраща ідея - перебираємо впідряд всі символи, якщо дужка відкриваюча то збільшуємо лічильник на 1, якщо закриваюча то мінус 1. Якщо в кінці лічильник 0 то TRUE інакше FALSE. Якщо в будь-який момент лічильник <0 то break відповідь FALSE.

Ковальчук_Олександр

Дата: Вт, 26.10.2010, 18:59 | Повідомлення № 40

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

vitert, я зрозумів свою помилку. Просто не врахував того, що дужки в виразі можуть бути розставлені типу ))((, орієнтувався тільки на типову помилку при записі виразів, коли кількість відкриваючих дужок не співпадає з кількістю закриваючих. Але моя програма також набрала максимальний бал

Ось програма, що базується на ваші ідеї і враховує всі можливі варіанти:

Code

program vyraz2;
var s:string; i,d,l:integer; rez:boolean;
begin
read(s);
        d:=0;
        l:=length(s);
        while (d>=0) and (i<=l) do
        begin
        i:=i+1;
        if s[i]='(' then inc(d);
        if s[i]=')' then d:=d-1;
        end;
        if d=0 then rez:=true else rez:=false;
        if rez then writeln('True') else writeln('False');
end.

alex

Дата: Вт, 26.10.2010, 19:58 | Повідомлення № 41

Активний учасник

Повідомлень: 586

Нагороди: 1

Рейтинг: 17

Цю задачу краще всього використати для пояснення роботи з використанням
організації даних "стек". Для випадку наявності в виразі трьох типів дужок
еврістика дає не дуже красивий і зрозумілий розв'язок.

pasichov

Дата: Ср, 27.10.2010, 01:11 | Повідомлення № 42

Наполегливий учасник

Повідомлень: 946

Нагороди: 3

Рейтинг: 70

Quote (vitert)

Найкраща ідея - перебираємо впідряд всі символи, якщо дужка відкриваюча то збільшуємо лічильник на 1, якщо закриваюча то мінус 1. Якщо в кінці лічильник 0 то TRUE інакше FALSE. Якщо в будь-який момент лічильник <0 то break відповідь FALSE.

Quote (alex)

Цю задачу краще всього використати для пояснення роботи з використанням
організації даних "стек".

Насправді описаний лічильник і є найпростішою реалізацією стека. Це найкращий спосіб розі"язати цю задачу. Хоча, якщо дужи різні (, [.{ , то стек буде трішки складнішим...
Дійсно, в дистанційному курсі ця задача ДЕТАЛЬНО ОПИСАНА, розглянуто варіанти розв"язку. Я зняв необхідність реєстрації. Пряме посилання: http://disted.edu.vn.ua/courses/learn/1140

Відредаговано: pasichov - Ср, 27.10.2010, 20:09

Ковальчук_Олександр

Дата: Нд, 31.10.2010, 20:27 | Повідомлення № 43

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Задача NewCircle

Дано послідовність цілих чисел. Відрізок послідовності утворюють числа, що йдуть в послідовності підряд. Знайти номери чисел, якими починається і закінчується перший відрізок з максимальною сумою, а також цю суму.

Технічні умови. Програма читає спочатку кількість елементів послідовності, а потім саму цю послідовність. Всі числа в одному рядку, їх розділено пропусками. Гарантовано, що послідовність не порожня, і всі розрахунки можна вести в межах типу longint. Програма виводить в один рядок 3 числа через пропуск - номера першого і останнього елемента шуканого відрізка і суму чисел відрізку

Приклади

Введення 3 -2 -1 0

Виведення 3 3 0

Введення 5 1 2 -3 3 0

Виведення 1 2 3

На мою думку не зовсім зрозуміла умова задачі. Я так розумію, що програма має аналізувати відрізки послідовності - числа, що йдуть підряд, наприклад, 1 2 3... Далі познаходити суму цих відрізків і визначити першу максимальну з них. Результатом виведення будуть перший і останній номер такого відрізка і сума його чисел.
Чому 0 розглядається як відрізок, це ж лише одне число? І взагалі -2 -1 0 - хіба це не відрізок. Чи від’ємні числа не розглядаються?

pasichov

Дата: Пн, 01.11.2010, 00:26 | Повідомлення № 44

Наполегливий учасник

Повідомлень: 946

Нагороди: 3

Рейтинг: 70

Quote (Ковальчук_Олександр)

Відрізок послідовності (ЗА УМОВОЮ ЦІЄЇ ЗАДАЧІ) цілі числа, що стоять підряд. Треба знайти початк, кінець першого такого відрізку з масимальною сумою і саму суму. -2, -1, 0 - це відрізок, елементи йдуть підряд, але сума їх -3, а відрізок довжиною в 1 елемент 0 має суму 0, що більше, ніж -3.
Так що умова і приклади коректні.

Ковальчук_Олександр

Дата: Пн, 01.11.2010, 02:01 | Повідомлення № 45

Ветеран спілкування

Повідомлень: 3657

Нагороди: 18

Рейтинг: 204

Quote (pasichov)

Відрізок послідовності (ЗА УМОВОЮ ЦІЄЇ ЗАДАЧІ) цілі числа, що стоять підряд.

Quote (pasichov)

а відрізок довжиною в 1 елемент 0 має суму 0, що більше, ніж -3.

Я розумію так, що відрізком послідовності слід вважати мінімум 2 числа, які йдуть підряд, всі інші числа нас не цікавлять. Наприклад, в послідовності 1 2 3 8 10 12 13 є два відрізки: 1 2 3 і 12 13. В іншому випадку до цих двох ще треба враховувати і 8 та 10, тобто матимемо чотири відрізки. Саме це я мав наувазі, що на перший погляд потрібно враховувати за відрізки тільки ті числа, що йдуть підряд (збільшення на 1), але тепер суть задачі зрозуміла.

Quote (pasichov)

-2, -1, 0

я ці три числа розглядав як одну послідовність і до цих пір не розумію, чому їх слід ділити на 2 послідовності, адже вони йдуть підряд (з кроком збільшення на 1)?