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

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

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

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

Нагороди: 18

Рейтинг: 209

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

alex

Дата: Вт, 05.10.2010, 07:45 | Повідомлення № 16

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

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

Нагороди: 1

Рейтинг: 17

На мою думку не початку програми елементи масиву потрібно занулити.
Можливо помиляюся, але не доводилось читати, що після опису масиву
всі його елементи дорівнюють 0. Опис передбачає виділення і поіменування
певної ділянки памяті, а що там знаходилось до того не відомо.

Bandalak

Дата: Вт, 05.10.2010, 13:22 | Повідомлення № 17

Лідер форуму

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

Нагороди: 44

Рейтинг: 285

Quote (alex)

а що там знаходилось до того не відомо.

Там можуть бути випадкові числа. Але все залежить від компілятора. Деякі компілятори самі автоматично онулюють доступні їм ділянки пам'яті під час запуску програми, а деякі залишають все так як є. Тому крще обнулити самому.

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

Дата: Вт, 05.10.2010, 22:12 | Повідомлення № 18

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

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

Нагороди: 18

Рейтинг: 209

Задача 4. Vinni

Вінні Пух любить складати віршики говорячи речення задом наперед. Якось йому попалось довге складне речення і він забув свій віршик, пробуючи його виговорити. Складіть програму, яка б допомагала ведмедику легко складати такі віршики. Зауваження: віршик може складатись як із 1 слова, так і з декількох, розділених пропусками.

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

На мою думку вся ідея розв’язку зводиться до друкування символів з кінця до початку, використовуючи цикл downto:

Code

var s:string; i:integer;
begin
       read(s);
       for i:=length(s) downto 1 do
       write(s[i]);
end.

Задача 5. Worms
Черв’ячки - цікаві тваринки. Якщо їх залишити вдвох і не турбувати, то через 10 хвилин їх стане четверо, через 20 хвилин – восьмеро, через 30 хвилин – 16 штук. Скільки їх стане через N (N>1) хвилин? Зауваження: на появу нових черв’ячків потрібно рівно 10 хвилин. Всі нові черв’ячки появляються одночасно.

Технічні умови. Програма зчитує з клавіатури ціле число N – кількість хвилин. Програма виводить на екран одне ціле число – кількість черв’ячків через вказаний час.

Приклад.

Введення> 5
Виведення> 2

Введення> 48
Виведення> 32

На мою думку розв’язок може бути таким: початкова кількість черв’яків = 2 (k:=2), кожних 10 хвилин їх кількість збільшується вдвічі (к:=к*2). Але цикл поділу черв’яків триває з 10 по 20, з 20 по 30 хв. і т.д., тобто якщо користувач вводить значення 11-19, то це буде один поділ. Визначити кількість таких поділів можна за формулою n:=n div 10. Якщо, наприклад, було введено значення n, що дорівнює 26, то кількість поділів буде n:=26 div 10 = 2.

Код програми:

Code

var n,i,k:integer;
begin
       read(n);
       n:=n div 10;
       k:=2;
       for i:=1 to n do
       k:=k*2;
       writeln(k);
end.

Задача 6. Nhex

Дано число в системі числення з основою m (2≤m≤16) . Написати програму що переводить дане число в систему числення з основою 10.
Технічні умови: Програма читає з клавіатури першому рядку число m (основу системи числення), а в другому - текстовий рядок, в якому записано саме число Ch (0≤Ch≤2+109) . Програма виводить на екран відповідь в вигляді десяткового числа.

Приклад:
Введення:
16
FFFF
Виведення:
65535

Для того, щоб перевести число з однієї системи в іншу (в десяткову), потрібно:
представити в десятковій системи число Р (основу) та цифрри запису;
обчислити суму добутків значень цифр та відповідних степенів числа Р

Наприклад:
Відповідно ця формула дає можливість написати програму. Ще один момент: оскільки ми вводими дані в стрічку, то текст потрібно перетворити в числа і записати їх в масив. Це можна зробити за допомогою функції Val.

Code

var
    m, l, i, code: integer; s: real;ch: string;mas: array[1..999] of integer;
begin
    read(m);
    read(ch);
    l := length(ch);
    for i := 1 to length(ch) do
    begin
      l := l - 1;
      else val(ch[i], mas[i], code);
      s := s + mas[i] * exp(ln(m) * l);
    end;
    write(s);
end.

Програма буде працювати і видавати результат, коли основа <=10. Якщо основа більша 10, то результат роботи програми буде не правильним. Оскільки, наприклад, в 16 річній системі числення, після цифри 9 ідуть букви А - 10, B - 11 і т.д. і при спробі обчислення суми будуть братися не цифри 10, а окремо 1 і 0. Цього уникнути можна, якщо доповнити програму так:

Code

var
    m, l, i, code: integer; s: real;ch: string;mas: array[1..999] of integer;

begin
    read(m);
    read(ch);
    l := length(ch);
    for i := 1 to length(ch) do
    begin
      l := l - 1;
      if ch[i] = 'A' then mas[i] := 10 else
      if ch[i] = 'B' then mas[i] := 11 else
      if ch[i] = 'C' then mas[i] := 12 else
      if ch[i] = 'D' then mas[i] := 13 else
      if ch[i] = 'E' then mas[i] := 14 else
      if ch[i] = 'F' then mas[i] := 15
      else val(ch[i], mas[i], code);
      s := s + mas[i] * exp(ln(m) * l);
    end;
    write(s);
end.

Тепер програма працює начебто коректно, але є одне але: при перевірці он-лайн не проходить тест на валідність. Підкажіть, будь-ласка, в чому помилка.

Прикріплення: 4425976.jpg(4.0 Kb)

vitert

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

Тут живе...

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

Нагороди: 1

Рейтинг: 22

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

Відповідь ціле число а не Real.

pasichov

Дата: Вт, 05.10.2010, 23:04 | Повідомлення № 20

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

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

Нагороди: 3

Рейтинг: 70

Quote (Bandalak)

Умова задана не зовсім однозначно. А який верхній поріг для N?

Згоден. Зауваження слушне. Виправляю.

Додано (05.10.2010, 23:04)
---------------------------------------------

Quote (alex)

Це залежить від комілятора. Але правила хорошого тону вимагають обнуляти масив перед використанням в будь-якому випадку.
Зручно (і економно за часом) це робити за допомогою стандартної процедури FillChar

Відредаговано: pasichov - Вт, 05.10.2010, 23:09

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

Дата: Ср, 06.10.2010, 14:52 | Повідомлення № 21

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

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

Нагороди: 18

Рейтинг: 209

Quote (vitert)

Відповідь ціле число а не Real.

Виправив програму до такого змісту:

Code

var m,l,i,code,s:integer;ch:string; mas:array[1..10]of integer;
begin
readln(m);
readln(ch);
l:=length(ch);
for i:=1 to length(ch) do
begin
l:=l-1;
if ch[i]='A' then mas[i]:=10 else
if ch[i]='B' then mas[i]:=11 else
if ch[i]='C' then mas[i]:=12 else
if ch[i]='D' then mas[i]:=13 else
if ch[i]='E' then mas[i]:=14 else
if ch[i]='F' then mas[i]:=15
else val(ch[i],mas[i],code);
s:=s+round(mas[i]*exp(ln(m)*l));
end;
write(s);
end.

Результати перевірки:

Тест Результат Время работы
01 FAILED (Wrong Answer) 0.01 сек.
02 PASSED (+1) 0.01 сек.
03 PASSED (+1) 0.01 сек.
04 FAILED (Wrong Answer) 0.01 сек.
05 FAILED (Wrong Answer) 0.01 сек.
06 FAILED (Wrong Answer) 0.01 сек.
07 PASSED (+1) 0.01 сек.
08 FAILED (Wrong Answer) 0.01 сек.
09 FAILED (Wrong Answer) 0.01 сек.
10 PASSED (+1) 0.01 сек.
Прошло тестов: 4 из 10.

Набрано баллов: 4 из 10.

vitert

Дата: Ср, 06.10.2010, 15:32 | Повідомлення № 22

Тут живе...

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

Нагороди: 1

Рейтинг: 22

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

Набрано баллов: 4 из 10.

Вставте long у потрібне місце вашої проги і витріть eger і буде вам щастя 10 із 10.

Відредаговано: vitert - Ср, 06.10.2010, 15:33

Bandalak

Дата: Ср, 06.10.2010, 16:53 | Повідомлення № 23

Лідер форуму

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

Нагороди: 44

Рейтинг: 285

vitert, правий. Сума дійсно може вийти за область значень типу Integer.
Змінну S потрыбно описати типом Longint.

pasichov

