Пт, 23.08.2019, 06:59
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

 
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Модератор форуму: Ktara, Bandalak, НІКОЛЯ, volevikt  
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Всеукраїнська олімпіада з інформатики (програмування)
Ковальчук_Олександр Дата: Вт, 20.11.2007, 20:07 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3709
Нагороди: 18
Рейтинг: 209
Шановні учасники форуму! Скоро районна олімпіада по інформатиці. Допоможіть мені та іншим вчителям інформатикам, які погано розуміються на задачах олімпіадного рівня, підвищити свої знання в області програмування.

Увага! При публікуванні розв’язку обов’язково, окрім самої паскаль-програми писати математичну модель задачі і роз’яснювати ваш розв’язок максимально зрозуміло. Бо із самого тексту програм, не завжди все зрозуміло для пересічного інформатика.


[admin]Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!![/admin]
DPV Дата: Пт, 09.12.2016, 21:49 | Повідомлення № 241
Прописаний назавжди
Повідомлень: 475
Нагороди: 7
Рейтинг: 76
Цитата Oxana_cher ()
Так?

Так.
априклад, першому ходу відповідає переміщення на дві клітини по горизонталі, і "-1" клітку по вертикалі (знак мінус вказує на напрямок переміщення). "


Цитата з опису,  тепер відповідає малюнку.



