e-olymp 685. Сумма на параллелепипеде

10/06/2019 by Никита Шпилевский

Задача

Задана трехмерная таблица чисел [latex]a_{ijt}[/latex], где [latex]1\leq i\leq n[/latex], [latex]1\leq j\leq m[/latex], [latex]1\leq t\leq k[/latex]. Для заданных [latex]l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}[/latex] найдите

[latex]S_{l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}}=\sum\limits_{i=lx,j=ly,t=lz}^{i\leq rx,j\leq ry,t\leq rz}a_{ijt}[/latex]

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

В первой строке записаны размеры таблицы — [latex]n, m, k \left ( 1\leq n, m, k\leq 100 \right )[/latex]. Далее записано [latex]n[/latex] блоков по [latex]m[/latex] строк, в каждой из которых записaно по [latex]k[/latex] чисел [latex]a_{ijt} \left ( 1\leq a_{ijt} \leq 1000 \right )[/latex]. Блоки разделены пустой строкой. В очередной строке записано число [latex]q \left ( 1\leq q\leq 10^{6} \right )[/latex] — количество запросов. В следующих [latex]q[/latex] строках описаны запросы [latex]l_{x_{i}}, l_{y_{i}}, l_{z_{i}}, r_{x_{i}}, r_{y_{i}}, r_{z_{i}}[/latex][latex]\left ( 1 \leq l_{x_{i}} \leq r_{x_{i}} \leq n, 1 \leq l_{y_{i}} \leq r_{y_{i}} \leq m, 1 \leq l_{z_{i}} \leq r_{z_{i}} \leq k \right )[/latex] .

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

Выведите [latex]q[/latex] чисел в отдельных строках — ответы на запросы.

Тесты

№	Входные данные	Выходные данные
1	2 3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 41 2 3 4 5 5 4 3 2 1 2 3 1 5 4 5 1 1 1 1 2 2 1 1 1 2 2 2 1 2 3 2 3 4 1 3 4 2 3 5 1 2 4 2 2 5	12 24 22 18 6

Код

