Блог вчителя інформатики Соломійчука Ігоря Васильовича: Олімпіада з інформатики 2023-2024 р.

3 грудня відбулася районна олімпіада з інформатики у Косівському районі. На цій сторінці буде розглянуто декілька задач олімпіади.

Задача А. Міс М живе на планеті Бітакуляндія, де найпопулярніша валюта — біткопійка. Нещодавно Міс М проводила мінізмагання для друзів, де кожен переможець отримує рівно три біткопійки.

Відомо, що в змаганні Міс М призовий фонд становить $n$ біткопійок, перемогло $m$ людей, і кожен переможець отримує рівно три біткопійки.

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

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $3 \leq n \leq 100$ ) — кількість біткопійок.

Другий рядок містить одне ціле число $m$ ( $1 \leq m \leq 100$ ) — кількість друзів Міс М, які перемогли в змаганні.

Гарантується, що в Міс М буде достатньо біткопійок, щоб роздати їх її друзям-переможцям.

Вихідні дані

Виведіть одне ціле число — кількість біткопійок, які залишаться в Міс М після того, як вона їх роздасть своїм друзям.

Приклади

Input

10 2

Answer

Note

У Міс М перемогли двоє друзів, кожному з них вона віддасть три біткопійки. Сумарно вона віддасть шість, тому залишаться лише чотири біткопійки.

Текст програми на Python.

n=int(input())

m=int(input())

print(n-m*3)

Задача B.

Міс М одну з квіткових клумб зробила у вигляді шахової дошки розмірами $n \times m$ , у кожній клітинці якої росте одна квітка.

Вона збирається в гості до Сонечки та вирішила для неї зібрати букет квітів з клумби. Але оскільки Міс М дуже поспішає, то вона доручила це завдання спеціальному роботу.

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

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

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1000$ ).

Другий рядок містить одне ціле число $m$ ( $1 \leq m \leq 1000$ ).

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Input

3

4

Answer

Note

Алгоритм збирання квітів за максимальну кількість проходів буде таким:

За перший прохід по клумбі робот збере рівно $6$ квітів, оскільки відвідає $6$ клітинок (на малюнках позначено червоним кольором).
Кожен наступний прохід буде проходити рівно через одну нову клітинку, тому робот збере наступних $6$ квіток за $6$ проходів.

Усього $1 + 6 = 7$ проходів.

Схема шляхів робота з першого прикладу з умови.

Текст програми на Python.

n=int(input())

m=int(input())

print((n-1)*(m-1)+1)

Задача С.

Міс M та Містер N живуть на планеті Бітакуляндії, де рік складається з $12$ місяців, а кожен місяць — з $30$ днів. Вони нещодавно виявили, що деякі люди могли народитися в один і той самий день, хоч і дати днів народження різні. Це можливо через зміну Байтуліанського календаря на Бітуліанський. Усі країни Бітакуляндії перейшли з одного на інший календар у дуже різні роки, тому деякі дати народжень різних жителів, які народилися в один день, можуть відрізнятися. Наприклад, дата $15$ березня за Байтуліанським календарем відповідає даті $28$ березня за Бітуліанським, тобто різниця в $13$ днів вперед.

Тепер Міс M та Містер N хочуть з'ясувати, чи не народилися вони в один день, якщо дата народження Містера N буде записана за Байтуліанським календарем, а Міс M — за Бітуліанським. Допоможіть їм у цьому!

Вхідні дані

Перший рядок містить два цілі числа $d_{1}$ та $m_{1}$ ( $1 \leq d_{1} \leq 30$ , $1 \leq m_{1} \leq 12$ ) — день та місяць за Байтуліанським календарем.

Другий рядок містить два цілі числа $d_{2}$ та $m_{2}$ ( $1 \leq d_{2} \leq 30$ , $1 \leq m_{2} \leq 12$ ) — день та місяць за Бітуліанським календарем.

Гарантується, що дата за Байтуліанським календарем — не пізніше за дату за Бітуліанським календарем.

