[ > ]
[ < ] /sg/ - steins;gate  [Каталог]        [Главная] [Фрейм] [Однопоток] [FAQ] [Борды] [Настройки] [Поиск]
Перейти:
Поиск:

[Назад] [Весь тред] [Последние 50 постов]
Ответ

Имя
Тема   (reply to 150452)
Текст
Прикрепить
Файл
Captcha image
Смайл CatHead EmoAnime RedFox BoardFaces Other
Опции     Предпросмотр поста
Пароль  (для удаления постов и файлов)
  • Поддерживаемые типы файлов: GIF, JPG, MP3, OGG, PNG, WEBM
  • Максимальный размер файла 35673 KB.
  • Максимальный размер поста 30 KB.
  • Запрещен постинг ЦП.
  • Запрещены вайп и реклама.
  • Шитпостинг не нужен. Это не /b/.
  • Обо всём остальном смотри FAQ.
  • ?????
  • El Psy Congroo.

Файл 153523411446.png — (817.16KB, 600x340) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
150452 No. 150452 Скрыть тред [ 1 ] quickreplyquickedit
Первый тред математиков и программистов-теоретиков. Здесь мы проверяем свои навыки аналитического мышления и мифической необходимой теоретической базы, оставляем интересные задачи или задачи, с которыми не справились, возможно, учим новое. Курису явно предпочитает эксперименты, а общество — полезную практику, однако здесь у всех есть свобода заниматься абстрактными и малополезными вещами. Просьба писать по теме.
33 Постов пропущено. Показаны последние 50.
No. 151084 Скрыть пост [ 35 ] quickreplyquickedit
>>151083
Сможешь организовать стек с элементом в 4 байта?

Ответы: >>151085
No. 151085 Скрыть пост [ 36 ] quickreplyquickedit
>>151084
Да, но это будет просто массив с очень неэффективными методами вставки. зато вписывающийся в пространственные ограничения. Но сложность вставки будет не хуже O(1000).

Ответы: >>151087
No. 151087 Скрыть пост [ 37 ] quickreplyquickedit
>>151085
Окей. Мне интересно. Сейчас писать не советую, потому что я смогу прочитать только утром. У меня у самого есть идея, я ей поделюсь завтра.

Ответы: >>151088
No. 151088 Скрыть пост [ 38 ] quickreplyquickedit
>>151087
Так тут писать даже нечего.
есть
int stack[100000] = {-1};


у нас есть индекс последнего элемента (изначально это 0)
если при PUSH A B у нас A == 1, то просто stack[index++] = B

если A > 1, сдвигаем все элементы вправо начиная с index — A и по index, а затем stack[index — A] = B

С POP A всё понятно. Но наверное это будет слишком медленно, раз, судя по всему, ты не воспринял это как верное решение сразу?

Ответы: >>151094, >>151095
No. 151094 Скрыть пост [ 39 ] quickreplyquickedit
>>151088
>С POP A всё понятно.
Вот как раз с POP A ничего не понятно. Если ты добавил элемент в index-4, а потом в index-2, то первый добавленный элемент будет уже в index-5. А если сначала в index-4, а потом в index-6, то первый элемент останется в index-4. Поэтому ты и не знаешь, где последний элемент одного из стеков находится. К тому же, эта программа не сможет обработать два последовательных запроса POP на один и тот же стек.

СПОЙЛЕР
Моя идея такая: в один массив всех элементов пихаю структуру из числа и индекса предыдущего элемента стека. Ну и ещё держу массив индексов последних элементов стеков. Получается 1000 связных списков, сваленных в один массив. Но суть в том, что для того, чтобы хранить число от 0 до 10^9, нужен минимум 30 бит памяти, а чтобы хранить индекс (от 0 до 100000) требуется минимум 17 бит. Поэтому для числа я завожу в структуре unsigned int, а для индекса предыдущего — short int, но при этом, 17-ый бит индекса храню в 31-ом бите числа, а в самом числе 31-ый бит игнорирую. Таким образом, один элемент у меня занимает 6 байт памяти.
No. 151095 Скрыть пост [ 40 ] quickreplyquickedit
>>151079
Ну лан, срез срезов интов. Новый стек = добавляем к срезу срез. Существующий срез — ищем нужный по индексу. Аппенд = пуш, v =s[len(s)] и s = s[0:len(s)] = поп

