281

Re: Цікаві задачі

leofun01 написав:
2andnot написав:
Люблю подібні задачки ...
Люблю подібні задачки, шкода що нових нема, то ж запропоную свою, мені її задавали на першому курсі на контрольну роботу. можливо комусь вона здаватиметься надто простою та типовою але мені вона сподобалась.
Є ряд натуральних чисел, від 1 до n(як показує практика n величиною  більше 10-12 краще не обирати), нехай це будуть числа від 1 до 5. вивести на консоль всі можливі комбінації. числа та комбінації не повторюються.
тобто наприклад

12345
14523
54312
і так далі
11234 буде невірним результатом
12345
12345 також буде невірним результатом якщо комбінація десь повторюватиметься

цей алгоритм можна використовувати не тільки для чисел.

Рішення мовою PHP:

<?php
    function print_all_int_permutations($columns, $maxValue)
    {
        echo 'columns = '.$columns.', maxValue = '.$maxValue." :<br/>\r\n\t";
        for($digits = array_fill(0, $columns, 1), $i = 0; $i >= 0; )
        {
            echo implode(', ', $digits)."<br/>\r\n\t";
            for($i = $columns; --$i >= 0 && ++$digits[$i] > $maxValue; )
                $digits[$i] = 1;
        }
        echo '<br/>';
    }
    print_all_int_permutations(5,5);
?>

В прикріпленому файлі функції f_while і f_for роблять одне й те саме (що і в наведеному тут коді), просто це був такий навчальний приклад для мого знайомого, щоб показати, що while і for працюють однаково.

Прихований текст
фу, у вас php...

erlang

L = [1,2,3,4,5],
[io:format("~p~p~p~p~p~n",[A,B,C,D,E]) || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A=/=E, B=/=C, B=/=D, B=/=E, C=/=D, C=/=E, D=/=E].
Прихований текст
трошки тупо, проте працює
https://blog.clever-games.win/
Це ще не кінець. Це навіть не початок кінця. Але, можливо, це кінець початку.
Зростання мудрості можна точно вимірювати ступенем зменшення злоби.
///// у творчій відпустці. не турбувати /////
Подякували: Betterthanyou, leofun012

282

Re: Цікаві задачі

0x9111A, так який все ж "красивий" розв'язок у пошуку двох відсутніх чисел у два проходи?

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

283

Re: Цікаві задачі

koala написав:

0x9111A, так який все ж "красивий" розв'язок у пошуку двох відсутніх чисел у два проходи?

1) Шукаємо суму чисел [1..N] по шкільній формулі і від неї віднімаємо суму вхідного масиву.
На виході сума відсутніх чисел, хай буде (x+y).
2) Оскільки числа не однакові, одне з них буде гаратновано <= (x+y)/2. Менше рівне щоб цілочисельне ділення запрацювало ( (3 + 4) / 2 = 3 ).
3) Використовуючи той самий метод що й у кроці 1, шукаємо x:
Тепер ми знаємо, що одне з чисел в діапазоні [1..(x+y)/2], а друге точно ні. Шукаємо суму чисел [1..(x+y)/2] по шкільній формулі і віднімаємо суму чисел з нашого масиво що підходять в цей діапазон.
4) Як знайти 'у' має бути зрозуміло тим хто дочитав :)

Графоманія

Maybe a = Just a | Nothing
Подякували: koala, 221VOLT2

284

Re: Цікаві задачі

Вимоги:
Мова програмування: будь-яка, можна використовувати фреймворкі, бібліотеки, т.д.
Час: 24 хв одна задача (4год для всіх)

A i B

http://i.piccy.info/i9/cb6a69c8548fd55c0970e34756aeb7d5/1521584287/422595/1230951/1.jpghttp://i.piccy.info/i9/cb6a69c8548fd55c0970e34756aeb7d5/1521584287/422595/1230951/1.jpg
C i D

http://i.piccy.info/i9/3e4057b07fcb04b2eb06bd4f2f5cdef6/1521584108/425314/1230951/11.jpghttp://i.piccy.info/i9/3e4057b07fcb04b2eb06bd4f2f5cdef6/1521584108/425314/1230951/11.jpg
E i F

http://i.piccy.info/i9/3de151f864c9c8bdcc6b1103103c6824/1521584084/308083/1230951/12.jpghttp://i.piccy.info/i9/3de151f864c9c8bdcc6b1103103c6824/1521584084/308083/1230951/12.jpg
G i H

http://i.piccy.info/i9/6329013d2b98b23763fa592c035a66ca/1521584102/282351/1230951/13.jpghttp://i.piccy.info/i9/6329013d2b98b23763fa592c035a66ca/1521584102/282351/1230951/13.jpg
I i J

http://i.piccy.info/i9/c3d5175826db83bf2b2ae3774da19e31/1521584130/476027/1230951/14.jpghttp://i.piccy.info/i9/c3d5175826db83bf2b2ae3774da19e31/1521584130/476027/1230951/14.jpg
Подякували: 221VOLT1

285

Re: Цікаві задачі

Щось не дуже цікаві. Ну, крім, хіба, B - але там всього 1440 комбінацій, перебором легко знайти всі за даний час. І над J треба ще трохи подумати.

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

286

Re: Цікаві задачі

Складність задач полягає в обмеженому часі 24 хв.
Кожна задача має пройти 100 тестів (на жаль в мене їх немає, тому не скину)

