e-olymp 8950. Шаблон 5

Условие

По заданному нечетному натуральному числу  [latex] n [/latex] вывести изображение размером  [latex] n × n [/latex], образованное символами звездочка и пробел как показано в примере.

* *
* * * *
* * * * *
* * * *
* *

Входные данные

Одно нечетное натуральное число [latex] n  (n>1)[/latex] .

Выходные данные

Вывести изображение  [latex] n × n [/latex].

Тесты

Входные данные Выходные данные
3
* *
* * *
* *
5
* *
* * * *
* * * * *
* * * *
* *
7
* *
* * * *
* * * * * *
* * * * * * *
* * * * * *
* * * *
* *

Код программы

Решение задачи

Считываем значение [latex]n[/latex]. Создаём двумерный массив [latex] n * n [/latex] все элементы которого равны единице. Далее в цикле заполняем пространство между [latex] * [/latex] нулями. Так как позиции [latex] (i,0)[/latex] и [latex] (i,n) [/latex] всегда [latex] * [/latex], ко второму счётчику [latex]  j  [/latex] прибавляем единицу . На    середине   [latex] m = ( n — 1 ) / 2  [/latex] цикл прекращает заполнение нулями, потому в следующем цикле верхняя часть отображается в нижнюю. После чего происходит вывод двумерного массива заменяя [latex]  0=« » [/latex]  и [latex] 1=«*» [/latex].

Задача на ideone
Засчитанное решение на e-olymp
Код вe-olymp

e-olymp 1821. Comparing Answers

Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

Tests

Input Output
1 3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 1
3 0 43
2 0 1
1 0 3
1 1 0
5 1 2
5 3 2
3 0 40
YES
NO
2 5
1 2 7 8 9
4 5 8 7 3
1 0 2 5 6
1 0 0 5 4
1 7 2 5 9
33 75 55 142 170
42 54 90 157 154
14 44 23 73 95
10 30 15 53 65
45 100 85 137 1435
1 2 7 8 9
4 5 8 7 3
1 0 2 5 6
1 0 0 5 4
1 7 2 5 9
33 75 55 142 170
42 4 90 157 154
14 44 23 73 95
10 30 15 53 65
45 100 85 137 1430
YES
NO
3 1
2
21
2
40
NO
YES
4 9
1 5 7 9 10 6 3 3 6
10 2 0 5 10 4 3 3 5
7 10 4 1 4 0 4 4 2
5 4 0 1 7 0 5 3 2
7 0 6 1 7 5 2 2 2
7 4 0 1 1 8 6 6 3
0 4 9 2 1 8 0 3 7
8 7 7 3 5 0 10 8 2
1 0 5 8 8 8 3 3 1
287 178 173 129 293 196 195 180 134
182 123 203 174 287 214 150 143 144
202 143 163 158 261 150 126 128 148
125 78 153 108 182 137 82 89 109
156 141 157 108 183 149 120 120 105
166 145 166 147 192 199 157 161 147
207 159 98 105 176 141 159 149 81
243 232 270 182 300 197 184 192 201
213 152 128 61 176 142 160 147 1000
YES

Code

Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$  between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

Links&References

e-olymp 7241. Transit

Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

Формат вихідних даних

В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

Вхідні дані Вихідні дані
1 4 7
1 8 6 11
  6
2 10 20
1 8 6 11 16 14 21 10 13 4
  11
3 5 10
12 4 3 6 9
  5
4 6 11
5 8 6 9 4 7
  4
5 2 1
2 2
  1

Код

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.

Посилання

e-olymp 8956. Вывести массив 4

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

Входные данные

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

Выходные данные

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 7
-2 5 4 -3 7 -1 0
3
-1 -3 -2
2 5
2 1 0 1 5
NO
3 3
-1 -2 -3
3
-3 -2 -1

Код программы

Решение задачи

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

e-olymp 2662. Метод минимума

Условие задачи

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

Входные данные

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