Вихідні дані

Виведіть «Same birthday!», якщо обидві дати позначають один і той самий день, та «Not the same» у протилежному випадку.

Приклади

Input

26 11

9 12

Answer

Same birthday!

Input #1

1 1

20 12

Answer #1

Not the same

Для вирішення даної задачі переведемо обидві дати у дні. Потім знайдемо різницю дат. Якщо різниця дорівнює 13 то це той самий день.

Текст програми на Python.

d1,m1=map(int,input().split())
d2,m2=map(int,input().split())
n1=(m1-1)*30+d1
n2=(m2-1)*30+d2
if n2-n1==13:
    print('Same birthday!')
else:
    print('Not the same')

Задача D.

Міс М живе на планеті Бітакуляндії та вирішила зробити переїзд із країни Держпродія до країни Тоболяндія.

Поки що вона вирішила перемістити чотири найважливіших речей. Для переміщення вона вирішила використовувати дві коробки, куди покладе усі речі. Відомо, що $i$ -а річ важить $w_{i}$ кілограмів та знаходиться в $t_{i}$ -й коробці.

Їй потрібно буде переміщати коробки по одній, тому вона дуже хотіла б, щоб коробки не були заважкими. Тобто щоб максимально можлива вага коробки була мінімальною. Через те, що в неї не так багато часу, вона може лише перемістити одну річ з однієї коробки в іншу.

Допоможіть їй полегшити переїзд та знайдіть, яку річ потрібно перекласти!

Вхідні дані

Перший рядок містить чотири цілі числа $w_{1}$ , $w_{2}$ , $w_{3}$ , $w_{4}$ ( $1 \leq w_{i} \leq 1 0^{6}$ ) — ваги кожної з чотирьох речей.

Другий рядок містить чотири цілі числа $t_{1}$ , $t_{2}$ , $t_{3}$ , $t_{4}$ ( $1 \leq t_{i} \leq 2$ ) — номери коробок, у яких лежать відповідні речі.

Вихідні дані

Виведіть одне ціле число $p$ ( $1 \leq p \leq 4$ ) — номер речі, яку потрібно перемістити в іншу коробку.

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

Якщо оптимально нічого не змінювати, то виведіть одне ціле число «-1».

Приклади

Input

5 2 4 3

1 2 2 1

Answer

-1

Input #1

4 2 3 7

2 1 1 2

Answer #1

Note

Для досягнення мінімальної максимальної можливої ваги після переміщення однієї речі з однієї коробки в іншу, у другому прикладі є лише один варіант. У початкового розподілення речей за коробками, ваги коробок — $5$ та $11$ . Розглянемо всі варіанти переміщення речей між коробками:

Якщо перемістити річ номер $1$ вагою $4$ з другої коробки в першу, то ваги коробок будуть $4 + 2 + 3$ та $7$ , $max = 9$ .
Якщо перемістити річ номер $2$ вагою $2$ з першої коробки в другу, то ваги коробок будуть $4 + 7 + 2$ та $3$ , $max = 13$ .
Якщо перемістити річ номер $3$ вагою $3$ з першої коробки в другу, то ваги коробок будуть $4 + 7 + 3$ та $2$ , $max = 14$ .
Якщо перемістити річ номер $4$ вагою $7$ з другої коробки в першу, то ваги коробок будуть $2 + 3 + 7$ та $4$ , $max = 12$ .

