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

09/05/2017 by Андреев Даниил

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <deque>
using namespace std;
 
int main(){
    deque<int> folder;
    unsigned long long N;
    
    cin >> N;
    folder.push_back(N%10);
    N/=10;
    while (N!=0){
        for (int i=0; i<folder.size(); i++){
            if (folder.at(i) == N%10)
                i+=folder.size();   
            if (i == folder.size() -1)
                folder.push_back(N%10);
        }
        N/=10;
    }
    cout << "sum:" << folder.size();
 
    return 0;
}

#include <iostream>

#include <deque>

using namespace std;

int main(){

deque<int> folder;

unsigned long long N;

cin >> N;

folder.push_back(N%10);

N/=10;

while (N!=0){

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

if (folder.at(i) == N%10)

i+=folder.size();

if (i == folder.size() -1)

folder.push_back(N%10);

}

N/=10;

}

cout << "sum:" << folder.size();

return 0;

}

Решение

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

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

#include <iostream>
using namespace std;
 
int main(){
    int folder[10]={0}, sum=0;
    long long N;
 
    cin >> N;
    while (N!=0){
        folder[N%10]++;
        N/=10;
    }
    for (int j=0; j<10; j++)
        if(folder[j]!=0)    sum++;
    cout << "sum:" << sum;
 
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int folder[10]={0}, sum=0;

long long N;

cin >> N;

while (N!=0){

folder[N%10]++;

N/=10;

}

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

if(folder[j]!=0) sum++;

cout << "sum:" << sum;

return 0;

}

Решение

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

Ссылки

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

Related Images:

e-olymp 6128. Простой дек

08/05/2017 by Андреев Даниил

Задача

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

push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size Вывести количество элементов в деке.
clear Очистить дек (удалить из него все элементы) и вывести ok.
exit Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит [latex]100[/latex]. Все операции:

pop_front,
pop_back,
front,
back
всегда корректны.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример входных данных.

Тесты

Входные данные	Выходные данные
push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit	ok ok 2 ok ok 1 ok 1 2 1 1 0 bye

Код программы на C++

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

struct deque{
    #define Size 200000
    int start, end;
    int folder[Size];
    
    deque(){
        start = end = Size/2;
    }
    void push_front(int var){
        folder[--start] = var;
        cout << "ok" << endl;
    }
    void push_back(int var){
        folder[end++] = var;
        cout << "ok" << endl;
    }
    void pop_front(){
        cout << folder[start++] << endl;
    }
    void pop_back(){
        cout << folder[--end] << endl;
    }
    void front(){
        cout << folder[start] << endl;
    }
    void back(){
        cout << folder[end-1] << endl;
    }
    void size(){
        cout << end-start << endl;
    }
    void clear(){
        start = end = Size/2;
        cout << "ok" << endl; 
    }
};
        