Выходные данные

Вывести количество перемещений первого элемента.

Тесты

Ввод Вывод
1 3

1 3 2

0
2 2

2 1

1
3 4

4 1 5 3

3
4 6

23 5 56 2 87 3

1
5 7
15 1 6 3 9 8 13
4

Код программы

Решение

Применяем метод выбора по возрастанию. Для этого мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы. Для того, чтобы найти количество перемещений первого элемента, мы проверяем совпадает ли значение первого элемента со значениями перемещаемых элементов. Также смотрим, чтобы значения этих  элементов не были равны между собой, так как в этом случае сам элемент никуда не сдвигается.

Подробное изложение алгоритма сортировки можно найти в  этой статье .

Ссылки

e-olymp 2663. Сортировка пузырьком

Условие

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

Входные данные

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$$9$.

Выходные данные

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

Ввод Вывод
1 3
1 3 2
1
2 2
2 1
1
3 4
4 1 5 3
3
4 5
5 4 1 100000 7
4
5 6
6 5 4 3 2 1
15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

Код программы

Ссылки

решение на e-olymp
код на ideone

e-olymp 2098. Переворачиватель

Условие

Заданы [latex]n[/latex] чисел. Выведите их в обратном порядке.

Входные данные

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

Выходные данные

Выведите заданные [latex]n[/latex] чисел в обратном порядке.

Тесты

Ввод Вывод
1 7
2 4 1 3 5 3 1
1 3 5 3 1 4 2
2 1
5
5
3 10
1 1 1 9999 5 -1 7 3 0 9
9 0 3 7 -1 5 9999 1 1 1

Код программы

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.

e-olymp 7849. Обменять max и min

Условие задачи

Задан массив из $n$ целых чисел. Замените все наибольшие его элементы на наименьший, а наименьшие элементы на наибольший.

Входные данные

В первой строке записано число $n ( n \leqslant 100 )$. В следующей строке записано $n$ целых чисел, каждое из которых по модулю не превосходит $100$.

Выходные данные

Вывести обновленный массив.

Тесты

Входные данные Выходные данные
1 7
3 5 -7 7 5 -9 -4
3 5 -7 -9 5 7 -4
2 2
1 2
2 1
3 9
12 99 87 42 55 8 65 40 72
12 8 87 55 99 65 40 72
4 8
-9 0 7 -5 2 5 1 -2
7 0 -9 -5 2 5 1 -2

Код

Решение

Для начала нам надо найти максимум и минимум в массиве. Для этого введем переменные максимума и минимума равные  $-100$ и $100$. (Так как элементы массива по условию не должны превышать значения $|100|$ ). Проверяем. Если значение элемента массива больше значения переменной максимума, присваиваем переменной это значение. Аналогично и для минимума. Затем присвоим максимальному элементу массива минимальное, а минимальному — максимальное.

Ссылки

Условие задачи на E-olymp

Код на Ideone

Засчитанное решение на E-olymp

e-olymp 5041. Синтаксический анализ вещественных чисел

Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.

Входные данные

Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.

Выходные данные

Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.

Тесты

Входные данные Выходные данные
1. 2
1.5e+2
3.
LEGAL
ILLEGAL
2. 4
752.45e+24
0.762e.
-0.355.6432e
LEGAL
ILLEGAL
ILLEGAL
3. 1
-652.32e+45
LEGAL
4. 3
542.512e+3
123.456E+42
123.456.789
LEGAL
LEGAL
ILLEGAL

Код

Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 7534. Замкнутое сокровище

Задача взята с сайта e-olymp

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

По имеющимся значениям $n$ и $m$ определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем $m$ бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

Входные данные

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

Выходные данные

Для каждого теста вывести в отдельной строке минимальное количество необходимых замков.

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 4
3 2
5 1
10 7
5 3
3
1
210
10
2 2
5 3
3 2
10
3
3 6
2 1
7 2
3 1
5 4
3 2
9 2
1
7
1
10
3
9