Это самое лоу лвл которое я могу придумать, если соблюдать одну вещь — стеки в проге должны быть именно нормальными стеками, а не какими то маняврированиями или многоходовочками чтобы сохранить память.

>>151088
> сдвигаем все элементы вправо
Rip
Массово двигать элементы в срезе/массиве это плохо, очень плохо.

Ответы: >>151098
No. 151098 Скрыть пост [ 41 ] quickreplyquickedit
>>151095
Динамическая структура данных. К тому же, на эту задачу ограничение языков: только С, С++ и Pascal. На других решения может тебе не быть. Мне пришлось поменять компилятор на Visual C++, потому что g++ зажирается и отдельно инициализирует себе 100 килобайт, из-из-иа чего моё решение не проходило по памяти.

Ответы: >>151109, >>151110
No. 151109 Скрыть пост [ 42 ] quickreplyquickedit
>>151098
Моё решение не сработало. Я пытался выделить на элемент в структуре 48 бит (6 байт), но это слишком неоптимально. Нужно ровно 47. Сейчас думаю, как бы это организовать.
No. 151110 Скрыть пост [ 43 ] quickreplyquickedit
>>151098
вот поетому я и говорю, давайте нормальные хоть скольк-т реалистичные задачки, байтоебство на 100кб или ограничение в 750кб это нереалистично в 95% случаев, заказчику дешевле планку или диск купить, чем платить гребцам, чтобы они тужились над такими вещами или тратили время на переключение блядь компилятора ради 100кб

кароч я понял что мне надо чет самому делоть, так сказатб

есть сервак, который в каждый момент времени может обрабатывать 1 мемес, или не обрабатывать мем вообще

есть школьники, которые срут на сервак мемчики (тоесть заявки, если научно так сказать), и серваку нужно мемы обработать

обработка мема = загрузка сервака на 100% на какое-то время, которое называется временем обслуживания заявки.

заявки скидываются в 1 очередь с дисциплиной fifo

входной поток заявок пуассоновский с интенсивностью λ, поток обслуживания тоже пуассоновский с интенсивностью μ. потоки стационарны, т.е. те 2 интенсивности не меняются (что конечно же нереалистично но неважно)

ваша задача — имитационно смоделить такую штуку и найти коеф.загрузки такой системы, среднюю длинну очереди, среднее время нахождения в системе (ожидание+обслуживание), вероятность того что на момент прихода мемеса в очереди будет n задач

имитационно = время дискретная величина, есть квант

по научному так скозатб эта штука(тоесть система) по классификации кендалла М/М/1

это очень существенно упрощенная 1-я лаба из предмета в шараге, так ее закодить просто
чуть сложнее = серваков может быть несколько, больше 1-го, тогда они берут из общей очереди
сделать несколько дисциплин, не только fifo/lifo
поток обслуживания может быть не пуассоновским

>ты хочешь чтобы мы делали за тебя лабы
да
нет, я её уже давно сдал

>нипрактична
нет, очень даже практична, и не только в ит

>имитационное моделирование говно говна
нет, юзается когда моделить дорого/долго
если хочешь не имитационное, каждый сервак = тред, система многопоточная, слушоешь по порту, с другой проги шлешь заявки, так даже интереснее будет, кек

Ответы: >>151124
No. 151111 Скрыть пост [ 44 ] quickreplyquickedit
Как поменять количество бит в байте?
No. 151123 Скрыть пост [ 46 ] quickreplyquickedit
Спасибо. Вопрос снят.
No. 151124 Скрыть пост [ 47 ] quickreplyquickedit
>>151110
>750кб это нереалистично в 95% случаев
А если запросов не сто тысяч, а несколько миллиардов? И тогда 750кб плавно перерастают в 10-15гб. А это уже вполне реальные ограничения. Я думаю, что эта задача практична хотя бы потому что сейчас идёт эпоха BigData и поэтому работать с ограниченными ресурсами приходится нередко.
No. 151141 Скрыть пост [ 48 ] quickreplyquickedit
Так её надо как решить? Смоделировать какое-то большое количество запросов или теми формулами всё? Если формулами, то это довольно скучно получается. А если моделировать, я смогу даже не один сервер реализовать, а сеть.

