Разминка для мозга

 

Ответ-то где лол. Для трапеции.

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

 

медиана треугольника ABC = 7+7/(10/4 -1) = 7 +14/3= 35/3

у треугольника ABC известна медиана 35/10, строна 10 и угол 45, откуда площадь 500/9

площадь трапеции = (1-16/100)*500/9 = 140/3

хз мог в расчётах ошибиться

 

 

 

Вголос, я тупо не понимаю, откуда у тебя все эти числа взялись: для медианы и площади треугольника, но ответ почему-то правильный.

Я знаю решение двумя способами. 1 - через легкую систему из 4х уравнений на основе подобий + теоремы косинусов. 2 - через параллельный перенос, теорему косинусов ну и там изи дальше.

Хз чё у тебя за формулы и как ты вообще считал значение медианы, уже молчу о площади через медиану ... почему-то никогда не слышал от такой формуле.

откуда у тебя все эти числа взялись: для медианы и площади треугольника

ну медиана понятно что проходит через 0, и описанные окружности с центрами в серединах гипотенуз проходят через точку О, откуда находим отрезок 2+5, а целиком медиану через подобие треугольников.

Формулу тоже не нашол через медиану, сторону и угол, но можно достроить до параллелограмма и воспользоваться формулами для вычисления диагоналей или ещё какнить.

хуёвое офк решение, но какое есть

А, всё, я понял. С медианами вообще круто получилось, я и забыл про свойство медиан для прямоугольного треугольника. Но, да, не это решение я ждал офк.

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"

struct Sudoku
{
#define N 9
#define M 3
    unsigned int m[N][N];
    unsigned int r[N][N];
    int copyCount;
    int change_rCount;

    void init(const char *fn)
    {
        copyCount = 0;
        change_rCount = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                m[i][j] = (1 << N) - 1;
            }
        FILE *f = fopen(fn, "r");
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                fscanf(f, "%u", &r[i][j]);
                if (r[i][j] == 0)
                    r[i][j] = N;
                else
                    r[i][j]--;
            }
        fclose(f);
    }

    void outAnswer(const char *fn1, const char *fn2)
    {
        FILE *out1 = fopen(fn1, "w");
        FILE *out2 = fopen(fn2, "w");
        int count = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                //fprintf(out1, "%4u", m[i][j]);
                unsigned int mm = m[i][j];
                for (int bitIndex = 0; bitIndex < N; bitIndex++)
                {
                    int bitValue = mm % 2;
                    fprintf(out1, "%u", bitValue);
                    mm /= 2;
                }
                fprintf(out1, " ");

                unsigned int res = r[i][j];
                if (res == N)
                    res = 0;
                else
                    res++;
                fprintf(out2, "%2u", res);
            }
            fprintf(out1, "\n");
            fprintf(out2, "\n");
        }
        fclose(out2);
        fclose(out1);
    }
    
    bool solve()
    {
        // инициализируем массивы в соответствии с исходными данными
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                if (r[i][j] != N)
                {
                    unsigned int mask = 1 << r[i][j];
                    if ((m[i][j] >> r[i][j]) % 2 == 0)    // это значение исключено - явно ошибка
                        return true;
                    if (change_r(i, j, r[i][j]))
                        return true;
                }
            }
        // вызываем перебор
        return enumeration();
    }

    bool enumeration()
    {
        // смотрим, в каком квадратике среди не определённых меньше всего вариантов
        int min, min_i, min_j;
        findMin(min, min_i, min_j);
        //printf("Min: NumberOfOnes[%d][%d] = %d\n", min_i, min_j, min);
        if (min == 1)
            return false;    // решение найдено
        else
        {
            unsigned int mm = m[min_i][min_j];
            for (int bitIndex = 0; bitIndex < N; bitIndex++)
            {
                int bitValue = mm % 2;
                if (bitValue == 1)
                {
                    // один из вариантов
                    copyCount++;
                    Sudoku newState = *this;
                    unsigned int mask = (1 << bitIndex);    // маска для обнуления всех битов кроме bitIndex
                    if (newState.change_m(min_i, min_j, mask))
                    {
                        // не пошло, сохраняем количество вызовов (solve() не вызывается)
                        change_rCount = newState.change_rCount;
                    }
                    else
                    {
                        if (newState.enumeration())
                        {
                            // не пошло, сохраняем количество вызовов
                            copyCount = newState.copyCount;
                            change_rCount = newState.change_rCount;
                        }
                        else
                        {
                            // решение найдено
                            *this = newState;
                            return false;
                        }
                    }
                }
                mm >>= 1;
            }
        }
        // решения нет
        return true;
    }

    // нахождение ячейки с меньким количеством вариантов
    void findMin(int &min, int &min_i, int &min_j)
    {
        min = N + 1;    // заведомо большое
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                if (r[i][j] == N)    // минимум среди не определённых
                {
                    unsigned int mm = m[i][j];
                    int NumberOfOnes = 0;
                    for (int bitIndex = 0; bitIndex < N; bitIndex++)
                    {
                        int bitValue = mm % 2;
                        NumberOfOnes += bitValue;
                        mm >>= 1;
                    }
                    if (NumberOfOnes < min)
                    {
                        min = NumberOfOnes;
                        min_i = i;
                        min_j = j;
                        if (min == 2)
                            break;    // 2 - идеальный вариант
                    }
                }
            }
        if (min == N + 1)
        {
            // неопределённых нет, значит решение найдено
            min = 1;
            min_i = 0;
            min_j = 0;
        }
    }

    // изменение значения элемента массива r
    bool change_r(int i, int j, unsigned int value)
    {
        change_rCount++;
        //printf("r[%d][%d] = %u\n", i, j, value + 1);
        r[i][j] = value;
        unsigned int mask = ((1 << N) - 1) - (1 << value);    // маска для обнуления бита номер value
        // строка и столбец
        for (int l = 0; l < N; l++)
        {
            if (l != j)
            {
                if(change_m(i, l, mask))    // исключение бита в m[i][l]
                    return true;
            }
            if (l != i)
            {
                if(change_m(l, j, mask))    // исключение бита в m[l][j]
                    return true;
            }
        }
        // квадрат
        int qi1 = i - i % M;
        int qj1 = j - j % M;
        for (int qi = qi1; qi < qi1 + M; qi++)
            for (int qj = qj1; qj < qj1 + M; qj++)
            {
                if (qi != i || qj != j)
                {
                    if(change_m(qi, qj, mask))    // исключение бита в m[qi][qj]
                        return true;
                }
            }
        return false;
    }
    
    // изменение значения элемента массива m
    bool change_m(int i, int j, unsigned int mask)
    {
        unsigned int newmij = (m[i][j] & mask);
        if (newmij == m[i][j])
            return false;
        else
        {
            m[i][j] = newmij;
            for (int bitIndex = 0; bitIndex < N; bitIndex++)
            {
                int bitValue = newmij % 2;
                if (bitValue == 1)
                {
                    if (newmij == 1)
                    {
                        // исключены все варианты кроме 1 - нашли ответ в ячейке
                        if(change_r(i, j, bitIndex))
                            return true;
                    }
                    return false;
                }
                newmij >>= 1;
            }
            // все биты 0 быть не могут => решения нет
            return true;
        }
    }
};

int main()
{
    Sudoku s;
    s.init("in.txt");
    if(s.solve())
        printf("no answer\n");
    else
        s.outAnswer("out_m.txt", "out_r.txt");
    printf("copyCount = %d\n", s.copyCount);
    printf("change_rCount = %d\n", s.change_rCount);
    return 0;
}


copyCount = 16
change_rCount = 203

прога офк решает

мгновенно, но

copyCount = 1850
change_rCount = 17301
то есть много перебирать приходится, ну а хуле, слишком тупой перебор (с единственной стратегией выбора: ставим цифру если, глядя на строку, столбец и малый квадрат, все остальные цифры исключены)

задача оказалась нп-жирной хуетой (придумывай сколько хочешь стратегий всё равно будешь в говне), поэтому оставляю как есть.

На счёт подсчёта количества ненулевых битов числа. Числа маленькие поэтому можно просто таблицу составить и цикл будет не нужен, сразу ответ на тебе.

Как же приятно отдохнут во время перерыва в этой теме. Спасибо, Женёк.