реши задачу по программированию на языке c++ : адача 12. Одним пальцем Имя входного…
- 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
- 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 до 9 имеет свою позицию по оси X, при этом Y всегда равен 0.
- Цифровой блок: Расположен в виде квадрата 3x3, где каждая цифра имеет свои координаты
(x, y).
-
Предварительное вычисление расстояний:
- Для всех возможных пар цифр (от 1 до 9) вычисляются расстояния на обычной клавиатуре и на цифровом блоке.
- Расстояние на обычной клавиатуре — это просто разница по оси X.
- Расстояние на цифровом блоке вычисляется по формуле евклидова расстояния:
sqrt((x1 - x2)^2 + (y1 - y2)^2).
-
Обработка входных данных:
- Строка цифр считывается целиком.
- Если строка содержит менее двух цифр, выводится
same, поскольку расстояние не изменяется. - Иначе, рассчитывается суммарное расстояние для обеих клавиатур путем итерации по парным символам строки и добавления соответствующих расстояний.
-
Сравнение и вывод результата:
- После получения сумм расстояний для обеих клавиатур, они сравниваются с учетом малой погрешности (
1e-9) для устранения возможных ошибок округления. - В зависимости от результата сравнения выводится
num,usualилиsame.
- После получения сумм расстояний для обеих клавиатур, они сравниваются с учетом малой погрешности (
Пример работы программы:
-
Вход:
144 -
Выход:
num -
Вход:
121 -
Выход:
same -
Вход:
343 -
Выход:
usual
Эта программа эффективно обрабатывает строки до 10^7 символов за счет предварительного вычисления всех расстояний и использования быстрых операций с массивами.
-