Ответы: >>151152
No. 151152 Скрыть пост [ 49 ] quickreplyquickedit
>>151141
Имитационно моделировать конечно же, я там так и написал.
Да, заявки офк, тысячу-две, но это неважно в принципе.
Формулы для понимания ситуации и ответов на вопросы, ну и для распределений конечно же.

Ответы: >>151154
No. 151154 Скрыть пост [ 50 ] quickreplyquickedit
>>151152
Кстати говоря, "практические твои значения с формулами должны совпадать

Ответы: >>151157
No. 151157 Скрыть пост [ 51 ] quickreplyquickedit
>>151154
А если я скажу, что запрос всегда идёт в самый быстрый доступный свободный сервер, это будет оптимально?

Ответы: >>151161
No. 151161 Скрыть пост [ 52 ] quickreplyquickedit
>>151157
в задаче интенсивность потока обслуживания на всех серверах одинаковая, поэтому если несколько серваков свободны, то заявку обслуживает рандомный, не имеет значения какой.
No. 151167 Скрыть пост [ 53 ] quickreplyquickedit
Короче, что-то сделяль.
https://ideone.com/zw49Sm

Порядок ввода таков: количество серверов, скорость выхода запросов, скорости обработки одного запроса серверами, дальше идут m-1 строк, на i-той список серверов, в которые запрос может попасть из сервера i. M-тый сервер замыкающий. На последней строке количество запросов. Я не уверен в правильности решения, но и проверять не на чем.

Ответы: >>151168
No. 151168 Скрыть пост [ 54 ] quickreplyquickedit
>>151167
Больше ничего не сделаю, потому что в этой теме не разбираюсь.
No. 151170 Скрыть пост [ 55 ] quickreplyquickedit
>>151052
Так вот. Я под катом оставлю решение.

РазвернутьПросто рандомно буквы выводите

No. 151584 Скрыть пост [ 56 ] quickreplyquickedit
Ребят, привет. Такая вам задача:

Есть 2 <= n <= 100000 отрезков, i-тый начинается в x_i и заканчивается в y_i. Как минимум n-1 из них имеют общую точку (может быть, и не одну). Выбрать из этих n отрезков n-1 так, чтобы их общая часть имела максимальную длину.

Если задача для вас слишком простая, скажите. Я стану кидать сложнее, мне не трудно.

Если скучная — скиньте задачу, которую считаете интересной.

Ответы: >>151594, >>151596, >>152163, >>154099
No. 151594 Скрыть пост [ 57 ] quickreplyquickedit
Файл 153597100387.jpg — (25.25KB, 400x400) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
151594
>>151584
>Ребят, привет.
Привет, внучок!
No. 151596 Скрыть пост [ 58 ] quickreplyquickedit
>>151584
Все отрезки лежат на одной прямой?

Ответы: >>151600
No. 151600 Скрыть пост [ 59 ] quickreplyquickedit
>>151596
Да
No. 152163 Скрыть пост [ 60 ] quickreplyquickedit
>>151584
Секунду, нам нужно выбрать n-1 отрезков из n. И известно что n-1 из n имеет общую точку. Но разве это не значит что мы должны тупо взять все отрезки кроме одного единственного который не имеет никаких общих точек? И из этих n-1 общая длина и будет максимальной среди n-1

Ответы: >>152245
No. 152245 Скрыть пост [ 61 ] quickreplyquickedit
>>152163
Последний может иметь общие точки. Но не со всеми. Нужно его быстро найти.
No. 153798 Скрыть пост [ 62 ] quickreplyquickedit
Ещё одна задачка: у вас на доске написан набор чисел. Они могут быть отрицательными и неотрицательными. Дальше идёт такая игра: за одно действие вы можете стереть любые два числа на доске и написать на той же доске их произведение. Также можно в любой момент просто стереть одно число, но не более одного раза. В любом случае, в какой-то момент на доске останется одно число. Нужно его максимизировать. Опишите свой алгоритм действий.