int main() {
    string s;
    deque deq;
    int n;

    while (cin >> s){
        if (s == "push_front"){
            cin >> n;
            deq.push_front(n);
        }
        else    if (s == "push_back"){
                cin >> n;
                deq.push_back(n);
        }
        else    if (s == "pop_front")   deq.pop_front();
        else    if (s == "pop_back")    deq.pop_back();
        else    if (s == "front")   deq.front();
        else    if (s == "back")    deq.back();
        else    if (s == "size")    deq.size();
        else    if (s == "clear")   deq.clear();
        else    if (s == "exit"){
                cout << "bye";
                return 0;
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

struct deque{

#define Size 200000

int start, end;

int folder[Size];

deque(){

start = end = Size/2;

}

void push_front(int var){

folder[--start] = var;

cout << "ok" << endl;

}

void push_back(int var){

folder[end++] = var;

cout << "ok" << endl;

}

void pop_front(){

cout << folder[start++] << endl;

}

void pop_back(){

cout << folder[--end] << endl;

}

void front(){

cout << folder[start] << endl;

}

void back(){

cout << folder[end-1] << endl;

}

void size(){

cout << end-start << endl;

}

void clear(){

start = end = Size/2;

cout << "ok" << endl;

}

};

int main() {

string s;

deque deq;

int n;

while (cin >> s){

if (s == "push_front"){

cin >> n;

deq.push_front(n);

}

else if (s == "push_back"){

cin >> n;

deq.push_back(n);

}

else if (s == "pop_front") deq.pop_front();

else if (s == "pop_back") deq.pop_back();

else if (s == "front") deq.front();

else if (s == "back") deq.back();

else if (s == "size") deq.size();

else if (s == "clear") deq.clear();

else if (s == "exit"){

cout << "bye";

return 0;

}

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

import java.util.*;

class deque{
    private static final int Size = 200000;
    int start, end;
    int [] folder = new int[Size] ;
    
    deque(){
        start = end = Size/2;
    }
    void push_front(int var){
        folder[--start] = var;
        System.out.println("ok");
    }
    void push_back(int var){
        folder[end++] = var;
        System.out.println("ok");
    }
    void pop_front(){
        System.out.println(folder[start++]);
    }
    void pop_back(){
        System.out.println(folder[--end]);
    }
    void front(){
        System.out.println(folder[start]);
    }
    void back(){
        System.out.println(folder[end-1]);
    }
    void size(){
        System.out.println(end-start);
    }
    void clear(){
        start = end = Size/2;
        System.out.println("ok");
    }
};

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        deque deq = new deque();
        String S;
        
        while (scan.hasNext()){
            S = scan.next();
            if (S.equals("push_front")) deq.push_front(scan.nextInt());
            else    if (S.equals("push_back"))  deq.push_back(scan.nextInt());
            else    if (S.equals("pop_front"))  deq.pop_front();
            else    if (S.equals("pop_back"))   deq.pop_back();
            else    if (S.equals("front"))  deq.front();
            else    if (S.equals("back"))   deq.back();
            else    if (S.equals("size"))   deq.size();
            else    if (S.equals("clear"))  deq.clear();
            else    if (S.equals("exit")){
                    System.out.println("bye");
                    System.exit(0);
                }
        }
    }
}

import java.util.*;

class deque{

private static final int Size = 200000;

int start, end;

int [] folder = new int[Size] ;

deque(){

start = end = Size/2;

}

void push_front(int var){

folder[--start] = var;

System.out.println("ok");

}

void push_back(int var){

folder[end++] = var;

System.out.println("ok");

}

void pop_front(){

System.out.println(folder[start++]);

}

void pop_back(){

System.out.println(folder[--end]);

}

void front(){

System.out.println(folder[start]);

}

void back(){

System.out.println(folder[end-1]);

}

void size(){

System.out.println(end-start);

}

void clear(){

start = end = Size/2;

System.out.println("ok");

}

};

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

deque deq = new deque();

String S;

while (scan.hasNext()){

S = scan.next();

if (S.equals("push_front")) deq.push_front(scan.nextInt());

else if (S.equals("push_back")) deq.push_back(scan.nextInt());

else if (S.equals("pop_front")) deq.pop_front();

else if (S.equals("pop_back")) deq.pop_back();

else if (S.equals("front")) deq.front();

else if (S.equals("back")) deq.back();

else if (S.equals("size")) deq.size();

else if (S.equals("clear")) deq.clear();

else if (S.equals("exit")){

System.out.println("bye");

System.exit(0);

}

Решение

Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.

push_front — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
push_back — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
pop_front — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
pop_back — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
front — выводим значение начала дека;
back — выводим значение перед [latex]end[/latex];
size — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
clear — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
exit — выводим «bye» и заканчиваем программу.

Ссылки

Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java

Related Images:

KM194. Взаимно простые числа

28/03/2017 by Андреев Даниил

Задача

Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by],[/latex] где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?

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

[latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.

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

[latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].

Тесты

Входные данные		Выходные данные
[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]
5	3	7
2	1	-1
3	2	1

Код программы на C++

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    
    cin >> a >> b;
    cout << a*b-a-b;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

cout << a*b-a-b;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        
        System.out.print(a*b-a-b);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int a = scan.nextInt();

int b = scan.nextInt();

System.out.print(a*b-a-b);

}

Решение

Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.

Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex] Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.

Ссылки

Ideone C++;
Ideone Java;
Решение задачи Журнал «Квант» №11 г.1973 (стр. 44-45);
Условие задачи Журнал «Квант» №3 г.1973 (стр. 35).

Related Images:

MS 7. Средняя зарплата

28/03/2017 by Андреев Даниил

Задача

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

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

Фамилия работника ([latex]name[/latex]) и величина его зарплаты ([latex]sal[/latex]).

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

Средняя зарплата по компании.

Тесты

Входные данные		Выходные данные
[latex]name[/latex]	[latex]sal[/latex]
Ivanov	200	200
Ivanov Smirnov Popov Sokolov	100 150 200 150	150

Код программы на C++

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

int main() {
    string name;
    double sal, total=0, sum=0;
    
    while (cin >> name){
        cin >> sal;
        total+=sal;
        sum++;
    }
    
    cout << total/sum;
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string name;

double sal, total=0, sum=0;

while (cin >> name){

cin >> sal;

total+=sal;

sum++;

}

cout << total/sum;

return 0;

}

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

import java.util.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        double total=0, sum=0;
        
        while (scan.hasNext()){
            if (!scan.hasNextDouble()){
                scan.next();
                total += scan.nextDouble();
                sum++;
            }
            else    scan.next();
        }
        System.out.print(total/sum);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

double total=0, sum=0;

while (scan.hasNext()){

if (!scan.hasNextDouble()){

scan.next();

total += scan.nextDouble();

sum++;

}

else scan.next();

}

System.out.print(total/sum);

}

Решение

В переменную [latex]total[/latex] которая изначально равна [latex]0[/latex] прибавляем зарплату каждого сотрудника, а [latex]sum[/latex] показывает количество сотрудников. Выводим зарплату всех сотрудников деленную на их количество.

Ссылки

Ideone C++
Ideone Java

Related Images:

D2574. Сумма ряда

27/02/2017 by Андреев Даниил

Задача

Найти сумму сходящегося ряда: [latex]\sum \limits_{n=1}^{n}\frac{\sin{nx}}{2^{n}}[/latex].

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

[latex]n[/latex] — количество шагов;
[latex]x[/latex] — значение [latex]x[/latex].

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

Сумма ряда [latex]\sum \limits_{n=1}^{n}\frac{sin(nx)}{2^{n}}[/latex].

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]x[/latex]
10	0.523598	0.651170
25	3.141592	0
15	1.570796	0.399994