#include <iostream>
using namespace std;
const long long INF = 105;
long long arr[INF][INF][INF];
long long amountArray[INF][INF][INF];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,m,k;
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n; i++){
        for(int j = 1 ; j <= m ; j++){
            for(int z = 1 ; z <= k ; z++){
                cin >> arr[i][j][z];
            }
        }
    }
    for(int i  = 1 ; i <= n; i++){
        for(int j = 1; j <= m ; j++){
            amountArray[i][j][1] = amountArray[i-1][j][1] + 
                amountArray[i][j-1][1] - amountArray[i-1][j-1][1] + arr[i][j][1];
        }
    }
    for(int i  = 1 ; i <= m; i++){
        for(int j = 1; j <= k ; j++){
            amountArray[1][i][j] = amountArray[1][i-1][j] + 
                amountArray[1][i][j-1] - amountArray[1][i-1][j-1] + arr[1][i][j];
        }
    }
    for(int i  = 1 ; i <= n; i++){
        for(int j = 1; j <= k ; j++){
            amountArray[i][1][j] = amountArray[i-1][1][j] + 
                amountArray[i][1][j-1] - amountArray[i-1][1][j-1] + arr[i][1][j];
        }
    }
 
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m ; j++){
            for(int z = 2; z <= k; z++){
                amountArray[i][j][z] = arr[i][j][z] + 
                    amountArray[i-1][j][z] + amountArray[i][j-1][z] - 
                    amountArray[i-1][j-1][z] + amountArray[i][j][z-1] - 
                    amountArray[i-1][j][z-1] - amountArray[i][j-1][z-1] + 
                    amountArray[i-1][j-1][z-1];
            }
        }
    }
    long long q;
    cin >> q;
    while(q--){
        long long x1, y1, z1, x2, y2, z2;
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        x1--;
        y1--;
        z1--;
        cout << amountArray[x2][y2][z2] - amountArray[x2][y2][z1] - 
            amountArray[x2][y1][z2] + amountArray[x2][y1][z1] - 
            amountArray[x1][y2][z2] + amountArray[x1][y1][z2] + 
            amountArray[x1][y2][z1] - amountArray[x1][y1][z1] << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

const long long INF = 105;

long long arr[INF][INF][INF];

long long amountArray[INF][INF][INF];

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

long long n,m,k;

cin >> n >> m >> k;

for(int i = 1 ; i <= n; i++){

for(int j = 1 ; j <= m ; j++){

for(int z = 1 ; z <= k ; z++){

cin >> arr[i][j][z];

}

for(int i = 1 ; i <= n; i++){

for(int j = 1; j <= m ; j++){

amountArray[i][j][1] = amountArray[i-1][j][1] +

amountArray[i][j-1][1] - amountArray[i-1][j-1][1] + arr[i][j][1];

}

for(int i = 1 ; i <= m; i++){

for(int j = 1; j <= k ; j++){

amountArray[1][i][j] = amountArray[1][i-1][j] +

amountArray[1][i][j-1] - amountArray[1][i-1][j-1] + arr[1][i][j];

}

for(int i = 1 ; i <= n; i++){

for(int j = 1; j <= k ; j++){

amountArray[i][1][j] = amountArray[i-1][1][j] +

amountArray[i][1][j-1] - amountArray[i-1][1][j-1] + arr[i][1][j];

}

for(int i = 2; i <= n; i++){

for(int j = 2; j <= m ; j++){

for(int z = 2; z <= k; z++){

amountArray[i][j][z] = arr[i][j][z] +

amountArray[i-1][j][z] + amountArray[i][j-1][z] -

amountArray[i-1][j-1][z] + amountArray[i][j][z-1] -

amountArray[i-1][j][z-1] - amountArray[i][j-1][z-1] +

amountArray[i-1][j-1][z-1];

}

long long q;

cin >> q;

while(q--){

long long x1, y1, z1, x2, y2, z2;

cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;

x1--;

y1--;

z1--;

cout << amountArray[x2][y2][z2] - amountArray[x2][y2][z1] -

amountArray[x2][y1][z2] + amountArray[x2][y1][z1] -

amountArray[x1][y2][z2] + amountArray[x1][y1][z2] +

amountArray[x1][y2][z1] - amountArray[x1][y1][z1] << "\n";

}

return 0;

}

Решение

Создаем массивы arr — массив элементов исходной матрицы, и amountArray — массив количества элементов «на префиксе». В первой тройке вложенных циклов for заполняем массив arr. Затем в трех парах вложенных массивов заполняем соответственно первый «этаж» матрицы amountArray, первую строку и первый столбец всех «этажей». Далее, в тройке вложенных циклов for заполняем оставшиеся элементы массива. После, читаем запросы и выводим ответы.

Ссылки

- Задача на e-olymp
- Решение на ideone

Related Images:

e-olymp 8173. Большинство

04/05/2019 by Никита Шпилевский

Задача

Голоса собраны! Были опрошены математики по всему миру, и каждый из них выбрал свой любимый номер между [latex]1[/latex] и [latex]1000[/latex]. Ваша цель — подсчитать голоса и определить самый популярный номер.

Если существует несколько голосов с наибольшим количеством, то выберите наименьшее число с максимальным количеством голосов.

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

Первая строка содержит количество тестов, от [latex]1[/latex] до [latex]100[/latex] включительно. Первая строка каждого теста содержит количество голосов [latex]V (1 \leq V \leq 1000)[/latex], за которой следуют [latex]V[/latex] строк — каждая из них содержит одно число от [latex]1[/latex] до [latex]1000[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	2 3 42 42 19 4 7 99 99 7	42 7
2	1 5 11 12 13 14 15	11
3	2 2 1000 1000 1 3	1000 3

Код

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int testAmount, V, digit, numberOfMax, max, maxDigit, answer;
    cin >> testAmount;
    for(int i = 0; i < testAmount; i++) {
        int digitAmountArray[1001] = {};
        maxDigit = 0;
        answer = 0;
        cin >> V;
        for (int k = 0; k < V; k++) {
            cin >> digit; 
            if(digit > maxDigit) maxDigit = digit;
            digitAmountArray[digit]++;
        }

        max = digitAmountArray[0];
        for (int p = 1; p <= maxDigit; p++) {
            if(digitAmountArray[p] > max) {
                max = digitAmountArray[p];
                numberOfMax = p;
            }
        } 
        for(int l = 0; l <= maxDigit; l++) {
            if(digitAmountArray[l] == digitAmountArray[numberOfMax]) {
                answer = min(numberOfMax, l); 
            }   
        }
        cout << answer << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int testAmount, V, digit, numberOfMax, max, maxDigit, answer;

cin >> testAmount;

for(int i = 0; i < testAmount; i++) {

int digitAmountArray[1001] = {};

maxDigit = 0;

answer = 0;

cin >> V;

for (int k = 0; k < V; k++) {

cin >> digit;

if(digit > maxDigit) maxDigit = digit;

digitAmountArray[digit]++;

}

max = digitAmountArray[0];

for (int p = 1; p <= maxDigit; p++) {

if(digitAmountArray[p] > max) {

max = digitAmountArray[p];

numberOfMax = p;

}

for(int l = 0; l <= maxDigit; l++) {

if(digitAmountArray[l] == digitAmountArray[numberOfMax]) {

answer = min(numberOfMax, l);

}

cout << answer << endl;

}

return 0;

}

Решение

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

Ссылки

- Задача на e-olymp
- Решение на e-olymp

Related Images:

e-olymp 518. Сумма двух

14/03/2019 by Никита Шпилевский

Задача

Найти сумму двух чисел.

Входные данные
Первая строка содержит количество тестов [latex]t (1\leq t\leq 100)[/latex]. Каждый тест состоит из двух целых чисел [latex]a[/latex] и [latex]b[/latex].

Выходные данные
Для каждого теста вывести в отдельной строке сумму чисел [latex]a[/latex] и [latex]b[/latex].

Тесты

№

Ввод

Вывод

2 3

17 -18

5 6

-1

Код

#include <iostream>
using namespace std;

int main() {
    short t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short t;

cin >> t;

while(t--) {

int a, b;

cin >> a >> b;

cout << a + b << endl;

}

return 0;

}

Решение

Считываем количество тестов, в цикле считаем каждый тест и выводим ответы.

Ссылки

- Задача на e-olymp
- Решение на e-olymp

Related Images:

e-olymp 3766. Тысячелетие

25/12/2018 by Никита Шпилевский

Задача

Мудрый король решил ввести новый календарь. «Завтра будет первый день календаря, то есть день [latex]1[/latex] месяца [latex]1[/latex] года [latex]1[/latex]. Каждый год состоит из [latex]10[/latex] месяцев, с [latex]1[/latex] по [latex]10[/latex], и начинается с большого месяца. Обычный год начинается с большого месяца, за которым следует малый месяц, затем большой месяц и так далее один за другим. То есть первый месяц большой, второй малый, третий большой, …, десятый, он же последний, малый. Большой месяц состоит из [latex]20[/latex] дней, а малый месяц из [latex]19[/latex] дней. Однако годы, кратные трем, то есть год [latex]3[/latex], год [latex]6[/latex], год [latex]9[/latex] и так далее, состоит из [latex]10[/latex] больших месяцев и ни одного малого.»

Много времени прошло со дня введения календаря, и для празднования дня тысячелетия [latex]([/latex]год [latex]1000[/latex], месяц [latex]1[/latex], день [latex]1[/latex][latex])[/latex] решено было организовать королевскую лотерею, победителями которой станут те, кто прожил столько же дней, какое число выпадет в лотерее. Напишите программу, которая поможет людям вычислить количество дней от их дня рождения до дня тысячелетия.

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

Входные данные имеют следующий формат:

n
Y₁ M₁ D₁
Y₂ M₂ D₂
…
Y_n M_n D_n

Первая строка задает количество тестов [latex]n, \left ( n \leq 100 \right )[/latex]. Далее следуют n тестов, каждый из которых представляет собой одну строку с тремя натуральными числами [latex]Y_{i}\left ( Y_{i}< 1000 \right ), M_{i} \left ( M_{i}< 10 \right )[/latex] и [latex]D_{i} \left ( D_{i}\leq 20 \right )[/latex], задающих соответственно год, месяц и день рождения некоторого человека в нотации королевского календаря.

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

Для каждой даты рождения следует вывести в отдельной строке количество дней, прошедших со дня рождения (включительно) до дня тысячелетия (не включительно).

Тесты

№	Ввод	Вывод
1	2 1 1 1 344 3 1	196470 128976
2	3 696 5 1 182 9 5 998 8 7	59710 160715 252
3	2 344 2 19 696 4 19	128977 59712
4	1 999 10 20	1

Код

#include <iostream>
using namespace std;

int main() {
    short n;
    int  Y, M, D, daysAmount;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D); 
        else{
            if(M % 2 == 0) daysAmount += (smallMonth - D); 
            else daysAmount += (bigMonth - D);
            for(int month = (M + 1); month <= 10; month++) {
                if(month % 2 == 0) daysAmount += smallMonth;
                else daysAmount += bigMonth;
            }
        }
        for(int year = (Y + 1); year < 1000; year++) {
            if((year % 3) == 0) daysAmount += bigYear;
            else daysAmount += smallYear;
        }
        cout << daysAmount + 1 << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

for(int i = 0; i < n; i++) {

daysAmount = 0;

cin >> Y >> M >> D;

if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D);

else{

if(M % 2 == 0) daysAmount += (smallMonth - D);

else daysAmount += (bigMonth - D);

for(int month = (M + 1); month <= 10; month++) {

if(month % 2 == 0) daysAmount += smallMonth;

else daysAmount += bigMonth;

}

for(int year = (Y + 1); year < 1000; year++) {

if((year % 3) == 0) daysAmount += bigYear;

else daysAmount += smallYear;

}

cout << daysAmount + 1 << endl;

}

return 0;

}

Решение

Запишем большой месяц (20 дней) и малый месяц (19 дней) соответственно в константы bigMonth и smallMonth, а также большой год (200 дней) и малый год (195 дней) соответственно в bigYear и smallYear. Затем проходим по циклу for n раз. Проверяем, если год, в котором родился человек, кратен 3, считаем количество полных прожитых человеком месяцев (каждый месяц — 30 дней) первого после рождения года, а также дни месяца, в котором он родился. В противном случае ( else) прибавляем дни каждого полного месяца, проверяя, большой он, и малый. Затем добавляем дни первого прожитого человеком месяца, так же учитывая его длительность. После этого проходим по циклу for, начальной итерацией которого является ( Y + 1), потому что дни года рождения мы посчитали ранее. За каждый год, номер которого кратен 3, добавляем 200 дней, а за некратный — 195. В конце выводим количество полученных дней +1, так как должны посчитать их количество включительно с днем рождения.

#include <iostream>
using namespace std;
 
int main() {
    short n;
    int  Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        lifeYears = 1000 - (Y + 1);
        if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;
        else multipleThree = lifeYears / 3;
        if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;
        notMultipleThree = lifeYears - multipleThree;
        daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;
        if(Y % 3 == 0) {
              daysAmount += (10 - M) * bigMonth;
              daysAmount += bigMonth - D;
        }
        else {
            if(M % 2 != 0) {
                daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;
                daysAmount += (bigMonth - D);
            }
            else {
                daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);
                daysAmount += (smallMonth - D);
            }
        }
        cout << daysAmount + 1<< endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

for(int i = 0; i < n; i++) {

daysAmount = 0;

cin >> Y >> M >> D;

lifeYears = 1000 - (Y + 1);

if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;

else multipleThree = lifeYears / 3;

if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;

notMultipleThree = lifeYears - multipleThree;

daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;

if(Y % 3 == 0) {

daysAmount += (10 - M) * bigMonth;

daysAmount += bigMonth - D;

}

else {

if(M % 2 != 0) {

daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;

daysAmount += (bigMonth - D);

}

else {

daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);

daysAmount += (smallMonth - D);

}

cout << daysAmount + 1<< endl;

}

return 0;

}

Решение

Снова проходим по циклу for n раз. Однако, теперь считаем дни без помощи циклов. В переменную lifeYears записываем годы жизни -1 , так как дни года рождения мы посчитаем далее. Затем, в if проверяем, находится ли количество прожитых лет в диапазоне от 1 до 3. Если да, то в переменную multipleThree записываем 1 — количество лет, кратных трем, то есть 999 год. В else multipleThree приравниваем к lifeYears, деленую на 3. В следующем if проверяем, больше ли количество лет трех. Если да, прибавляем 5 дней за больший 999 год. Затем, в переменную notMultipleThree записываем количество лет, не кратных трем. В следующей строке прибавляем ко дням жизни годы, умноженные на соответствующие им количества в каждом. После, в if проверяем, кратен ли год рождения 3. Если да, Находим количество полных прожитых месяцев, и умножаем его на bigMonth. Далее, находим дни, прожитые в месяц рождения. В else проверяем, родился ли человек в нечетном месяце. Если да, добавляем к дням количество дней, вычисляющееся по формуле, записанной в коде, если нет — аналогично. В конце, выводим количество дней +1, так как должны посчитать их количество включительно с днем рождения.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Никита Шпилевский

e-olymp 685. Сумма на параллелепипеде

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

e-olymp 8173. Большинство

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

e-olymp 518. Сумма двух

Задача

Тесты

Код

Решение

Ссылки

Related Images:

e-olymp 3766. Тысячелетие

Задача

Тесты

Код

Решение

Решение

Ссылки

Related Images: