ОП того треда. Увидишь, обязательно реализуй. Так 1. быстрее дойдет 2. поможет в развитии
А ну и да. Алгоритм заточен на шестизначные числа. Можно и универсализировать, но в данном примере будет выполнено на несколько операций больше. Поэтому сделал разбор поразрядно с заданной длиной
нахуй ненужная хуйня
Т.е. вы хотите сказать, что я зря это высрал, и тому опу оно не надо?
Пункт первый
в условиях указано, что ближайшее к 265680 это 265706, что в корне неправильно, так как между 680 и 706 - 26 чисел, а между 680 и 670 - 10 чисел, и ближайшее к 265680 будет 265670
это собственно раз, а теперь пунк два, сейчас я пойду с работы домой и если вы дауны не проебете тред, я приду и покажу как эта задача решается в пару строчек.
Там в примерах к условию ошибка, да, я тож видел.
Не думаю, что ты напишешь что-то быстрее моего решения. Можем даже проверить, не поленюсь его закодить. Че там? Джава пойдет. Сейчас накидаю
бамп
bump
не утонуть
>Очевидно, что решать в лоб это - проебать. (т.к. написать циклик перебора можно и в 7м классе)
Интересно было бы посмотреть насколько это быстрее перебора, имею в виду, разумеется, он быстрее, просто если там какая-то ничтожная разница, которой можно пренебречь, то толку такое из себя высирать. Я понимаю, что задача олимпиадная и здесь смысл не в том, чтобы сделать эффективно, а чтобы выебнуться, но всё же, просто интересно.
Через признак делимости на 11 я бы попробовал намутить. Первую половину ставлю на чётные позиции, вторую половину ставлю на нечётные. Но перебор проще, если нет других требований то чё мозг парить. Мб он даже быстрее получится.
Доберусь, напишу для сравнения тебе и перебор
Да не надо, алгоритм-то мне не нужен, к тому же там более-менее всё понятно, мне интересна скорость выполнения на одинаковой машине. Вот если оба напишешь в виде кода и прогонишь у себя — тогда сбрось время выполнения, если тред не утонет, будет здорово на это всё посмотреть.
Да. Но не успею перед серфингом. Через часа 4 замучу, если тред не утонет
Падажжи ебана.
[code]
switch (input) {
case 398083:
return 398299;
case 265680:
return 265706;
// ...3 other cases
default: // never happens
throw new RuntimeException();
}
[/code]
это были примеры для проверок
Нихуя не поняла.
В общем, если вы таки утопите тред за 4 часа, я пересоздам новый по возвращение.
https://arhivach.ng/thread/497299/
https://arhivach.ng/thread/497299/
Не топим, СТОИМ!!!
пук
Вот вам питоний цикл # убрать
n=int(input())
a, b=n, n
def check(n):
# s=str(n)
# return int(s[0])+int(s[1])+int(s[2])==int(s[3])+int(s[4])+int(s[5])
while a>0 and !check(a):
# a-=1
while b<1000000 and !check(b):
# b+=1
print(min(a, b))
n=int(input())
a, b=n, n
def check(n):
# s=str(n)
# return int(s[0])+int(s[1])+int(s[2])==int(s[3])+int(s[4])+int(s[5])
while a>0 and !check(a):
# a-=1
while b<1000000 and !check(b):
# b+=1
print(min(a, b))
Хорошо. НЕ ТОНЕМ.
Экипаж подводной лодки готов к погружению.
Q
Давайте прикинем частоту счастливых чисел.
Сумма трёх цифр >=0 и <=27.
Число 1 можно представить 3 способами (100,010,001)
2 - 3+3=6 способов
3 - 4+6*...
55252 если нигде не ошибся.
т.е. чуть больше 1/20=5%
Если допустить что они распределены равномерно что, очевидно, не так, то среди любой 20-ки мы найдем хотя бы одно сч в интервале [0; 1000] их нет из чего следует что линейного алгоритма более чем достаточно.
К слову, пробег по всей окрестности на питоне занял 33 сек что довольно много
А тут есть ошибки
б
Так чё там?
Вы че на говне каком-то пилите, раз взялись, то пилите на чем-то нормальном, на том же С++, например
Не начинай.
Да блять, чего не начинай то, это уже какой тред? Второй? Потому самый первый я видел часов 5 назад. И до сих пор не разрешили, хайв, блять, майнд. Дайти посмияцца то
Прочел таки текст задачки, вы серьезно так долго с этим ябётесь?
ОП ты тут?
Кто-нибудь возьмётся?
Расскажи мне, как вы за столько времени так и не пришли к какому-то результату?
В оп треде что-то есть
и мой питон
А сажу бросил случайно
Я вернулся с серфинга. Ща все запилю вам
/hc
\гороскоп
Сегодня звезды встали таким образом, что ты можешь получить по глазам. Однако, есть риск напихать от себя. Поэтому Двач напоминает тебе, братишка: все продается.
Сегодня звезды встали таким образом, что ты можешь получить по глазам. Однако, есть риск напихать от себя. Поэтому Двач напоминает тебе, братишка: все продается.
Что, блядь, ты несёшь?
На пхп это решается в лоб:
1 сторока: Берём это число, как стринг и превращаем в массив цифр.
2 строка: Делим массив на две части.
3 строка. Сравниваем сумму элементов этих двух массивов. если равны - решение найдено. Если нет, то смыть, повторить.
Можно, конечно, изъебнуться и проверить какой массив больше и скольько в меньшем не хватает, а потом высчитать результат, но нахуй и в пизду. Я сэкономлю две минуты своего времени на набивание кода, и пусть машина считает на 5 микросекунд дольше.
Лол. Я и пишу, что с такими ебобо подходами нахуй можешь проследовать
Мой подход быстро решает нужную задачу. Это раз. И решает её правильно, нет места ошибкам, опискам, неправильным алгоритмам. Это два. Мой код точно будет работать. А это и нужно работодателю рабочий код, который можно продать клиенту. Из денег клиента строится и моя зарплата. Всем насрать на алгоритмы, паттерны, хуятерны. Бизнесу нужно решение практических задач.
>>Всем насрать на алгоритмы,
Спешите видеть: макака в треде!
свежее говно стайлиш мен
да ты прав
A нy и дa. Aлгopитм зaтoчен нa шестизнaчные числa. Мoжнo и yнивеpсaлизиpoвaть, нo в дaннoм пpимеpе бyдет выпoлненo нa нескoлькo oпеpaций бoльше. Пoэтoмy сделaл paзбop пopaзpяднo с зaдaннoй длинoй
У втopaя бaлдeжнaя, кaк жe я в нee зaдpaчивaл
Почемy двачеpы так не любят Пyтина? Pазве не пpи нем битаpдам живется лyчше всего
>признак делимости на 11
>быстрее получится
Деление вообще достаточно дорогой опкод процессора. Цена не только в скорости самого опкода (хотя деление в несколько раз медленнее умножения), а ещё и в занимаемых регистрах (для результата нужно два (частное и остаток), а делитель и делимое тоже загрузить как-то надо). gcc, ЕМНИП, в делении небольших чисел часто заменяет опкод деления на другой набор опкодов (например, на умножение с последующим шифтом битов) для оптимизации скорости. Но если сам компилятор языка не умеет переменные по регистрам раскладывать, а альтернатива требует простыню кода, то это не так и дорого будет, хоть и в оптимизированных алгоритмах деление стараются не использовать.
мимобайтоеб
Не тонем, ведь скоро результат.
ебаааать ПОШУТИЛ ИНТЕЛЛЕКТУАЛЬНО , мне чо теперь ПОХЛОПАТЬ ТЕБЕ МБ? так вот, хлопаю тебе по ебалу, кусок говна псевдоинтеллектуального
>Очевидно, что решать в лоб это - проебать.
PREMATURE OPTIMIZATION IS THE ROOT OF ALL EVIL
школьники-олимпиадники к жизни не приспособлены. Мои подчиненные обучены гнать таких пидоров ссаными тряпками с собеседований.
ентерпрайз-илита 300^10ксек
>Мой подход быстро решает нужную задачу. Это раз. И решает её правильно, нет места ошибкам, опискам, неправильным алгоритмам. Это два. Мой код точно будет работать. А это и нужно работодателю рабочий код, который можно продать клиенту. Из денег клиента строится и моя зарплата. Всем насрать на алгоритмы, паттерны, хуятерны. Бизнесу нужно решение практических задач.
Зато у тебя нет дипломчика "Вручено участнику олимпиады Нижнезалупинского компьютерного клуба за второе место". Обоссал тебя.
бамп
Схуяли это брутфорс через цикл не подходит? Наихудший там <2000 итераций всего блять, это ничтожно мало. На олимпиадные задачи обычно накладывают ограничения в 1 секунду исполнения, так что перебор самый оптимальный вариант.
fkn ez
Впрочем, решение вышло то же, что и у ОПа.
Прикол в том, что для реальных оптимизаций в разы выгоднее использовать ЯП более низкого уровня, чем пытаться переписывать на том же. Иначе все сводится к перебору конструкций синтаксиса языка в попытках найти более оптимальный набор опкодов, вместо написания этих же опкодов самому (asm, на крайняк с оберткой в C).
Лол, Ты просто прогнал тесты, которые там для примера проверки. Алгоритм должен любую ситуацию подбирать
import java.util.;
public class Main {
public static void main(String[] args) {
final int count = 10000000;
int[] values = new int[count];
Random r = new Random();
for (int i = 0; i < count; i++) {
int n = r.ints(1, (9999999 + 1)).limit(1).findFirst().getAsInt();
values = n % (int) Math.pow(10, (int) Math.log10(n));
}
System.out.println("============");
System.out.print("My solution time ms: ");
measure(new HappyTicketFinderMine(), values);
System.out.println("============");
System.out.print("Loop over time ms: ");
measure(new HappyTicketFinderLoopOver(), values);
}
private static void measure(IHappyTicketFinder finder, int[] dataset) {
long startTime = System.currentTimeMillis();
for (int value : dataset) {
finder.getNextHappyTicket(value);
}
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
interface IHappyTicketFinder {
int getNextHappyTicket(int current);
}
static class HappyTicketFinderMine implements IHappyTicketFinder {
@Override
public int getNextHappyTicket(int current) {
int[] digits = getAllDigits(current, 6);
int[] digitsFirst = Arrays.copyOfRange(digits, 3, 6);
int[] digitsSecond = Arrays.copyOfRange(digits, 0, 3);
int sumPart1 = calcSum(digitsFirst);
int sumPart2 = calcSum(digitsSecond);
if (sumPart1 == sumPart2) return current;
if (digitsSecond[2] > sumPart1) {
digitsFirst = getAllDigits(collectValue(digitsFirst) + 1, 3);
sumPart1 = calcSum(digitsFirst);
//новая первая часть[][][] и [0][0][sumPart1]
int[] ret = {sumPart1, 0, 0, digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
if (sumPart1 - digitsSecond[2] < 18) {
int needToAdd = sumPart1 - digitsSecond[2] - digitsSecond[1];
if (needToAdd <= 9) {
//ответ [x1][x2][x3][y1][y2][needToAdd]
int[] ret = {needToAdd, digitsSecond[1], digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
//ответ [x1][x2][x3][y1][needToAdd - 9][9]
int[] ret = {9, needToAdd - 9, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
}
} else {
int restTwoDigits = sumPart1 - digitsSecond[2];
if (restTwoDigits > 18) {
digitsSecond[2] = sumPart1 - 18;
}
if (restTwoDigits <= 9) {
//ответ [x1][x2][x3][y1][0][restTwoDigits]
int[] ret = {restTwoDigits, 0, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
//ответ [x1][x2][x3][y1][restTwoDigits - 9][9]
int[] ret = {9, restTwoDigits - 9, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
}
}
}
}
}
static class HappyTicketFinderLoopOver implements IHappyTicketFinder {
@Override
public int getNextHappyTicket(int current) {
int sumPart1 = 0;
int sumPart2 = 0;
int iter = current - 1;
do {
iter ++;
int[] digits = getAllDigits(iter, 6);
int[] digitsFirst = Arrays.copyOfRange(digits, 3, 6);
int[] digitsSecond = Arrays.copyOfRange(digits, 0, 3);
sumPart1 = calcSum(digitsFirst);
sumPart2 = calcSum(digitsSecond);
} while (sumPart1 != sumPart2);
return iter;
}
}
static int calcSum(int[] digits) {
return digits[0] + digits[1] + digits[2];
}
static int[] getAllDigits(int val, int cap) {
int[] digits = new int[cap];
for (int i = 0; i < cap; i++) {
digits = val % 10;
val = val / 10;
}
return digits;
}
static int collectValue(int[] digits) {
int value = 0;
int mult = 1;
for (int digit : digits) {
value += mult digit;
mult *= 10;
}
return value;
}
}
public class Main {
public static void main(String[] args) {
final int count = 10000000;
int[] values = new int[count];
Random r = new Random();
for (int i = 0; i < count; i++) {
int n = r.ints(1, (9999999 + 1)).limit(1).findFirst().getAsInt();
values = n % (int) Math.pow(10, (int) Math.log10(n));
}
System.out.println("============");
System.out.print("My solution time ms: ");
measure(new HappyTicketFinderMine(), values);
System.out.println("============");
System.out.print("Loop over time ms: ");
measure(new HappyTicketFinderLoopOver(), values);
}
private static void measure(IHappyTicketFinder finder, int[] dataset) {
long startTime = System.currentTimeMillis();
for (int value : dataset) {
finder.getNextHappyTicket(value);
}
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
interface IHappyTicketFinder {
int getNextHappyTicket(int current);
}
static class HappyTicketFinderMine implements IHappyTicketFinder {
@Override
public int getNextHappyTicket(int current) {
int[] digits = getAllDigits(current, 6);
int[] digitsFirst = Arrays.copyOfRange(digits, 3, 6);
int[] digitsSecond = Arrays.copyOfRange(digits, 0, 3);
int sumPart1 = calcSum(digitsFirst);
int sumPart2 = calcSum(digitsSecond);
if (sumPart1 == sumPart2) return current;
if (digitsSecond[2] > sumPart1) {
digitsFirst = getAllDigits(collectValue(digitsFirst) + 1, 3);
sumPart1 = calcSum(digitsFirst);
//новая первая часть[][][] и [0][0][sumPart1]
int[] ret = {sumPart1, 0, 0, digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
if (sumPart1 - digitsSecond[2] < 18) {
int needToAdd = sumPart1 - digitsSecond[2] - digitsSecond[1];
if (needToAdd <= 9) {
//ответ [x1][x2][x3][y1][y2][needToAdd]
int[] ret = {needToAdd, digitsSecond[1], digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
//ответ [x1][x2][x3][y1][needToAdd - 9][9]
int[] ret = {9, needToAdd - 9, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
}
} else {
int restTwoDigits = sumPart1 - digitsSecond[2];
if (restTwoDigits > 18) {
digitsSecond[2] = sumPart1 - 18;
}
if (restTwoDigits <= 9) {
//ответ [x1][x2][x3][y1][0][restTwoDigits]
int[] ret = {restTwoDigits, 0, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
} else {
//ответ [x1][x2][x3][y1][restTwoDigits - 9][9]
int[] ret = {9, restTwoDigits - 9, digitsSecond[2], digitsFirst[0], digitsFirst[1], digitsFirst[2]};
return collectValue(ret);
}
}
}
}
}
static class HappyTicketFinderLoopOver implements IHappyTicketFinder {
@Override
public int getNextHappyTicket(int current) {
int sumPart1 = 0;
int sumPart2 = 0;
int iter = current - 1;
do {
iter ++;
int[] digits = getAllDigits(iter, 6);
int[] digitsFirst = Arrays.copyOfRange(digits, 3, 6);
int[] digitsSecond = Arrays.copyOfRange(digits, 0, 3);
sumPart1 = calcSum(digitsFirst);
sumPart2 = calcSum(digitsSecond);
} while (sumPart1 != sumPart2);
return iter;
}
}
static int calcSum(int[] digits) {
return digits[0] + digits[1] + digits[2];
}
static int[] getAllDigits(int val, int cap) {
int[] digits = new int[cap];
for (int i = 0; i < cap; i++) {
digits = val % 10;
val = val / 10;
}
return digits;
}
static int collectValue(int[] digits) {
int value = 0;
int mult = 1;
for (int digit : digits) {
value += mult digit;
mult *= 10;
}
return value;
}
}
Итого на 10000000 повторений вывод:
============
My solution time ms: 365
============
Loop over time ms: 7372
Получаем на таком количестве увеличение производительности в 20 раз. Всем спасибо
Вот я тебе сделал:
Наркоман?
Алгоритм решает ситуацию в целом, проверяя её по кейсам из таблицы. Или, по твоему, реальные unit-тесты выглядят как:
for (i in 0..999999) {
verifyMyShit()
}
?
Не полностью вник в твое решение, но разве оно сработает, если нужно увеличить первую тройку цифр?
У нас в школе я обосрался на подобной задаче в десятом классе (2000 г.): посчитать количество счастливых билетов, не используя цикл, на Паскале.
т.e. 001999 -> 002002
Это другая задача. Там через логорифмы решается в одну строчку
Есть пример, где её вообще нужно увеличивать?
Таки да. Тут проёб.
Я потому и написал, что у них в задаче тесты не полные и их недостаточно.
Но я тоже решил ее неверно. Не дочитал. Там не обязательно инкрементировать номер билета. Он может и вниз идти, просто сказано "ближайший". Пофиг. Смысл сохраняется, переделывать не буду
Вот перебором, получается меньше секунды для ВСЕХ возможных вариантов вообще. Так что это идеальный вариант для ОЛИМПИАДНОГО программирования т.к. там не одна такая задача, а 10, и побеждает не самый оптимизированный код, а тот кто предоставит решение максимально быстро. мимо не раз был на таких соревнованиях
Благодарю.
я текстовое решение без редактора написал за 5 минут. Закодить его - 15 минут. В чем проблема? На олимпиадах не был, но, подозреваю, мое решение ебало в рот твои переборы при оценке задачи
Да и хрен с ним. Это некрасивое решение, а мы сейчас не на одимпиаде.
пошел нахуй со своим гото паттерном мудак
> гото паттерном
это что?
Уверен, что оно у тебя компайл-тайм не посчиталось или вообще оптимизировалось нахуй (away) для чисел кроме/после 228322? А то один умник уже так сравнивал скорость крестов и C# через луп, кресты в два раза проигрывали, а потом вскрыли машинный код, и оказалось, что в C# компилятор весь цикл просто удалил нахуй, а время уходило на подгрузку библиотек .NET.
это красивое решение. Оно читается мгновенно и поддерживается легко, в отличие от оповского n = k + t - s % ohuet_kak_ja_krut. как правило, эти микрооптимизаторы могут переизобрести улучшенную сортировку пузырьком, но в реальном проекте не могут согласовать пять классов. Не этим надо выебываться, молодежь.
если ты будешь писать физический движок, у которого в ядре расчет счастливых билетиков - вот тогда залупишься и будешь наздоровье на ассемблере свою хуйню аптимизировать, выигрывая фпсы.
Да, я спецом для этого и запихал все в вектор т.к. компилятор пидор просто весь цикл удалял.
>Не этим надо выебываться, молодежь.
Братишка, ты еблан.
Работаю, как раз, в энтерпрайзе с сервлетами, где все хуй клали на эти ваши оптимизации. Там реально лишь бы денех приносило и слава богу, а машин докупим.
Однако, придя домой, абсолютно нет смысла писать ответы на рафинированные задачки с настроем, мол, "шоб работало". Тут интересно именно математическое решение. Кого ебёт, что оно у тебя "просто работает"? Ты этот код продавать собрался, или всё таки для развлечения, как и я, его пишешь?
Это бумер застрял во временах, когда использовали ассембли омегалул.
Не работает для 987000 - > 986986
Рофл
Второй сверху тест из текста задачи, кажется, тоже не проходит.
А, нет, проходит, извиняюсь.
>Ты этот код продавать собрался, или всё таки для развлечения, как и я, его пишешь?
и вот скажи мне, развлекатор, тебя развлекают эти макароны на бейсике?
>Если sumPart1 - y1 < 18 , переходим к пункту 8. Иначе переходим к пункту 5.
меня нет. это тупо и некрасиво.
вот если бы кто попробовал по-крупному разменять время на память и заебошить хеш-табличку (математически подумав, не длиной в 999999, понятно) - вот это было бы забавно, я бы поаплодировал.
вы чё, ебанутые? просто берешь и хуяришь 999999 строк условия :
If x=000001 then y=001100
If x=000002 then y=001100
...
...
If x=222223 then y=222222
...
...
If x=999999 then y=999999
И всё блять, конец, работает? Работает. И похую.
>вот если бы кто попробовал по-крупному разменять время на память и заебошить хеш-табличку
>вы чё, ебанутые? просто берешь и хуяришь 999999 строк условия
хеш-табличка уровня бэ.
алсо аплодирую.
И че, это типо круто найти счастливый билет для одного числа за 0.032 милисекунды?
Вот как это происходит на языке богов.
>Вот как это происходит на языке богов.
10 PRINT "PASHOL NAHUI"
20 GOTO 10
RUN
>и вот скажи мне, развлекатор, тебя развлекают эти макароны на бейсике?
Они уже лучше чем брутфорс. Ясен хрен, это не вершина инженерной мысли, но уже более интересно чем "я просто буду дрочить счётчик, ыыы".
Наверное тебе покажется невероятным инсайтом, но все изначально знают приведённое тобой решение. И оно начинает сосать, стоит только числу из условия подрасти на несколько знаков.
Ебать вы.
1. Отнимаем сумму второй половины чисел от первой.
2. Делаем из второй половины число
3. Прибавляем сумму из пункта 1 ко второй половине
4. Готово
Серьёзно?
1. Отнимаем сумму второй половины чисел от первой.
2. Делаем из второй половины число
3. Прибавляем сумму из пункта 1 ко второй половине
4. Готово
Серьёзно?
>1. Отнимаем сумму второй половины чисел от первой.
>2. Делаем из второй половины число
>3. Прибавляем сумму из пункта 1 ко второй половине
>4. Готово
Работает только в некоторых случаях.
Не, нихуя.
Проверни это для:
1990 -> 2002
Тесты указанные проходит? Проходит ну ладно, на самом деле мне лень проверять Первую половину там не трогают, потому что любое изменение первой половины это уже нихуя не более близкое число ибо разряды первой половины больше разрядов второй по определению.
Переполнения числа которое составлено из второй части быть не может.
>И оно начинает сосать, стоит только числу из условия подрасти на несколько знаков.
Magic numbers "sumPart1 - y1 < 18" начинают не просто сосать, а принимать в жопу, стоит только числу подрасти на ОДИН знак.
Если бы задача ставилась исходно в обобщенном виде, никому и в страшном сне не пришел бы вот этот весь ad-hoc хакинг из ОП-поста. И в обобщенном виде это хоть как-то интересно было бы обсуждать. Но ОП ставит задачу "давайте оптимизировать хуйню".
>но уже более интересно
Ладно, Господь с вами. Развлекайтесь. Сдаюсь.
>Тесты указанные проходит?
Макакен, какая разница, проходит тесты или нет, если алгоритм все равно некорректный?
1+9 - (9+0) = 1
90+1 = 91
1991 ответ. Что не так?
>Ебать вы.
>1. Отнимаем сумму второй половины чисел от первой.
>2. Делаем из второй половины число
>3. Прибавляем сумму из пункта 1 ко второй половине
>4. Готово
>Серьёзно?
Вот это уже прикольненько. "Проверять я это, конечно, не буду"(с), но хотя бы полет мысли и математический геней.
gg
В твоём решении выхордит: 001990 -> 001991
0+0+1 = 1
9+9+1 = 19
Что не так сам догадаешься?
Разряды числа по 3 знака как бе, 1!=9+9+1
Я понял, я понял. Я проверил и увидел что это не сработает.
Ну ладно. Тогда ту разницу двух частей надо распределять между отдельными числами второй половины, начиная справа (то есть, с наименее значимых разрядов), проверяя чтобы мы не впёрлись в граничные условия. Наверное это и написано в ОП-посте.
Вроде живое, хоть и сложность возрасла.
В общем, хз.
Дурак что ли такой здоровый высер с одним 4-байтовым параметром инлайнить? У тебя встроенный ассемблер есть, оптимизатор хуев
Просто иди нахуй.
Доебался до хуйни. Рот твой ебал, собаку твою ебал, сестру твою у тебя на спине ебал, полоумный ты чёрт.
У этих пидоров в примерах ошибка. Второй должен быть 265670, а не 265706.
> Очевидно, что решать в лоб это - проебать. (т.к. написать циклик перебора можно и в 7м классе)
С хуя ли? В нормальных олимпиадных задач всегда пишут ограничения по времени, а здесь их нет.
Число шестизначное, его перебор не займет хоть сколь нибудь значимого времени.
Хуя макаку порвало. Чего же ты через Ctrl-C прямо туда кода не налепил, а компилятору приказал это сделать? Слов модных в доках насмотрятся и пихают их куда попало, не разобравшись в сути. Компилятор может быть и сам бы заинлайнил твои высеры, если бы в этом был смысл
Какие же двачеры тупые, пиздец просто. Решать элементарную задачу через какую-то жопу.
Слегка через жопу но вот это так делается.
Я победил. Можно наконец-то пойти покурить и спать.
Вот это красивый код со стороны байтоеба. Только простые операции (вычитание, добавление и присваивание), никаких дорогих делений. Молодец, хорошо сделал.
Я так и не пойму, тред для прикола создан или нет?
> Вот это красивый код со стороны байтоеба.
> Хранить данные в массивах
Ну-ну
Чем тебе массивы-то не угодили?
Можно отоптимизировать по памяти, сэкономив целых 12 байт, если засунуть ticket_lhs, ticket_rhs и diff в первые три элемента массива, но я уже не стал так издеваться
А где их хранить предлагаешь? Через inline assembly он явно никто не будет раскидывать по регистрам и добавлять, а возможностями языка нормально. В крестах, как и в C, массив это указатель на первый элемент, а с RAM данные брать всё равно придется, т.к. хуй там компилятор будет по регистрам это всё раскидывать. Вот по делу мог доебаться, что написано через main, а не mainCRTStartup с кастомным парсингом параметров. Тернарка тоже, например, не самая дешевая вещь, но компиляторы её гораздо лучше if оптимизируют.
Оптимизаций там ещё дофига можно сделать, если переписать весь код на ассемблер, т.к. почти любой ЯП сам по себе будет иметь настолько огромный оверхэд, что пара десятков байтов - капля в море.
Ебать вы хуиту программируете. Эта олимпиадная задача на 7кю по рейтингу codewars не тянет.
Эта строка вся влезет в 64-битный регистр, то есть тут вообще всю программу можно кое как уложить не особо трогая память кроме как чтобы один раз прочитать строку аргумента и один раз добавить туда то что нужно.
В первую очередь мог пнуть не за main а за то что юзаю iostream вообще там где один puts только и нужен
> Magic numbers "sumPart1 - y1 < 18" начинают не просто сосать, а принимать в жопу, стоит только числу подрасти на ОДИН знак.
Привет, кодировщик. Я там писал, что можно мою схему универсализировать. Это, как два пальца, и будет работать в десятки раз быстрее, чем перебор. Но в приведенном условии о 6 знаках быстрее будет работать захардкоженный алгоритм именно под 6 знаков.
ты бы не прошел мое собеседования, звыняй
>тут вообще всю программу можно кое как уложить не особо трогая память
Если бы он на ассемблере писал/знал его, тогда да. Но для крестов код достаточно оптимальный, не учитывая вышеприведенные замечания. Вот этот вариант, например гораздо хуже, как мне кажется (чуть ли не до того, что будет дешевле конвертировать в массив char'ов, а потом уже работать с ним).
>iostream вообще там где один puts только и нужен
Не разбирался с стандартной либой крестов (сишную получше знаю), так что интуитивно не заметил. Вообще тогда можно напрямую вызывать системные ядро/библиотеку, заодно и размер бинарника должен упасть в несколько раз (на Windows весь ввод/вывод в консоль через вызовы к Kernel32 делается).
Знаю я ассемблер и это ты мне отвечаешь, кстати
Думал сейчас как переписать под ассемблер, но уже голова не варит, не могу быстро придумать как conditional set/move заюзать чтобы прыжки не юзать.
iostream вообще может спровоцировать на оператор << вызов виртуальной функции, хотя я точно не скажу, может операторы под дефолтные типы невиртуальные.
printf/puts тоже есть в kernel32.dll или ntdll.dll, а писать бойлерплейт чтобы вывести в консоль два раза не особо интересно. Уверен что GetStdHandle вызывается и так при старте программы чтобы stdout работал, так что вызывать его снова не круто, круто юзать готовый puts который там зашит и так.
По памяти, я подумал, не оптимизируешь больше на плюсах: тот код что я написал позволяет компилятору ticket_[lhs/rhs] и diff поместить в регистры. Энивей, стек на нас определённого размера так и так выделен, reserved и committed даже с самого старта программы, так что я ничего не трачу, просто юзаю что у меня уже лежит под рукой.
Парсить аргументы самому... Ну, да, там универсальный алгоритм, не заточенный под конкретно два аргумента, но он, я уверен, достаточно быстр.
Да и вообще всю эту программу загрузить в память дольше чем исполнить.
Надо спать, просплю завтра всё
>ты бы не прошел мое собеседования, звыняй
Упаси господь даже просто попасть на собеседование в такое место. Это же как оголодать нужно. Может тебе и ручку продать, эйчар?
)) запах гари неосилторов и говнокодеров. приятненько
>говнокодеров
>Если sumPart1 - y1 < 18 , переходим к пункту 8. Иначе переходим к пункту 5.
не продолжай.
Мань, да как бы я переменные не назвал, твой всратый цикл хуже где-то в 40 раз. Хммм. А ведь писать 18 - это лучше, чем писать const max 9, ... < max*2, не сможешь найти мужества, чтобы это принять?
>Знаю я ассемблер и это ты мне отвечаешь, кстати
Думал, что с двумя людьми разговариваю, лол.
В чистом C чуть получше можно оптимизировать, конечно. Там хотя бы есть ключевое слово register, популярные компиляторы под винду его вроде как пытаются использовать (а gcc нет).
>Да и вообще всю эту программу загрузить в память дольше чем исполнить.
Вот из-за этого часто и возникает желание переписать на ассемблер. Подключил пару библиотек с прокладками для системных библиотек, а там уже бинарник на 50+ KB. Вот на ассемблере можно хорошие прокладочки пописать, даже если сама программа на C/++ будет.
>Надо спать, просплю завтра всё
Иди, конечно. ОПа оригинального треда вообще только решение на Delphi интересовало, как я понял, так что мы тут хуйней занимаемся.
Удачи тебе, анон! Спокойной ночи, спасибо за разговор. Рад, что ещё не всех байтоебов заменили на хипстеров-смузихлебов.
>А ведь писать 18 - это лучше, чем писать const max 9, ... < max*2
Чем лучше? Компайл-тайм ведь рассчитывается. Если там значение в нескольких местах используется, и может возникнуть необходимость его когда-либо поменять, то лучше вынести в константу же
мимодругойанон
Лол, в этом треде нет ни одного человека, знающего линейное программирование? Задача же аналитически за 5 минут решается, а вы с кодом не можете, дауны
> может возникнуть необходимость его когда-либо поменять, то лучше вынести в константу же
не может
Где-то читал что сегодня register не стоит юзать: компиляторы умнее стали, сами поймут что стоит в регистры пихать а что не стоит.
Хотя, я видел как в 32-битных программах MSVC делает регистр полный нулей чтобы обнулять другие регистры вместо того чтобы юзать xor eax, eax который процессоры давно привыкли особо обрабатывать без реального XORинга. Короче, это уже надо играться и тестировать разные возможности оптимизации. И почитать что там компилятор сейчас нагенерил.
Доброй ночи, да
> поменять
> вынести в константу
ватафак эм ай ридин?
А по сабжу, обозначим входные цифры l1, l2, l3, r1, r2, r3. Ну вы понели что они значат. Искомые цифры обозначим также, но со штрихами. Задача сводится к поиску минимума следующей функции:
100000 (l1' - l1) + 10000 (l2' - l2) + ... + (r3' - r3)
при условии:
l1' + l2' + l3' = r1' + r2' + r3'
т.е. мы получаем задачу на поиск минимума линейной функции при линейном ограничении
Как такое решать - знает каждый инженегр первокурсник
Так ты расскажи, будем знать. Я погуглил, что-то сильно математическое. Я на пальцах считаю, так что очевидно что про такую штуку я не знаю
мальца проебался с функцией для минимизации - нужен модуль от этой параши. ну или взять квадрат разности, это ни на что не повлияет, а анаитически будет приятней решать
Ты вообще или про этот конкретный случай? В этом конкретном случае ты прав, а вот в другом коде - нет (я воспринял, что ты имеешь ввиду, что целочисленные константы вообще плохо юзать, а не в примере из ОП-поста)
Поменять с перекомпиляцией, очевидно же
мне влом читать весь тред, но никто еще не предложил просто заранее все это просчитать и сложить в массив?
мегабайтный массив в целом то фигня по меркам нынешнего быдлокодерства, зато скорость куда как пошустрее будет
мегабайтный массив в целом то фигня по меркам нынешнего быдлокодерства, зато скорость куда как пошустрее будет
Ах да, если взять тупо квадрат разности в качества целевой функции - тупо получится система из 7 линейных уравнений с 7 неизвестными. А под это дело уже есть готовые бибилиотеки которые решат за 3 наносекунды
Если я правильно посчитал, то для хранения всех шестицифровых значений нужно будет около 3.5 мегабайт. В RAM сложить и брать результат оттуда идея вполне себе ничего, но этот тред скорее про олимпиадное программирование (где каждая доля секунды и килобайт памяти важны, а время на написание кода - нет)
достаточно хранить дельты, и вот тут возникает вопрос, хватит ли одного байта? это уже теорема, которую также можно олимпиадно задать
но двух байтов однозначно хватит с головой - следовательно 2 миллионов байт гарантированно хватит, если не страдать уплотнением
уж 25 лет меня мучает желание нарисовать софтину которая на полотне 1000x1000 пикселей зажжет все счастливые билеты...
но хватает иных задач
>это красивое решение
>Решать не нп-полную задачу перебором
>красивое решение
>уж 25 лет меня мучает желание нарисовать софтину которая на полотне 1000x1000 пикселей зажжет все счастливые билеты
Интересная идея. Не ленись, сделай обязательно. Я в свое время делал скатерть Улама, тоже интересно было
>>уж 25 лет
>Не ленись
тебе ничего сдесь не кажется нестыкующимся?
я помню как поставить точку на экране в досе, бейсиках, паскалях, сях
но сейчас же мне для этой радости придется вникать во чтото современное, ну какойть GD например
хотяяя... я же могу просто в однострочником на перле сгенерить xpm и тупо его конвертнуть потом в png
>Не ленись
тебе ничего сдесь не кажется нестыкующимся?
я помню как поставить точку на экране в досе, бейсиках, паскалях, сях
но сейчас же мне для этой радости придется вникать во чтото современное, ну какойть GD например
хотяяя... я же могу просто в однострочником на перле сгенерить xpm и тупо его конвертнуть потом в png
Можно прям в браузере на js посчитать и вывести в canvas. Это наверное проще всего.
не, мне не проще - это надо курить канвасы эти на js
мне проще на перле нашлепать
ща...
ну мне влом щас страдать детальным анализом сего высера, проще спросить альтернативного мнения
#!/usr/bin/perl
use v5.12;
say <<HEAD;
static char* z[]={
"1000 1000 2 1",
". c #000000",
"x c #ffffff",
HEAD
for(0..999){
my$z=eval join '+', split'';
my$l='';
$l.=($z == eval join '+', split'')?'x':'.' for 0..999;
say qq'"$l",';
}
say '};'
Тоже посчитал на жс в канвас.
мне кажется что ты пиздишь
говнокод прилагаю
а не, возможно и не пиздишь...
ну код показывай тогда
у меня выхлоп 1кб, у тебя 35кб
Пипец перловка какая. Давно ее не видел.
это я еще спать немного хочу, потому без гольфа
ато там бы вместо split-join-eval был бы примитивный s///e
хотя... щас поссу, бокал обновлю, чуть курну perlre, ибо не помню нужного мне кусочка, и чуть "упрощу" это
Лол, большинство скопировали мой алгоритм перебора из прошлого треда.
#!/usr/bin/perl
use v5.12;
say <<HEAD;
static char* z[]={
"1000 1000 2 1",
". c #000000",
"x c #ffffff",
HEAD
for my$z(map{eval(s/(?=.)/+/gr)}0..999){
say '"'.(join'', map{$z==eval s/(?=.)/+/gr?'x':'.'}0..999).'",'
}
say '};'
# чутка упростил, наслаждайся
#!/usr/bin/perl
use v5.12;
say <<HEAD;
static char* z[]={
"1000 1000 2 1",
". c #000000",
"x c #ffffff",
HEAD
for my$z(map{eval(s/(?=.)/+/gr)}0..999){
say '"',(map{$z==eval s/(?=.)/+/gr?'x':'.'}0..999),'",'
}
say '};'
#пардон, забыл мусор убрать
Мозговзрывающая штука. Надеюсь, никогда больше не придется на нее смотреть.
ну в продакшн так всеравно никто не пишет
но всетаки за что люблю перл - это за то что на нем можно так вот, матом, писать
да и собственно тут то ничего особенного то и нет, так, дешовый синтаксический сахар
Балдеж
Чутка упростил. Канвас в начале все равно забивается нулями, поэтому нет смысла его нулями повторно заполнять.
сажа, я такие в 7м классе кодил
На каком языке?
Да я в курсе что деления на степени двойки сделаны через побитовые сдвиги, другие деления через умножения могут быть. Сам пользуюсь при умножении десятичных на 5 в уме умножаю на 10 и делю на 2, это проще если как я не знаешь таблицу умножения. Циклы конвееризуются хорошо, а в хитрых схемах он ломаться будет. Написать несколько вариантов и проверить надёжнее чем впадать в теорию алгоритмов и байтоебство с дизассемблированием.
>>206071257
Очевидно, что решать в лоб это - проебать. (т.к. написать циклик перебора можно и в 7м классе)
Входящее значение N. Сумма первой половины sumPart1, сумма второй половины sumPart2. Разбивка N : [x1][x2][x3][y1][y2][y3].
Алгоритм такой.
1. Смотрим изначально, является ли y1 > sumPart1. Если да, то увеличиваем последний разряд первой части Тут же смотрим ошибку на переполнение в случае первой части 999 и пересчитываем sumPart1. Если нет, идем к пункту 4.
2. sumPart1 > 9, если нет - ответ: новая первая часть[][][] и [0][0][sumPart1]
3. Если да - ставим y3 = 9. Считаем rest = sumPart1 - y3. Если rest <= 9, ответ: новая первая часть[][][] и [0][rest][9]. Если rest > 9, ответ: новая первая часть[][][] и [sumPart1 - 18][9][9]
4. И так. Первая часть для ответа у нас уже есть. Подбираем ближайшую вторую.
Если sumPart1 - y1 < 18 , переходим к пункту 8. Иначе переходим к пункту 5.
5. restTwoDigits = sumPart1 - y1. Если restTwoDigits > 18, y1 = sumPart1 - 18
6. Если restTwoDigits <= 9, ответ [x1][x2][x3][y1][0][restTwoDigits]
7. В противном случае ответ [x1][x2][x3][y1][restTwoDigits - 9][9]
8. У нас [y1]+[y2] - минимальное число, которое нужно увеличить до достижения sumPart1. needToAdd = sumPart1 - y1 - y2. Если needToAdd <= 9, ответ [x1][x2][x3][y1][y2][needToAdd]
9. Иначе ответ [x1][x2][x3][y1][needToAdd - 9][9]
Надеюсь, что понятно. Вроде как очень просто описал, рисовать блоксхему лень.