Если хотите, объясню решение последней задачи.
No. 154099 Скрыть пост [ 63 ] quickreplyquickedit
>>151584
вот в общем.
https://pastebin.com/t0tFnArf
на питоне потому что для мелких вещей проще.

Ответы: >>154150
No. 154150 Скрыть пост [ 64 ] quickreplyquickedit
>>154099
Опиши значение переменных, пожалуйста.

Ответы: >>154152
No. 154152 Скрыть пост [ 65 ] quickreplyquickedit
>>154150
solution возвращает индекс отрезка, у которого количество отрезков с общими с ним точками меньше чем n — 1
target и otherTarget — потенциальные кандидаты
common — текущее значение общей части

Ответы: >>154157
No. 154157 Скрыть пост [ 66 ] quickreplyquickedit
>>154152
Жадное решение, но вполне вероятно, что сработает. У меня было другое. Тип p[i] — общий отрезок отрезков от 0-го до i-того, а s[i] — от i-того до последнего. Короче, для каждой i мы проверяем общие точки p[i-1] и s[i+1], то есть как бы проверяем отрезок, если из него выкинуть i-тый. Но если понять, что у «лишнего» максимальный a_i или минимальный b_i, задача становится ещё проще.

Ответы: >>154161
No. 154161 Скрыть пост [ 67 ] quickreplyquickedit
>>154157
вроде должно сработать, ответы полностью совпадают с реализацией в лоб тупым и надежным перебором O(n^2).
100000 отрезков проходит за 0.2 секунды, хотя я не знаю какие ограничения, они не уточнялись.

понятно.

Ответы: >>154179
No. 154179 Скрыть пост [ 68 ] quickreplyquickedit
>>154161
Вообще, когда линейный алгоритм работает с такой скоростью, это печально. 500000 уже едва пройдёт в таймлимит. Учитывая, что разработчики могут линейному алгоритму и 10 миллионов скармливать, получается не по-олимпиадному как-то. Очень медленный язык. Поэтому когда на таких тяжеловесных задачах стоит длинная арифметика, я плачу кровью, потому что джаву я не учил, а в крестах её нет.

Ответы: >>154180
No. 154180 Скрыть пост [ 69 ] quickreplyquickedit
>>154179
не понял, проблема в языке или самом алгоритме. или и там и там.

Ответы: >>154184
No. 154184 Скрыть пост [ 70 ] quickreplyquickedit
>>154180
Алгоритм нормальный, язык плохой.

Ответы: >>154195
No. 154195 Скрыть пост [ 71 ] quickreplyquickedit
>>154184
ну питон всё же не очень предназначен для суперскоростных олимпиадных штук, увы.
No. 155892 Скрыть пост [ 72 ] quickreplyquickedit
Файл 153892610674.jpg — (131.96KB, 865x516) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
155892
Вот вам классика:

Ответы: >>155893
No. 155893 Скрыть пост [ 73 ] quickreplyquickedit
>>155892
Как бы вы её решили? Желательно за O(n).

Ответы: >>155895, >>155896
No. 155895 Скрыть пост [ 74 ] quickreplyquickedit
>>155893
Второй левел — решить эту задачу в двумерном варианте.
No. 155896 Скрыть пост [ 75 ] quickreplyquickedit
Файл 15389265373.png — (5.20MB, 2048x2048) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
155896
>>155893
никак, сосу, у тебя ничего по проще нет, 2+2 = ? или типа того ?

Ответы: >>155898
No. 155898 Скрыть пост [ 76 ] quickreplyquickedit
>>155896
Каков шанс того, что при броске двадцатигранного кубика выпадет число, которое делится на 3?
No. 158898 Скрыть пост [ 77 ] quickreplyquickedit
Есть ли вообще смысл поддерживать этот тред? Не хотелось бы на него забивать, но и распинаться перед стеной тоже не хочется.