Дата: Чт, 07.10.2010, 11:20 | Повідомлення № 24

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

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

Нагороди: 3

Рейтинг: 70

Code

Program Nhex;
Var a         :array [0..300] of byte;
      n,k,b     :longint;

Procedure input;
          var st   : string;
              i,ec : integer;
          begin
               readln(n);
               read(st);
               k:=length(st);
               for i:=k downto 1 do
                   begin
                        val(st[i],a[k-i],ec);
                        if ec<>0 then a[k-i]:=ord(st[i])-55;
                   end;
          end;

          procedure main;
          var i,p:longint;
          begin
               b:=0;
               p:=1;
               for i:=0 to k-1 do
                   begin
                        b:=b+a[i]*p;
                        p:=p*n;
                   end;
          end;

          procedure output;
          begin
               write(b);
          end;

begin
       input;
       main;
       output;
end.

Ось цей код проходить повністю перевірку. Він є прикладом реалізації "структурованого" підходу до задачі і дозволяє конструювати алгоритм розв"язку на псевдокоді, не переймаючись введенням-виведенням. Не варто боятися лишніх стрічок - "прозорість" коду важливіша! В першу чергу для того, хто його пише!
Що ж стосується помилок в попередньому розв'язку, то вони виникли дійсно через вихід за межі типу integer

Відредаговано: pasichov - Чт, 07.10.2010, 11:23

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

Дата: Пт, 08.10.2010, 00:08 | Повідомлення № 25

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

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

Нагороди: 18

Рейтинг: 209

Красивий розв’язок, Юрію Яковичу. І інтуєтивно зрозумілий, все розкладено по поличках. Буду намагатися виробляти культуру програмування. Про функцію ord я попросту забув, а це дає змогу уникнути розгалужень if ch[i]='A' then mas[i]:=10 else ... Дуже дякую.

pasichov

Дата: Пт, 08.10.2010, 08:16 | Повідомлення № 26

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

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

Нагороди: 3

Рейтинг: 70

Задача Hex
Дано число Ch в десятковій системі числення. Написати програму що переводить дане число в систему числення з основою m.
Технічні умови: Програма читає з клавіатури в першому рядку число m (2≤m≤16), в другому - число Ch (0≤Ch≤2*10^9) в десятковій системі. Програма виводить на екран відповідь в вигляді текстового рядка.
Приклад:
Введення:
16
1024
Виведення:
400
==================================================================================== ==
Розглянемо шлях отримання розв'язку

Відомий алгоритм перведення числа, записаного в десястковій системі числення в систему числення з основою m зводиться до:

Code

поки ЧИСЛО <>0
пц
     знаходимо залишок від ділення ЧИСЛО на m
     зберігаємо залишок від ділення
      ділимо націло ЧИСЛО на m - результат => нове ЧИСЛО
   кц
Виписуємо залишки в зворотньому порядку.

Далі - лише технічні складнщі. Як їх подолати - видно з кода.

Code

Program Hex;
type tab=array[0..35] of integer;
var chislo:longint;
      t:tab;
      rez:string;
      m,i:integer;

procedure inp;
begin
     readLn(m);
     Read(Chislo);
end;

procedure main(n:integer;ch:longint;var p:integer;var z:tab);
var k:byte;
begin
     p:=-1;
     while ch<>0 do
        begin
           k:=ch mod n;
           p:=p+1;
           z[p]:=k;
           ch:=ch div n;
        end;
end;

function peret(chch:integer):char;
begin
     if chch<10 then peret:=chr(chch+48)
                else peret:=chr(chch+55);
end;

procedure out(pp:integer;zz:tab;var otv:string);
var w:char;
      ch:integer;
begin
     otv:='';
     while pp>=0 do
        begin
           ch:=zz[pp];
           pp:=pp-1;
           w:=peret(ch);
           otv:=otv+w;
        end;
end;
begin
     inp;
     main(m,chislo,i,t);
     out(i,t,rez);
     if rez='' then write('0')
               else write(rez);

end.

Відредаговано: pasichov - Пт, 08.10.2010, 14:03

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

Дата: Пт, 08.10.2010, 21:51 | Повідомлення № 27

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

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

Нагороди: 18

Рейтинг: 209

Задача Hex мені здалась значно складнішою, за Nhex в плані технічної реалізації.

Задача Clock