Код программы на C++

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    int e=1, n;
    double x, t, o=0;
 
    cin >> n >> x;
 
    for (int j=1; j<(n+1); j++)
    {
        t=sin(j*x);
        e*=2;
        o+=t/e;
    }
 
    cout << fixed << o;
 
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int e=1, n;

double x, t, o=0;

cin >> n >> x;

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

{

t=sin(j*x);

e*=2;

o+=t/e;

}

cout << fixed << o;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int e=1;
        double t, o=0;
        int n = scan.nextInt();
        double x = scan.nextDouble();
        
        for (int j=1; j<(n+1); j++){
            t=Math.sin(j*x);
            e*=2;
            o+=t/e;
        }
        
        System.out.printf("%1$.6f", o);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int e=1;

double t, o=0;

int n = scan.nextInt();

double x = scan.nextDouble();

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

t=Math.sin(j*x);

e*=2;

o+=t/e;

}

System.out.printf("%1$.6f", o);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone на C++;
Ideone на Java;
WolframAlpha.

Related Images:

A320. Вложенный цикл

25/12/2016 by Андреев Даниил

Задача

Вычислить [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

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

Произвольные [latex]n[/latex] и [latex]m.[/latex]

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

Значение [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]m[/latex]
10	15	983455
2	5	150
3	6	816

Код программы на C++

#include <iostream>
using namespace std;
int main()
{
    long double sum_1=0, sum_2=0;
    int n, m;
    cin >> n >> m;
    for(int k=1;k<=n;k++)
    {
        for(int l=1;l<=m;l++)
        {
            sum_2+=(k-l)*(k-l);
        }
        sum_1+=k*k*k*sum_2;
        sum_2-=sum_2;
    }
    cout << sum_1;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

long double sum_1=0, sum_2=0;

int n, m;

cin >> n >> m;

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

{

for(int l=1;l<=m;l++)

{

sum_2+=(k-l)*(k-l);

}

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

cout << sum_1;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        double sum_1=0, sum_2=0;
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        for(int k=1; k<=n; k++){
            for(int l=1; l<=m; l++)  sum_2+=(k-l)*(k-l);
            sum_1+=k*k*k*sum_2;
            sum_2-=sum_2;
        }
        
        System.out.print(sum_1);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

double sum_1=0, sum_2=0;

int n = scan.nextInt();

int m = scan.nextInt();

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

for(int l=1; l<=m; l++) sum_2+=(k-l)*(k-l);

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

System.out.print(sum_1);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone C++;
Ideone Java;
WolframAlpha.

Related Images:

Mif 9. Пересечение отрезков

06/11/2016 by Андреев Даниил

Задача

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.

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

Координаты концов отрезка[latex]AB[/latex] и [latex]CD[/latex].

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

Пересекаются ли отрезки.

Тесты

Входные данные								Выходные данные
[latex]x1[/latex]	[latex]y1[/latex]	[latex]x2[/latex]	[latex]y2[/latex]	[latex]x3[/latex]	[latex]y3[/latex]	[latex]x4[/latex]	[latex]y4[/latex]
1	0	2	1	1	0	2	0	Отрезки пересекаются
-1	1	2	-2	0	-2	1	3	Отрезки пересекаются
1	1	2	2	2	2	1	1	Отрезки пересекаются
-1	1	-1	2	1	1	2	2	Отрезки не пересекаются
-2	-1	-2	3	0	-1	0	3	Отрезки не пересекаются
-2	0	0	2	0	-2	1	1	Отрезки не пересекаются

Код программы на C++

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    double x1, y1, x2, y2, x3, y3, x4, y4;
    double Ua, Ub, numerator_a, numerator_b, denominator;
    
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
    if (denominator == 0){
        if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)
            cout << "Отрезки пересекаются";
        else cout << "Отрезки не пересекаются";
    }
    else{
        numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
        numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
        Ua=numerator_a/denominator;
        Ub=numerator_b/denominator;
        cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x1, y1, x2, y2, x3, y3, x4, y4;

double Ua, Ub, numerator_a, numerator_b, denominator;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);

if (denominator == 0){

if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)

cout << "Отрезки пересекаются";

else cout << "Отрезки не пересекаются";

}

else{

numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);

numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);