Код программы

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.
Для нахождения биномиальных коэффициентов воспользуемся треугольником Паскаля, который будем хранить в двумерном массиве.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Треугольник Паскаля на Wikipedia

e-olymp 682. Сумма на отрезке

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

Входные данные

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

Выходные данные

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

# Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 5
2 3
3 4
2 5
1 4
15
5
7
14
10
2 10
10 10 10 10 10 10 10 10 10 10
5
1 3
3 5
5 7
7 9
3 7
30
30
30
30
50
3 10
57 42 24 73 98 71 65 76 12 33
7
1 2
4 5
8 10
1 10
7 10
2 5
3 8
99
171
121
551
186
237
407
4 3
10 15 20
2
1 2
1 3
25
45
5 7
299 38924 2388 4399 7549 79475 57947
10
1 3
2 3
3 3
4 7
6 7
3 5
5 5
6 6
1 6
1 7
41611
41312
2388
149370
137422
14336
7549
79475
133034
190981

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 2099. Два массива

Задача

Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

Входные данные

Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает [latex]100[/latex]. Все элементы — целые числа.

Выходные данные

В первой строке выведите количество искомых элементов, а во второй выведите те элементы первого массива, которых нет во втором, в том порядке, в каком они идут в первом массиве.

Тесты

# ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
1 7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
4
3 3 2 12
2 5
12 16 17 45 68
6
1 93 45 68 34 38
3
12 16 17
3 10
15 47 68 59 75 25 35 61 21 86
10
15 47 69 58 75 26 36 61 21 89
5
68 59 25 35 86
4 10
15 47 68 59 75 25 35 61 21 86
10
15 47 68 59 75 25 35 61 21 86
0
0

Код программы

Решение задачи

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

Ссылки

e-olymp 2322. Столбцы

Столбцы

Дана таблица [latex]n × n[/latex], заполненная целыми числами. Петр Первый считает столбец хорошим, если тот содержит число [latex]x[/latex]. Требуется для каждого столбца выяснить, является ли тот хорошим.

Входные данные

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 109. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 109 — числа в ячейках таблицы.

Выходные данные

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1
2
0 1
0 0
NO
YES
2 23
3
23 0 23
21 12 23
11 13 23
YES
NO
YES
3 7
1
0
NO
4 13
3
13 33 75
23 45 31
13 13 13
YES
YES
YES

Код

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

Запустить код (ideone) можно здесь
Задача на E-olymp

e-olymp 8361. Робот

Задача взята с сайта e-olymp

Условие

