141 Востаннє редагувалося koala (22.09.2018 13:30:52)

Re: Потрібна допомога

Проблема в тому, що для 4 кубів потрібно 33 сірники.
Підозрюю, що треба зробити найближчий до N куб із сірників і доповнювати грані.

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

Що там за малороси перекладали? Не вистачає фантазії - то вже писали б Саморобко чи Саморобок, а не "Самадєлкін".

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

142

Re: Потрібна допомога

koala написав:

Проблема в тому, що для 4 кубів потрібно 33 сірники.
Підозрюю, що треба зробити найближчий до N куб із сірників і доповнювати грані.

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

Що там за малороси перекладали? Не вистачає фантазії - то вже писали б Саморобко чи Саморобок, а не "Самадєлкін".

Тобто 4 куба складаються, в квадратній формі, а не в пряму лінію?
Напряжно получається... Ну, буду думати...

143

Re: Потрібна допомога

Поки що підкажу лише, що операція

o = 12
for i in range(1, n):
    o = o + 8

настільки часто використовується в Python (та й в математиці взагалі), що отримала окрему назву і коротке позначення:

o=4+n*8
Подякували: Eff1c1

144 Востаннє редагувалося koala (22.09.2018 21:47:00)

Re: Потрібна допомога

не зазирати, правильна програма
def parallelogram_matches(x,y,z):
    return x*(y+1)*(z+1)+(x+1)*y*(z+1)+(x+1)*(y+1)*z

def side_matches(n):
    side = int(n**.5)
    if (side+1)**2==n:
        side += 1
    square_matches = 2*side*(side+1)+(side+1)**2
    if side**2==n:
        return square_matches
    if n-side**2<=side:
        return square_matches + 5 + 3*(n-side**2-1)
    else:
        return square_matches + 5 + 3*(side-1) + 5 + 3*(n-side**2-side-1)

def cube_matches(n):
    side = int(n**(1/3))
    if (side+1)**3==n:
        side+=1
    if side**3==n:
        return parallelogram_matches(side,side,side)
    if n <= side*side*(side+1):
        return parallelogram_matches(side,side,side)+side_matches(n - side**3)
    elif n<= side*(side+1)*(side+1):
        return parallelogram_matches(side,side,side+1)+side_matches(n - (side+1)*side**2)
    else:
        return parallelogram_matches(side,side+1,side+1)+side_matches(n - side*(side+1)**2)

код, швидше за все, можна скоротити в рази, але мені ліньки

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

145 Востаннє редагувалося /KIT\ (01.01.2022 01:18:09)

Re: Потрібна допомога

koala написав:

код, швидше за все, можна скоротити в рази, але мені ліньки

Challenge accepted (437 bytes)
pm=lambda x,y,z:x*(y+1)*(z+1)+(x+1)*y*(z+1)+(x+1)*(y+1)*z
def sm(n):s=int(n**.5);s+=1if(s+1)**2==n else 0;sq=2*s*(s+1)+(s+1)**2;return sq if s**2==n else(sq+5+3*(n-s**2-1)if n-s**2<=s else sq+5+3*(s-1)+5+3*(n-s**2-s-1))
def cube_matches(n):s=int(n**(1/3));s+=1if(s+1)**3==n else 0;return pm(s,s,s)if s**3==n else(pm(s,s,s)+sm(n-s**3)if n<=s*s*(s+1)else(pm(s,s,s+1)+sm(n-(s+1)*s**2)if n<=s*(s+1)*(s+1)else pm(s,s+1,s+1)+sm(n-s*(s+1)**2)))
Подякували: ostap34PHP, Eff1c2

146 Востаннє редагувалося leofun01 (23.09.2018 17:10:22)

Re: Потрібна допомога

/KIT\ написав:
koala написав:

код, швидше за все, можна скоротити в рази, але мені ліньки

Challenge accepted (437 bytes)
pm=lambda x,y,z:x*(y+1)*(z+1)+(x+1)*y*(z+1)+(x+1)*(y+1)*z
def sm(n):s=int(n**.5);s+=1if(s+1)**2==n else 0;sq=2*s*(s+1)+(s+1)**2;return sq if s**2==n else(sq+5+3*(n-s**2-1)if n-s**2<=s else sq+5+3*(s-1)+5+3*(n-s**2-s-1))
def cube_matches(n):s=int(n**(1/3));s+=1if(s+1)**3==n else 0;return pm(s,s,s)if s**3==n else(pm(s,s,s)+sm(n-s**3)if n<=s*s*(s+1)else(pm(s,s,s+1)+sm(n-(s+1)*s**2)if n<=s*(s+1)*(s+1)else pm(s,s+1,s+1)+sm(n-s*(s+1)**2)))

koala не це мав на увазі.
Робити таке на Python ...
Це прояв JavaScript'изму головного мозку. (ну ладно, трохи перегнув, сподіваюсь не образив вас).

147

Re: Потрібна допомога

leofun01 написав:

Це прояв JavaScript'изму головного мозку.

а ось це ображає...

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

148

Re: Потрібна допомога

Пане /KIT\, ну не тупо ж мініфікувати (до речі, ви дволітерні ідентифікатори використовуєте, коли ще не вичерпалися однолітерні). Принаймні, не до основних оптимізацій.
Наприклад, зараз я бачу, що parallelogram_matches завжди має хоча б пару однакових параметрів (а використовує вона їх симетрично). Отже, можна зробити

def parallelogram_matches(x,z):
    return x*(x+1)*(z+1)+(x+1)*x*(z+1)+(x+1)*(x+1)*z

а це далі скорочується до

def parallelogram_matches(x,z):
    return 2*x*(x+1)*(z+1)+(x+1)*(x+1)*z

можна ще спробувати

