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

e-olymp 4496. Приключение Незнайки и его друзей

Задача с сайта e-olymp.com.

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

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

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

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

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 4
2 1 10
1 4
2
0
3 2
999999999 1000000000
4
1 999999999
2 1 1000000000
1 999999999
1 1000000000
1
0
1

Код на C++

Код на Java

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

A302. Количество различных цифр числа в его десятичной записи

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные Выходные данные
[latex]N[/latex] [latex]sum[/latex]
12345678900987654321 sum:10
302 sum:3

Код программы с использованием deque

 

Решение

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

Код программы с использованием массива

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).