Ua=numerator_a/denominator;

Ub=numerator_b/denominator;

cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");

}

return 0;

}

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

import java.util.*;
 
class Main{
    public static void main (String[] args) throws java.lang.Exception{
        Scanner scan = new Scanner(System.in);
        double Ua, Ub, numerator_a, numerator_b, denominator;
        double x1 = scan.nextDouble();
        double y1 = scan.nextDouble();
        double x2 = scan.nextDouble();
        double y2 = scan.nextDouble();
        double x3 = scan.nextDouble();
        double y3 = scan.nextDouble();
        double x4 = scan.nextDouble();
        double y4 = scan.nextDouble();
 
        denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
        if (denominator == 0){
            if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)  System.out.print("Отрезки пересекаются");
            else System.out.print("Отрезки не пересекаются");
        }
        else{
            numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
            numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
            Ua=numerator_a/denominator;
            Ub=numerator_b/denominator;
            if (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1)   System.out.print("Отрезки пересекаются");
            else    System.out.print("Отрезки не пересекаются");
        }
    }
}

import java.util.*;

class Main{

public static void main (String[] args) throws java.lang.Exception{

Scanner scan = new Scanner(System.in);

double Ua, Ub, numerator_a, numerator_b, denominator;

double x1 = scan.nextDouble();

double y1 = scan.nextDouble();

double x2 = scan.nextDouble();

double y2 = scan.nextDouble();

double x3 = scan.nextDouble();

double y3 = scan.nextDouble();

double x4 = scan.nextDouble();

double y4 = scan.nextDouble();

denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);

if (denominator == 0){

if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0) System.out.print("Отрезки пересекаются");

else System.out.print("Отрезки не пересекаются");

}

