OCPC2021. Задача A. Колёса деда Панаса (код решения)

20/01/2024 by Александр Мармалюк

Условие

Дед Панас, постоялец палаты номер 17 заведения «Покосившийся Скворечник», срочно должен был принять свои таблетки умиротворения. К сожалению, нянечка рассыпала их по столу и теперь дед Панас твёрдо уверен, что он – Генри Форд, а на столе лежат колёса, из которых нужно собирать автомобили и мотоциклы. Сосед деда Панаса, дед Архип, также не дождавшийся своих таблеток, убеждён, что он – Блез Паскаль, и, заметив, что колёс на столе четное количество, донимает нянечку вопросом: «Сколькими способами можно распределить эти колёса между автомобилями и мотоциклами так, чтобы не оставалось лишних?» Поскольку дед Архип не уймётся, пока не получит ответа, и будет мешать нянечке собирать таблетки со стола, на помощь позвали вас и просят подсказать ей правильный ответ.

На ввод поступает единственное целое четное число $n$ $(2 \leqslant n \leqslant 10^9)$ – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно $4$ колеса, для мотоцикла – $2$. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Тесты

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

6	2
2	1
12	4
1000000000	250000001

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << ((n / 4) + 1);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << ((n / 4) + 1);

return 0;

}

Решение

Некоторое количество колёс уходит на автомобили, а все остальные — на мотоциклы. Тогда заметим, что каждому способу разделить колёса между автомобилями и мотоциклами соответствует количество автомобилей, которые используются в этом разделении. Всего мы можем взять от $0$ до $\frac{n}{4}$ автомобилей включительно (целочисленное деление).

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Related Images:

e-olymp 1704. Умная черепашка

23/01/2020 by Виктория Крачилова

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (m > n) swap(n, m);
    long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
    for (int i = 0; i < m - 1; i++) {
        ways *= n + i;
        if (ways % den == 0) {
            ways /= den;
            den++;
        }
    }
    cout << ways;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

if (m > n) swap(n, m);

long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

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

ways *= n + i;

if (ways % den == 0) {

ways /= den;

den++;

}

cout << ways;

return 0;

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Код программы (динамическое программирование)

#include <iostream>
#define N 30
int main() {
    // Создаем треугольную матрицу для хранения всех ответов
    long *x[N];
    for (int i=0; i < N; ++i) x[i] = new long[i+1];
    // Находим все ответы
    x[0][0] = 1;
    for (int i=1; i < N; ++i) {
        x[i][0] = 1;
        for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
        x[i][i] = 2 * x[i][i-1];        
    }
    // Проходим все тесты
    int m, n; 
    std::cin >> m >> n;
    std::cout << x[std::max(n,m)-1][std::min(n,m)-1];
}

#include <iostream>

#define N 30

int main() {

// Создаем треугольную матрицу для хранения всех ответов

long *x[N];

for (int i=0; i < N; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

int m, n;

std::cin >> m >> n;

std::cout << x[std::max(n,m)-1][std::min(n,m)-1];

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (циклы)

Ссылки (динамическое программирование)

Related Images:

e-olymp 1290. Номерной знак

20/12/2019 by Таня Осипенко

Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $A$ арабских цифр и $B$ больших букв латинского алфавита. Будем считать, что для обеспечения уникальности номера разрешено использовать любую последовательность букв и цифр.

Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

№	Входные данные	Выходные данные
1	3 3	17576000
2	2 5	67600000
3	7 1	80318101760
4	1 1	260
5	26 26	615611958020715731079667428840020377600000000000000000000000000

Код

#include <iostream>
#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел 
  for (int i = n - 1; i >= 0; i--) {
    cout << (int) x[i];
  }
}
int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел
  memset(z, 0, n + m); // обнуляем массив
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      char w = x[j] * y[i] + z[i + j];
      z[i + j + 1] += w / 10;
      z[i + j] = w % 10;
    }
  }
  int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); //  кол-во разрядов
  return res;
}
const int N = 100; // кол-во элементов массивов с небольшим запасом
char acc[N] = {1};
int acc_size = 1;
char tmp[N] = {0};
char v_26[] = {6, 2}; // 26

int main() {
  int A, B; // входные данные
  cin >> B >> A;
  for (int i = 0; i < B; i++) { // возведение 26 в степень B
    memcpy(tmp, acc, acc_size);
    acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26
  }
  print(acc, acc_size); // вывод результата
  for (int i = 0; i < A; i++){ // домножение на 10 в степени A
    cout << "0";
  }
  return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел

for (int i = n - 1; i >= 0; i--) {

cout << (int) x[i];

}

int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел

memset(z, 0, n + m); // обнуляем массив

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

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

char w = x[j] * y[i] + z[i + j];

z[i + j + 1] += w / 10;

z[i + j] = w % 10;

}

