 |
Вітаю Вас, Гість · RSS |
 |
Задачі для початківців з сайту http://netoi.org.ua/
| |
kom_adm |
Дата: Su, 26.09.2010, 22:32 | Повідомлення № 1 |
Ветеран спілкування
Повідомлень: 3767
| Пропоную в даній темі обговорювати оптимальні методи розв’язання задач для початківців, що викладені на сайті http://netoi.org.ua/ На мій погляд чудові задачі для тих, хто тільки починає свій рух в напрямку олімпіадного програмування. До того ж є можливість зразу в он-лайні перевірити задачу. Формат спілкування в цій темі вільний, головне, без особистих образ і приниження учасників форуму. За проявлену відверту зверхність - бан на місяць.
|
|
| |
alex |
Дата: Mo, 01.11.2010, 16:37 | Повідомлення № 46 |
Активний учасник
Повідомлень: 586
| Quote (Ковальчук_Олександр) що відрізком послідовності слід вважати мінімум 2 числа ВІдрізком послідовності ввжааємо множину чисел. Оскільки множина чисел може складатися з одного елемента, то і відрізок послідовності може бути одне число. Quote (Ковальчук_Олександр) чому їх слід ділити на 2 послідовності Елементи підпослідовності деякої послідовності можуть давати більшу суму чисел, ніж елементи самої послідовності.
|
|
| |
kom_adm |
Дата: Mo, 01.11.2010, 19:25 | Повідомлення № 47 |
Ветеран спілкування
Повідомлень: 3767
| Дякую за роз’яснення. Ну що ж починаємо думати над розв’язком:)
|
|
| |
kom_adm |
Дата: We, 03.11.2010, 21:48 | Повідомлення № 48 |
Ветеран спілкування
Повідомлень: 3767
| Задача Newcircle. Знову Влад розв’язав цю задачу своїм оригінальним методом. Можливо не найоптимальнішим, проте гадаю, його розв’язок заслуговує на увагу і має право на життя. Програма набирає максимально 10 із 10 балів при перевірці он-лайн. Я понаписував коментарі, профі зрозуміють. program newcircle; type massyv=array[1..1000]of longint; var i,n,kl,g,x,h,maxn,maxp,kp,kd:longint;x1,x2,a,sum:massyv; begin read(n); for i:=1 to n do begin read(a[i]); if a[i]>0 then inc(kd); {Підраховуємо кількість додатніх елементів} end; for i:=1 to n do if a[i]+1<>a[i+1] then inc(kp); {Підраховуємо кількість відрізків} if kd>0 then {якщо є додатні елементи, тоді...} begin g:=0; for h:=1 to kp do {послідовно переглядаємо відрізки} begin for i:=g+1 to n do {послідовно переглядаємо елементи відрізка} if a[i]>=0 then {якщо елемент додатній} if a[i]+1=a[i+1] {та якщо поточний+1=наступному} then inc(x) {тоді підраховуємо їх кількість. Тобто підраховується кількість елементів у відрізку, в якому елементи йдуть один за одним} else begin x2[h]:=i; {в масив х2 виписуємо останній номер елементу поточного відрізка} x1[h]:=x2[h]-x; {в масив х1 виписуєм номер першого елементу поточного відрізка} g:=i; {для розгляду наступного відрізка} x:=0; {обнулити кількість елементів відрізку} break; end; end; for h:=1 to kp do for i:=x1[h] to x2[h] do sum[h]:=sum[h]+a[i]; {обчислення сум кожної послідовності} maxn:=1; maxp:=sum[1]; for h:=2 to kp do if sum[h]>maxp then begin maxp:=sum[h]; {шукаємо максимальну суму} maxn:=h; {шукаємо номер максимальної суми} end; end else if kd=0 then {якщо додатні елементи відсутні, тоді...} begin maxp:=a[1]; maxn:=1; x1[maxn]:=1; x2[maxn]:=1; for i:=2 to n do if a[i]>maxp then begin maxp:=a[i]; {шукаємо найбільший недодатній елемент} x1[maxn]:=i; {шукаємо номер найбільшого недодатнього елементу} x2[maxn]:=i; {шукаємо номер найбільшого недодатнього елементу} end; end; writeln(x1[maxn],' ',x2[maxn],' ',maxp); end.
|
|
| |
alex |
Дата: We, 03.11.2010, 22:45 | Повідомлення № 49 |
Активний учасник
Повідомлень: 586
| Quote (Ковальчук_Олександр) for i:=1 to n do if a[i]+1<>a[i+1] then inc(kp); Алгоритмічна помилка. Вихід за рамки масива. При і=n йде звертання до a[n+1] елемента, а такого немає. Таких помилок не одна. НЕ претендуючи на оптимальність, пропоную двопрохідний алгоритм розв'язку 1) проходими 1 раз і розглядаючи "зростаючі" відрізки, визначає відрізок з максимальною сумою. 2) проходими 2 раз і розглядаючи "спадаючі" відрізки, визначає відрізок з максимальною сумою. 3) З відрізків , знайдених в пунктах 1 та 2 вибираємо відрізок з найбільшою сумою .Це і є відповідь.
|
|
| |
kom_adm |
Дата: We, 03.11.2010, 22:54 | Повідомлення № 50 |
Ветеран спілкування
Повідомлень: 3767
| Quote (alex) При і=n йде звертання до a[n+1] елемента, а такого немає. Так, але нам і не потрібно, щоб він був, оскільки останній елемент не буде дорівнювати неіснуючому в будь-якому разі, умова справдиться і останній відрізок порахується.
|
|
| |
alex |
Дата: We, 03.11.2010, 23:41 | Повідомлення № 51 |
Активний учасник
Повідомлень: 586
| Quote (Ковальчук_Олександр) Так, але нам і не потрібно, щоб він був Quote (Ковальчук_Олександр) останній елемент не буде дорівнювати неіснуючому Не можна порівнювати число з тим, чого нема. Це щось на кшталт:"Іди туди не знаю куди, принеси то не знаю що"
|
|
| |
Bandalak |
Дата: Th, 04.11.2010, 15:27 | Повідомлення № 52 |
Лідер форуму
Повідомлень: 6386
| Quote (Ковальчук_Олександр) не буде дорівнювати неіснуючому Поняття "неіснуючий елемент" не має. Насправді це або нуль, або якесь числове сміття, залежно від компілятора! Але якщо n+1 виходить за межі описаного в Array діапазону, то буде відповідне повідомлення про помилку.
|
|
| |
pasichov |
Дата: Fr, 05.11.2010, 19:17 | Повідомлення № 53 |
Наполегливий учасник
Повідомлень: 946
| Я вимушений принести вибачення за цю задачу. ЇЇ мені передали з ОІПОПП, попросили встановити в систему для курсів учителів. Я, особливо не вчитуючись, розмістив, використав надані тести...Зараз, прочитавши дискусію, вчитався,і ...взявся за голову. Задача НЕ ДЛЯ ПОЧАТКІВЦІВ. Насправді - це СКЛАДНА задача, на динамічне програмування, ще й зіпсована! Пояснюю. З прикладів робимо висновок, "Відрізок послідовності утворюють числа, що йдуть в послідовності підряд" - щось типу х,x,...2,3,4....x,x,x або х,х,х.....,2,1,0,-1,-2.....х,х,х . Це слідує з умови та ПРИКЛАДІВ. Так зрозуміли всі, крім "авторів"....ВОНИ РОЗУМІЛИ "ПІДРЯД" як виключно ЗРОСТАЮЧИЙ ряд , тобто типу 1,2,3.....або -3,-2,-1.....Це слідує з аналізу тестів, які волни мені надали ("авторського" розв"язку, зрозуміло, не дали), отже при перевірці повні бали МОЖУТЬ НАБИРАТИ НЕПРАВИЛЬНІ РОЗВ"ЯЗКИ!!!!!! АЛЕ САМЕ СМІШНЕ, ЩО В ОРИГІНАЛІ (Арсак, "Програмування ігор та головоломок"), звідки взято цю задачу, відрізок - це будь-який фрагмент підряд вишикуваних елементів, головне, щоб номер початку фрагмента був не більше номера кінця, і все! ТОБТО ВІДРІЗОК СКЛАДАЄТЬСЯ З БУДЬ-ЯКИХ ЕЛЕМЕНТІВ, ЩО ЙДУТЬ ПІДРЯД ОДИН ЗА ОДНИМ! ЦЕ СЛІДУЄ З УМОВИ, НАВЕДЕНОЇ НА САЙТІ, АЛЕ НЕ СЛІДУЄ З ПРИКЛАДІВ, ЩО ЇХ НАДАЛИ "АВТОРИ"!!!! ВИЙШЛО ДУЖЕ ПОВЧАЛЬНО:-( І СУМНО: - УМОВА ОДНІЄЇ (КЛАСНОЇ, АЛЕ СКЛАДНОЇ) ЗАДАЧІ, ПРИКЛАДИ І ТЕСТИ(!) ВІД ДРУГОЇ, А ВСІ РОЗВ"ЯЗУВАЛИ ТРЕТЮ І ОТРИМУВАЛИ "ПРАВИЛЬНИЙ" РЕЗУЛЬТАТ! ЩЕ РАЗ ПРОШУ ВИБАЧЕННЯ ЗА свою неуважність...і за "авторів" Пропоную такий вихід з положення. Я вношу незначну правку в умову- означаю відрізок як в прикладах і тестах, тобто типу 1,2,3... (нова версія умови http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=106 ), це відповідає тестам і прикладам - саме ІМХО, це мали на увазі "автори" . Задача стала простішою, але все рівно цікавою .... Нашвидку написва розв'язок - здається, що так: Code Program NewCircle; Const z=1000; Var a:array[1..z] of longint; i,j,n,nMax,k,kMax,s,sMax:longint; BEGIN Read(j); for i:=1 to j do Read(a[i]); n:=1;k:=1;s:=a[1]; nMax:=n;kMax:=k;sMax:=s; for i:=2 to j do Begin if (a[i]=a[i-1]+1)and (a[i]>0) then begin inc(k);s:=s+a[i] end else begin s:=a[i]; n:=i;k:=i end; if s>sMax then begin sMax:=s;Nmax:=n;kMax:=k end; end; Write(nMax,' ',kMax,' ',sMax); END. Як видно, задача робиться "за один прохід, тобто алгоритм має лінійну складність. А ось дійсно оригінальну умову з првильними прикладами і нормалними текстами додаю в розділ ЗАДАЧІ ДЛЯ ПОЧАТКІВЦІВ під назвою NewCircle2 (далі буде) Додано (04.11.2010, 17:58) --------------------------------------------- Розмістив НОВУ задачу NewCircle2 http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=992 Саме в такому варіанті вона була в першоджерелі, і тут ВІДРІЗОК - це просто пдряд розміщені члени послідовності, починаючи з будь-якого, і закінчуючи будь-яким з не меншим номером. (див приклади!!!!). Ось тепер вийшла ДІЙСНО ЦІКАВА ЗАДАЧА!!! ДЛЯ БАЖАЮЧИХ: ПОВНИЙ ОПИС РОЗВ"ЯЗКУ ВИКЛАВ НА http://disted.edu.vn.ua/courses/learn/2947 (тут не можу - таблиці треба креслити...) Додано (05.11.2010, 19:17) --------------------------------------------- За добу - ЖОДНОГО відвідування за вказаним ппосиланнм
Відредаговано: pasichov - Th, 04.11.2010, 20:21 |
|
| |
kom_adm |
Дата: Fr, 05.11.2010, 20:35 | Повідомлення № 54 |
Ветеран спілкування
Повідомлень: 3767
| Як тільки звільнюсь від роботи - щонайменше 1 відвідування появиться. Ми з моїм учнем проаналізуємо нову задачу і спробуємо розв’язати. Чим більше цікавлюсь цією темою, тим більше усвідомлюю, що цікавіше за програмування може бути тільки програмування. Жалко, що не всі учні (та й вчителі) це усвідомлюють.
|
|
| |
TarasBTS |
Дата: Tu, 11.10.2011, 21:58 | Повідомлення № 55 |
Новий користувач
Повідомлень: 1
| Задача Worms. Її можна розвязати без циклів. Code program worms; var n,h,c: integer; begin read(n); h:=n div 10; c:=2; c:=round(c*exp(ln(2)*h)); writeln(c); end.
Відредаговано: TarasBTS - We, 12.10.2011, 21:44 |
|
| |
© Форум інформатиків України, 2007-2022.  |