e-olymp 1484. Серебрянная матрица

13/07/2018 by Данилов Андрей

Задача

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

Размеры матрицы [latex]n\times n[/latex].
Все элементы матрицы лежат во множестве [latex]S = [/latex]{[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Для каждого целого числа [latex]i \left(1 ≤ i ≤ n\right),[/latex] все элементы [latex]i[/latex]-ой строки и [latex]i[/latex]-го столбца образуют множество {[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Например, следующая матрица размера [latex]4×4[/latex] является серебряной:

1	2	5	6
3	1	7	5
4	6	1	2
7	4	3	1

Доказано, что серебряная матрица размером [latex]2^K\times 2^K[/latex] всегда существует. Вам следует построить серебряную матрицу [latex]2^K\times 2^K[/latex].

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

Единственное число [latex]K \left(1 ≤ K ≤ 9\right).[/latex]

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

Вывести серебряную матрицу размером [latex]2^K×2^K[/latex]. Для вывода матрицы [latex]2^K\times 2^K[/latex], следует вывести [latex]2^K[/latex] строки, каждая из которых содержит [latex]2^K[/latex] целых чисел.

Тесты

#	Входные данные	Выходные данные
1	2	3 1 7 5 4 6 1 2 7 4 3 1
2	1	1 2 3 1
3	3	1 2 5 6 9 10 13 14 3 1 7 5 11 9 15 13 4 6 1 2 12 14 9 10 7 4 3 1 15 12 11 9 8 10 13 14 1 2 5 6 11 8 15 13 3 1 7 5 12 14 8 10 4 6 1 2 15 12 11 8 7 4 3 1

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

#include <iostream>
using namespace std;

void create(int** x, int k) {
  if (k == 1) {
    x[0][0] = 1;
    x[0][1] = 2;
    x[1][0] = 3;
    x[1][1] = 1;
  } else {
    create(x, k - 1);
    int from = 1 << (k - 1), n = 1 << k;
    for (int i = from; i < n; i++)
      for (int j = from; j < n; j++)
        x[i][j] = x[i - from][j - from];
    for (int i = 0; i < from; i++)
      for (int j = 0; j < from; j++) {
        x[i + from][j] = x[i][j] + n;
        x[i][j + from] = x[i][j] + n;
      }
    for (int i = 0; i < from; i++)
      x[i + from][i]--;
  }
}

int main() {
  int k, n = 1;
  scanf("%d", &k);
  n <<= k;
  int** x = new int*[n];
  for (int i = 0; i < n; i++)
    x[i] = new int[n];
  create(x, k);
  for (int i = 0; i < n; i++) {
    printf("%d", x[i][0]);
    for (int j = 1; j < n; j++)
      printf(" %d", x[i][j]);
    printf("\n");
  }
  return 0;
}

#include <iostream>

using namespace std;

void create(int** x, int k) {

if (k == 1) {

x[0][0] = 1;

x[0][1] = 2;

x[1][0] = 3;

x[1][1] = 1;

} else {

create(x, k - 1);

int from = 1 << (k - 1), n = 1 << k;

for (int i = from; i < n; i++)

for (int j = from; j < n; j++)

x[i][j] = x[i - from][j - from];

for (int i = 0; i < from; i++)

for (int j = 0; j < from; j++) {

x[i + from][j] = x[i][j] + n;

x[i][j + from] = x[i][j] + n;

}

for (int i = 0; i < from; i++)

x[i + from][i]--;

}

int main() {

int k, n = 1;

scanf("%d", &k);

n <<= k;

int** x = new int*[n];

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

x[i] = new int[n];

create(x, k);

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

printf("%d", x[i][0]);

for (int j = 1; j < n; j++)

printf(" %d", x[i][j]);

printf("\n");

}

return 0;

}

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

Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая [latex]k = 1[/latex] подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю [latex]k = 1[/latex] и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.

Ссылки

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

Related Images:

e-olymp 54. Мурзик

27/06/2018 by Данилов Андрей

Задача

Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является исключением! Но если он чрезвычайно активен днем – то точно так же крепко спит ночью. Причем несчастный хищник видит преимущественно кошмары…

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [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

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

#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;
}

#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

Related Images:

e-olymp 8287. Петро підприємець

14/01/2018 by Данилов Андрей

Задача

Петро приватний підприємець і він продає різні цукерки. Петро помітив, що деякі цукерки шалено популярні, а інші взагалі не користуються попитом.

В голові приватного підприємця виникла ідея зробити асорті (змішати два види цукерок — популярні і не популярні). Взявши різну масу кожного виду цукерок Петро отримав асорті вартість [latex]1[/latex] кг якого [latex]A[/latex] грн.

Знаючи, що популярні цукерки коштують [latex]P[/latex] грн/кг а не популярні [latex]N[/latex] грн/кг, а також значення [latex]А[/latex], знайдіть скільки грам популярних цукерок в асорті.

Вихідні дані

Три дійсних числа [latex]P[/latex], [latex]N[/latex], [latex]А[/latex] ціна [latex]1[/latex] кг різних видів цукерок, що входять до складу асорті, та ціна асорті.

Вхідні дані

Одне дійсне число округлене до десятих — кількість грамів популярних цукерок в асорті, або [latex]-1[/latex] якщо визначити не можливо.

Тести

#	вхідні дані	вихідні дані
1	100 50 75	500.00
2	100 100 5	-1
3	50 25 20	-1
4	50 30 30	0.0

Код програми

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

int main() {
    double A,P,N;
    cin >> P >> N >> A;
    double res = (A-N) / (P-N) * 1000;
    if (res >= 0 && P != N) cout <<fixed <<setprecision(1)<< res;
    else cout << -1;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double A,P,N;

cin >> P >> N >> A;

double res = (A-N) / (P-N) * 1000;

if (res >= 0 && P != N) cout <<fixed <<setprecision(1)<< res;

else cout << -1;

return 0;

}

Рішення завдання

За умовою завдання у нас єдине невідоме це кількість популярних цукерок в асорті. 1 кг = 1000 г. Таким чином складаємо рівняння з одним невідомим і отримуємо [latex]1000(A-N) / (P-N)[/latex].

Посилання

Посилання на e-olymp
Посилання на ideone

Related Images:

e-olymp 5868. A xor B

26/12/2017 by Данилов Андрей

Задача

На стандартный вход подаются 2 натуральных числа [latex]A[/latex] и [latex]B[/latex]. Выведите на стандартный вывод результат применения к ним операции побитового исключающего или.

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

2 натуральных числа [latex]A, B ≤ 10^9[/latex] в десятичной системе счисления, разделённые пробелом.

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

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

Тесты

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

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

#include <iostream>
using namespace std;

int main() {
    int a,b;
    cin >> a >>b;
    int c = a^b;
    cout << c << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a,b;

cin >> a >>b;

int c = a^b;

cout << c << endl;

return 0;

}

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

Введем два числа и применим операцию исключающего или.В языке программирования С++ данная операция выглядим так как показано в коде программы.

Ссылки

e-olymp
ideone

Related Images:

e-olymp 7365. Молоко и пирожок

16/12/2017 by Данилов Андрей

Задача

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее [latex]30[/latex] кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость [latex]200[/latex] мл, а упаковки молока – [latex]0,9[/latex] л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

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

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

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

Тесты

#	Входные данные	Выходные данные
1	4 30 36 29 47	1 1
2	5 30 36 29 47 26	1 2
3	8 30 36 29 47 26 27 30 31	1 3
4	1 29	1 1
5	5 26 27 28 29 25	2 5

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

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

int main() {
    double children ; double cakes = 0 ; double milk = 0; double child ;
    cin >> children ;
    while ( cin >> child) {
        if ( child < 30) {
            cakes++; milk += 2;
        }
    }
    cout << ceil(milk/9) << " " << cakes;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double children ; double cakes = 0 ; double milk = 0; double child ;

cin >> children ;

while ( cin >> child) {

if ( child < 30) {

cakes++; milk += 2;

}

cout << ceil(milk/9) << " " << cakes;

return 0;

}

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

По условию задачи мы должны узнать сколько нужно упаковок молока и штук пирожков для детей.Для пирожков мы заводим счетчик, который увеличивает на единицу, если появился подходящий ребенок.А для молока будем использовать целые числа (0,2 домножим на 10 и 0,9 также домножим на 10).И будем считать сколько всего тратится молока,затем поделим на 9 и узнаем сколько пачек молока нужно,так как могут быть на выходе не целые числа,то округляем вверх.

Ссылки

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

Related Images:

e-olymp 442. Построения

29/11/2017 by Данилов Андрей

Задача

Иван Петрович преподает в школе физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из [latex]N[/latex] человек. Иван Петрович выяснил, что если [latex]N[/latex]– простое число, то получается только [latex]2[/latex] построения: в колонну по одному ([latex]1[/latex]×[latex]N[/latex]) и в шеренгу ([latex]N×1[/latex]). Эти тривиальные построения возможны для любого [latex]N[/latex] > [latex]1[/latex] (для [latex]N = 1[/latex] существует только одно построение ([latex]1×1[/latex]), которое не является ни шеренгой, ни колонной). Если [latex]N[/latex] – составное число, то существует и другие нетривиальные построения. Для [latex]100[/latex] человек существует девять построений: ([latex]1×100[/latex]), ([latex]2×50[/latex]), ([latex]4×25[/latex]), ([latex]5×20[/latex]), ([latex]10×10[/latex]), ([latex]20×5[/latex]), ([latex]25×4[/latex]), ([latex]50×2[/latex]) и ([latex]100×1[/latex]).

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

В первой строке ввода содержится одно целое число [latex]N[/latex] (1 ≤[latex]N[/latex]≤ 109).

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

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

Тесты

#	Входные данные	Выходные данные
1	100	9
2	1	1
3	6	4
4	999983	2
5	2	2

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

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

int main () { 
    int NumberOfPeople;
    cin >> NumberOfPeople;
    if(NumberOfPeople == 1){
        cout << 1;
        return 0;
    } 
    else
    {
          int deviders = 0;
          for(int i = 1; i < sqrt(NumberOfPeople);i++){
                if(NumberOfPeople % i == 0) deviders++; // проверка на делимость
    }
    deviders *= 2;
    int Root = sqrt(NumberOfPeople);
    if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость
    cout << deviders;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

int NumberOfPeople;

cin >> NumberOfPeople;

if(NumberOfPeople == 1){

cout << 1;

return 0;

}

else

{

int deviders = 0;

for(int i = 1; i < sqrt(NumberOfPeople);i++){

if(NumberOfPeople % i == 0) deviders++; // проверка на делимость

}

deviders *= 2;

int Root = sqrt(NumberOfPeople);

if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость

cout << deviders;

}

return 0;

}

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

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

Ссылки

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