Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

реши задачу по программированию на языке c++ : адача 12. Одним пальцем Имя входного…

  1. User

    реши задачу по программированию на языке c++ : адача 12. Одним пальцем Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти: стандартный ввод стандартный вывод 1 секунда 256 мегабайт Рассмотрим процесс набора одним пальцем длинных чисел на обычной клавиатуре и цифровом блоке. Числа состоят из цифр от 1 до 9 включительно. При наборе двух соседних цифр палец проходит расстояние, равное евклидову расстоя- нию между центрами соответствующих клавиш. Клавиши являются квадратами со стороной 1. Расстоянием между клавишами можно пренебречь. Клавиши в обычной клавиатуре расположены в виде прямоугольника 1×9 со следующей раскладкой: 123456789 Клавиши в цифровом блоке расположены в виде прямоугольника 3 × 3 со следующей раскладкой: 789 456 123 Время набора числа одним пальцем зависит от суммарного расстояния, пройденного паль- цем — если расстояние меньше, то и время набора меньше. Считается, что первоначально палец сразу установлен на первую цифру и что сами нажатия происходят мгновенно, то есть число, состоящее из одинаковых цифр, набирается за время 0. Вам дано длинное число, требуется выяснить, на чём его быстрее набирать — только на обычной клавиатуре или только на цифровой. Формат входных данных Входные данные содержат одну строку, состоящую из не менее 2 и не более 107 цифр от 1 до 9 включительно — число, которое требуется ввести. Формат выходных данных Выведите num, если число быстрее набрать на цифровом блоке, usual, если на обычной клавиатуре, или same, если там и там число набирается за одинаковое время. Примеры 144 121 343 стандартный ввод стандартный вывод num same usual

  2. Assistant

    Вот решение задачи на языке C++. Программа считывает строку цифр, вычисляет суммарное расстояние при наборе на обычной клавиатуре и цифровом блоке, а затем сравнивает эти суммы и выводит результат согласно условию задачи.

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        
        // Определяем позиции для обычной клавиатуры (1x9)
        // pos_usual_x[digit 1-9]
        double pos_usual_x[9];
        for(int d=0; d<9; d++){
            pos_usual_x[d] = d;
        }
        
        // Определяем позиции для цифрового блока (3x3)
        double pos_num_x[9];
        double pos_num_y[9];
        for(int d=1; d<=9; d++){
            int idx = d -1;
            if(d <=3){
                pos_num_x[idx] = d-1;
                pos_num_y[idx] = 2;
            }
            else if(d <=6){
                pos_num_x[idx] = d -4;
                pos_num_y[idx] =1;
            }
            else{
                pos_num_x[idx] = d -7;
                pos_num_y[idx] = 0;
            }
        }
        
        // Предварительно вычисляем расстояния между всеми парами цифр
        double usual_distance[9][9];
        double num_distance[9][9];
        for(int a=0; a<9; a++){
            for(int b=0; b<9; b++){
                // Расстояние на обычной клавиатуре
                usual_distance[a][b] = abs(pos_usual_x[a] - pos_usual_x[b]);
                
                // Расстояние на цифровом блоке
                double dx = pos_num_x[a] - pos_num_x[b];
                double dy = pos_num_y[a] - pos_num_y[b];
                num_distance[a][b] = sqrt(dx * dx + dy * dy);
            }
        }
        
        // Считываем строку цифр
        string s;
        cin >> s;
        
        // Если строка состоит из одной цифры, время набора равно нулю
        if(s.length() < 2){
            cout << "same";
            return 0;
        }
        
        // Инициализируем суммы расстояний
        double sum_usual =0.0, sum_num=0.0;
        int prev = s[0] - '1';
        for(int i=1; i< s.length(); i++){
            int current = s[i] - '1';
            sum_usual += usual_distance[prev][current];
            sum_num += num_distance[prev][current];
            prev = current;
        }
        
        // Сравниваем суммы и выводим результат
        if( sum_num + 1e-9 < sum_usual ){
            cout << "num";
        }
        else if( sum_usual + 1e-9 < sum_num ){
            cout << "usual";
        }
        else{
            cout << "same";
        }
    }
    

    Пояснение решения:

    1. Определение позиций клавиш:

      • Обычная клавиатура: Расположена в одном ряду, каждая цифра от 1 до 9 имеет свою позицию по оси X, при этом Y всегда равен 0.
      • Цифровой блок: Расположен в виде квадрата 3x3, где каждая цифра имеет свои координаты (x, y).
    2. Предварительное вычисление расстояний:

      • Для всех возможных пар цифр (от 1 до 9) вычисляются расстояния на обычной клавиатуре и на цифровом блоке.
      • Расстояние на обычной клавиатуре — это просто разница по оси X.
      • Расстояние на цифровом блоке вычисляется по формуле евклидова расстояния: sqrt((x1 - x2)^2 + (y1 - y2)^2).
    3. Обработка входных данных:

      • Строка цифр считывается целиком.
      • Если строка содержит менее двух цифр, выводится same, поскольку расстояние не изменяется.
      • Иначе, рассчитывается суммарное расстояние для обеих клавиатур путем итерации по парным символам строки и добавления соответствующих расстояний.
    4. Сравнение и вывод результата:

      • После получения сумм расстояний для обеих клавиатур, они сравниваются с учетом малой погрешности (1e-9) для устранения возможных ошибок округления.
      • В зависимости от результата сравнения выводится num, usual или same.

    Пример работы программы:

    • Вход: 144

    • Выход: num

    • Вход: 121

    • Выход: same

    • Вход: 343

    • Выход: usual

    Эта программа эффективно обрабатывает строки до 10^7 символов за счет предварительного вычисления всех расстояний и использования быстрых операций с массивами.