Движение робота управляется программой. Программа состоит из следующих команд:

  • [latex]S[/latex] — сделать шаг вперед
  • [latex]L[/latex] — повернуться на [latex]90°[/latex] влево
  • [latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

Входные данные

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

Выходные данные

Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

Тесты

Inputs Outputs
1 SSLSLSLSSRSRS 5
2 LSSSS -1
3 LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS 15
4 LLLLLLLL -1
5 SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL 7

Код

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

e-olymp 5057. Спиралька

Задача

Выведите двумерный массив, размерами [latex]n \times n[/latex], заполненный числами от [latex]1[/latex] до [latex]n^2[/latex] по спирали. Числовая спираль начинается в левом верхнем углу и закручивается по часовой стрелке.

Входные данные

Одно число [latex]n (1 \leqslant n \leqslant 10)[/latex].

Выходные данные

Выведите [latex]n^2[/latex] чисел – заполненный по спирали массив.

Тесты

Ввод Вывод
1 1 1
2 2 1 2
4 3
3 3 1 2 3
8 9 4
7 6 5
4 5 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
5 9 1 2 3 4 5 6 7 8 9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17

Код программы

Решение задачи

Все решение задачи сводится к тому, чтобы постепенно заполнять крайние квадраты, «окаймляя» внутренность массива и постепенно сужая диапазон заполнения и длину стороны заполняемого квадрата. В основном цикле вложенными циклами поочередно заполняем строки и столбцы: верхнюю, крайний справа, нижнюю, крайний слева. После «сворачиваем» вправо, когда вложенные циклы заканчиваются и во внешнем(основном) счетчик увеличивается на 1. Полный цикл на n действий делать смысла не имеет в силу того, что, дойдя до половины, массив уже будет полностью заполнен в строках ниже.

Ссылки

e-olymp 5282. Седловые точки

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

Входные данные

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

Выходные данные

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

e-olymp 2666. Половина

Задача

Напишите программу, заполняющую массив [latex]n \times n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

Входные данные

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

Выходные данные

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

Код программы

Решение задачи

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20[/latex]. Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

  • [latex]i + j = n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 7809. Утренняя зарядка

Задача


Утром многие школьники делают танцевальную зарядку. По сложившейся традиции, ученики танцуют в фирменных футболках. За первые три дня изменения школьниками и преподавателями было замечено, что пара, которая танцует в одинаковых футболках, выглядит эстетичнее. Они решили перед началом зарядки сначала поставить пару из детей в одинаковых футболках, а затем с оставшихся. Отличнику Сереже захотелось научиться быстро считать, сколько эстетических пар можно образовать из всех, кто пришел на зарядку.

Входные данные

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9[/latex]. Всего в строке не более, чем [latex]10^6[/latex] чисел.

Выходные данные

В выходной файл нужно вывести единственное число — количество эстетических пар, которые можно сложить.

Тесты

# Входные данные Выходные данные
1 0 3 6 3 0 0 1 2
2 8 8 9 9 7 6 7 8 4 3
3 5 6 7 3 2 0
4 2 7 6 8 9 2 1 1
5 8 7 7 5 4 3 5 4 8 4

Код программы

Решение задачи

Для того, чтобы решить задачу нужно найти количество пар, которые можно составить с заданной последовательности чисел. Для этого создаем массив, состоящий из [latex]10[/latex] элементов, где будем хранить числа, которые означают цвет футболки. Далее будем считывать символы и переводить их в цифры. После прочтения входного потока, найдем числа, из которых можно составить пару,и выведем их количество на экран.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 907. Первый не больший чем 2.5

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

Входные данные

В первой строке задано количество элементов массива [latex]n (0 < n ≤ 100)[/latex]. В следующей строке задано [latex]n[/latex] вещественных чисел.

Выходные данные

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные Выходные данные
[latex]5 \\ 6 \; 7.5 \; 2.1 \; 2.0 \; 0[/latex] [latex]3 \; 2.10[/latex]
[latex]5 \\ 6 \; 7.5 \; 5.1 \; 7.0 \; 80[/latex] [latex]Not \; Found[/latex]
[latex]7 \\ 5 \; 4.7 \; 50 \; 8.9 \; 2.7 \; 3 \; 1.5[/latex] [latex]7 \; 1.5[/latex]

Решение задачи с помощью массивов

Код программы

Решение задачи

Введем обозначения: [latex]x[/latex] – имя массива, [latex]n[/latex] – количество элементов в массиве, [latex]i[/latex] – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести Not Found.

Решение задачи с помощью потоковой обработки

Код программы

Решение задачи

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найдененого первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, выводим на экран Not Found.

Ссылки

Условие задачи на e-olymp
Код решения с помощью массивов на ideone
Код решения с помощью потоковой обработки на ideone

e-olymp 2807. Кубики — 3

Задача

Дома у Витека было [latex]2[/latex] одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Витеку определить, какой же из кубиков отсутствует в одном из наборов.

Входные данные

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

Выходные данные

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

# Входные данные Выходные данные
1 5 abcac b
2 8 ryirhiyh Ok
3 3 AVA V
4 6 DjkjDk Ok
5 7 LnCsCnL s

Код программы

Решение задачи

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.

Ссылки

Ссылка на e-olymp

Ссылка на ideone