281

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

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

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


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

282

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

283

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

284 Востаннє редагувалося Betterthanyou (21.03.2018 13: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

285

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

286

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

287

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

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

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

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

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

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

290

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

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

291 Востаннє редагувалося Yola (19.07.2018 10: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, бо дзен теорії автоматів для мене залишається непізнаним.

Подякували: morgot, leofun012

292

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

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

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

?

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

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

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

koala написав:

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

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

?

leofun01 написав:

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

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

 basic_ostream& operator<<( ... );

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

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

294

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

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

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

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

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

koala написав:

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

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

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

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

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

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

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

297 Востаннє редагувалося leofun01 (19.07.2018 18:32:34)

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

morgot написав:

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

@Vo_Vik дав правильну підказку :

Vo_Vik написав:

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

Та що там підказку ... Можна сказати Vo_Vik розв'язав задачу.


Yola написав:
Для 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, бо дзен теорії автоматів для мене залишається непізнаним.

Ого.. Цікавий розв'язок. Але ++j не дозволяється.
Це задача із тих, про які кажуть "розв'язується в 3 рядки коду".


koala написав:

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

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

?

Хороше питання. Про потоковий вивід я не подумав. Але будемо вважати, що це багато викликів виводу.

upd: Ладно, <<endl можете використовувати скільки хочете, <<endl не рахуємо.

Подякували: 221VOLT1

298

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

Vo_Vik написав:

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

Красиво!

299

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

leofun01 написав:
koala написав:

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

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

?

Хороше питання. Про потоковий вивід я не подумав. Але будемо вважати, що це багато викликів виводу.

upd: Ладно, <<endl можете використовувати скільки хочете, <<endl не рахуємо.

У цьому випадку забагато констант цілих 8 буде.

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

300 Востаннє редагувалося ReAl (19.07.2018 20:32:52)

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

leofun01 написав:

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

Все ж таки не втримався.
На базових бітових операціях робиться напівсуматор, а для інкрементора навіть повний суматор непотрібен, досить напівсуматорів по числу бітів. Для декрементора те ж саме, тільки десь інверсію треба вставити.
Щоб не сперечатися, жменя одиниць по коду це одна константа, чи жменя — просто завів змінну one :D
Все одно вийшло в сумі 4 сутності (дві змінних і дві константи, якщо не рахувати тих, що у коментарі ;) )
Друк довільної кількості чисел до 256 включно (від 255 до 0).
Для 15 можна викинути частину рядків, для 65535 додати :)

#include <stdio.h>
#include <stdint.h>

int main()
{
    uint8_t one = 1;
    uint8_t i = 15; // 0 для чисел від 255 до 0
    do {
        i ^= one
            | (~i & one) << one
            | (~i & (~i & one) << one) << one
            | (~i & (~i & (~i & one) << one) << one) << one
            | (~i & (~i & (~i & (~i & one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one) << one
            | (~i & (~i & (~i & (~i & (~i & (~i & (~i & one) << one) << one) << one) << one) << one) << one) << one
            ;
        printf("%d\n", i);
    } while (i);

    return i;
}

ліньки думати, як переписати красивіше, бо починав як для інкрементора, але тоді треба починати з
i = one - one;
і йти вгору, тоді константу «до якого числа» треба писати в умову циклу і щоб дійти до 255 потрібно брати змінні більшої за 8 розрядності, а це перевитрата бітів :-)

Подякували: leofun01, NaharD, /KIT\, Yola, 221VOLT5