1

Тема: Допоможіть, будь ласка, розв’язати завдання

Рунічні цифри

В давніх рунах використовуються числа, подібні до римських, але дещо спрощених. Використовуються цифри I, V, X, L відповідні 1, 5, 10 и 50 відповідно. Інші цифри використовувати не можна. Числа в цій системі обчислення записують як послідовність з однієї, або кількох цифр. Значення запису дорівнює сумі всіх цифр в ньому.
Наприклад запис XXXV відповідає числу 35, а запис IXI — числу 12.
На відміну від звичайних римських чисел будь-яка послідовність цифр є коректною, порядок цифр не має значення (запис IX означає 11, а не 9).
Тому одне й теж число можна записати по-різному.
Обчисліть, скільки є різних чисел, які можна записати, використовуючи хоч би одну з рівно n рунічних цифр I, V, X и L.

Формат входных данных

В одному рядку дано ціле число n (1 ≤ n ≤ 109) — число рунічних цифр в запису чисел.

Формат результата

Виведіть одне — кількість різних чисел, які можна записати, використовуючи рівно n рунічних цифр I, V, X и L.

Примеры

Входные данные
1
Результат работы
4
Входные данные
2
Результат работы
10
Входные данные
10
Результат работы
244
Примечания

В першому прикладі є рівно 4 різних числа, які можна отримати — I, V, X и L. В другому прикладі можна отримати рунічні числа: 2 (II), 6 (VI), 10 (VV), 11 (XI), 15 (XV), 20 (XX), 51 (IL), 55 (VL), 60 (XL) и 100 (LL).

2

Re: Допоможіть, будь ласка, розв’язати завдання

Чим допомогти, перепрошую? Вам потрібна психологічна підтримка? У якій саме формі? Тут треба писати "я знаю, ти зможеш, я вірю в тебе" чи "а ну швидко пішла робити, бо з універу виженуть"?

Подякували: 0xDADA11C71

3

Re: Допоможіть, будь ласка, розв’язати завдання

Другу добру намагаюсь утрішити, але не можу( На даному етапі розумію, що там у закономірності є трикутні числа. Але саму формулу не можу ніяк підібрати (жодна з формул комбінаторики не підійшла)

4

Re: Допоможіть, будь ласка, розв’язати завдання

А тут чиста комбінаторика дає певні збої.
Наприклад, LIIIII і XXXXXV - одне й те саме число(55); але як це нормально враховувати в комбінаторній формулі?
Треба подумати.

Прихований текст

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

Так, і 109 - це реально 109 чи 109?

5

Re: Допоможіть, будь ласка, розв’язати завдання

Знайшла, що для 2-х значного - 10, 3-х - 20, 4-х - 35, 5 - 56, 6 - 84 (виводилося на папірі способом перебору). За моєю логікою далі повинно іти: 7 - 120, 8 - 165, 9 - 220, 10 - 285. І ось тут не зходиться, тому що у завданні сказано, що для десятизначного - 244, а в мене виходить 285

Подякували: koala1

6

Re: Допоможіть, будь ласка, розв’язати завдання

Тако ж знайшла послідовність, що (нехай i - 1, v - 2, x - 3, L - 4) (для зручності спочатку перебираю усі варіаціі з першою цифрою, потім з другою, потім з третьою. Тоді за моїми розрахунками кількість варіацій для першого числа == кількості варіацій першого числа + трикутне число під номером кількості цифр усього числа(маю на увазі 1 (для однозначного), 3 - для двозначного, 6 - трьохзначне, 10 - чотирьох, 15 -...), яке на одну цифру меньше (наприклад для і у трьохзначного - 10 варіації (4(кількість варіацій для першої цифри двозначного) + 6 (трикутне число під номером 3)). Тако ж вивела, що кількість комбінацій для останньої цифри - завжди == 1. Для третього числа(переостаннього) - кількість цифр(двозначне - 2, десятизначне - 10, двадцяти - 20)

Подякували: koala1

7

Re: Допоможіть, будь ласка, розв’язати завдання

Дуже тупий і прямолінійний код: https://ideone.com/CselZx
Якщо бажаєте, можна переробити, щоб виводив комбінації і значення, це Python.
Для 109 - працює. Для 109 - ні.

Подякували: rita15062425, Chemist-i2

8

Re: Допоможіть, будь ласка, розв’язати завдання

Дуже Дуже Дуже дякую . (Все ж таки перекладати тести у гугл плей на українську, було набагато легше, ніж вирішувати цю задачу :)  І дякую, що все ж таки виправили негативні відгуки на позитивні)))

9

Re: Допоможіть, будь ласка, розв’язати завдання

А чи не підкажете, чим можна замінити три вложена цикли for? Переписала цю задачу на C#, але все рівно не виконує з великими числами. Може є якісь варіанти?

10