Ответы: >>158939
No. 158939 Скрыть пост [ 78 ] quickreplyquickedit
>>158898
Нет смысла говорить со стенкой, но и удалять/убивать тред смысла нет. Пости задачи, которые считаешь интересными, если кому-то из нас будет интересно, начнется дискуссия, как начиналась и тогда.
Хотя сделаю небольшую ремарочку на то, что сейчас учебный год, а, значит, у некоторых посетителей треда времени и желания думать может быть меньше, это уж так сложилось, ничего не поделаешь.
No. 162420 Скрыть пост [ 79 ] quickreplyquickedit
Вот теперь такая задача: у вас есть город, который можно представить в виде таблицы NxM, каждая ячейка таблицы — жилой дом. У каждого дома есть стоимость — целочисленное значение, чем дом дороже, тем больше это число. Нужно этот город поделить на К районов так, чтобы границы каждого района можно было представить в виде одной неразрывной фигуры если слишком непонятно, то, короче, чтобы из любого дома в районе можно было перейти в любой другой в том же районе, не выходя из этого района. Но чтобы избавиться от внутрирайонного неравенства, было решено ввести для каждого района уровень неравенства: стоимость самого дорогого здания в районе вычесть стоимость самого дешёвого здания в районе. Требуется разделить город на районы так, чтобы наибольший уровень неравенства из всех районов был как можно меньше.

Примечание: эта задача не решается каким-то быстрым 100% методом, поэтому приветствуются эвристические подходы.

Ответы: >>162458
No. 162458 Скрыть пост [ 80 ] quickreplyquickedit
>>162420
сначала делим город на районы по числу домов, т.е. один район — один дом. потом на каждом шаге объединяем два соседних района в городе по принципу наименьшего роста самого большого неравенства до тех пор, пока районов не станет K. по сути задача на объединение соседних вершин графа с наименьшим весом ребра, где веса рёбер пересчитываются после каждого объединения.
хз насколько оптимальным будет результат, и как лучше выбирать из альтернативных шагов с одинаковым значением роста неравенства, дальше думать лень

Ответы: >>162461
No. 162461 Скрыть пост [ 81 ] quickreplyquickedit
>>162458
Алгоритм Крускала, значит? Тоже о нём думал. Хороший, но пересчитывать рёбра долго. Ещё могут быть случаи, когда район берёт «в кольцо» дом, который ну никак не подходит. Но это пока лучший вариант, как по мне.
No. 162464 Скрыть пост [ 82 ] quickreplyquickedit
Можно добавить алгоритм «высвобождения» здания из кольца, где ты соединяешь каким-то путём этот проблемный дом с областью, куда он подходит лучше. Могут юыьб проблемы территориальные. Думал ещё над таким решением, чтобы сначала разделить город на прямоугольники площадь примерно n/k(округлять в меньшую), а потом оставшиеся распределять по областям примерно оптимальным алгоритмом и параллельно разбивать области на змейки длиной n/k, но там нужен +/- хороший алгоритм поиска нужного пути (и быстрый). При пересечении худший вариант разбивать на две части как в змейке. Два разных решения в итоге сравнить и вывести лучший. Вообще, когда есть запас времени, стоит решать такие задачи несколькими противоположными алгоритмами.
No. 162976 Скрыть пост [ 83 ] quickreplyquickedit
Вот вам задачи трёх разных уровней.

Высокий: Есть у вас N двумерных коробок (N <= 200000). Для каждого известна длина и ширина. Коробки можно поворачивать на 90 градусов (менять местами высоту и ширину) и ставить друг на друга. Нужно таким образом выстроить башню из всех коробок так, чтобы высота была максимальной. Но для того, чтобы башня не упала, должно выполняться условие, что ширина каждой коробки должна быть строго больше ширины всех коробок, которые находятся над ней. Гарантируется, что башню выстроить получится.

