e-olimp 6129. Дек неограниченного размера

28/08/2016 by Ирина Литвиненко

Задача:

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Тесты:

Последовательность

Результат

push_front
4
push_back
5
front
push_front
3
back
size
pop_front
pop_back
clear
pop_back
size
exit

4
ok

5
3
3
5
ok
error
0
bye

import java.util.Scanner;

public class Deque {

    private class Node {
        Node prev;
        Node next;
        int x;

        Node() {
            prev = null;
            next = null;
            x = 0;
        }
        Node(Node a, Node b, int c) {
            prev = a;
            next = b;
            x = c;
        }
    };

    Node Front = null;
    Node Back = null;
    int Size = 0;

    int size() {
        return Size;
    }

    void push_back(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(null, Back, p);
            Back.prev = NewNode;
            Back = NewNode;
        }
        Size++;
    }

    void push_front(int p) {
        if (Size == 0) {
            Node NewNode = new Node(Back, Front, p);
            Front = NewNode;
            Back = NewNode;
        } else {
            Node NewNode = new Node(Front, null, p);
            Front.next = NewNode;
            Front = NewNode;
        }
        Size++;
    }

    int back() {
        if (Size != 0) {
            return Back.x;
        } else {
            return 0;
        }
    }

    int front() {
        if (Size != 0) {
            return Front.x;
        } else {
            return 0;
        }
    }

    int pop_front() {
        if (Size != 0) {
            int x = Front.x;
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    int pop_back() {
        if (Size != 0) {
            int x = Back.x;
            Node NewNode = Back.next;
            Back = NewNode;
            Size--;
            return x;
        } else {
            return 0;
        }
    }

    void clear() {
        while (Size > 0) {
            Node NewNode = Front.prev;
            Front = NewNode;
            Size--;
        }
        Front = null;
        Back = null;
    }


    public static void main(String[] args) {
        Deque deque = new Deque();
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();

        while (!command.equals("exit")) {
            if (command.equals("push_back")) {
                int v = scanner.nextInt();
                deque.push_back(v);
                System.out.println("ok\n");
            } else if (command.equals("push_front")) {
                int v = scanner.nextInt();
                deque.push_front(v);
                System.out.println("ok\n");
            } else if (command.equals("front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("size")) {
                System.out.println(deque.size());
            } else if (command.equals("pop_front")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_front());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("pop_back")) {
                if (deque.size() > 0) {
                    System.out.println(deque.pop_back());
                } else {
                    System.out.println("error\n");
                }
            } else if (command.equals("clear")) {
                System.out.println("ok\n");
                deque.clear();
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
    }
};

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

import java.util.Scanner;

public class Deque {

private class Node {

Node prev;

Node next;

int x;

Node() {

prev = null;

next = null;

x = 0;

}

Node(Node a, Node b, int c) {

prev = a;

next = b;

x = c;

}

};

Node Front = null;

Node Back = null;

int Size = 0;

int size() {

return Size;

}

void push_back(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(null, Back, p);

Back.prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p) {

if (Size == 0) {

Node NewNode = new Node(Back, Front, p);

Front = NewNode;

Back = NewNode;

} else {

Node NewNode = new Node(Front, null, p);

Front.next = NewNode;

Front = NewNode;

}

Size++;

}

int back() {

if (Size != 0) {

return Back.x;

} else {

return 0;

}

int front() {

if (Size != 0) {

return Front.x;

} else {

return 0;

}

int pop_front() {

if (Size != 0) {

int x = Front.x;

Node NewNode = Front.prev;

Front = NewNode;

Size--;

return x;

} else {

return 0;

}

int pop_back() {

if (Size != 0) {

int x = Back.x;

Node NewNode = Back.next;

Back = NewNode;

Size--;

return x;

} else {

return 0;

}

void clear() {

while (Size > 0) {

Node NewNode = Front.prev;

Front = NewNode;

Size--;

}

Front = null;

Back = null;

}

public static void main(String[] args) {

Deque deque = new Deque();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.equals("push_back")) {

int v = scanner.nextInt();

deque.push_back(v);

System.out.println("ok\n");

} else if (command.equals("push_front")) {

int v = scanner.nextInt();

deque.push_front(v);

System.out.println("ok\n");

} else if (command.equals("front")) {

if (deque.size() > 0) {

System.out.println(deque.front());

} else {

System.out.println("error\n");

}

} else if (command.equals("back")) {

if (deque.size() > 0) {

System.out.println(deque.back());

} else {

System.out.println("error\n");

}

} else if (command.equals("size")) {

System.out.println(deque.size());

} else if (command.equals("pop_front")) {

if (deque.size() > 0) {

System.out.println(deque.pop_front());

} else {

System.out.println("error\n");

}

} else if (command.equals("pop_back")) {

if (deque.size() > 0) {

System.out.println(deque.pop_back());

} else {

System.out.println("error\n");

}

} else if (command.equals("clear")) {

System.out.println("ok\n");

deque.clear();

}

command = scanner.nextLine();

}

System.out.println("bye");

}

};

Решение

Решение на Ideone
Дек — (двухсторонняя очередь) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO. Для реализации дека неограниченного размера удобно использовать двусвязный список.

Class Matrix

28/08/2016 by Ирина Литвиненко

Задача:

Напишите класс для хранения матриц и реализуйте основные операции работы с ними.

Тесты:

№	Исходные данные	Операция	Результат
1.	A: B: -9 1 0 1 0 0 4 1 1 0 2 0 -2 2 -1 0 0 1	+	-8 1 0 4 3 1 -2 2 0
2.		—	-10 1 0 4 -1 1 -2 2 -2
3.		*	-9 2 0 4 2 1 -2 4 -1
4.	-9 1 0 4 1 1 -2 2 -1	transposition	-9 4 -2 1 1 2 0 1 -1

public class Matrix {

    private int a[][];

    public Matrix(int n, int m) {
        a = new int[n][m];
    }

    public Matrix(int a[][]) {
        this.a = a;
    }

    public int getVerticalSize() {
        return a.length;
    }

    public int getHorizontalSize() {
        return a[0].length;
    }

    public int getElement(int i, int j) {
        return a[i][j];
    }

    public void setElement(int i, int j, int value) {
        a[i][j] = value;
    }

    @Override
    public String toString() {
        String s = "\n";
        for (int[] vector : a) {
            for (int value : vector)
                s += value + " ";
            s += "\n";
        }
        return s;
    }

    public static Matrix add(Matrix a, Matrix b) {
        int v = a.getVerticalSize();
        int h = a.getHorizontalSize();
        Matrix result = new Matrix(v, h);

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < v; j++) {
                int value = 0;
                value = a.getElement(i, j) + b.getElement(i, j);
                result.setElement(i, j, value);
            }
        }
        return result;
    }

    public static Matrix subtract(Matrix a, Matrix b) {
        int v = a.getVerticalSize();
        int h = a.getHorizontalSize();
        Matrix result = new Matrix(v, h);

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < v; j++) {
                int value = 0;
                value = a.getElement(i, j) - b.getElement(i, j);
                result.setElement(i, j, value);
            }
        }
        return result;
    }

    public static Matrix multiply(Matrix a, Matrix b) {
        int v = a.getVerticalSize();
        int h = b.getHorizontalSize();
        int temp = a.getHorizontalSize();

        Matrix result = new Matrix(v, h);

        for (int i = 0; i < v; i++)
            for (int j = 0; j < h; j++) {
                int value = 0;
                for (int k = 0; k < temp; k++) {
                    value += a.getElement(i, k) * b.getElement(k, j);
                }
                result.setElement(i, j, value);
            }
        return result;
    }

    public void transMatrix() {
        int x = a.length;
        int retA[][] = new int[x][x];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < x; j++) {
                retA[j][i] = a[i][j];
            }
        }
        for (int i = 0; i < a.length; i++) {
            System.arraycopy(retA[i], 0, a[i], 0, a.length);
        }
    }

    public static void main(String[] args) {

        int[][] a = {{-9, 1, 0}, {4, 1, 1}, {-2, 2, -1}};
        int[][] b = {{0, 0, 0}, {0, 2, 0}, {0, 0, 1}};

        Matrix A = new Matrix(a);
        System.out.println("A" + A);
        System.out.println("Element [0,0] : " + A.getElement(0, 0));

        Matrix B = new Matrix(b);
        B.setElement(0, 0, 1);
        System.out.println("Size of matrix B : " + B.getHorizontalSize() + " " + B.getVerticalSize() + B);

        Matrix C;
        C = add(A, B);
        System.out.println("add " + C);

        C = subtract(A, B);
        System.out.println("subtract " + C);

        C = multiply(A, B);
        System.out.println("multiply " + C);

        A.transMatrix();
        System.out.println("Transposed A : " + A);

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

public class Matrix {

private int a[][];

public Matrix(int n, int m) {

a = new int[n][m];

}

public Matrix(int a[][]) {

this.a = a;

}

public int getVerticalSize() {

return a.length;

}

public int getHorizontalSize() {

return a[0].length;

}

public int getElement(int i, int j) {

return a[i][j];

}

public void setElement(int i, int j, int value) {

a[i][j] = value;

}

@Override

public String toString() {

String s = "\n";

for (int[] vector : a) {

for (int value : vector)

s += value + " ";

s += "\n";

}

return s;

}

public static Matrix add(Matrix a, Matrix b) {

int v = a.getVerticalSize();

int h = a.getHorizontalSize();

Matrix result = new Matrix(v, h);

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

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

int value = 0;

value = a.getElement(i, j) + b.getElement(i, j);

result.setElement(i, j, value);

}

return result;

}

public static Matrix subtract(Matrix a, Matrix b) {

int v = a.getVerticalSize();

int h = a.getHorizontalSize();

Matrix result = new Matrix(v, h);

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

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

int value = 0;

value = a.getElement(i, j) - b.getElement(i, j);

result.setElement(i, j, value);

}

return result;

}

public static Matrix multiply(Matrix a, Matrix b) {

int v = a.getVerticalSize();

int h = b.getHorizontalSize();

int temp = a.getHorizontalSize();

Matrix result = new Matrix(v, h);

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

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

int value = 0;

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

value += a.getElement(i, k) * b.getElement(k, j);

}

result.setElement(i, j, value);

}

return result;

}

public void transMatrix() {

int x = a.length;

int retA[][] = new int[x][x];

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

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

retA[j][i] = a[i][j];

}

for (int i = 0; i < a.length; i++) {

System.arraycopy(retA[i], 0, a[i], 0, a.length);

}

public static void main(String[] args) {

int[][] a = {{-9, 1, 0}, {4, 1, 1}, {-2, 2, -1}};

int[][] b = {{0, 0, 0}, {0, 2, 0}, {0, 0, 1}};

Matrix A = new Matrix(a);

System.out.println("A" + A);

System.out.println("Element [0,0] : " + A.getElement(0, 0));

Matrix B = new Matrix(b);

B.setElement(0, 0, 1);

System.out.println("Size of matrix B : " + B.getHorizontalSize() + " " + B.getVerticalSize() + B);

Matrix C;

C = add(A, B);

System.out.println("add " + C);

C = subtract(A, B);

System.out.println("subtract " + C);

C = multiply(A, B);

System.out.println("multiply " + C);

A.transMatrix();

System.out.println("Transposed A : " + A);

}

Решение на Ideone

e-olymp 2162. Палиндром

16/08/2016 by Ирина Литвиненко

Палиндром — это строка, которая одинаково читается слева направо и справа налево. Составьте программу, которая проверяет, является ли заданный текст палиндромом. Не забудьте, что при чтении пробел никак не произносится.

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

Дана строка S (|S| ≤ 255), состоящая из строчных латинских букв и пробелов. Под |S| подразумевается длина строки.

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

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

Тесты

№	Входные данные	Выходные данные
1	palindrom	NO
2	a roza upala na lapu azora	YES
3	my gym	YES
4	character	NO

import java.util.Scanner;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner scanner = new Scanner(System.in);
		String s = scanner.nextLine();
		System.out.print(isPalindrome(s) ? "Yes" : "No");
	}
	
	public static boolean isPalindrome(String text) {
		text = text.replaceAll(" ","");
		return text.equals(new StringBuilder(text).reverse().toString());
	}
}

import java.util.Scanner;

class Main {

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

Scanner scanner = new Scanner(System.in);

String s = scanner.nextLine();

System.out.print(isPalindrome(s) ? "Yes" : "No");

}

public static boolean isPalindrome(String text) {

text = text.replaceAll(" ","");

return text.equals(new StringBuilder(text).reverse().toString());

}

Решение на Ideone
Решение на e-olymp

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

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

А137е

06/07/2016 by Ирина Литвиненко

Даны натуральные [latex]n[/latex], действительные [latex]a_1,\ldots, a_n[/latex].

Вывести: [latex]a_1+1!, a_2 +2!,\ldots, a_n+n![/latex].

Тесты:

n	a1	a2	a3	a4
4	1	2	3	4	Output	2	4	9	28
4	0.1	0.2	0.3	0.4	Output	1.1	2.2	6.3	24.4

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int n;
		double a, fact = 1.0;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); //читаем n
		
		for(int k = 1; k <= n; k++) {
			
			a = scanner.nextDouble(); //читаем из потока k-ый элемент 
			fact *= k; //увеличиваем фаториал
			System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int n;

double a, fact = 1.0;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt(); //читаем n

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

a = scanner.nextDouble(); //читаем из потока k-ый элемент

fact *= k; //увеличиваем фаториал

System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала

}

www.ideone.com

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл for, от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.

А404

03/07/2016 by Ирина Литвиненко

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

Даны натуральные числа [latex]i[/latex], [latex]j[/latex], действительная матрица размера [latex]18 / 24[/latex], [latex]1\leq i\leq j\leq 24[/latex].
Поменять местами в матрице [latex]i[/latex]-й и [latex]j[/latex]-й столбцы.

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

Вводим матрицу [latex]M[/latex]– строк, [latex]N[/latex]– столбцов. В следующей строке вписываем номера столбцов которые хотим поменять.

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

Матрица, в которой поменялись местами столбцы.

Тесты

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

3 6

0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

import java.util.*;
import java.lang.*;
import java.io.*;

	
class Ideone{
	
	public static final int M = 18;
	public static final int N = 24;


	public static void main (String[] args) throws java.lang.Exception {
		
		double[][] a = new double[M][N];
		
		Scanner in = new Scanner(System.in);
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				a[i][j] = in.nextDouble();
			}
		}
		int i , j;
		
		i = in.nextInt();
		j = in.nextInt();
	
		for(int k = 0; k < M; k++){
			double temp = a[k][i-1];
			a[k][i-1] = a[k][j-1];
			a[k][j-1] = temp;
		}
		
		for(int q = 0; q < M; q++){
			for(int z = 0; z < N; z++){
				System.out.print(a[q][z] + ((z == N-1)? "\n": " "));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

public static final int M = 18;

public static final int N = 24;

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

double[][] a = new double[M][N];

Scanner in = new Scanner(System.in);

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

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

a[i][j] = in.nextDouble();

}

int i , j;

i = in.nextInt();

j = in.nextInt();

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

double temp = a[k][i-1];

a[k][i-1] = a[k][j-1];

a[k][j-1] = temp;

}

for(int q = 0; q < M; q++){

for(int z = 0; z < N; z++){

System.out.print(a[q][z] + ((z == N-1)? "\n": " "));

}

www.ideone.com

Решение

Для задания размера матрицы объявлены константы M и N. В вложенном цикле вводим значения матрицы. Вводим номера столбцов, которые мы хотим переставить. В цикле переставляем местами элементы указанных столбцов. Затем выводим матрицу.

e-olymp 141. Минимальная сумма цифр

01/07/2016 by Ирина Литвиненко

Задача взята с сайта www.e-olymp.com

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

Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

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

Во входном файле два числа [latex]M[/latex] и [latex]N[/latex], [latex]1\le M\le N\le 1000000[/latex].

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

В выходной файл нужно записать ответ – одно число.

Тесты

№	M	N	Вывод
1	1	100	3
2	2	17	1
3	32	1024	2
4	1	1000000	7
5	10	10	1

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

import java.util.*;
import java.lang.*;
import java.io.*;


class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int sumMin, counter = 1;
		
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		int n = scanner.nextInt();
		
		sumMin = sumOfDigits(m);
		
		for(int i = m + 1; i <= n; i++) {
			if (sumOfDigits(i) < sumMin) {
				sumMin = sumOfDigits(i);
				counter = 1;
			} else if (sumOfDigits(i) == sumMin)   
		    counter++;
		}
		System.out.println(counter);
	}
	
	public static int sumOfDigits(int a){
		int sum = 0;
		while (a > 0) {
			sum += a%10;
			a /= 10;
		}
	return sum;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int sumMin, counter = 1;

Scanner scanner = new Scanner(System.in);

int m = scanner.nextInt();

int n = scanner.nextInt();

sumMin = sumOfDigits(m);

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

if (sumOfDigits(i) < sumMin) {

sumMin = sumOfDigits(i);

counter = 1;

} else if (sumOfDigits(i) == sumMin)

counter++;

}

System.out.println(counter);

}

public static int sumOfDigits(int a){

int sum = 0;

while (a > 0) {

sum += a%10;

a /= 10;

}

return sum;

}