Re: Допоможіть, будь ласка, розв’язати завдання

Я ж написав: це тупий код. Щоб маленькі значення отримати.
Для великих треба думати.

11

Re: Допоможіть, будь ласка, розв’язати завдання

Взгляніть, будь ласка, на цю задачу. Чомусб пише, що в мене неповне рішення. (Тільки ці дві задачі залишилися невирішенними з дванадцяти)


Олімпіада в школі юних чарівників
Учениця школи юних чарівників відмінниця Герміона отримала доручення підготувати завдання для олімпіади з магії серед учнів першого курсу. Всього потрібно скласти n завдань, за розв’язання кожного i-го завдання першокурсник отримую pi балів (де pi – ціле число не менше, ніж 1). Загальна оцінка учасника олімпіади розраховується, як сума балів за всі завдання.

Герміона вболіває за учня факультету Грифіндор, та знає, що учень Слізеріну теж приймає участь в олімпіаді. Тому вона хоче, щоб представник Слізеріну отримав менше балів, ніж представник Грифіндору. І вона намагається розрахувати бали за завдання таким чином, щоб учень Грифіндору отримав строго більше балів, ніж учень Слізеріну. Але вона не хоче, щоб бали грифіндорця були дуже великими, тому намагається мінімізувати максимальну суму pi за всіма задачами.

Допоможіть Герміоні знайти мінімально можливе граничне значення на кількість балів за одне завдання.

Формат входных данных
В першому рядку задано одне ціле число n (1 ≤ n ≤ 100) – кількість завдань в олімпіаді.
В другому рядку задано n цілих чисел g1, g2, …, gn (0 ≤ gi ≤ 1), кожне gi = 1 означає, що грифіндорець розв’яже завдання i, gi = 0, що не зможе розв’язати завдання i.
В третьому рядку задано n цілих чисел s1, s2, …, sn (0 ≤ si ≤ 1), кожне si = 1 означає, що слізерінець розв’яже завдання i, si = 0, що не зможе розв’язати завдання i.

Формат результата
Якщо грифіндорець ні в якому разі не може набрати більше балів, ніж слізерінець – виведіть -1. Якщо зможе – виведіть мінімально можливе значення max(pi), де i = 1, …, n, при якому можна задати такі значення pi, що грифіндорець отримає строго більше балів, ніж слізерінець.

Примеры
Входные данные
5
1 1 1 0 0
0 1 1 1 1
Результат работы
3
Входные данные
3
0 0 0
0 0 0
Результат работы
-1
Входные данные
4
1 1 1 1
1 1 1 1
Результат работы
-1
Входные данные
9
1 0 0 0 0 0 0 0 1
0 1 1 0 1 1 1 1 0
Результат работы
4
Примечания
У першому прикладі можливий розподіл балів p={3,1,3,1,1}, тоді грифіндорець отримає 7 балів, а слізерінець – 6.
В другому прикладі - обоє получать 0 балів.
В третьому прикладі – обоє розв’яжуть усі завдання.










n = int(input())


g = input()
g = g.split()

s = input()         
s = s.split()

count_Grif = 0
count_Sliz = 0

now = 0     

stavka = 0
write = 0


while count_Grif <= count_Sliz:
    if stavka < 20:
        stavka = stavka + 1
        now = 0
        count_Grif = 0
        count_Sliz = 0
        while now < n:
            if int(g[now]) == 1:     
                count_Grif = count_Grif + stavka
                count_Sliz = count_Sliz +  int(s[now]) * stavka
            else:
                count_Sliz = count_Sliz +  int(s[now]) * 1
       
            now = now + 1
    else:
        print(-1)
        count_Grif = 10000000000
        write = 1   
if write == 0:
    print(stavka)

12

Re: Допоможіть, будь ласка, розв’язати завдання

Будь ласка, доперекладайте текст і поставте теги code (кнопка <>) навколо коду.

Подякували: rita150624251

13

Re: Допоможіть, будь ласка, розв’язати завдання

Все цю задачу вирішила. Але ніяк не можу ортимізувати задчу про руни. А до кінця здачі робіт залишилося 40 хвилин :( Але все рівно дуже дякую за допомогу

14

Re: Допоможіть, будь ласка, розв’язати завдання

Для Гоґсварду: треба знайти кількість задач, де в Грифіндора 1 і Слізерина 0 (g) чи навпаки (s), а решта не впливають на відповідь. Далі ставимо за ті, де виграє Слізерин, по 1 балу (разом s балів), ділимо на g (бо за кожен грифіндорець має отримати саме стільки балів) і округлюємо вгору (бо має бути ціле).

Подякували: rita150624251

15

Re: Допоможіть, будь ласка, розв’язати завдання

Так і зробила. Тільки здається (Слизерин +1)/Грифендор. І math.ceil, як ви й написали