int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); // кол-во разрядов

return res;

}

const int N = 100; // кол-во элементов массивов с небольшим запасом

char acc[N] = {1};

int acc_size = 1;

char tmp[N] = {0};

char v_26[] = {6, 2}; // 26

int main() {

int A, B; // входные данные

cin >> B >> A;

for (int i = 0; i < B; i++) { // возведение 26 в степень B

memcpy(tmp, acc, acc_size);

acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26

}

print(acc, acc_size); // вывод результата

for (int i = 0; i < A; i++){ // домножение на 10 в степени A

cout << "0";

}

return 0;

}

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

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

Related Images:

e-olymp 3873. Счастливый номер

19/12/2019 by Валентин Цушко

Условие

Подавляющее большинство людей стараются найти закономерности, которые приносят удачу! Зуб акулы в ухе папуаса — к удачной рыбной ловле. Черная кошка, которая передумала перебегать вам дорогу — к отмене контрольной. Любимая игрушка у компьютера — к удаче в командном чемпионате по программированию.

Для большинства студентов несомненным является тот факт, что номер трамвайного билетика приносит удачу. А уж если такой билетик достался перед экзаменом, пятерка обеспечена! Главное тут — четко понимать, что такое счастливый билет. И почему, спрашивается, многие считают, что только номер автобусного или троллейбусного билета может приносить удачу своему владельцу?! Чем хуже, скажем, номер паспорта или номер кассового чека в гастрономе? Главное, чтобы номер был счастливым!

Витька всегда считал, что удачу приносят такие номера, в записи которых цифры идут в неубывающем порядке. Например, счастливыми являются номера $11111$ или $12345$. Даже номер $00000$ — тоже счастливый!

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

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

Входной файл содержит единственное целое число $N$, $(1 \leq N \leq 64)$, $N$ — длина числа, для которой нужно вычислить количество счастливых номеров.

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

Вывести одно число — количество счастливых номеров.

Тесты

№	Входные данные	Выходные данные
1	2	55
2	4	715
3	3	220

Программный код

#include "iostream"
using namespace std;

long long int factorial(int n){
    long long int a = 1;
    for (int i = (n + 9); i > n; i--) a = a * i;  // мы сократили, чтобы не пришлось делить огромные числа
    return a;
}

int main()
{
    int n;
    cin >> n;
    long long int fact = 1;
    for (int i = 2; i <= 9; i++) fact = fact * i;
    cout << (factorial(n) / fact);

    return 0;
}

#include "iostream"

using namespace std;

long long int factorial(int n){

long long int a = 1;

for (int i = (n + 9); i > n; i--) a = a * i; // мы сократили, чтобы не пришлось делить огромные числа

return a;

}

int main()

{

int n;

cin >> n;

long long int fact = 1;

for (int i = 2; i <= 9; i++) fact = fact * i;

cout << (factorial(n) / fact);

return 0;

}

Решение

Для того, чтобы решить эту задачу, я начертил таблички (рис. 1.1) для всех вариантов $2$ значного числа и $1$ значного (рис. 1.2). Для $3$ значного аналогично, только рядов будет $3$. Из комбинаторики мы помним формулу: $C_n^m=\frac{n!}{m!(n-m)!}$, из которой мы получим: $(n + 9)! \over {9! \times n!}$. Потому-что из картинки мы видим что при 1 значном числе количество вариантов равно $10$. В коде я сразу сокращал на $n!$, чтобы не получались огромные числа.

рис 1.1

рис 1.2

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 1327. Ладьи на шахматной доске

14/12/2019 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

Программный код

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

for (int i = 0; i < s.size(); i++) {

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

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

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

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

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = x.size() - 1; i >= 0; i--) {
    temporary = int(x[i] - '0') * y + carry;
    carry = temporary / 10;
    answer = char(temporary % 10 + '0') + answer;
}
while (carry) {
    answer = char(carry % 10 + '0') + answer;
    carry /= 10;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = x.size() - 1; i >= 0; i--) {

temporary = int(x[i] - '0') * y + carry;

carry = temporary / 10;

answer = char(temporary % 10 + '0') + answer;

}

while (carry) {

answer = char(carry % 10 + '0') + answer;

carry /= 10;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

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

s = multiplication(s, i);

}