Текст програми на Python.
```
v1,v2,v3,v4=map(int,input().split())
t1,t2,t3,t4=map(int,input().split())
v=[v1,v2,v3,v4]           #перетворимо вхідні дані у список
t=[t1,t2,t3,t4]
h=[]
s1=0
s2=0
for i in range(4):        #обчислимо вагу кожної з двох коробок
    if t[i]==1:
        s1=s1+v[i]    
    else:
        s2=s2+v[i]
s=max(s1,s2)               #знайдемо більшу з коробок

for i in range(4):         #тепер будемо розглядати варіанти перекладання кожної речі у іншу 
    if t[i]==2:            #коробку. 
        a=s1+v[i]
        b=s2-v[i]
    else:
        a=s1-v[i]
        b=s2+v[i]
    h.append(max(a,b))       #більшу з одержаних мас зберігаємо у новий список.
if s>min(h):
    print(h.index(min(h))+1) #якщо у новому списку є менша маса то виводимо її номер
else:
    print(-1)                #якщо при вереміщення вантажів ми не одержали меншу масу коробок
```
```
                             #то виводимо -1. 
```
Задача Е. Сонечка — найкраща подруга Міс М. Вона вступила до найкращого університету далекої та прогресивної країни Безчаїндії. Міс М дуже сумує за подружкою, тому вирішила зробити подарунок для Сонечки, поки вона навчається в іншій країні.
Сьогодні в Сонечки день народження, але Міс М ще може встигнути підготувати подарунок, оскільки має час, адже Сонечка повернеться трішки пізніше.
Міс М вирішила, що хоче навчитися вишивати хрестиком і зробити орнаменти на вишиванці, яка буде подарунком для Сонечки, і подарувати, коли та повернеться. Але вона поки взагалі не знає, з чого почати. У неї з'явилася ідея написати програму, що буде робити орнамент потрібної ширини та довжини, який вона може потім використовувати як приклад для вишивки.
Вишиванка — це прямокутник $n \times m$ . Орнаменти — це два промені, які виходять з верхніх кутів вишиванки та мають кути $4 5^{\circ}$ . Промінь відбивається, коли доторкається до вертикального краю. Коли промінь доторкається до нижнього краю — він зникає. Для кращого розуміння можете подивитися приклади.
Допоможіть Міс М навчитися вишивати хрестиком та подарувати красиву вишиванку прекрасній Сонечці на день народження, написавши таку програму, яка відповідно до заданої ширини $n$ та довжини $m$ виведе приклад орнаменту.
Вхідні дані
Перший рядок містить два цілі числа $n$ та $m$ ( $3 \leq n, m \leq 1000$ ) — висота та ширина відповідно.
Вихідні дані
Виведіть орнамент розмірами $n \times m$ .
Приклади
Input
```
6 4
```
Answer
```
x..x

.xx.

.xx.

x..x

.xx.

.xx.
```
Input #1
```
12 5
```
Answer #1
```
x...x

.x.x.

..x..

.x.x.

x...x

.x.x.

..x..

.x.x.

x...x

.x.x.

..x..

.x.x.
```
Input #2
```
21 12
```
Answer #2
```
x..........x

.x........x.

..x......x..

...x....x...

....x..x....

.....xx.....

.....xx.....

....x..x....

...x....x...

..x......x..

.x........x.

x..........x

.x........x.

..x......x..

...x....x...

....x..x....

.....xx.....

.....xx.....

....x..x....

...x....x...

..x......x..
```
```
 
```
Текст програми на Python.
```
a='.'
b='x'
n,m=map(int,input().split())
for i in range(n):
    for j in range(m):
        if j==i%(m-1) or j==m-i%(m-1)-1:
            print(b,end='')
        else:
            print(a,end='')
    print(end='\n') 
```
```
 
```
На перший погляд дуже складна задача, але якщо розібратися то текст програми не такий вже й складний. Організовуємо друк символів по рядках. У кожному рядку перевіряємо умову, коли повинен друкуватися символ "х".

Блог вчителя інформатики Соломійчука Ігоря Васильовича

Олімпіада з інформатики 2023-2024 р.

Вхідні дані

Вихідні дані

Приклади

Вхідні дані

Вихідні дані

Приклади

Input

Answer

Note

Вхідні дані

Вихідні дані

Приклади

Вхідні дані

Вихідні дані

Приклади

Input

Answer

Input #1

Answer #1

Note

Вхідні дані

Вихідні дані

Приклади

Input

Answer

Input #1

Answer #1

Input #2

Answer #2

Немає коментарів:

Дописати коментар