281

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

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

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

282

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

283

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

284

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

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

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

285

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

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

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


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

286

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

287

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

288 Востаннє редагувалося 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

289

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

290

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

291

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

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

292 Востаннє редагувалося leofun01 (19.07.2018 09:42:32)

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

Задача :

Вивести (на екран, в файл, ще кудись - не важливо) всі числа від 0 до 7 включно в довільній послідовності не використовуючи арифметичних операцій. Кожне число має бути виведено рівно 1 раз.

Умови :

Заборонено використовувати :
- арифметичні операції +, -, *, /, %, +=, -=, *=, /=, %=, ++, --;
- функції sum, add, div, mod, accumulate, і інші арифметичні чи статистичні функції;
- функції log, log2, pow, sin, cos, і інші аналітичні функції;
- умовні оператори if, else, switch, case, ?:, ??;
- оператори переходу goto;
- стрічки String, char*, wchar_t*, "str", 'str' (крім випадків, коли виконується приведення типів для виводу числа на екран, або коли застосовується стрічка форматування, наприклад "%i");
- стандартну функцію виводу 2 або більше разів в коді;
- константи і змінні, які займають більше ніж 8 біт (роз'яснення: ви можете використовувати і 16- і 32- бітні типи, але їхні значення повинні вміщатися в 8 біт);
- масиви, кортежі, вектори, послідовності, колекції, списки, стеки і інші контейнери даних;

Дозволено використовувати :
- бітові операції &, ^, |, &=, ^=, |=, &&, ||, ;
- операції зсуву <<, >>, <<=, >>=, >>>;
- присвоєння =, :=;
- порівняння ==, ===, !=, !==, >, <, >=, <=;
- стандартні бітові функції AND, XOR, OR, NOR, ... якщо такі надаються мовою програмування;
- цикли while, do while, for, until, але тільки 1 цикл і 1 раз;
- стрічки форматування виводу "%g", "{0}";
- стандартну функцію виводу 1 раз в коді (в циклі);
- константи і змінні, які займають до 8 біт включно;
- будь-яку мову програмування;

Приклади виводу :

Можна так :

0
1
5
7
6
3
4
2

або так :

010
111
011
110
101
000
001
100

upd: змінних і констант разом має бути не більше ніж 5.

Подякували: Yola, Betterthanyou2

293 Востаннє редагувалося leofun01 (19.07.2018 09:38:08)

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

А для тих, хто пізнав дзен в теорії автоматів, попробуйте вивести всі числа від 0 до 15 включно з тими самими умовами і з поправкою :
Заборонено використовувати константи і змінні, які займають більше ніж 32 біти;

294

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

leofun01, я щось не розумію, як можна не використовувати стандартну функцію виводу 2 або більше разів в коді. І вивести ці числа, за 1 раз. Де їх тоді зберігати, якщо умовою задачі массиви заборонені,а змінні не більше 8 біт?

295 Востаннє редагувалося Yola (19.07.2018 11:24:24)

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

Для 7:

char spreadLSB(char in) {
    in = in & 1;
    in = in | (in << 1) | (in << 2) | (in << 3) | (in << 4) | (in << 5) | (in << 6) | (in << 7);
    return in;
}

void leofun() {
    bool curr1;
    bool prev0 = true;
    unsigned char i = (unsigned char)-1;
    char out = 0;
    while (out != 7) {
        out = 0;
        for (int j = 1; j < 8; ++j) {// цей цикл лише для читності коду, можна розгорнути в 7 блоків
            curr1 = i & (1 << j);
            bool useIt = curr1 && prev0;
            out |= spreadLSB(useIt) & j;
            prev0 = !curr1;
        }
        std::cout << (int)out << " ";
        i = i << 1;
    }
}
Консоль написав:

1 0 2 3 4 5 6 7

Для 15: Замінюємо char на short, 7 на 15 і 8 на 16.

void leofun() {
    bool curr1;
    bool prev0 = true;
    unsigned short i = (unsigned short)-1;
    short out = 0;
    while (out != 15) {
        out = 0;
        for (int j = 1; j < 16; ++j) {
            curr1 = i & (1 << j);
            bool useIt = curr1 && prev0;
            out |= spreadLSB(useIt) & j;
            prev0 = !curr1;
        }
        std::cout << (int)out << " ";
        i = i << 1;
    }
}
Консоль написав:

1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Очевидно, що це не те, що хтів пан leofun01, бо дзен теорії автоматів для мене залишається непізнаним.

ukrainian.stackexchange.com - це питання-відповіді з української мови
Подякували: morgot, leofun012

296

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

А яке з правил забороняє робити

cout<<0<<endl<<1<<endl<<2<<endl...

?

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

297 Востаннє редагувалося Yola (19.07.2018 13:30:11)

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

koala написав:

А яке з правил забороняє робити

cout<<0<<endl<<1<<endl<<2<<endl...

?

leofun01 написав:

- стандартну функцію виводу 1 раз в коді (в циклі);

Оператор << має такий вигляд

 basic_ostream& operator<<( ... );

тобто кожен наступний << це окремий виклик.

ukrainian.stackexchange.com - це питання-відповіді з української мови
Подякували: leofun011

298

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

std::cout << (int)out << " "; - це 2 виклики, правильно?

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

299 Востаннє редагувалося Yola (19.07.2018 16:05:20)

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

koala написав:

std::cout << (int)out << " "; - це 2 виклики, правильно?

Вкусіть мене за сраку. Мисліть ширше.

ukrainian.stackexchange.com - це питання-відповіді з української мови
Подякували: leofun011

300 Востаннє редагувалося Vo_Vik (19.07.2018 19:00:22)

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

00101110
1, 2, 5, 3,  7,  6, 4, 0
Нє?

Подякували: leofun01, ReAl, Yola, 0x9111A4