cout << s << endl;

}

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки: #include <vector> и #include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

Related Images:

e-olymp 9036. Комбинация игральных костей

10/12/2019 by Алина Зозуля

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

Первый способ (выполняется быстрее, но использует больше памяти)

#include <iostream>
using namespace std;

int main() {
    int n;
    int ans;
    cin >> n; //считываем сумму, для которой будем считать количество перестановок
    long long a[n+1]; //создаем массив
    if (n == 1) ans = 1;
    if (n == 2) ans = 2;
    if (n == 3) ans = 4;
    if (n == 4) ans = 8;
    if (n == 5) ans = 16;
    if (n == 6) ans = 32;
    // частные случаи
    
    if (n > 6)
    {
        a[1] = 1; 
        a[2] = 2; 
        a[3] = 4; 
        a[4] = 8;
        a[5] = 16; 
        a[6] = 32; 
        for (int i = 7; i < n + 1; i++)
        {
            a[i]=0;
            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
                a[i] = ( a[i] + a[i-j] ) % 1000000007;
        }
        ans = a[n];
    }
    
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int ans;

cin >> n; //считываем сумму, для которой будем считать количество перестановок

long long a[n+1]; //создаем массив

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

cout << ans;

return 0;

}

Второй способ (использует меньше памяти, но выполняется дольше)

#include <iostream>
using namespace std;

