e-olymp 4749. Выручка театра

Задача

В театре [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

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

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

Описываем целочисленный одномерный массив 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].

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

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

По условию заданы количество строк [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 (код с многомерными массивами)

e-olymp 2375. Квартира

Задача

Вы являетесь одним из разработчиков программного обеспечения для агентства недвижимости. Вам следует реализовать различные статистические функции для квартир, которые продает агентство. Каждая квартира состоит из различных типов комнат: спальня, ванная комната, кухня, балкон и другие. Стоимость квартиры равна произведению уменьшенной общей площади и стоимости одного квадратного метра. Уменьшенной общей площадью считается общая площадь всех помещений кроме балконов плюс половина площадей всех балконов.
Вам будет предоставлена информация о площади каждой комнаты в квартире и стоимость одного квадратного метра. Необходимо рассчитать следующие значения для квартиры:

  • общую площадь комнат;
  • общую площадь всех спален;
  • стоимость квартиры.

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

Первая строка содержит два целых числа [latex]n [/latex] [latex](1 \leqslant n \leqslant 10)[/latex] и [latex]c[/latex] [latex](1 \leqslant c \leqslant 100000)[/latex] — количество комнат в квартире и стоимость квадратного метра соответственно. Каждая из следующих [latex]n[/latex] строк содержит целое число [latex]a_i (1 \leqslant a_i \leqslant 100)[/latex] и слово [latex]t_i[/latex] — площадь [latex]i[/latex]-ой комнаты и ее тип соответственно. Слово [latex]t_i[/latex] может содержать только одно из следующих значений: [latex] «bedroom»[/latex], [latex] «bathroom»[/latex], [latex] «kitchen»[/latex], [latex] «balcony»[/latex], [latex] «other»[/latex].

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

Первая строка содержит одно целое число — общую площадь всех комнат квартиры. Вторая строка содержит одно целое число — общую площадь всех спален в квартире. Третья строка содержит одно действительное число — стоимость квартиры с точностью не больше [latex]10^{-6}[/latex].

Следующий рисунок отображает план квартиры, заданной в первом примере.

Тесты

Входные данные Выходные данные
1 6 75000 46
8 other 16
3 bathroom 3187500.000000
2 bathroom
10 kitchen
16 bedroom
7 balcony
2 2 75123 25
10 kitchen 0
15 balcony 1314652.500000
3 4 110000 41
7 other 18
4 bathroom 4510000.000000
12 kitchen
18 bedroom

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

Считываем данные из потока. При этом используем цикл for(int i=1; i=n; i++). Общую площадь квартиры рассчитываем по формуле S += ai. Площадь спален вычисляем по формуле Ss += ai, учитывая, что ti=="bedroom". Для дальнейшего вычисления стоимости квартиры вычисляем площадь балконов по формуле Sb += ai, учитывая, что ti=="balcony". Стоимость квартиры рассчитываем по формуле Ck=(S-Sb/2.)*c.

Ссылки

e-olymp
ideone

Коды Грея

Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex]
[latex]1[/latex]
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex]
[latex]01[/latex]
[latex]11[/latex]
[latex]10[/latex]
Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex]
[latex]001[/latex]
[latex]011[/latex]
[latex]010[/latex]
[latex]110[/latex]
[latex]111[/latex]
[latex]101[/latex]
[latex]100[/latex]
При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

Входные данные Выходные данные
1 3 2
14 9
5 7
12 10
2 0 0
72 108
265 397
4781 7163
50642 42811
3 1010234 581415
96721758 119682801
640214927 893162568
2456987013 3679188807
51027963402 60418988303
1000000000000000000 797398725282889728

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

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

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

e-olymp 944. Площадь пирамиды

Задача

Треугольная пирамида задана координатами своих вершин [latex] A(x_1; y_1; z_1), [/latex] [latex] B(x_2; y_2; z_2), [/latex] [latex] C(x_3; y_3; z_3), [/latex] [latex] S(x_4; y_4; z_4). [/latex] Определить площадь полной поверхности пирамиды.

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

В четырех строках заданы координаты [latex] x, y, z [/latex] вершин пирамиды. Все числа целые, не превышающие по модулю 100.

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

Вывести полную поверхность пирамиды с точностью до десятых.

Тесты

Входные данные Выходные данные
1 -3 0 0 69,8
0 6 0
3 0 0
0 2 5
2 2 4 8 159,1
2 -6 9
5 -4 0
1 3 0
3 5 0 1 107,3
4 1 7
-9 0 4
6 2 8

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

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

Для того, чтобы найти площадь полной поверхности пирамиды, необходимо найти площади треугольников, которые являются гранями пирамиды.
Для нахождения площади треугольника можно воспользоваться формулой Герона: [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)} [/latex],где [latex] p [/latex]-полупериметр треугольника, [latex] a,b,c [/latex] — стороны треугольника. Чтобы воспользоваться формулой Герона, необходимо предварительно найти длины сторон треугольников, используя формулу нахождения длин отрезков по координатам концов отрезка: [latex] |AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2} [/latex], где [latex] А,В [/latex] — концы отрезка, [latex] x_a, y_a,z_a [/latex] — координаты [latex] А [/latex], [latex] x_b, y_b,z_b [/latex] — координаты [latex] В [/latex].
Найденные площади всех треугольников, из которых состоит пирамида, складываем и получаем искомую площадь полной поверхности пирамиды.

Ссылки

e-olymp
ideone