Стрілки годинника рухаються з постійним кутовими швидкостями h годин m хвилин. Найти число повних хвилин до найближчого моменту, в яких стрілки співвпадуть.
Технічні умови: Програма читає два цілих числа h та m з клавіатури. Програма виводить. ціле число хвилин на екран.
Приклади.
Введення: 0 0
Виведення 0

Введення: 1 1
Виведення: 4.

Ось ця дійсно для початківців. Але чомусь знову не проходить повністю перевірку, набирає лише 5 із 20 балів. В чому може бути помилка?

Code

program clock;
var h,m,rez:byte;
begin
read(h,m);
rez:=h*5-m;
write(rez);
end.

alex

Дата: Пт, 08.10.2010, 23:40 | Повідомлення № 28

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

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

Нагороди: 1

Рейтинг: 17

Зайдіть будь-ласка на disted.edu.vn.ua. Там є повний розбір цієї задачі в розділі "Позакласна робота.
Дистанційні курси. =>Методика розвязування олімпіадних задач з інформатики (для вчителів)."
Правда вхід тільки для зареєстрованих користувачів.

Відредаговано: alex - Пт, 08.10.2010, 23:42

pasichov

Дата: Сб, 09.10.2010, 14:57 | Повідомлення № 29

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

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

Нагороди: 3

Рейтинг: 70

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

Ось ця дійсно для початківців. Але чомусь знову не проходить повністю перевірку, набирає лише 5 із 20 балів. В чому може бути помилка?
Код

Дублюю власний текст з дистанційного курсу. (адреса вище, потрібно зарєструватися)

Задача Сlock
(надана службою точного часу)

Стрілки годинника рухаються з постійними кутовими швидкостями і показують h годин m хвилин. Найти число повних хвилин до найближчого моменту, в яких стрілки співпадуть.
Технічні умови: Програма читає два цілих числа h та m з клавіатури. Програма виводить ціле число хвилин на екран.
Приклади.

Введення: 0 0

Виведення 0

Введення: 1 1
Виведення: 4

Ця задача - типовий приклад "задач на придумку". Для того, щоб такі задачі розв'язувати, не потрібно знати якісь спеціальні методи. Потрібно лише ДУЖЕ АКУРАТНО і послідовно думати. Ця якість (точніше - її відсутність) саме "акуратного" способу мислення дуже часто заважає учням навіть з непоганою математичною підготовкою успішно справлятися з задачами з інформатики.

Спробуємо провести "сеанс акуратного думання" :-).

Спочатку з'ясуємо, як часто стрілки сходяться:

рівно в 0:00, потім приблизно в 1:05, в 2:11, і так далі, в 10:55 - всього одинадцять положень.

Кутові швидкості стрілок постійні, тому «збіги» настають через рівні проміжки часу.

Отже, між ними проходить 12/11 години, або (12*60) /11 хвилин.

Проміжок часу від моменту першого збігу 0:00 до моменту h : m (h годин m хвилин) рівний 60*h+m хвилин і є проміжком часу від одного із збігів стрілок до моменту h:m.

Причому, це збіг останній, якщо 60*h+m <(12*60)/11.

Якщо ж 60*h+m >= (12*60)/11, то можна обчислити 60*h+m - (12*60) /11 (час після другого збігу), 60*h+m - 2*(12*60) /11 (після третього) і так далі.
На деякому кроці отримаємо різницю t в межах від 0 до (12*60) /11. Це і буде проміжок часу після останнього збігу до моменту h: m.

Отже, до наступного "збігу" залишилося (12*60) /11 - t хвилин, і залишається лише узяти цілу частину цього числа.

Якщо ви все зрозуміли - спробуйте написати розв'язок

Власне, розв'язок задачі Clock

За одиницю часу приймемо не хвилину, а одну одиннадцяту хвилини.

Тоді всі числа будуть цілими, і t можна обчислити не в циклі, а за допомогою операції mod, як в наступній програмі:

Code

Рrogram Сlock;
var h, m, t : integer;

      begin
        readln(h, m);

        t := 11*(60*h+m) mod 720;

        if t <> 0  then  t := 720 - t;

        writeln (t div 11); {ціле число хвилин}

end.

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

Відредаговано: pasichov - Сб, 09.10.2010, 15:12

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

Дата: Сб, 09.10.2010, 22:51 | Повідомлення № 30

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

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

Нагороди: 18

Рейтинг: 209

Я зрозумів помилку. Дякую за розв’язок. Цікава задача.