Олімпіадні задачі з програмування на мові Pascal

Олімпіадні задачі з  програмування на мові Pascal

Запишіть алгоритми мовою Pascal  і протестуйте їх правильність

1. Максиму треба порахувати скількома способами можна розфарбувати клітинки таблиці mхm трьома кольорами так, щоб для довільних i, j, k  (які приймають натуральні значення від 1 до m) клітинки (i,j), (j,k) та  (k,i) були або одного кольору, або трьох різних кольорів?

Технічні умови. У програму з  клавіатури вводиться ціле додатне число m, що відповідає умові 3 <m<12.  Результатом виконання програми є тільки одне число, яке виводиться теж на екран.

Приклади.  А)Введення: 7.  Виведення: 2187. Б) Введення: 9  виведення: 19683.  В)Введення: 12.  Виведення: 531441.

Розв'язання. Є 3^m способів заповнити верхній рядок таблиці (клітинки (1,1), ...,(1,m)). Поставимо у відповідність кольорам остачі від ділення на 3 так, щоб кольору клітинки (1,1) відповідав 0. Тоді умова рівносильна тому, що для всіх i, j, k cума чисел для клітинок (i,j), (j,k), (k,i) ділиться на 3. Оскільки суми чисел для клітинок (1,1), (1,j), (j,1) та (1,i), (i,j), (j,1) діляться на 3, то клітинці (i,j) має відповідати така остача від ділення на 3, як і у різниці чисел, що відповідають клітинкам (1,i) та (1,j). Оскільки в цьому випадку таблиця задовольняє умові, то вона однозначно

відновлюється за першим рядком, отже, є 3^m розфарбувань таблиці.

2. Дмитрику треба кожне складене двоцифрове число можна подати у вигляді  доданків  xy + y + x  + 1 для деяких цілих  x, y.

Технічні умови. У програму з  клавіатури вводиться ціле додатне число m, що відповідає умові 9<m<100.  Результатом виконання програми є пара  цілих чисел:  х, у, які виводяться теж на екран через один пробіл і задовольняють умові задачі.

Приклади.  А)Введення: 10.  Виведення: 1   4.  Б) Введення: 99  виведення: 2  32.  В)Введення: 12.  Виведення: 2  3.

Розв'язання. Для складеного числа n можна записати  n=ab. Маємо: a∙b=(a-1)(b-1)+(b-1) +(a-1) + 1.  Отже, дане число варто розкласти на два множники a та b. Тоді х = a-1 y=b-1.

3. Баба Фрося щодня продає картоплю на ринку «УРОЖАЙ». У неї денна ціна картоплі  по відношенню  з ранковою знижується на m%, вечірня ціна картоплі по відношенню до денної знижується  на n%.  Допоможіть бабі Фросі  скласти алгоритм, який знаходить відповіді на два запитання: Скільки відсотків становить вечірня ціна картоплі порівняно з ранковою і на скільки  відсотків вона знижується від початкової?

Технічні умови. У програму з  клавіатури вводиться два цілих додатних числа m та n, що відповідають умові 4<m<26    19< n <51.   Результатом виконання програми є пара  цілих чисел:  v, r, які виводяться теж на екран через один пробіл і дають цілочисельні відповіді на  перше та друге запитання баби Фросі  відповідно.

Приклади.  А)Введення: 5  20.  Виведення: 76     24 .

Б) Введення:  12  30  виведення: 62   38.  В)Введення: 25  50.  Виведення: 38  62.

Розв’язання. Позначимо х грн - ціна картоплі вранці, нехай вона дорівнює 100 грн,  тоді y  грн  - ціна картоплі вдень, z грн - ціна картоплі ввечері.  

Якщо відома ранкова ціна, тоді денна ціна  у = х(1-m/100) грн.

Якщо відома ранкова ціна, тоді вечірня ціна  z = х(1-m/100)(1-n/100) грн.

Таким чином, даємо відповіді на перше запитання: відсоткове відношення  між ранковою ціною та вечірньою ціною, що записана у відсотках:  V = 100x/z. Таким чином, даємо відповіді на друге запитання:

різниця r між ранковою ціною та вечірньою, що записана у відсотках:

R= 100(x-z)/x.

4.Сім’я з батька, матері  і дворічного Дениса взялися разом навести порядок в своїй квартирі. Бабуся Дениса задумалася, за який час сім’я наведе повний порядок в своїй квартирі, якщо одна мати навела б його за n години, один батько – за m години, а син, якого лишити напризволяще, зробить повний гармидер за k год?

Технічні умови. У програму з  клавіатури вводиться три цілих додатних числа m, n, k, що відповідають умові 1<m<10;   3< n <10; 2<k<6;     Результатом виконання програми є пара  цілих чисел:  v, r, які виводяться теж на екран через один пробіл і дають відповідь до задачі:  перше v – це ціле кількість годин, а друге число r – це ціла кількість хвилин  відповідно.

Приклади.  А)Введення: 5  6  4.  Виведення: 8     35.

Б) Введення: 9  9  5.  Виведення: 45     0  В) Введення: 3  4  5.  Виведення: 2   37.

Розв'язання.

Знайдемо спільне кратне для чисел m, n, k, це число nsk. Таким чином, за nsk годин одна  мати навела б nsk/m разів порядок, один батько –  nsk/n разів навів би порядок, а син зробив би повний гармидер тільки nsk/k рази. Отже, nsk/(m + n – k) = p разів уся сім’я навела б повний порядок у квартирі за nsk годин. Ясно, що  за  nsk/p годин у квартирі буде повний порядок.