Средняя: У тебя есть n (<= 10^9) монеток, одна из них — фальшивая. Есть весы, которыми можно взвесить две горсти монет, но они сломаны: каждый раз, когда вес двух горстей неравенства, стрелка отклоняется в случайную сторону. Тебе даётся M (<= 10^9) взвешиваний. После того, как попытки кончатся, вам придётся выбирать монетку наугад. Какая наибольшая вероятность угадать фальшивую монетку, учитывая, что ситуация будет оборачиватьсч всегда не в вашу пользу. Пример: у вас 3 монеты и 1 взвешивание. Мы берём случайные две и взвешиваем. Если веса равны, то оставшаяся монета фальшивая, но так как ситуация всегда против нас, веса будут неравны. Тогда мы сможем взять одну из двух монет и с вероятностью 0.5 она окажется фальшивой. Итого, ответ — 0.5.

Низкая: На научной конференции вы представляете новый язык программирования и решили доказать, что сложение строк в нём коммутативно. Но так как вы прекрасно понимаете, что сложение двух строк — операция некоммутативная, вам для примера придётся специально подобрать две строки a и b, состоящие из заглавных букв латинского алфавита,
с длинами N и М соответственно так, чтобы выполнялось условие a+b=b+a (где + означает объединение двух строк, «ab»+«cd» = «abcd»). При этом, вы знаете ещё одно слабое место своего нового языка: вы имеете на бумажке две строки s и t с длинами N и M соответственно и знаете, что если в строке a в какой-либо позиции i стоит символ s[i] и/или в строке b в какой-либо позиции j стоит символ t[j], ваша программа выдаст фатальную ошибку деления на ноль. Ваше задание: зная N, M, s и t выведите строки a и b или же выведите «-1», если таких строк не существует.
(1 <= N, M <= 100000).

Могу подсказать, если что. Удачи.
No. 168845 Скрыть пост [ 84 ] quickreplyquickedit
Файл 154691488481.jpg — (8.61KB, 175x288) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
168845
Хочу рассказать немного о сайте codechef.com
Когда-то там были интересные задачи, длинные 10-тидневные контесты, над которыми приходилось поломать голову. Но сейчас, когда очередной контест написали индусы (которые являются основной аудиторией таких сайтов), я просмотрел типичные индские сборы иибудто паззлы в моей голов сложились в одну картину. О мастерстве индусов-программистов можно говорить долго, но сейчас я увидел, на каких задачах растут спортивные программисты в Индии.
У них абсолютно отсутствуют многие базовые подходы к решению задач. Из шести задач на индском соревновании ни одна не является на какой-либо алгоритм или оптимизационную идею. Лишь конструктив и чистая математика школьного уровня. Задача на конструктив — это, по факту, задача уровня «раскрасьте клетчатую доску в минимальное количество цветов так, чтобы никакие клетки не имели одинаковый цвет, если у них есть общая клетка-сосед». Это не задача на раскраску графа и не динамика. Ты просто сидишь и подбираешь узор, а потом ищешь частные случаи. Второй их любимый тип задач — это чистой воды математика, т.е. когда ты решаешь задачу на листочке, а потом в код выписываешь одну формулу и расписываешь к тому ряд исключений. Их высший пилотаж — соединение двух тяжеловесных структур данных (а потом постоянно ограничения меняют, потому что, оказывается, люди не только на С++ пишут) вкупе с чем-то из области университетской дискретной математики. Опять же, никакой уникальной задумки. Пустая зубрёжка. О качестве и однозначности поставленных условий и регулярных изменениях в этих условиях со словами «we changed ... in our problem .. due to ... Problems were rejudged, time was added. Sorry for inconvenience!» я молчу. Я понимаю, они начинают, развиваются, все дела, но хуже всего то, что, сидя на таких сборах и на сайтах вроде codechef.com, они считают это нормой и, получив ранг кандидата в мастера или мастера, думают, что преуспели, хотя те же кандидаты и мастера из сайта codeforces.com в соревновании не дадут им шанса. Слышал, они это называют Indian School, особенностью их школы программирования вроде геометрии в России, кододрочерства в Китае и идейности и рандомизаций головного мозга в Польше. Конструктив — их достояние. Только недалеко он их заводит, как шутили над ними, так и шутят. А перебор решений в голове — удел мартышек, если вы спросите моё мнение. Вот так. Вот вам и индийская школа.
 ●  Причина:
Пароль: []