Я встиг зробити B, C, E, G приблизно за пів години. Задачі A, H забрали 1.20 год ( але всі тести так і не були пройдені )


Що до A i H. Як їх найшвидше реалізувати ?

287

Re: Цікаві задачі

A:

w,h,n=[int(x) for x in input().split()]
x = [0,w+1]#"віртуальні" вежі в кутках за межами поля
y = [0,h+1]
for _ in range(n):
  new_x, new_y = [int(i) for i in input().split()]
  x.append(new_x)
  y.append(new_y)
x.sort()
y.sort()
max_x = max(a-b for a,b in zip(x[1:],x))
max_y = max(a-b for a,b in zip(y[1:],y))
print((max_x-1)*(max_y-1))
Подякували: Betterthanyou1

288

Re: Цікаві задачі

H: не зрозумів, нащо там про "цікавиться однаковою кількістю цифр". Ну, хіба що для загальної стимуляції роздумів.
1 - 1
2 - 01, 10
3 - 02, 11, 20
4 - 03, 12, 21, 30
...
10 - 09, 18, 27, 36, 45, 54, 63, 72, 81, 90
далі щось не так. Вилізаємо у третій розряд.
11 - 19, 28, 37, 46, 55, 64, 73, 82, 91, 109, 118 - не дуже, бо
11 - 09, 18, 27, 36, 45, 54, 63, 72, 81, 90, 108 краще.
Схоже, що треба лишатися в 1-значних сумах, але так, щоб максимальнозначних було якнайменше. А початок був такий симетричний. Гм...
001, 010, 100
002, 011, 020, 101, 110, 200
003, 012, 021, 102, 111, 120, 201, 210, 300
Ні, не виходить. Ну і біс із ним, ніколи не любив програмування на швидкість.

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

289 Востаннє редагувалося Betterthanyou (21.03.2018 14:52:21)

Re: Цікаві задачі

Я зрозумів так:

"N натуральних чисел з однаковою сумою цифр і мінімально можливою загальною сумою (чого ? напевно чисел)"

мінімально можливою загальною сумою: 00 + 11 = 11

однаковою сумою цифр: 0 + 0 + 1 + 1 = 1 + 1

мінімально можливою загальною сумою: 00 + 11 + 22 = 33

однаковою сумою цифр: 0 + 0 + 1 + 1 + 2 + 2 = 3 + 3

290

Re: Цікаві задачі

Так тоді 0+1=1 чим не підходить?
n=2. Числа {1,10}, сума цифр у всіх 1, сума всіх чисел - 11 мінімальна.
n=3. Числа {1,10,100} - не підходять, бо {2,11,20} мають меншу суму.
Значить, просто тупо генеруємо для всіх S=1,2,... всі i-значні (i=1,2,...) числа з сумою цифр S, доки не наберемо n чисел, і порівнюємо суму. Питання тільки в тому, коли перерватися.
4-значні числа мають суми цифр до 36; 4-значних чисел із сумою цифр 18 буде 670 (https://ideone.com/MiiykC), а цього замало, нам треба до 5000. В 5-значних вже суми 22 і 23 набирають по 6000 значень, цього буде гарантовано досить.
Отже, треба перебрати суми до 22, згенерувати n чисел із потрібною сумою і знайти мінімальну суму, що не вилізає за межі 5-значних чисел. Все просто. Але, звісно, не на 24 хвилини.

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

291

Re: Цікаві задачі

https://ideone.com/JtIJmu

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

# your code goes here
import re

def find_n_nums(n):
    very_big_number = 1e12
    
    min_sum = very_big_number
    for i in range(1,23):
        #print('looking for sum',i)
        val = min_num_with_sum(i)
        #print('starting from',val)
        s = val
        for _ in range(n-1):
            val = next_num_with_sum(val)
            #print(val,end=' ')
            s += val
            if s>very_big_number:
                break
        #print('digit sum',i,'number sum',s)
        min_sum = min(min_sum,s)
    return min_sum

def min_num_with_sum(s):
    if s<10:
        return s
    elif s<19:
        return (s-9)*10+9
    else:
        return (s-18)*100+99

def next_num_with_sum(v):
    #print('want to find next to',v)
    v = str(v)
    #looking for 'XXXX9999X0000' pattern
    match = re.search(r'9*\d?0*$',v)
    #print('match is',match)
    v = [0]+[int(d) for d in v]
    #print(v)
    tail_len = len(match.group(0)) #at least 1
    tail_sum = sum(v[-tail_len:]) - 1
    #print('v',v,'tail sum=',tail_sum,end=' ')
    v[-tail_len-1] += 1 #it is not 9
    new_tail = [int(d) for d in str(min_num_with_sum(tail_sum))]
    #print(new_tail)
    new_tail = [0]*(tail_len-len(new_tail))+new_tail
    #print('new_tail',new_tail)
    v[-tail_len:] = new_tail
    #print('v',v,int(''.join(str(d) for d in v)))
    return int(''.join(str(d) for d in v))

n = int(input())
print(find_n_nums(n))

Дебажні повідомлення не видаляв.
Але 24 хвилини... Ну, хіба що зекономити на решті завдань час.

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

292

Re: Цікаві задачі

В D питання з оптимізацією. Маємо 100 кіл і 20000*20000=4e8 точок. Разом - 4e10 операцій, на що може не вистачити 3 секунди.
Хоча, якщо робити навпаки - лічити точки в колах - може, і пройде. Не лічити, боюся, не вийде, вони ж накладаються і мають рубані межі.