Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.
Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.
Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.
| Входные данные | Вывод программы |
| 10 | 9 |
| 25833798135522720 | 4918510377816614 |
| 88888888888888 | 20334926626631 |
В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.
Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.
Выведите общую выручку от продажи билетов.
| № | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 3 | 25 |
| 1 2 3 | ||
| 4 5 6 | ||
| 7 8 9 | ||
| 1 0 1 | ||
| 0 1 0 | ||
| 1 0 1 | ||
| 2 | 2 2 | 0 |
| 1 1 | ||
| 2 2 | ||
| 0 0 | ||
| 0 0 | ||
| 3 | 4 5 | 380 |
| 15 16 17 18 19 | ||
| 19 18 17 16 15 | ||
| 19 20 21 22 23 | ||
| 23 22 21 20 19 | ||
| 1 1 1 1 1 | ||
| 1 1 1 1 1 | ||
| 1 1 1 1 1 | ||
| 1 1 1 1 1 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; int main() { int x [500*500]; int n, m; cin >> n >> m; int nm= n*m; for(int i = 1; i <= nm; i++){ cin >> x[i]; } int k; long long int v = 0; for(int i = 1; i <= nm; i++){ cin >> k; v+= k*x[i]; } cout << v << endl; return 0; } |
Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int x[500][500]; int main(){ int n, m, p; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> x[i][j]; unsigned long long v = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> p; if (p) v += x[i][j]; } } cout << v; } |
По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.
e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)
Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).
Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.
Выведите матрицу $r \cdot c$.
| № | Входные данные | Выходные данные |
| 1 | 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2 |
1 2 5 6 9 1 |
| 2 | 5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3 |
18 25 34 54 65 75 95 15 25 -4 15 -6 |
| 3 | 2 0 -1 23 69 1 1 |
0 |
| 4 | 3 1 2 3 -4 -5 -6 7 8 9 3 1 |
1 -4 7 |
Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; #define N 100 int main() { int n; cin >> n; int arr[N * N]; for (int i = 0; i < n * n; i++) { cin >> arr[i]; } int r, c; cin >> r >> c; for (int i = 0; i < c * r; i++) { cout << arr[((i / c) * n) + (i % c)] << ((1+i) % c == 0? "\n" : " "); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; #define N 100 int main() { int n, r, c; cin >> n; int arr[N][N]; for (int i = 0; i < n; i++) { for (int j = 0 ; j < n; j++) cin >> arr[i][j]; } cin >> r >> c; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cout << arr[i][j] << " "; } cout << endl; } return 0; } |
Задача взята с сайта e-olymp
Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.
В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.
В одной строке вывести m чисел с точностью до двух десятичных знаков — балл каждого спортсмена.
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 1 | 5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8 |
8.33 5.33 9.00 8.50 |
| 2 | 3 4 1 2 3 3 5 2 7 1 6 9 8 3 |
2.00 3.00 6.00 8.00 |
| 3 | 10 2 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 2 3 3 3 4 |
5.50 2.50 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <iomanip> using namespace std; int main() { cout << fixed << setprecision(2); int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax; cin >> n >> m; for(int j = 0 ; j < m ; j++){ sumGl = sumMin = sumMax = 0; valMin = 11; valMax = 0; countMin = countMax = 0; for(int i = 0 ; i < n; i++) { cin >> tmp; sumGl += tmp; if(tmp < valMin) { sumMin = tmp; valMin = tmp; countMin = 1; } else if(tmp == valMin) { sumMin += tmp; countMin++; } if(tmp > valMax) { sumMax = tmp; valMax =tmp; countMax = 1; } else if(tmp == valMax) { sumMax += tmp; countMax++; } } cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " "; } return 0; } |
Читая каждую оценку:
Тогда после введения всех [latex]n[/latex] оценок имеем:
Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу: [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <iomanip> using namespace std; double res(int *arr, int len) { int min,max; min = arr[0]; max = arr[0]; for(int i = 1; i < len; i++) { if(arr[i] > max) { max = arr[i]; } if(arr[i]<min) { min = arr[i]; } } int sum = 0; int count = 0; for(int i = 0; i < len; i++) { if(arr[i] != max && arr[i] != min) { sum += arr[i]; count++; } } return sum/((double)count); } int main() { int m, n; cin >> n >> m; cout << fixed << setprecision(2); for(int i = 0; i < m; i++) { int* arr = new int[n]; for(int j = 0 ; j < n; j++) { cin >> arr[j]; } cout << res(arr, n) << " "; delete[] arr; } return 0; } |
Делаем без счетчиков, запоминаем все элементы. Находим минимум и максимум, дальше проходим по всем оценкам и, если она не минимальная и не максимальная, добавляем к сумме и увеличиваем количество оценок, которые учитываются для среднего значения. В конце выводим среднее значение с двумя знаками после запятой.
Условие задачи на e-olymp
Код программы на ideone (Потоковая обработка)
Код программы на ideone (Массивы)
Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.
Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.
Напишите программу, которая вычислит результат попиксельного применения заданной логической операции к двум черно-белым изображениям одинакового размера.
Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.
Вывести результат применения заданной логической операции к изображениям в том же формате, в котором изображения заданы во входных данных.
| Входные данные | Выходные данные | |
|---|---|---|
| 1 | 5 3 01000 11110 01000 10110 00010 10110 0110 |
11110 11100 11110 |
| 2 | 2 3 010 111 000 101 1010 |
11 10 10 |
| 3 | 4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011 |
1111 0101 0000 1110 |
| 4 | 3 6 100011 000111 000000 111011 001100 010101 1000 |
000 100 110 000 101 010 |
( использован одномерный массив)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> using namespace std; bool my_operation (bool a, bool b, bool* res) { if (!a and !b) return res[0]; else if (!a and b) return res[1]; else if (a and !b) return res[2]; else return res[3]; } int main() { int w, h, n; bool truth_t[4]; cin >> w >> h; n = w * h; bool *first_t = new bool [n]; bool *second_t = new bool [n]; char c; for (int i = 0; i < n; i++) { cin >> c; first_t[i] = (c == '1' ? true : false); } for (int i = 0; i < n; i++) { cin >> c; second_t[i] = (c == '1' ? true : false); } for (int i = 0; i < 4; i++) { cin >> c; truth_t[i] = (c == '1' ? true : false); } for (int i = 0; i < n; i++) { if (i != 0 && i % w == 0) cout << endl; cout << my_operation(first_t[i], second_t[i], truth_t); } return 0; } |
(использован двумерный массив)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> using namespace std; bool my_operation (bool a, bool b, bool* res) { if (!a and !b) return res[0]; else if (!a and b) return res[1]; else if (a and !b) return res[2]; else return res[3]; } int main() { int w, h; bool truth_t[4]; cin >> w >> h; bool **first_t = new bool *[h]; bool **second_t = new bool *[h]; for (int i = 0; i < h; i++) { first_t[i] = new bool [w]; second_t[i] = new bool [w]; } char c; for (int i = 0; i < h; i++){ for (int j = 0; j < w; j++) { cin >> c; first_t[i][j] = (c == '1' ? true : false); } } for (int i = 0; i < h; i++){ for (int j = 0; j < w; j++) { cin >> c; second_t[i][j] = (c == '1' ? true : false); } } for (int i = 0; i < 4; i++) { cin >> c; truth_t[i] = (c == '1' ? true : false); } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cout << my_operation(first_t[i][j], second_t[i][j], truth_t); } if (i < h - 1) cout << endl; } return 0; } |
Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.
Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.
После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.
Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.
Подумав несколько ночей у него получилось написать программу которая находит слово анаграмму в словаре к другому — данному. Но перед ним встал новый вопрос, — а какое слово имеет наибольшее количество анаграмм в заданном словаре.
Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.
Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.
Вывести все слова что имеют максимальное количество анаграмм в нем.
Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.
Теперь пройдемся по словарю и будем проверять соседние элементы. Если они равны, то мы будем увеличивать счетчик анаграмм, если же нет, то мы сравним максимальное количество анаграмм, найденное ранее, с текущим значением счетчика. Если они равны, то добавим индекс последнего слова анаграммы в массив индексов, если же больше, то мы очистим массив индексов и добавим туда индекс последнего слова анаграммы. В любом случае, при не равенстве соседних строк сбрасываем счетчик и продолжаем.
На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.
| № | Ввод | Вывод |
|
1 |
trace react crate
dear dare read post stop spot |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <string> #include <algorithm> #include <vector> #define DIFFERENCE ('A' - 'a') // разность регистров using namespace std; bool IsBigAlpha(char a) { return (a >= 'A' && a <= 'Z'); } bool IsSmalAlpha(char a) { return (a >= 'a' && a <= 'z'); } string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы string rez = ""; for(char a : str) { if (IsBigAlpha(a)) a -= DIFERENSE; if (IsSmalAlpha(a)) rez += a; } return rez; } bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке return a.second < b.second; } int main() { vector <pair<string, string>> words; // словарь string str; while (getline(cin, str, '\n')) { pair<string, string> word; // слово word.first = str; word.second = edit(str); sort(word.second.begin(), word.second.end()); // сортируем буквы в слове words.push_back(word); } sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам vector <int> indeces; // массив индексов int Count = 0, MaxCount = 0, n = words.size(); for (int i = 1; i < n; i++) { if (words[i-1].second == words[i].second) Count++; else { if (Count > MaxCount) { MaxCount = Count; indeces.clear(); indeces.push_back(i-1); } else if (Count == MaxCount) indeces.push_back(i-1); Count = 0; } } if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм MaxCount = Count; indeces.clear(); indeces.push_back(n-1); } else if (Count == MaxCount) indeces.push_back(n-1); bool first = 1; for (int index : indeces) { // выводим if (!first) cout << endl << "---------------" << endl; else first = 0; for (int i = 0; i <= MaxCount; i++) { if (i != 0) cout << endl; cout << words[index - i].first; } } return 0; } |
Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…
Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.
Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.
Номер команды, выигравшей соревнования. Если несколько команд имеют одинаковые результаты, то побеждает та, у которой больше номер.
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 3 20 10 30 15 20 20 30 30 20 |
3 |
| 2 | 3 3 20 -10 -30 15 25 20 30 -30 20 |
1 |
| 1 | 3 3 0 -10 -30 15 25 20 30 -30 20 |
2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <cmath> #include <climits> using namespace std; double INF = 1e18; int sgn(long long a){ if(a < 0) return -1; else if(a == 0) return 0; else return 1; } struct logNumber{ long long sign; double value; logNumber(int sign = 1, double value = 0){ this->sign = sign; this->value = value; } void operator *= (long long a){ sign *= sgn(a); if(sign == 0) value = 0; else value += log(abs(a)); } bool operator >(logNumber a){ return (sign > a.sign) or (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value); } bool operator ==(logNumber a){ return sign == a.sign and value == a.value; } }; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n,k; cin>>n>>k; logNumber mult[n]; for(int i =0; i < k; i++){ for(int j=0; j < n; j++){ long long temp; cin>>temp; mult[j] *= temp; } } logNumber maxMult = mult[0]; int maxTeam = 0; for(int i = 0; i < n; i++){ if (mult[i] > maxMult){ maxMult = mult[i]; maxTeam = i; } else if(mult[i]==maxMult){ maxTeam = max(i, maxTeam); } } cout << maxTeam + 1; return 0; } |
Произведение результатов крыс может быть очень большим числом. Поэтому можно сравнивать их по знаку, если же по знаку они равны, то можно сравнивать не сами числа, а логарифмы от чисел. Создаем структуру, которая реализует эту идею.
Ссылка на e-olymp
Ссылка на ideone
Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.
Задано две матрицы $A$ и $B$. Найти их произведение.
В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.
В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.
| Входные данные | Выходные данные |
|---|---|
| 2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1 |
2 3 7 2 15 1 10 7 |
| 3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1 |
3 2 7 14 3 19 13 38 |
| 4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0 |
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 |
| 3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2 |
-1 |
| 2 3 57 -49 31 89 11 -37 3 1 19 -19 0 |
2 1 2014 1482 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std; int main() { int na, ma, nb, mb; cin >> na >> ma; int **a = new int *[na]; for (int i = 0; i < na; i++) { a[i] = new int[ma]; } for (int i = 0; i < na; i++) { for (int j = 0; j < ma; j++) { cin >> a[i][j]; } } cin >> nb >> mb; // Проверяем возможность вычисления произведения матриц if (ma != nb) { cout << -1; return 0; } int **b = new int *[nb]; for (int i = 0; i < nb; i++) { b[i] = new int[mb]; } for (int i = 0; i < nb; i++) { for (int j = 0; j < mb; j++) { cin >> b[i][j]; } } int **c = new int *[na]; for (int i = 0; i < na; i++) { c[i] = new int[mb]; } // Вычисляем произведение for (int i = 0; i < na; i++) { for (int j = 0; j < mb; j++) { for (int r = 0; r < ma; r++) { c[i][j] += a[i][r] * b[r][j]; } } } // Выводим результат cout << na << " " << mb << "\n"; for (int i = 0; i < na; i++) { for (int j = 0; j < mb; j++) { cout << c[i][j]; if (j + 1 != mb) cout << " "; } cout << "\n"; } return 0; } |
Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$
Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia
Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.
В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.
Выведите перевернутый массив в формате входных данных.
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 2 2
1 2 3 4 |
2 2
3 1 4 2 |
| 2 | 3 3
1 2 3 4 5 6 7 8 9 |
3 3
4 7 1 8 5 2 9 6 3 |
| 3 | 3 4
4 5 7 8 3 6 8 7 2 2 4 5 |
4 3
2 3 4 2 6 5 4 8 7 5 7 8 |
| 4 | 1 2
5 4 |
2 1
5 4 |
| 5 | 1 1
2 |
1 1
2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int ** x = new int *[n]; for (int i = 0; i < n; i++) x[i] = new int[m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> x[i][j]; cout << m << " " << n; cout << endl; for (int j = 0; j < m; j++){ for (int i = n - 1; i >= 0; i--) cout << x[i][j] << " "; cout << endl; } return 0; } |
Алгоритм решения данной задачи состоит в том, чтоб при выводе матрицы, начать выводить ее элементы не по строкам, а по столбцам, снизу вверх, начиная с первого столбца (левого нижнего угла матрицы).
Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.
В единственной строке задан номер мобильного телефона.
В первой строке вывести количество отсутствующих в номере цифр. Во второй строке в порядке возрастания вывести отсутствующие цифры, разделенные пробелом.
| Входные данные | Выходные данные |
|---|---|
| 0631562976 | 2 4 8 |
| 2139087 | 3 4 5 6 |
| 1111111111 | 9 0 2 3 4 5 6 7 8 9 |
| 7 | 9 0 1 2 3 4 5 6 8 9 |
| 4848 | 8 0 1 2 3 5 6 7 9 |
| 0921234567 | 1 8 |
| 6723545 | 4 0 1 8 9 |
| 9867453210 | 0 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int main() { // Номер мобильного телефона int c, count = 0; int n[] = {0,0,0,0,0,0,0,0,0,0}; while ((c = cin.get()) != EOF) { n[c - 48]++; } for (int i = 0; i < 10; i++) { if (n[i] == 0) count++; } cout << count << "\n"; for (int i = 0; i < 10; i++) { if (n[i] == 0) cout << i << " "; } return 0; } |
Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.
Условия задачи на e-olymp
Код задачи на ideone
Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.
Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.
Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].
Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].
Вывести одно число — количество клеток в наибольшем прямоугольнике, не защищенном башнями.
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 10 10 3
1 1 2 2 3 3 |
49 |
| 2 | 15 15 4
4 4 5 5 7 8 13 15 |
30 |
| 3 | 30 30 5
13 14 16 27 29 30 5 5 10 15 |
132 |
| 4 | 100 100 2
1 1 100 100 |
9604 |
| 5 | 3 3 3
1 1 2 2 3 3 |
0 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <algorithm> using namespace std; int main() { int x_max, y_max, n, a=0, b=0; cin>>x_max>>y_max>>n; int *x=new int[n+2]; int *y=new int[n+2]; for(int i=1;i<n+1;i++) cin>>x[i]>>y[i]; x[0] = y[0] = 0; x[n+1] = x_max + 1; y[n+1] = y_max + 1; sort(x, x + n+1); sort(y, y + n+1); for(int i=0; i<n+1; i++){ if(x[i+1]-x[i]>a) a=x[i+1]-x[i]; if(y[i+1]-y[i]>b) b=y[i+1]-y[i]; } cout<<(a-1)*(b-1); return 0; } |
Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.
Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex] Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.
На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.
В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].
Искомое число [latex]k[/latex].
| Входные данные | Выходные данные |
|---|---|
| 5 2 -1 3 0 0 4 -3 0 -2 1 |
6 |
| 5 0 0 2 4 6 6 10 34 -42 -48 |
10 |
| 4 0 0 0 1 1 0 1 1 |
0 |
| 8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2 |
24 |
| 5 0 0 0 1 -1 0 -1 -1 3 -3 |
3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; int main() { unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0}; unsigned long long c = 0; cin >> n; for (int i = 0; i < n; i ++){ cin >> x1 >> y1; if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++; else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++; else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++; else A [3] ++; } for(int i = 0; i < 4; i ++){ for(int j= 0; j < 4; j ++){ if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6; else c += A[i] * (A[i] - 1) * A[j] / 2; } } cout << c; return 0; } |
Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.
Условие задачи на сайте E-Olymp
код задачи на Ideone
описание теоремы Пика на Wikipedia
описание псевдоскалярного произведения на Wikipedia
Условие задачи
Задан массив целых чисел длины [latex]n[/latex]. Сдвинуть элементы массива вправо циклически на [latex]1[/latex] шаг.
Входные данные
В первой строке задано количество элементов массива [latex]n[/latex] [latex](n ≤ 100)[/latex]. Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает [latex]100[/latex].
Выходные данные
В одной строке вывести [latex]n[/latex] чисел — новые значения элементов массива.
Санта Клаус
Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки [latex]n[/latex] детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.
Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.
Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.
Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими [latex]n[/latex]. Все дети должны получить подарок на Рождество, иначе Санта расстроится.
В первой строке выведите одно число [latex]a[/latex] — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке [latex]a[/latex] чисел — номера детей, которым эти подарки должны быть доставлены.
| Входные данные | Выходные данные |
|---|---|
| 2 1 1 2 1 |
0 |
| 3 1 2 1 2 3 |
0 |
| 7 2 1 7 3 1 |
4 2 4 5 6 |
| 100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54 |
82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100 |
| 10 3 5 2 5 8 3 7 1 4 9 |
2 6 10 |
| 61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25 |
36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59 |
| 12 3 3 1 2 3 11 10 8 |
6 4 5 6 7 9 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; int main() { int n, m, k, num; cin >> n >> m >> k; bool children[n]; for (int i = 0; i < n; i++) { children[i] = false; } for (int i = 0; i < m + k; i++) { cin >> num; num--; children[num] = true; } cout << (n - m - k) << "\n"; for (int i = 0; i < n; i++) { if (!children[i]) { cout << (i + 1) << " "; } } return 0; } |
Создадим массив типа bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.
Условия задачи на e-olymp
Код задачи на ideone
Алиса любит свой цифровой будильник. Она устанавливает его каждый вечер. Прошлой ночью Алисе приснились ее часы. К сожалению, единственное, что она помнит — так это количество отображаемых сегментов на часах. Алиса хочет узнать, какое время показывали ее часы во сне.
Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).
Часы имеют следующее представление цифр:
Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.
Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].
| Входные данные | Выходные данные |
|---|---|
| 23 | 00:02 |
| 28 | Impossible |
| 0 | Impossible |
| 15 | 01:12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> using namespace std; int main() { int n; while (cin >> n) { int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; for (int i = 0; i < 24; i++) for (int j = 0; j < 60; j++) { int a = 0; a = a + seg[i / 10]; a = a + seg[i % 10]; a = a + seg[j / 10]; a = a + seg[j % 10]; if (a == n) { if (i < 10) cout << '0' << i; else cout << i; cout << ':'; if (j < 10) cout << '0' << j; else cout << j; return 0; } } cout << "Impossible"; } } |
Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].
Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов [latex]N[/latex] различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).
Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.
Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.
В выходной файл выведите минимально возможное количество переводов.
| ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|
| 2 4 2 5 1 |
1 |
| 1 4 4 |
0 |
| 3 2 2 2 4 1 1 |
2 |
| 3 6 3 1 0 0 10 |
9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> using namespace std; int main() { int size; cin >> size; long *arr1 = new long[size]; long *arr2 = new long[size]; for(int i = 0; i < size; i++){ cin >> arr1[i]; } for(int i = 0; i < size; i++){ cin >> arr2[i]; } long tmp = 0; for(int i = 0; i < size; i++){ tmp+= abs(arr2[i] - arr1[i]); } cout << tmp / 2; delete []arr1; delete []arr2; return 0; } |
Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.
• Задача на e-olymp.
• Решение на сайте ideone.
Задача с сайта e-olymp.com
Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…
Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.
В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].
В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.
| № | Входные данные | Выходные данные |
| 1 | 5 1000 2 3 1 3 |
6 |
| 2 | 2 1 2 |
2 |
| 3 | 4 1 3 100 0 |
3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int main() { int n, i; cin >> n; int *dp; dp = new int [n+1]; for(i = 1; i<=n; ++i){ cin >> dp[i]; } dp[0] = 0; dp[1] = 0; for(int i = 2; i<=n; ++i){ if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]); } cout << dp[n]; return 0; } |
Засчитанное решение на e-olymp.com.
Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.
Код на ideone.com.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> using namespace std; int *dp; int *used; int f(int i){ if(i < 2) return 0; else{ if(used[i] == 0){ dp[i] = dp[i] + max(f(i-2), f(i-3)); used[i] = 1; } return dp[i]; } } int main() { int n, i; cin >> n; dp = new int [n+1]; used = new int [n+1]; for(i = 1; i<=n; ++i){ cin >> dp[i]; used[i] = 0; } f(n); cout << dp[n]; return 0; } |
Засчитанное решение на e-olymp.com.
В данном случае используется функция [latex]f[/latex], принимающая номер ячейки массива и возвращающая максимальное количество монет после посещения ячейки с этим номером. Сначала объявляются два глобальных массива:
[latex]dp[/latex], в [latex]i[/latex]-й ячейке которого изначально хранится количество монет в [latex]i[/latex]-й ячейке лабиринта, и [latex]used[/latex], элементы которого принимают значения [latex]0[/latex] или [latex]1[/latex] (значение [latex]0[/latex] в [latex]i[/latex]-й ячейке означает, что максимальное количество монет после посещения
ячейки лабиринта с тем же номером рассчитано ещё не было). Далее всё происходит как в решении с использованием цикла, но одновременно с чтением входных данных обнуляются элементы [latex]used[/latex], а вместо второго цикла происходит вызов функции [latex]f[/latex]. Сама же функция [latex]f[/latex], если значение параметра меньше двух, возвращает [latex]0[/latex], а иначе, если этого не было сделано ранее, вычисляет максимальное количество монет после посещения ячейки с номером [latex]i[/latex] по формуле [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex] и возвращает его.
Код на ideone.com.
Кроме того, об идее решения данной задачи можно почитать здесь.
Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»
Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].
Дерево отрезков — структура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности [latex]O\left(\log_{2}{n}\right)[/latex] и значительно улучшить общую сложность программы с [latex]O\left(n+n\cdot m\right) = O\left(n\cdot m\right)[/latex] до [latex]O\left(n+m\cdot\log_{2}{n}\right)[/latex].
Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.
Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
#include <iostream> using namespace std; template <class TYPE> class segments_tree { TYPE *SegmentTree; size_t base_capacity = 0; TYPE (*g)(TYPE, TYPE); TYPE neutral; /* TYPE: Type of elements in the tree. SegmentTree: (pointer) Array-based tree of elements. base_capacity: (unsigned integer value) Parental array size, rounded to the closest upper power of 2. g: (pointer) Pointer to the funtion (associative binary operation), applied on the given array of elements. WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise. neutral: (array element) The value of element, which is neutral relatively to "g" function. ################################ #### INNER HELPER FUNCTIONS #### ################################ result_on_segment_in: returns value on segment [l, r]; */ TYPE result_on_segment_in ( size_t v, size_t tl, size_t tr, size_t l, size_t r ) { if (l > r) return neutral; else if (l == tl && r == tr) return SegmentTree[v]; else { size_t tm = (tl + tr) / 2; return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)), result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r)); } } /* make_monoid_and_fill_rest: - fills the unused space of array (which appears due to rounding of size of parental array) with neutral elements. - assigns the necessary values to the upper "vertexes" of the tree. */ void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr) { g = f; neutral = neutr; for(size_t i = base_capacity+n; i < 2*base_capacity; ++i) { NewTree[i] = neutral; } for(size_t i = base_capacity-1; i > 0; --i) { NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]); } SegmentTree = NewTree; } /* fix_capacity: Rounds base_capacity of the base array to closest upper power of 2. */ void fix_capacity(const size_t &base_array_size) { for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1); } public: /* ########################## #### PUBLIC FUNCTIONS #### ########################## Definitions: n - amount of elements in the parental array; lb - binary logarithm. Lowest level of the tree - parental array (segment of elements, which is a base of the tree) and (if exists) unused space, filled with neutral elements. construct: Constructs the tree by copying elements of [begin; end) memory block into the segment tree, and by building tree's structure using the given binary operation "f" and its neutral element "neutr". Complexity: O(n). */ void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr) { size_t base_size = end - begin; fix_capacity(base_size); TYPE *NewTree = new TYPE[base_capacity*2]; for(size_t i = 0; i < base_size; ++i) { NewTree[base_capacity+i] = begin[i]; } make_monoid_and_fill_rest(NewTree, base_size, f, neutr); } /* read_and_construct: Constructs the tree by filling with it with elements, created by "preprocessing_function", and by building tree's structure using the given binary operation "f" and its neutral element "neutr". This method is useful for creating tree by giving preprocessing_function an ability to read the data from the incoming stream, if the separate memorisation of the base array is not needed. Complexity: O(n). */ void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr) { fix_capacity(amount_of_elements); TYPE *NewTree = new TYPE[base_capacity*2]; for(size_t i = 0; i < amount_of_elements; ++i) { NewTree[base_capacity+i] = preprocessing_function(); } make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr); } /* assign: Assigns new value to the element of base array with given index. Complexity: O(lb(n)) */ void assign(const size_t index, const TYPE new_value) { SegmentTree[base_capacity+index] = new_value; for (size_t i = (base_capacity+index)/2; i > 0; i /= 2) { SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]); } } /* result_on_segment: Returns value of operation on the given segment of parental array. Complexity: O(lb(n)). */ TYPE result_on_segment (size_t l, size_t r) { return result_on_segment_in(1, 0, base_capacity-1, l, r); } }; int sum(int a, int b) { return a+b; } int main() { return 0; } |
Далее [latex]n[/latex] — размерность базы дерева.
| Название объекта | Описание |
|---|---|
| Параметр | |
| TYPE | Тип объектов дерева, над которыми будут проводится вычисления. |
| Внутренние объекты | |
| SegmentTree | Массив, хранящий в себе дерево отрезков. |
| base_capacity | Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков. |
| g | Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция. |
| neutral | Нейтральный элемент относительно бинарной операции g. |
| Методы класса | |
| construct |
Аргументы:
Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков. |
| read_and_construct | Аргументы:
Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков. |
| assign | Аргументы:
Заменяет значение элемента с заданным индексом на новое. |
| result_on_segment | Аргументы:
Возвращает результат функции на заданном отрезке. |
Прежде всего, код универсального дерева отрезков необходимо скопировать в исходную программу.
Построение:
Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.
Примечание: условие и альтернативное решение приведённой ниже задачи находится по этой ссылке.
Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.
Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).
Остальная часть решения требует только замены старых элементов новыми и вычислений результатов на отрезках, для чего есть готовые методы класса.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> using namespace std; // . . . . . . . . . . . . . . . . . . . . // . . . . segments_tree class . . . . . . // . . . . . . . . . . . . . . . . . . . . struct number_sign { bool zero, plus; number_sign() { zero = 0; plus = 1; } number_sign(bool a, bool b) { zero = a; plus = b; } }; number_sign make_number_sign(const short &X) { return number_sign(X == 0, X > 0); } number_sign prod(number_sign a, number_sign b) { return number_sign(a.zero|b.zero, !(a.plus^b.plus)); } char sign(const number_sign d) { if (d.zero) return '0'; else if (d.plus) return '+'; else return '-'; } int main() { unsigned int i, j, m; char q; short X; segments_tree <number_sign> A; number_sign *B, neutr; while (cin >> i) { scanf("%u", &m); A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign()); scanf("\n"); ++m; while (--m) { scanf("%c%u", &q, &i); if (q == 'P') { scanf("%u", &j); printf("%c", sign(A.result_on_segment(i-1, j-1))); } else { scanf("%hd", &X); A.assign(i-1, make_number_sign(X)); } scanf("\n"); } printf("\n"); } return 0; } |
Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:
Написать таблицу новых функций и параметров.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <iostream> using namespace std; template <class TYPE> class segments_tree { TYPE *SegmentTree; size_t base_capacity = 0; TYPE (*g)(TYPE, TYPE); TYPE neutral; /* TYPE: Type of elements in the tree. SegmentTree: (pointer) Array-based tree of elements. base_capacity: (unsigned integer value) Parental array size, rounded to the closest upper power of 2. g: (pointer) Pointer to the funtion (associative binary operation), applied on the given array of elements. WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise. neutral: (array element) The value of element, which is neutral relatively to "g" function. ################################ #### INNER HELPER FUNCTIONS #### ################################ result_on_segment_in: returns value on segment [l, r]; */ TYPE result_on_segment_in ( size_t v, size_t tl, size_t tr, size_t l, size_t r ) { if (l > r) return neutral; else if (l == tl && r == tr) return SegmentTree[v]; else { size_t tm = (tl + tr) / 2; return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)), result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r)); } } /* make_monoid_and_fill_rest: - fills the unused space of array (which appears due to rounding of size of parental array) with neutral elements. - assigns the necessary values to the upper "vertexes" of the tree. */ void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr) { g = f; neutral = neutr; for(size_t i = base_capacity+n; i < 2*base_capacity; ++i) { NewTree[i] = neutral; } for(size_t i = base_capacity-1; i > 0; --i) { NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]); } SegmentTree = NewTree; } /* fix_capacity: Rounds base_capacity of the base array to closest upper power of 2. */ void fix_capacity(const size_t &base_array_size) { for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1); } public: /* ########################## #### PUBLIC FUNCTIONS #### ########################## Definitions: n - amount of elements in the parental array; lb - binary logarithm. Lowest level of the tree - parental array (segment of elements, which is a base of the tree) and (if exists) unused space, filled with neutral elements. construct: Constructs the tree by copying elements of [begin; end) memory block into the segment tree, and by building tree's structure using the given binary operation "f" and its neutral element "neutr". Complexity: O(n). */ void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr) { size_t base_size = end - begin; fix_capacity(base_size); TYPE *NewTree = new TYPE[base_capacity*2]; for(size_t i = 0; i < base_size; ++i) { NewTree[base_capacity+i] = begin[i]; } make_monoid_and_fill_rest(NewTree, base_size, f, neutr); } /* read_and_construct: Constructs the tree by filling with it with elements, created by "preprocessing_function", and by building tree's structure using the given binary operation "f" and its neutral element "neutr". This method is useful for creating tree by giving preprocessing_function an ability to read the data from the incoming stream, if the separate memorisation of the base array is not needed. Complexity: O(n). */ void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr) { fix_capacity(amount_of_elements); TYPE *NewTree = new TYPE[base_capacity*2]; for(size_t i = 0; i < amount_of_elements; ++i) { NewTree[base_capacity+i] = preprocessing_function(); } make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr); } /* assign: Assigns new value to the element of base array with given index. Complexity: O(lb(n)) */ void assign(const size_t index, const TYPE new_value) { SegmentTree[base_capacity+index] = new_value; for (size_t i = (base_capacity+index)/2; i > 0; i /= 2) { SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]); } } /* result_on_segment: Returns value of operation on the given segment of parental array. Complexity: O(lb(n)). */ TYPE result_on_segment (size_t l, size_t r) { return result_on_segment_in(1, 0, base_capacity-1, l, r); } }; int main() { return 0; } |
| Название объекта | Описание |
|---|---|
| Новый внутренний объект | |
| base_size | Переменная, хранящая размерность базы дерева отрезков. |
| Новые методы класса | |
| begin |
Аргументы: отсутствуют. |
| end | Аргументы: отсутствуют. Возвращает адрес конца базы. Вычислительная сложность: константа. |
| push_back | Аргумент: значение нового элемента базы. Добавляет новый элемент в конец базы. Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex]. |
| pop_back |
Аргументы: отсутствуют. |
| insert |
Аргументы:
Добавляет на заданную позицию базы новый элемент с заданным значением. |
| erase |
Аргумент: индекс удаляемого элемента. |
| size |
Аргументы: отсутствуют. |
| capacity |
Аргументы: отсутствуют. |
| resize |
Аргумент: новый размер базы. |
In stations and airports you often see this type of screen:
Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!
Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.
Line 1: the width
L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height
H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text
T, composed of N ASCII characters.
Following
H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.
The text
T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.
| Input | Output |
|---|---|
| 1 1 Encoding using ASCII? Hah! ?ZYXWVUTSRQPONMLKJIHGFEDCBA |
WNYMXSNUAGISNUA?IYSSAAT?TA |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { short Lwidth, Lheight; cin >> Lwidth >> Lheight; cin.ignore(); string Text; char **alphabet = new char*[256]; //initializing alphabet for (char ltr = 'a'; ltr < 'z'+1; ++ltr) { alphabet[ltr] = new char[Lwidth]; } for (char ltr = 'A'; ltr < 'Z'+1; ++ltr) { alphabet[ltr] = new char[Lwidth]; } alphabet['?'] = new char[Lwidth]; getline(cin, Text); for (short h = 0; h < Lheight; ++h) { char ltr; for (ltr = 'a'; ltr < 'z'+1; ++ltr) //reading letters { for (short w = 0; w < Lwidth; ++w) { scanf("%c", &alphabet[ltr][w]); alphabet[ltr-('a'-'A')][w] = alphabet[ltr][w]; } } for (short w = 0; w < Lwidth; ++w) //reading ? { scanf("%c", &alphabet['?'][w]); } scanf("%c", <r); //reading endl if (ltr != '\n') cerr << "ERROR: INVALID TESTS PROVIDED\n"; //Putting result out. for (short i = 0; i < Text.size(); ++i) { if //it is a letter ( (('a'-1 < Text[i]) && (Text[i] < 'z'+1)) || (('A'-1 < Text[i]) && (Text[i] < 'Z'+1)) ) //then print it cout << alphabet[Text[i]]; else //it is definitely something weird cout << alphabet['?']; } cout << '\n'; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; import java.io.*; class Solution { public static void main(String args[]) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); short Lwidth = in.nextShort(), Lheight = in.nextShort(); Map alphabet = new HashMap(); if (in.hasNextLine()) { in.nextLine(); } String Text = in.nextLine(); for (short h = 0; h < Lheight; ++h) { String alphabet_line = in.nextLine(); short i = 0; for(char sym = 'a', Sym = 'A'; sym <= 'z'; ++sym, ++Sym, ++i) { String letter = alphabet_line.substring(i*Lwidth, (i+1)*Lwidth); alphabet.put(sym, letter); alphabet.put(Sym, letter); } alphabet.put('?', alphabet_line.substring(i*Lwidth, (i+1)*Lwidth)); for(i = 0; i < Text.length(); ++i) { if //it is a letter ( (('a' <= Text.charAt(i)) && (Text.charAt(i) <= 'z')) || (('A' <= Text.charAt(i)) && (Text.charAt(i) <= 'Z')) ) out.print(alphabet.get(Text.charAt(i))); else //it is definitely something weird out.print(alphabet.get('?')); } out.print('\n'); } out.flush(); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
<?php fscanf(STDIN, "%d", $Lwidth); fscanf(STDIN, "%d", $Lheight); $alphabet = array(); $Text = stream_get_line(STDIN, 1024, "\n"); for ($h = 0; $h < $Lheight; ++$h) { $ltr = 'a'; $ltr2 = 'A'; while(true) //reading letters { $alphabet[$ltr] = stream_get_line(STDIN, $Lwidth); $alphabet[$ltr2] = $alphabet[$ltr]; if ($ltr == 'z') break; ++$ltr; ++$ltr2; } //reading '?' $alphabet['?'] = stream_get_line(STDIN, $Lwidth); //reading endl fscanf(STDIN, "%c", $useless); for ($i = 0; $i < strlen($Text); ++$i) { if //it is a letter ( (('a' <= $Text[$i]) and ($Text[$i] <= 'z')) or (('A' <= $Text[$i]) and ($Text[$i] <= 'Z')) ) //then print it echo $alphabet[$Text[$i]]; else //it is definitely something weird echo $alphabet['?']; } echo "\n"; } ?> |
After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.
The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.
The goal is to find, when they exist, the horizontal and vertical neighbors of each node.
To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.
If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].
You lose if:
The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.
Line 1: one integer width for the number of cells along the x axis.
Line 2: one integer height for the number of cells along the y axis.
Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.
[latex]0 <[/latex] width[latex]\le 30[/latex]One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:
| Input | Output |
|---|---|
| 2 2 00 0. |
0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 |
| 4 4 .0.. .000 000. ..0. |
1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <string> using namespace std; int main() { short width; // the number of cells on the X axis cin >> width; cin.ignore(); short height; // the number of cells on the Y axis cin >> height; cin.ignore(); string *node = new string[height]; short x, y; for (y = 0; y < height; ++y) { getline(cin, node[y]); } for (y = 0; y < height; ++y) { for (x = 0; x < width; ++x) { if (node[y][x] == '0') { cout << x << ' ' << y << ' '; short x2, y2, ansX = -1, ansY = -1; for (x2 = x+1; x2 < width; ++x2) { if (node[y][x2] == '0') { ansX = x2; ansY = y; break; } } cout << ansX << ' ' << ansY << ' '; ansX = -1; ansY = -1; for (y2 = y+1; y2 < height; ++y2) { if (node[y2][x] == '0') { ansX = x; ansY = y2; break; } } cout << ansX << ' ' << ansY << '\n'; x = x2-1; } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.*; import java.io.*; import java.math.*; class Player { public static void main(String args[]) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); short width = in.nextShort(); // the number of cells on the X axis short height = in.nextShort(); // the number of cells on the Y axis if (in.hasNextLine()) { in.nextLine(); } String node[] = new String[height]; for(short y = 0; y < height; ++y) { node[y] = in.nextLine(); } for(short y = 0; y < height; ++y) { for(short x = 0; x < width; ++x) { if (node[y].charAt(x) == '0') { out.printf(String.valueOf(x)+" "+String.valueOf(y)+" "); short x2, y2, ansX = -1, ansY = -1; for (x2 = (short)(x+1); x2 < width; ++x2) { if (node[y].charAt(x2) == '0') { ansX = x2; ansY = y; break; } } out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" "); ansX = -1; ansY = -1; for(y2 = (short)(y+1); y2 < height; ++y2) { if (node[y2].charAt(x) == '0') { ansX = x; ansY = y2; break; } } out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n"); x = (short)(x2-1); } } } out.flush(); } } |
First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.
After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.
This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.
Для отправки комментария необходимо войти на сайт.