int main() {
    int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6
    int n, quantity, counter = 6;
    cin >> n; //считываем сумму
    if (n > 6)
    {
        while (counter < n)
        {
            counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов
            quantity = 0;
            for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы
                quantity = (quantity + a[6-j]) % 1000000007;
                
            for (int i = 0; i < 5; i++)  
                a[i] = a[i+1];
            a[5] = quantity;
        }
        cout << a[5];
    }
    else cout << a[n-1];
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6

int n, quantity, counter = 6;

cin >> n; //считываем сумму

if (n > 6)

{

while (counter < n)

{

counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов

quantity = 0;

for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы

quantity = (quantity + a[6-j]) % 1000000007;

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

a[i] = a[i+1];

a[5] = quantity;

}

cout << a[5];

}

else cout << a[n-1];

return 0;

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

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

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

Related Images:

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

03/06/2019 by Алина Гук

Задача взята с сайта 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

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

#include <iostream>
#include <cstring>
#define MAX 31
using namespace std;

int main() {
    int tests, n, m;
    long long c[MAX][MAX];
    memset(c, 0, sizeof(c));
    for(int i = 0; i < MAX; i++) c[i][0] = 1;
    for(int i = 0; i < MAX; i++)
        for(int j = 1; j <= MAX; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    cin >> tests;
    while(tests--) {
        cin >> n >> m;
        cout << c[n][m - 1] << "\n";
    }
    
    return 0;
}

#include <iostream>

#include <cstring>

#define MAX 31

using namespace std;

int main() {

int tests, n, m;

long long c[MAX][MAX];

memset(c, 0, sizeof(c));

for(int i = 0; i < MAX; i++) c[i][0] = 1;

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

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

c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

cin >> tests;

while(tests--) {

cin >> n >> m;

cout << c[n][m - 1] << "\n";

}

return 0;

}

Решение

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

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

Ссылки

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

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

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

Related Images:

e-olymp 1325. Васькины дорожки

27/11/2018 by Иван Киреев

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

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

Единственное число — количество различных способов для Василия попасть на нужный участок для охоты.

Тесты

№	Ввод	Вывод
1	3 2 3 4 5 3	15
2	10 5 7 1 2 3 4 5 6 7 8 9 10	210
3	4 2 1 3 4 7 8	12
4	10 8 8 1 9 6 7 5 3 8 2 4 10	2
5	1 1 1 1	1
6	10 1 10 1 1 1 1 1 1 1 1 1 10	10
7	7 5 3 2 2 2 4 4 4 5	32
8	10 1 10 10 10 10 10 10 10 10 10 10 10	10000000000
7	5 3 2 1 2 3 4 5 6 7 8 9 10	6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0$. И не превышают $10$, следовательно максимальное значение переменной rez будет $10^{10}$ что помещается в unsigned long.

Код

#include <iostream>
using namespace std;

int main() {
    int n, m, k, a, MIN, MAX;
    unsigned long rez = 1;
    cin >> n >> m >> k;
    MIN = min(m, k);
    MAX = max(m, k);
    for (int i = 1; i <= MAX; i++) {
        cin >> a;
        if (i >= MIN) rez *= a;
    }
    cout << rez;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, k, a, MIN, MAX;

unsigned long rez = 1;

cin >> n >> m >> k;

MIN = min(m, k);

MAX = max(m, k);

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

cin >> a;

if (i >= MIN) rez *= a;

}

cout << rez;

return 0;

}

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

Решение

Код на ideone

Related Images:

e-olymp 8514. Never drink too much!

26/11/2018 by Руслан Масальский

The task is taken from e-olymp

Task

Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud’s attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys — n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo 10⁹ + 7.

Input

Given the number of cowboys — n (1 ≤ n ≤ 10⁷).

Output

The answer to the problem as specified above.

Tests

№	Inputs	Outputs
1	1	0
2	4	9
3	9	133349
4	555	335132588
5	10000000	824182295

Code

#include <bits/stdc++.h> 
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
 
int32_t main() {
    IOS;
    int n, m = 1e9 + 7;
    cin >> n;
    if(n == 1){
        cout << 0;
        return 0;
    }
    int res = n%2==0? 1 : -1;
    int prev = res;
    for (int i = n - 1; i >1; i--) {
        res += prev * (-i - 1 +m) % m;
        prev *= (-i - 1);
        prev = (prev + m) % m;
        res = (res + m) % m;
    }
    cout << res;
    return 0;
}

#include <bits/stdc++.h>

#define int long long

#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define endl "\n"

using namespace std;

int32_t main() {

IOS;

int n, m = 1e9 + 7;

cin >> n;

if(n == 1){

cout << 0;

return 0;

}

int res = n%2==0? 1 : -1;

int prev = res;

for (int i = n - 1; i >1; i--) {

res += prev * (-i - 1 +m) % m;

prev *= (-i - 1);

prev = (prev + m) % m;

res = (res + m) % m;

}

cout << res;

return 0;

}

Solution

We have all possible permutations [latex]C_n^0 \cdot n![/latex] , minus one fixed (one of them is not stupid) we get [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)![/latex] but we subtract for minimum fixed pair (two of them are not stupid) we need to add them [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! [/latex] etc.
So the [latex]k[/latex] member is [latex]C_n^k \cdot (n-k)! \cdot (-1)^k[/latex] Let`s find the attitude of [latex]k[/latex] member to the previous one. It`s [latex]-k -1[/latex] The last one will be [latex]-1[/latex] it depends on parity of [latex]n[/latex].
First two are the same ( [latex]n![/latex] ) so we skip them, but in this case we need to check if[latex]n[/latex] equals [latex]1[/latex] And next we make a loop to find the answer by multiplying start value and add it to the answer.
The complexity is [latex]O(n)[/latex]

e-olymp 1326. В хоккей играют настоящие…

24/10/2018 by Яна Юрковская

Задача

Лесные жители решили провести хоккейный турнир между $N$ командами. Сколькими способами могут быть распределены комплекты золотых, серебряных и бронзовых медалей, если одно призовое место может занять только одна команда?

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

В единственной строке расположено единственное натуральное число $N$, не превышающее 100.

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

Единственное число — искомое количество способов.

Тесты

№	Ввод	Вывод
1	1	1
2	2	2
3	3	6
4	5	60
5	56	166320
6	100	970200

Код

#include <iostream>
using namespace std;
     
int main() {
    int N;
    cin >> N;
    if (N < 3) cout << N;
    else cout << (N*(N - 1)*(N - 2));
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N;

cin >> N;

if (N < 3) cout << N;

else cout << (N*(N - 1)*(N - 2));

return 0;

}

Решение

Чтобы рассчитать количество способов воспользуемся формулой размещения из комбинаторики $A_N^k = \frac{N!}{(N−k)!}$, где $k = 3$, так как существует всего 3 призовых места и следовательно комплекты медалей можно распределить $N$$(N — 1)$$(N — 2)$ способами, при $N >= 3$. При $N < 3$ существует всего $N$ способов распределения, так как команд меньше чем призовых мест.

Ссылки

e-olymp
ideone

Related Images:

e-olymp 1289. Ланч

10/10/2018 by Александр Мога

Задача

Влад хочет взять с собой для ланча пару фруктов. У него есть $a$ различных бананов, $b$ различных яблок и $c$ различных груш. Сколькими способами он может выбрать 2 разных фрукта из имеющихся у него?

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

В одной строке заданы три неотрицательных числа: $a$, $b$, $c$. Все числа не превышают [latex]10^6[/latex].

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

Вывести количество способов, которыми можно выбрать 2 фрукта разного вида.

Тесты

Вход	Выход
2 3 4	26
6 2 4	44
0 4 8	32
1052 886 225	1368122
772 621 124	652144

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

#include <iostream>
using namespace std;

int main() {
    long int a,b,c,n;
    cin >> a >> b >> c;
    n= a*b+b*c+a*c; 
    cout << n;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int a,b,c,n;

cin >> a >> b >> c;

n= a*b+b*c+a*c;

cout << n;

return 0;

}

Решение

Пусть у нас $1$ банан и $b$ различных яблок. Мы можем взять $1$ банан и одно яблоко $b$ способами. Так как бананов $a$, по одному яблоку и банану можем взять [latex](a \cdot b)[/latex] способами. Аналогично, так как груш $с$, то есть [latex](a \cdot с)[/latex] способов взять по одному банану и одну грушу, и [latex](c \cdot b)[/latex] способов взять по одному яблоку и одну грушу. То есть всего [latex](a \cdot b + b \cdot c + c \cdot a) [/latex].

Ссылки

e-olymp

ideone

Related Images:

e-olymp 97. Числа Белла

23/05/2018 by Томас Пасенченко

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

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

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

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

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные	Выходные данные
1 5 3 2 4 2 4 3 10000 3	0 2 5 2 24962375
18 2 465 1009 9998 9221 548 11	134 0 778 14412
1093 1093 1103 1723 3931 617 4868 6113 9534 71	1 0 10635 0 639989
617 17 42 11 0 5	11295 63 0

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

#include <iostream>
using namespace std;

int main() {
    // Числа Белла
    int n, p;
    while (cin >> n >> p) {
        int k = 0;
        for (int i = 1; i <= n; i++) {
            int fact = i;
            while (fact) {
                fact /= p;
                k += fact;
            }
        }
        cout << k << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

// Числа Белла

int n, p;

while (cin >> n >> p) {

int k = 0;

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

int fact = i;

while (fact) {

fact /= p;

k += fact;

}

cout << k << "\n";

}

return 0;

}

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

Related Images:

e-olymp 239. Треугольники

19/05/2018 by Андрей Святозар Чернецкий

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

#include <iostream>
using namespace std;
 
int main() {
    unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};
    unsigned long long c = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> x1 >> y1;
        if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;
        else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;
        else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;
        else A [3] ++;
    }
    for(int i = 0; i < 4; i ++){
        for(int  j= 0; j < 4; j ++){
            if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;
            else c += A[i] * (A[i] - 1) * A[j] / 2;
        }       
    }
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

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

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

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

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

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

Related Images:

e-olymp 1503. Вписанные треугольники

26/01/2018 by Мороз Дима

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

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

Тесты

Входные данные	Выходные данные
5 10 10 100 300 310 320 3 20 10 100 300 0 0	286 320
3 5 25 176 243 0 0	25
4 20 30 80 130 330 0 0	822
2 7 30 230 0 0	0

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

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;

int main(){
    double ang, s, sq, r2, res, M[500];
    int n, r, pts;
    while(cin >> n >> r, n + r != 0){
        for(int i = 0; i < n; i++){
                cin >> M[i];
                M[i] = M[i] * M_PI / 180;
        }
        sort(M, M + n);
        res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;
        r2 = r * r / 2.0;
        sq = M_PI * r * r;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                ang = M[j] - M[i];
                if(ang < M_PI){
                        s = r2 * (ang - sin(ang));
                }else{
                    ang = 2 * M_PI - ang;
                    s = sq - r2 * (ang - sin(ang));
                }
                pts = n - (j - i + 1);
                res = res - s * pts;
                pts = n - 2 - pts;
                res = res - (sq - s) * pts;
            }
        }
        printf("%.f\n", res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

int main(){

double ang, s, sq, r2, res, M[500];

int n, r, pts;

while(cin >> n >> r, n + r != 0){

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

cin >> M[i];

M[i] = M[i] * M_PI / 180;

}

sort(M, M + n);

res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;

r2 = r * r / 2.0;

sq = M_PI * r * r;

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

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

ang = M[j] - M[i];

if(ang < M_PI){

s = r2 * (ang - sin(ang));

}else{

ang = 2 * M_PI - ang;

s = sq - r2 * (ang - sin(ang));

}

pts = n - (j - i + 1);

res = res - s * pts;

pts = n - 2 - pts;

res = res - (sq - s) * pts;

}

printf("%.f\n", res);

}

return 0;

}

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции sort().

В переменную res изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2- $ pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной pts и выводим полученное значение.

Ссылки

Условие задачи на e-olymp.com
Решение задачи ideone.com

Related Images:

A1029

17/06/2015 by Іванов Вячеслав Володимирович

Задача о восьми мирных ладьях

Условие

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

Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска [latex]8 \times 8[/latex].

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

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение [latex]j[/latex] по индексу [latex]i[/latex] соответствовало строке [ [latex]j[/latex], в которой находится ладья в [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел [latex]1,..,8[/latex]. Как известно, число различных перестановок длины [latex]n[/latex] — [latex]P_{n}=n![/latex]. Следовательно, всего существует [latex]8!=40320[/latex] различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья

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

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int main()
{
    do{
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++)
                printf("%c ", (state[i] == j ? 'R' : '#'));
            printf("\n");
        }
        printf("\n");
    } while(next_permutation(state, state+8));
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};

int main()

{

do{

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

for(int j = 0; j < 8; j++)

printf("%c ", (state[i] == j ? 'R' : '#'));

printf("\n");

}

printf("\n");

} while(next_permutation(state, state+8));

return 0;

}

Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

