241

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

0x9111A написав:
Arete написав:

Задачка. Якщо Пінокіо скаже "Зараз в мене виросте ніс." що відбудеться?

Ну хз

Гадаю він у нього мав би таки вирости, бо ніхто не може зазирати в майбутнє, тому він збрехав, про те, що знає, що відбудеться.

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

242

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

Ну після цього він може сказати любу неправду і ніс таки виросте.

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

243

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

Vo_Vik написав:

Ну після цього він може сказати любу неправду і ніс таки виросте.

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

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

244

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

Ніс виросте одразу після того, як «зараз» мине.

245

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

Доречі в казці було сказано, що коли він бреше, то в нього росте ніс, але не було зворотньої умови. Може в нього ніс росте також коли він бачить Мальвіну.

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

246

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

Ще одне: ніс росте, коли Пінокіо свідомо бреше, але нічого не сказано про випадок, коли він помиляється.

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

247

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

P.Y. написав:

Ніс виросте одразу після того, як «зараз» мине.

Я схильний проеціонувати час на вісь дійсних чисел, тому між будь-якими двома значеннями завжди нескінченна і незліченна кількість значень. Тобто немає двох послідовних значень як у цілих, наприклад.

248

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

Yola написав:
P.Y. написав:

Ніс виросте одразу після того, як «зараз» мине.

Я схильний проеціонувати час на вісь дійсних чисел, тому між будь-якими двома значеннями завжди нескінченна і незліченна кількість значень. Тобто немає двох послідовних значень як у цілих, наприклад.

Ну але ж має бути  діапазон значень часу, що відповідають поняттю «зараз», сказаному в певний момент часу (напр., через місяць — це вже не зараз).

З іншого боку, «зараз» триває в будь-яку поточну мить, тому, якщо прийняти таке визначення, кінець «зараз» не настане ніколи — а отже, й момент, коли можна визначити, збрехав Пінокіо чи ні.

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

249

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

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Алгоритм розв'язання під спойлером, тому спершу спробуйте подумати самі:

"спробуйте подумати ще"

Якщо взяти цей же масив:
3 1 4 6 5
і пронумерувати і додати ще один номер (одне число відсутнє):
1 2 3 4 5 6
то видно, що елементи і їхні номери відрізняються якраз відсутнім числом. Отже, якщо від суми номерів відняти суму елементів з верхнього масиву, отримаємо відсутнє число.

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

250

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

ну таке вийшло.

#! python3

data = [int(i) for i in input().split()]
len_data, mn, mx = len(data), min(data), max(data)
if mx - len_data == mn:
    print(*[i for i in range(mn + 1, mx) if i not in data])
else:
    print(mn - 1 if mn + len_data != mx else mx + 1)

зараз гляну під спойлер....

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

251

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

ping написав:

ну таке вийшло.

#! python3

data = [int(i) for i in input().split()]
len_data, mn, mx = len(data), min(data), max(data)
if mx - len_data == mn:
    print(*[i for i in range(mn + 1, mx) if i not in data])
else:
    print(mn - 1 if mn + len_data != mx else mx + 1)

зараз гляну під спойлер....

Ну, у вас data - це вже масив :)

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

252

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

Master_Sergius написав:

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Алгоритм розв'язання під спойлером, тому спершу спробуйте подумати самі:

"спробуйте подумати ще"

Якщо взяти цей же масив:
3 1 4 6 5
і пронумерувати і додати ще один номер (одне число відсутнє):
1 2 3 4 5 6
то видно, що елементи і їхні номери відрізняються якраз відсутнім числом. Отже, якщо від суми номерів відняти суму елементів з верхнього масиву, отримаємо відсутнє число.

ну і як алгоритм працюватиме, якщо масив починається  з довільного числа, а не з 1?

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

253

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

Master_Sergius написав:
ping написав:

ну таке вийшло.

#! python3

data = [int(i) for i in input().split()]
len_data, mn, mx = len(data), min(data), max(data)
if mx - len_data == mn:
    print(*[i for i in range(mn + 1, mx) if i not in data])
else:
    print(mn - 1 if mn + len_data != mx else mx + 1)

зараз гляну під спойлер....

Ну, у вас data - це вже масив :)

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

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

254

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

Master_Sergius написав:

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Наступний рівень
Та сама ситуація, але немає двох чисел
"Найкраще" рішення працює за лінійний час і з константною пам’яттю

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

255

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

0x9111A написав:
Master_Sergius написав:

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Наступний рівень
Та сама ситуація, але немає двох чисел
"Найкраще" рішення працює за лінійний час і з константною пам’яттю

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

1. Від суми всіх натуральних чисел від 1 до n віднімаємо суму всіх наявних чисел, отримуємо суму двох відсутніх.
2. Добуток всіх натуральних чисел ділимо на добуток наявних чисел, отримуємо добуток відсутніх.
3. Отримуємо систему x + y = a; x*y = b; розв'язуємо її, отримуємо x та y

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

256

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

0x9111A написав:
Master_Sergius написав:

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Наступний рівень
Та сама ситуація, але немає двох чисел
"Найкраще" рішення працює за лінійний час і з константною пам’яттю

А два рази пройтись по вхідним даним можна? Це буде 2N, тобто лінійний час. Бо більше не бачу варіантів :)

Подякували: koala, 221VOLT2

257

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

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

1. Від суми всіх натуральних чисел від 1 до n віднімаємо суму всіх наявних чисел, отримуємо суму двох відсутніх.
2. Добуток всіх натуральних чисел ділимо на добуток наявних чисел, отримуємо добуток відсутніх.
3. Отримуємо систему x + y = a; x*y = b; розв'язуємо її, отримуємо x та y

Хороше рішення, але продовжуємо боротьбу (є краще рішення)

Без довгої арифметики, факторіал дуже швидко переповнить стандартний тип

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

258

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

Master_Sergius написав:

А два рази пройтись по вхідним даним можна? Це буде 2N, тобто лінійний час. Бо більше не бачу варіантів :)

Можна чого ж ні, але що робити ті два рази?
Хешувати не підходить бо пам’ять не константна

259

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

Не втримався і погуглив :)
Але все одно цікаво чи ті операції не будуть важчі за два проходи (хоча все залежить від довжини масиву). Однак, задача цікава, дійсно.

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

260

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

Master_Sergius написав:

Не втримався і погуглив :)
Але все одно цікаво чи ті операції не будуть важчі за два проходи (хоча все залежить від довжини масиву). Однак, задача цікава, дійсно.

Мені здається, що ми ймовірно знаємо різні рішення  :)
Це ви про які операції?

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