def parallelogram_matches(x,z):
    return (x+1)*(2*x*(z+1)+(x+1)*z)

А якщо дужки в зовнішних розкрити, то матимемо

def parallelogram_matches(x,z):
    return (x+1)*(3*x*z+2*x+z)

поки що виходить з 85 символів 63 проти ваших 57 - але ж це ще без жодної мініфікації, та й ще з десяток символів далі по коду вилетить, бо тепер замість parallelogram_matches(s+1,s+1,s) пишемо parallelogram_matches(s+1,s).
До речі, я якогось біса тут parallelogram замість parallelepiped написав. А насправді ж треба писати box, і тоді

def box_matches(x,z):
    return (x+1)*(3*x*z+2*x+z)

53 символи без мініфікації - проти ваших 57.
Ще можна подумати, як ефективно отримувати найбільше число, 2-ий чи 3-ій степіть котрого не перевищує задане. Оскільки 1/3 трохи менше за третину, int(125**(1/3)) дає 4; через це мені довелося дописати оте

    side = int(n**(1/3))
    if (side+1)**3==n:
        side+=1

Але, гадаю, це можна вирішити якось простіше (і коротше); скажімо,

side = int((n+.5)**(1/3))

і т.д.

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

149

Re: Потрібна допомога

286
b=lambda x,z:(x+1)*(3*x*z+2*x+z)
r=lambda x,p:int((x+.5)**(1/p))
def m(n):s=r(n,2);p=n-s**2;return 3*s**2+4*s+1+(3*p+(4-2*(p<=s))if p else 0)
def c(n):s=r(n,3);x,y=(s+1,s)if n<=s*(s+1)*(s+1)else(s,s+1);return b(s,s)+(0if s**3==n else m(n-s**3))if n<=s*s*(s+1) else b(y,x)+m(n-x*y**2)

викликати функцію c.

Подякували: /KIT\, Eff1c2

150

Re: Потрібна допомога

Я зрозумів, що зарано взявся за цю задачку... Вона занадто складна.
Але все-одно - дуже дякую) Повернусь до неї пізніше...

151

Re: Потрібна допомога

А поки що - https://www.e-olymp.com/uk/problems/20
Розв'язав цю задачку з двома while, але вибило, що 70% відповідей правильні, а решта 30% - не вкладаються в ліміт часу...
Переробив другу while на for...

inp = int(input())
inp1 = inp
outp = 0
m = 0
n = 1
while n > 0:
    m = 0
    n = 0
    t = len(str(inp))
    for i in range(t):
        m = m + (inp % 10)
        inp = inp // 10
    n = inp1 - m
    outp = outp + 1
    inp1 = n
    inp = inp1
print(outp)

Але результат такий самий...
Як можна ще спростити прогу? Чи прийдеться писати її на c++?

152

Re: Потрібна допомога

А ви гадаєте, str створюється без циклу та ділення?
Ну і так, схоже, на Python задача не розв'язується - 2*10^9 дає не менше 2*10^7 операцій, а ділення обчислюється не дуже швидко. Навіть divmod не рятує. Можна, звісно, погратися у віднімання від масиву, але навряд чи там вийде краще, а той факт, що всі числа, крім першого n, діляться на 9, не дуже допомагає.

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

153

Re: Потрібна допомога

Ок, спробую переробити на c++

154

Re: Потрібна допомога

ну от наприклад - варіант скорочення:
Ви якось ту суму цифр рахуєте складно
якщо вже робити це через  літерал числа, то так простіше:

>>> number = 123456
>>> print(sum(map(int, list(str(number)))))
21
>>> 

поміряємо швидкість:

from time import time
number = ''.join([str(i) for i in range(10**3)])
number = int(number)
print(number)
number_copy = number

Ваш код:

t_start = time()
m = 0
t = len(str(number))
for i in range(t):
    m = m + (number % 10)
    number = number // 10
print(m)
print(time() - t_start)

13500
0.015638351440429688

короткий варіант:

t_start = time()
print(sum(map(int, list(str(number_copy)))))
print(time() - t_start)

13500
0.0008478164672851562

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

155

Re: Потрібна допомога

inp = int(input())
inp1 = inp
outp = 0
m = 0
n = 1
while n > 0:
    n = 0
    m = sum(map(int, list(str(inp))))
    n = inp - m
    outp = outp + 1
    inp = n
print(outp)

Результат той самий...

156

Re: Потрібна допомога

ну,тут ще можна трохи оптимізувати, вернуся до компа  - наишу.але, нефакт що поможе
типу
x, y = y, x+1

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

157

Re: Потрібна допомога

Навряд чи допоможе, бо час виконання 3 секунди, а максимум 2...
І від тої оптимізації час виконання фактично не змінився (змінився на 1 мілісекунду)...

158

Re: Потрібна допомога

Eff1c написав:

Навряд чи допоможе, бо час виконання 3 секунди, а максимум 2...
І від тої оптимізації час виконання фактично не змінився (змінився на 1 мілісекунду)...

ну, принаймі хоч код спроститься:

inp, outp = int(input()), 0
while inp > 0:
    inp -= sum(map(int, list(str(inp))))
    outp += 1    
print(outp)
Подякували: Eff1c, ReAl2

159

Re: Потрібна допомога

Я в усі ці ваші map ще не вмію, але оце працює ± не повільніше

n = int(input())
outp = 0
while n > 0:
    m = 0
    s = str(n)
    for ch in s:
        # m = m + int(ch)
        m = m + ord(ch) - ord('0')
    n = n - m
    outp = outp + 1
print(outp)
Подякували: ping1

160

Re: Потрібна допомога

Та там просто неможливо цю задачку зробити на python і щоб вона вклалася в 2 секунди. Як не крути...