Related Images:

А1033

17/06/2015 by Марченко Філіп Олександрович

Условие

Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.

Код на С++

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;


int a1[6]; int a2[6]; int cnt=0;


//генерация перестановок
void permut (int m){
	for (int j=1; j<=m; j++) a2[j]=a1[j];
	int i = 1;
	int j;
	while (i != 0){
		for (int i=1; i<=m; i++) cout << a2[i];
		cout << endl;
		i=m-1;
		while (a2[i]>a2[i+1]) i--;
		j=m;
		while (a2[j]<a2[i]) j--;
		swap (a2[j],a2[i]);
		int k=i+1;
		int kk=i+floor((m-i)/2);
		while (k<=kk){
			swap(a2[k],a2[m-k+i+1]);
			k++;
		}
		cnt++;
	}
}

int main() {
    int n=9, k=5;
	int p=k;
        //генерация размещений
	for (int i=1; i<=k; i++) a1[i]=i;
	while(p>=1){
        permut(k);
		if (a1[k]==n)
			p-=1;
		else
			p=k;
		if (p>=1)
			for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
	}
        //проверка количества размещений
	cout << cnt << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

int a1[6]; int a2[6]; int cnt=0;

//генерация перестановок

void permut (int m){

for (int j=1; j<=m; j++) a2[j]=a1[j];

int i = 1;

int j;

while (i != 0){

for (int i=1; i<=m; i++) cout << a2[i];

cout << endl;

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

swap (a2[j],a2[i]);

int k=i+1;

int kk=i+floor((m-i)/2);

while (k<=kk){

swap(a2[k],a2[m-k+i+1]);

k++;

}

cnt++;

}

int main() {

int n=9, k=5;

int p=k;

//генерация размещений

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

permut(k);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

//проверка количества размещений

cout << cnt << endl;

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A {
	public static int cnt = 0;
	public static void Permutation (int m, int[] a1, int[] a2){
		for (int j=1; j<=m; j++) a2[j] = a1[j];
		int j;
		int i = 1;
		while (i != 0){
			//for (i=1; i<=m; i++) System.out.print(a2[i]);
			//System.out.print("\n");
			i=m-1;
			while (a2[i]>a2[i+1]) i--;
			j=m;
			while (a2[j]<a2[i]) j--;
			int tmp = a2[j];
			a2[j] = a2[i];
			a2[i] = tmp;
			int k=i+1;
			int kk=i + (m-i)/2;
			while (k<=kk){
				tmp = a2[k];
				a2[k] = a2[m-k+1+i];
				a2[m-k+1+i] = tmp;
				k++;
			}
			cnt++;
		}
	}
	public static void main (String[] args) {
		int[] a1; int[] a2;
		a1 = new int [6];
		a2 = new int [6];
		int n=9, k=5;
		int p=k;
		for (int i=1; i<=k; i++) a1[i]=i;
		while(p>=1){
	        Permutation(k, a1, a2);
			if (a1[k]==n)
				p-=1;
			else
				p=k;
			if (p>=1)
				for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
		}
		System.out.println(cnt);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A {

public static int cnt = 0;

public static void Permutation (int m, int[] a1, int[] a2){

for (int j=1; j<=m; j++) a2[j] = a1[j];

int j;

int i = 1;

while (i != 0){

//for (i=1; i<=m; i++) System.out.print(a2[i]);

//System.out.print("\n");

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

int tmp = a2[j];

a2[j] = a2[i];

a2[i] = tmp;

int k=i+1;

int kk=i + (m-i)/2;

while (k<=kk){

tmp = a2[k];

a2[k] = a2[m-k+1+i];

a2[m-k+1+i] = tmp;

k++;

}

cnt++;

}

public static void main (String[] args) {

int[] a1; int[] a2;

a1 = new int [6];

a2 = new int [6];

int n=9, k=5;

int p=k;

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

Permutation(k, a1, a2);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

System.out.println(cnt);

}

Решение

При решении этой задачи мне понадобились 2 источника информации:

Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:

Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];

Таким образом, генерируя вначале сочетание, я генерировал перестановки этого сочетания. В результате вышло 15120 размещений.

Related Images:

e-olimp 4475. Часы

03/04/2015 by Іванов Вячеслав Володимирович

4475. Часы

Постановка задачи

Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

Во входном потоке содержится количество секунд в минуте [latex]S[/latex], минут в часе [latex]M[/latex], часов в сутках [latex]H[/latex] и число шариков [latex]K[/latex].

Алгоритм решения

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
[latex]\scriptsize \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &6 & 7 & 8 & 9 & 10\\ 1 & 5 & 8 & 2 & 4 & 3 &7 & 9 & 6 & 10 \end{pmatrix}[/latex]
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Реализация:

ideone: http://ideone.com/nz2JlG
Засчитанное решение: http://www.e-olimp.com/solutions/1937971

#include <iostream>
    #include <iomanip>  //cout.setprecision(), cout.fixed
    #include <deque>
    #include <stack>
    #include <cmath>    //floor()
    #include <map>
    using namespace std;

    //НОД
    long double gcd(long double a, long double b){
       while(b){
           a = a - b*floor(a/b);
           swap(a, b);
       }
       return a;
    }

    //НОК
    long double lcm(long double a, long double b){
       return a*(b/gcd(a,b));
    }

    int main()
    {
        int S, M, H, K;
        cin >> S >> M >> H >> K;

        //инициализация очереди
        deque<int> clock;
        for(int i = 1; i <= K; i++)
           clock.push_back(i);

        //моделирование суточного цикла
        stack<int> s, m, h;
        while(h.size() != H){
           s.push(clock.front());  //первый шарик очереди падает
           clock.pop_front();           //на секундную чашу
           if(s.size() == S){           //при переполнении чаши
               m.push(s.top());   //последний упавший шарик
               s.pop();            //переходит на минутную чашу
               while(!s.empty()){       //остальные шарики
                   clock.push_back(s.top());   //переходят в конец очереди
                   s.pop();                //в обратном порядке
               }
               if(m.size() == M){               //аналогично при переполнении
                   h.push(m.top());       //минутной чаши
                   m.pop();
                   while(!m.empty()){
                       clock.push_back(m.top());
                       m.pop();
                   }
               }
           }
        }

        while(!h.empty()){
           clock.push_back(h.top());
           h.pop();
        }

        //суточная перестановка
        //1  2  3  4  5  6  ... K
        //a1 a2 a3 a4 a5 a6 ... ak
        int* permutation = new int[K+1];
        for(int i = 1; i <= K; i++){
           permutation[i] = clock.front();
           clock.pop_front();
        }

        //разложение перестановки в композицию непересекающихся циклов
        bool *used = new bool[K+1]; //метки на посещенных элементах
        long double permutation_order = 1; //порядок перестановки
        for(int i = 1; i <= K; i++){
           if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов
               long double cycle_length = 1;  //найти длину его цикла
               for(size_t x = i; permutation[x] != i; x = permutation[x]){
                   used[x] = true;
                   cycle_length++;
               }
               //и воспользоваться тем, что порядок перестановки -
               //произведение длин циклов из его разложения
               permutation_order = lcm(permutation_order, cycle_length);
           }
        }
        cout << setprecision(0) << fixed << permutation_order << endl;
        return 0;
    }

#include <iostream>

#include <iomanip> //cout.setprecision(), cout.fixed

#include <deque>

#include <stack>

#include <cmath> //floor()

#include <map>

using namespace std;

//НОД

long double gcd(long double a, long double b){

while(b){

a = a - b*floor(a/b);

swap(a, b);

}

return a;

}

//НОК

long double lcm(long double a, long double b){

return a*(b/gcd(a,b));

}

int main()

{

int S, M, H, K;

cin >> S >> M >> H >> K;

//инициализация очереди

deque<int> clock;

for(int i = 1; i <= K; i++)

clock.push_back(i);

//моделирование суточного цикла

stack<int> s, m, h;

while(h.size() != H){

s.push(clock.front()); //первый шарик очереди падает

clock.pop_front(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.top()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.push_back(s.top()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.top()); //минутной чаши

m.pop();

while(!m.empty()){

clock.push_back(m.top());

m.pop();

}

while(!h.empty()){

clock.push_back(h.top());

h.pop();

}

//суточная перестановка

//1 2 3 4 5 6 ... K

//a1 a2 a3 a4 a5 a6 ... ak

int* permutation = new int[K+1];

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

permutation[i] = clock.front();

clock.pop_front();

}

//разложение перестановки в композицию непересекающихся циклов

bool *used = new bool[K+1]; //метки на посещенных элементах

long double permutation_order = 1; //порядок перестановки

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

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

long double cycle_length = 1; //найти длину его цикла

for(size_t x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycle_length++;

}

//и воспользоваться тем, что порядок перестановки -

//произведение длин циклов из его разложения

permutation_order = lcm(permutation_order, cycle_length);

}

cout << setprecision(0) << fixed << permutation_order << endl;

return 0;

}

Примечания

Экспериментально выяснено, что только тип long double является достаточно вместительным для избежания переполнения.
Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.
Модификатор fixed используется для предотвращения вывода чисел в научном формате (с использованием степеней десятки).

Related Images:

А36

04/11/2014 by Гусак Дмитро Євгенович

Задача: Даны действительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Проверить, выполняются ли неравенства [latex]a<b<c[/latex].

Тесты:

Ввод			Вывод	Результат
a	b	c		неравенство не выполнено
2	1	3	b<=a<c: нер-во a<b<c не выполняется	неравенство не выполнено
1	3	2	a<=c<=b: нер-во a<b<c не выполняется	неравенство не выполнено
3	1	2	b<=c<=a: нер-во a<b<c не выполняется	неравенство не выполнено
3	2	1	c<=b<=a: нер-во a<b<c не выполняется	неравенство не выполнено
2	3	1	c<=a<b: нер-во a<b<c не выполняется	неравенство не выполнено
1	2	3	нер-во a<b<c справедливо	неравенство выполнено

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

#include <iostream>
using namespace std;
int main() {
	double a, b, c;
	printf("введите a: \n");
	scanf("%lf", &a);
	printf("введите b: \n");
	scanf("%lf", &b);
	printf("введите c: \n");
	scanf("%lf", &c);
	if (a >= b && a < c)
	{
		printf("b<=a<c: неравенство a<b<c не выполняется \n");
	}
	else if (a < b && a <= c && b >= c)
	{
		printf("a<=c<=b: неравенство a<b<c не выполняется \n");
	}
	else if (a >= b && a >= c && b < c)
	{
		printf("b<=c<=a: неравенство a<b<c не выполняется \n");
	}
	else if (a >= b && a >= c && b >= c)
	{
		printf("c<=b<=a: неравенство a<b<c не выполняется \n");
	}
	else if (a < b && a >= c && b > c)
	{
		printf("c<=a<b: неравенство a<b<c не выполняется \n");
	}
	else
	{
		printf("неравенство a<b<c справедливо \n");
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, b, c;

printf("введите a: \n");

scanf("%lf", &a);

printf("введите b: \n");

scanf("%lf", &b);

printf("введите c: \n");

scanf("%lf", &c);

if (a >= b && a < c)

{

printf("b<=a<c: неравенство a<b<c не выполняется \n");

}

else if (a < b && a <= c && b >= c)

{

printf("a<=c<=b: неравенство a<b<c не выполняется \n");

}

else if (a >= b && a >= c && b < c)

{

printf("b<=c<=a: неравенство a<b<c не выполняется \n");

}

else if (a >= b && a >= c && b >= c)

{

printf("c<=b<=a: неравенство a<b<c не выполняется \n");

}

else if (a < b && a >= c && b > c)

{

printf("c<=a<b: неравенство a<b<c не выполняется \n");

}

else

{

printf("неравенство a<b<c справедливо \n");

}

return 0;

}

Отчет:

После ввода чисел a, b, c программа проверит их соотношения. Ввиду наличия трех сравниваемых чисел имеем 3! = 6 возможных комбинаций чисел, и только одна из них соответствует требованию. Если неравенство [latex]a<b<c[/latex] имеет место быть, то программа сообщит о его выполнении. В противном же случае консоль выдаст ответ о не выполненном неравенстве, предварительно сообщив причину.

Копия кода на сайте Ideone: ideone.com/aYmMJ2