Відредаговано: DPV - Пт, 09.12.2016, 22:49
skif Дата: Нд, 11.12.2016, 00:08 | Повідомлення № 242
Прописаний назавжди
Повідомлень: 444
Нагороди: 3
Рейтинг: 64
Цитата skif ()
буду писати - викладу.
на сторінці 13 було обговорення львівської задачі (хто пам'ятає). Ось завершив:

Код
const u=100000;
var s:ansistring;
    a:array[1..u,1..u] of byte;
    c:array[1..u] of char;      {sumvolu, jki perestavlaemo}

    n:array[1..u] of longword; {nomeru sumvoliv}
    b:array[1..u] of boolean; {matrucia perevirenuh sumvoliv}
    t,m,i,x,y,cr:longword;

procedure poriadok(a:array of char);       {vporiadkyvannia sumvoliv}
        var i,j,k:longword; min,l:char;
  begin

                for i:=1 to cr-2 do
                        begin
                    min:=c[i]; k:=i;
                    for j:=i+1 to  cr-1 do
                    if c[j]<min then begin min:=c[j]; k:=j; end;

                    l:=c[i]; c[i]:=min; c[k]:=l;
                        end;
  end;

procedure graf(nom:longword);      {poshyk grafa}
        var j:longword;
  begin

       write(s[nom],' ' ) ;
       for j:=1 to t do
        if (a[nom,j]<>0) and (b[j]) then
                begin
                   c[cr]:=s[j];
                   n[cr]:=j;
                   inc(cr);
                   b[j]:=false;
                   graf(j);
                end;
        writeln;
        poriadok(c);

  end;

procedure zamina;                   {zamina po zrostannj}
        var r,i:longword;
        begin
                r:=1;

                for i:=1 to cr-1 do begin s[n[r]]:=c[r];  inc(r) end;

        end;

begin
s:='klmrabd';
m:=3;    {kilkist par - vhidne dane}
t:=length(s);
fillchar(b,t,false);

for i:=1 to m do            {matrucia zviaznosti}
        begin
                readln(x,y);
                 a[x,y]:=1; a[y,x]:=1;  b[x]:=true; b[y]:=true;
        end;

for i:=1 to t do
        begin
                if b [i]then
                        begin
                    c[1]:=s[i];
                    n[1]:=i;
                    cr:=2;
                    b[i]:=false;
                    graf(i);
                    zamina;

                        end;
        end;

writeln(s);
end.


Відредаговано: skif - Нд, 11.12.2016, 08:44
Bandalak Дата: Нд, 11.12.2016, 10:32 | Повідомлення № 243
Лідер форуму
Повідомлень: 6206
Нагороди: 44
Рейтинг: 285
Рекурсивна тільки процедура graf?
SLKuty Дата: Нд, 11.12.2016, 14:43 | Повідомлення № 244
Монтажер
Повідомлень: 833
Нагороди: 8
Рейтинг: 118
В нас відбулася районна олімпіада. Цього року учні показали непогані результати. Найбільше мене здивував наш районний методист (мій колишній учень) він справився зі всіма задачами за 20 хв. Навіть не знаю чи варто таким програмістам прозябати у нашій освіті?
Bandalak Дата: Нд, 11.12.2016, 19:46 | Повідомлення № 245
Лідер форуму
Повідомлень: 6206
Нагороди: 44
Рейтинг: 285
Завдання покажете?
skif Дата: Нд, 11.12.2016, 20:04 | Повідомлення № 246
Прописаний назавжди
Повідомлень: 444
Нагороди: 3
Рейтинг: 64
Цитата Bandalak ()
Рекурсивна тільки процедура graf?
так, нерекурсивна реалізація суттєво збільшує програму.
skif Дата: Нд, 11.12.2016, 22:09 | Повідомлення № 247
Прописаний назавжди
Повідомлень: 444
Нагороди: 3
Рейтинг: 64
Цитата SLKuty ()
В нас відбулася районна олімпіада. Цього року учні показали непогані результати. Найбільше мене здивував наш районний методист (мій колишній учень) він справився зі всіма задачами за 20 хв. Навіть не знаю чи варто таким програмістам прозябати у нашій освіті?
якщо не важко покажіть йому цю задачу. Мені хоча б алгоритм
Прикріплення: 6292373.pdf(84.9 Kb)
Oxana_cher Дата: Нд, 18.12.2016, 20:06 | Повідомлення № 248
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Задача о Турах (Ладьях).
Есть шахматная доска размером NxN клеток, N<=250.
1. Написать программу для расчета минимального числа Тур (L), которые надо поставить на доску так, что-бы бились все клетки;
2. Подсчитать количество возможных вариантов (K) таких расстановок;
3. Напечатать матрицу одного из вариантов.

Додано (18.12.2016, 20:06)
---------------------------------------------
По логике выставить N тур в ряд и всё.
Но можно ли использовать <N Тур?

Відредаговано: Oxana_cher - Вт, 13.12.2016, 23:07
Bandalak Дата: Нд, 18.12.2016, 20:38 | Повідомлення № 249
Лідер форуму
Повідомлень: 6206
Нагороди: 44
Рейтинг: 285
Oxana_cher, може пан Scrooge Вам допоможе?
Бачу людина дуже компетентна.
skif Дата: Нд, 18.12.2016, 22:30 | Повідомлення № 250
Прописаний назавжди
Повідомлень: 444
Нагороди: 3
Рейтинг: 64
в мене пропозиція - тексти задач викладати в одні темі (без обговорень). Розв'язки відкривати в окремих темах. 
Задачі на шахматні коні, тури дуже цікаві і я думаю заслуговують окремих тем, бо дуже важко читати (я хоч не коментував але ознайомився досить докладно) з перемішкою аналізу інших задач.
Oxana_cher Дата: Пн, 19.12.2016, 08:13 | Повідомлення № 251
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Неплохая идея.
Пилипчук_О_П Дата: Вт, 20.12.2016, 18:08 | Повідомлення № 252
Ветеран спілкування
Повідомлень: 4308
Нагороди: 38
Рейтинг: 406
Цитата Oxana_cher ()
По логике выставить N тур в ряд и всё.
Но можно ли использовать <N Тур?

Дошку 2x2 однією турою побити неможливо. При додаванні наступних рядка й стовпця з'являється клітинка (на перетині рядка й стовпця), яку не б'є жодна з раніше поставлених тур. Тому потрібно N - по одній в кожному рядку або стовпці.
swetikccc Дата: Вт, 20.12.2016, 19:35 | Повідомлення № 253
Ветеран спілкування
Повідомлень: 4158
Нагороди: 31
Рейтинг: 387
Цитата Oxana_cher ()
2. Подсчитать количество возможных вариантов (K) таких расстановок;

K!++++ а далі я не математик що комбінаторики примінити
Скоріше всього
Число размещений из n элементов по m


Відредаговано: swetikccc - Вт, 20.12.2016, 19:43
Пилипчук_О_П Дата: Вт, 20.12.2016, 22:48 | Повідомлення № 254
Ветеран спілкування
Повідомлень: 4308
Нагороди: 38
Рейтинг: 406
З кількістю варіантів складніше... Кожна тура - в іншому рядку. Для кожної - N варіантів. Отримуємо NN. Якщо розставляти по стовпцях - ще набігає NN варіантів. Але ж деякі з них збігаються, отже загальна кількість менша ніж 2NN. Збігаються ті варіанти, де тури стоять в різних рядках і стовпцях. Таких є N! в кожному з випадків. Тоді загальна кількість буде 2NN-N!. Якось так. Не знаю, може щось пропустив :)

Відредаговано: Пилипчук_О_П - Вт, 20.12.2016, 22:49
swetikccc Дата: Ср, 21.12.2016, 08:53 | Повідомлення № 255
Ветеран спілкування
Повідомлень: 4158
Нагороди: 31
Рейтинг: 387
Цитата Пилипчук_О_П ()
З кількістю варіантів складніше... Кожна тура - в іншому рядку. Для кожної - N варіантів. Отримуємо NN. Якщо розставляти по стовпцях - ще набігає NN варіантів. Але ж деякі з них збігаються, отже загальна кількість менша ніж 2NN. Збігаються ті варіанти, де тури стоять в різних рядках і стовпцях. Таких є N! в кожному з випадків. Тоді загальна кількість буде 2NN-N!. Якось так. Не знаю, може щось пропустив
+++
От вам ще один доказ що олімпіадне це наперво математика, а потім кодування.
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Пошук:


© Форум інформатиків України, 2007-2019.