else{

numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);

numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);

Ua=numerator_a/denominator;

Ub=numerator_b/denominator;

if (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1) System.out.print("Отрезки пересекаются");

else System.out.print("Отрезки не пересекаются");

}

Решение

Пусть концы отрезков имеют координаты [latex]A(x_1,y_1)[/latex], [latex]B(x_2,y_2)[/latex], [latex]C(x_3,y_3)[/latex] и [latex]D(x_4,y_4)[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=u x_1+(1−u)x_2; \newline y=uy_1+(1−u)y_2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx_3+(1−v)x_4 \newline y=vy_3+(1−v)y_4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux_1+(1−u)x_2=vx_3+(1−v)x_4 \newline uy_1+(1−u)y_2=vy_3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y_4-y_3)\cdot(x_1-x_2)-(x_4-x_3)\cdot(y_1-y_2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x_4-x_2)\cdot(y_4-y_3)-(x_4-x_3)\cdot(y_4-y_2)}{denominator} \newline Ub=\frac{(x_1−x_2)\cdot(y_4−y_2)−(x_4−x_2)\cdot(y_1−y_2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone C++
Ideone Java

Related Images:

ML37. Самолёт и ветер

30/09/2016 by Андреев Даниил

Задача

Самолёт летит из пункта в [latex]A[/latex] в пункт [latex]B[/latex] и обратно со скоростью [latex]V[/latex] км/час. Всё время дует ветер с постоянной скоростью [latex]U[/latex] км/час под углом [latex]\alpha[/latex] радиан к направлению движения (0 соответствует попутному ветру). Расстояние между пунктами составляет [latex]S[/latex] км. Для любых неотрицательных действительных значений угла, расстояния и скоростей вычислите время в пути.

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

[latex]V[/latex]-скорость самолета, [latex]U[/latex]-скорость ветра, [latex]S[/latex]-расстояние [latex]AB[/latex], [latex]\alpha[/latex]-угол направления ветра.

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

Время полета [latex]t[/latex] в часах.

Тесты

Входные данные				Выходные данные
[latex]V[/latex]	[latex]U[/latex]	[latex]S[/latex]	[latex]\alpha[/latex]	[latex]t[/latex]
600	20	1200	1,5708	4.0013
600	20	1200	0	4.00445
600	20	1200	3,1415	4.00436
600	20	1200	1,0472	4.0013
600	20	1200	2,6179	4.00077
600	601	1200	0	inf
0	20	1200	0	inf

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

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    double V, U, S, a, t;
    
    cin >> V >> U >> S >> a;
    
    t=S/(V+cos(a)*U)+S/(V-cos(a)*U);//Сумма времени полета от A к B и обратно
    
    cout << (U>=V ? 1/tan(0) : t);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double V, U, S, a, t;

cin >> V >> U >> S >> a;

t=S/(V+cos(a)*U)+S/(V-cos(a)*U);//Сумма времени полета от A к B и обратно

cout << (U>=V ? 1/tan(0) : t);

return 0;

}

Решение

Учитывая скорость ветра [latex]U[/latex] и угол [latex]\alpha[/latex] под которым ветер дует на самолет, на пути от [latex]A[/latex] к [latex]B[/latex] скорость самолета будет равна [latex]V+cos(\alpha)\cdot U[/latex] , а на обратном пути от [latex]B[/latex] к [latex]A[/latex] скорость самолета будет равна [latex]V-cos(\alpha)\cdot U[/latex].Общее время полета узнаем по формуле [latex]t =\frac{S}{V+cos(\alpha)\cdot U} +\frac{S}{V-cos(\alpha)\cdot U}[/latex].

Ссылки

Ideone