www.ideone.com

Решение
Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму [latex](sumMin)[/latex] сумме цифр первого числа [latex]M[/latex], счетчик количества элементов с минимальной суммой цифр изначально равен 1. В цикле подсчитываем сумму цифр каждого последующего числа, если найдется число с меньшей суммой цифр, значит теперь эта сумма и является минимальной, присваиваем её значение переменной [latex]sumMin[/latex]. Если же встречаются элементы, сумма цифр которых равна [latex]sumMin[/latex], увеличиваем счетчик. Он и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.
Ссылка на полностью засчитанное решение на сайте e-olymp.

e-olymp 905. Какой треугольник?

01/07/2016 by Ирина Литвиненко

Задача взята с сайта www.e-olymp.com

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

Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон.

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

В единственной строке задано [latex]3[/latex] целых числа – длины сторон треугольника. Длины сторон не превышают [latex]100[/latex].

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

В единственной строке вывести [latex]1[/latex], если треугольник равносторонний, [latex]2[/latex] если равнобедренный и [latex]3[/latex] если разносторонний.

Код

import java.util.*;
import java.lang.*;
import java.io.*;

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

		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int c = scanner.nextInt();
		int result;
		
		/*if (a == b && b == c && a == c) {
			System.out.print(1);
		}
		else if (a == b || b == c || a == c) {
			System.out.print(2);
		}
		else {
			System.out.print(3);
		}*/
		
		result = (a == b && b == c && a == c) ? 1 : (a == b || b == c || a == c) ? 2 : 3;
		
		System.out.print(result);

	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

Scanner scanner = new Scanner(System.in);

int a = scanner.nextInt();

int b = scanner.nextInt();

int c = scanner.nextInt();

int result;

/*if (a == b && b == c && a == c) {

System.out.print(1);

}

else if (a == b || b == c || a == c) {

System.out.print(2);

}

else {

System.out.print(3);

}*/

result = (a == b && b == c && a == c) ? 1 : (a == b || b == c || a == c) ? 2 : 3;

System.out.print(result);

}

www.ideone.com

№	Входные данные	Выходные данные
1	3 3 3	1
2	3 4 3	2
3	3 4 5	3

Решение

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

Для начала задаем три переменные [latex]a[/latex], [latex]b[/latex] и [latex]c[/latex], которые равны сторонам треугольника. Вводим их произвольно. Для того, чтобы определить какой это треугольник мы задаем параметры :

если [latex]a=b=c[/latex], то есть все стороны равны, то у нас равносторонний треугольник;
если [latex]a=b[/latex] или [latex]b=c[/latex], или [latex]a=c[/latex], то есть две из трех сторон треугольника равны, то у нас равнобедренный треугольник;
если [latex]a\neq b\neq c[/latex], стороны не равны, то у нас разносторонний треугольник.

e-olymp 248. Юный садовод

30/06/2016 by Ирина Литвиненко

Задача взята с сайта www.e-olymp.com

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

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

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

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

Количество ярусов $n (0 \leq n \leq 1000)$ на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

№	Входные данные	Выходные данные
1	3	13
2	0	1
3	50	2551
4	560	314161

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

import java.lang.*;
import java.io.*;
import java.util.Scanner;

class Main {
	
	public static void main (String args[]) {
 
		int a1 = 2;
		int d = 2;
		int sum = 0;
		
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
 
		sum = ( ( 2 * a1 + d * (n - 1) ) / 2 ) * n;
 
		System.out.println(sum + 1);
 
	}
}

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

public static void main (String args[]) {

int a1 = 2;

int d = 2;

int sum = 0;

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

sum = ( ( 2 * a1 + d * (n - 1) ) / 2 ) * n;

System.out.println(sum + 1);

}

www.ideone.com

Решение

Для решения этой задачи необходимо найти сумму арифметической прогрессии, где [latex]a_1=2[/latex] и [latex]d=2[/latex], и добавить к ней единицу (лист с верхушки). Для этого можно воспользоваться формулой суммы арифметической прогрессии [latex]S_n =\frac{2a_1 + d(n-1)}{2}n.[/latex]

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Ирина Литвиненко

e-olimp 6129. Дек неограниченного размера

Задача:

Решение

Class Matrix

e-olymp 2162. Палиндром

А137е

А404

e-olymp 141. Минимальная сумма цифр

e-olymp 905. Какой треугольник?

e-olymp 248. Юный садовод