acm.timus.ru №2002. Тестовое задание

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

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

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

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq{n}\leq100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные

Результат

logout vasya

success: new user added

fail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Решение

Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value) и HashSet (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

«register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
«login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
«logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
put(Key K, Value V) — записывает пару ключ-значение в структуру;
get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:

contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
add(Object o) — добавляет элемент во множество;
remove(Object o) — удаляет элемент из множества.

Теперь для С++:

В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:

find (K key) — возвращает итератор элемента.
end() — возвращает итератор за последним элементом.

set или без него?

Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.

Код на Java:

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

 class Ideone {
    public static void main (String[] args) {
        
        //create an DB for online and reged users
        Map DB = new HashMap<String, String> (); 
        HashSet <String> DBin = new HashSet <String> ();
        
        Scanner in = new Scanner (System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        //a number of queries
        int n = in.nextInt();
        
        
        for (int i = 0; i < n; i++){
            String s, log, pass;
            
            //command
            s = in.next();
            
            if (s.equals("register")){
                log = in.next();    //login
                pass = in.next();   //password
                if (DB.containsKey(log)){   //login in DB?
                    out.println("fail: user already exists");
                    out.flush();
                }
                else {
                    DB.put(log, pass);
                    out.println("success: new user added");
                    out.flush();
                }
            }
            
            if (s.equals("login")){
                log = in.next();
                pass = in.next();
                if (DB.containsKey(log)){ //if user is reg
                    if (pass.equals(DB.get(log))) { //if the password is well
                        if (!DBin.contains(log)) {  //online?
                            DBin.add(log);
                            out.println("success: user logged in");
                            out.flush();
                        }
                        //Errors
                        else {
                            out.println("fail: already logged in");
                            out.flush();
                        }
                    }
                    else {
                        out.println("fail: incorrect password");
                        out.flush();
                    }
                }
                else {
                    out.println("fail: no such user");
                    out.flush();
                }
            }
            if (s.equals("logout")){
                log = in.next();
                if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.
                    out.println("fail: no such user");
                    out.flush();
                }
                else {
                    if (!DBin.contains(log)){   //so offline user does
                        out.println("fail: already logged out");
                        out.flush();
                    }
                    else {
                        DBin.remove(log);
                        out.println("success: user logged out");
                        out.flush();
                    }
                }
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

//create an DB for online and reged users

Map DB = new HashMap<String, String> ();

HashSet <String> DBin = new HashSet <String> ();

Scanner in = new Scanner (System.in);

PrintWriter out = new PrintWriter(System.out);

//a number of queries

int n = in.nextInt();

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

String s, log, pass;

//command

s = in.next();

if (s.equals("register")){

log = in.next(); //login

pass = in.next(); //password

if (DB.containsKey(log)){ //login in DB?

out.println("fail: user already exists");

out.flush();

}

else {

DB.put(log, pass);

out.println("success: new user added");

out.flush();

}

if (s.equals("login")){

log = in.next();

pass = in.next();

if (DB.containsKey(log)){ //if user is reg

if (pass.equals(DB.get(log))) { //if the password is well

if (!DBin.contains(log)) { //online?

DBin.add(log);

out.println("success: user logged in");

out.flush();

}

//Errors

else {

out.println("fail: already logged in");

out.flush();

}

else {

out.println("fail: incorrect password");

out.flush();

}

else {

out.println("fail: no such user");

out.flush();

}

if (s.equals("logout")){

log = in.next();

if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.

out.println("fail: no such user");

out.flush();

}

else {

if (!DBin.contains(log)){ //so offline user does

out.println("fail: already logged out");

out.flush();

}

else {

DBin.remove(log);

out.println("success: user logged out");

out.flush();

}

Код на С++:

#include <iostream>
#include <stdio.h>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;

struct status { //status - password and online
    string password;
    bool online = false;
};

map <string, status> database; //user database


int main () {
    int n; cin >> n; //number of queries
    typedef std::map<std::string, status> db; // use this typedef for an iterator
    while (n--){
        string com, login; //command and login
        status query; //for status input
        cin >> com;
        if (com == "register"){
            cin >> login >> query.password;
            db::iterator it = database.find(login); //returning an iterator
            if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db
                cout << "fail: user already exists\n";
            }
            else {
                database[login].password = query.password; // register
                cout << "success: new user added\n";
            }
        }
        //user can log in if he isn't online but he is registered
        if (com == "login") {
            cin >> login >> query.password;
            db::iterator it = database.find(login);
            if (it != database.end()){
                if (query.password == database[login].password){
                    if(!database[login].online){
                        database[login].online = true;
                        cout << "success: user logged in\n";
                    }
                    else cout << "fail: already logged in\n";
                }
                else cout << "fail: incorrect password\n";
            }
            else cout << "fail: no such user\n";
        }
        //logout
        if (com == "logout") {
            cin >> login;
            if (database.find(login) == database.end()) cout << "fail: no such user\n";
            else {
                if (!database[login].online) cout << "fail: already logged out\n";
                else {

                    database[login].online = false;
                    cout << "success: user logged out\n";
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <string>

#include <iomanip>

#include <stack>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

struct status { //status - password and online

string password;

bool online = false;

};

map <string, status> database; //user database

int main () {

int n; cin >> n; //number of queries

typedef std::map<std::string, status> db; // use this typedef for an iterator

while (n--){

string com, login; //command and login

status query; //for status input

cin >> com;

if (com == "register"){

cin >> login >> query.password;

db::iterator it = database.find(login); //returning an iterator

if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db

cout << "fail: user already exists\n";

}

else {

database[login].password = query.password; // register

cout << "success: new user added\n";

}

//user can log in if he isn't online but he is registered

if (com == "login") {

cin >> login >> query.password;

db::iterator it = database.find(login);

if (it != database.end()){

if (query.password == database[login].password){

if(!database[login].online){

database[login].online = true;

cout << "success: user logged in\n";

}

else cout << "fail: already logged in\n";

}

else cout << "fail: incorrect password\n";

}

else cout << "fail: no such user\n";

}

//logout

if (com == "logout") {

cin >> login;

if (database.find(login) == database.end()) cout << "fail: no such user\n";

else {

if (!database[login].online) cout << "fail: already logged out\n";

else {

database[login].online = false;

cout << "success: user logged out\n";

}

return 0;

}

Результаты

Обе реализации прошли все тесты на Тимусе с такими результатами:

Язык	Время работы	Память
С++	0.015	412 КБ
Java	0.124	1 804 КБ

Ссылки

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-olymp 4850. Шайтан-машинка

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

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.

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

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

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

Вывести минимальное необходимое количество действий.

Задача
Зачтённое решение

Код

Ideone

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе
    int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
    return res;
}

bool was [10000]; //массив использованных вершин.
int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
queue<int> q; //очередь для BFS

//BFS
void bfs (int start, int finish){
    if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
        cout << 0 << endl;
        return;
    }
    else {
        for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
            vertex[i]=1;
        }
        q.push (start); //будем рассматривать каждую вершину
        was[start] = true;
        while (!q.empty()){
            int tmp = q.front(); //рассматриваемая вершина
            q.pop();
            int tmp1 = tmp;
            tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
            if (!was[tmp1]){
                if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                    q.push(tmp1);
                    vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
                }
            }
            //действия повторяются для других операций.
            tmp1=tmp;
            tmp1 += sum_n(tmp1);
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
            tmp1=tmp;
            tmp1 -= 2;
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b; //ввод начала и конца
    bfs (a, b);//процедура выполнения
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе

int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;

return res;

}

bool was [10000]; //массив использованных вершин.

int vertex[10000]; //подсчёт кол-ва пройденных рёбер..

queue<int> q; //очередь для BFS

//BFS

void bfs (int start, int finish){

if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы.

cout << 0 << endl;

return;

}

else {

for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1

vertex[i]=1;

}

q.push (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.empty()){

int tmp = q.front(); //рассматриваемая вершина

q.pop();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.push(tmp1);

vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum_n(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

int main() {

int a, b;

cin >> a >> b; //ввод начала и конца

bfs (a, b);//процедура выполнения

return 0;

}

Код на Java:

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

class ShaitanEngines {
    private static int N = 10001;
    private static boolean [] was = new boolean [N];
    private static int [] vertice = new int [N];
    private static Queue <Integer> q = new LinkedList();
    public static int sum (int n) {
        return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);  
    }
    public static void bfs (int start, int finish) {
        if (start == finish) {
            System.out.println(1);
            return;
        }
        else {
            for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1
                vertice[i]=1;
            }
            q.add (start); //будем рассматривать каждую вершину
            was[start] = true;
            while (!q.isEmpty()){
                int tmp = q.element(); //рассматриваемая вершина
                q.remove();
                int tmp1 = tmp;
                tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
                if (!was[tmp1]){
                    if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                        q.add(tmp1);
                        vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.
                    }
                }
                //действия повторяются для других операций.
                tmp1=tmp;
                tmp1 += sum(tmp1);
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
                tmp1=tmp;
                tmp1 -= 2;
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
            }
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        bfs(a, b);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class ShaitanEngines {

private static int N = 10001;

private static boolean [] was = new boolean [N];

private static int [] vertice = new int [N];

private static Queue <Integer> q = new LinkedList();

public static int sum (int n) {

return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);

}

public static void bfs (int start, int finish) {

if (start == finish) {

System.out.println(1);

return;

}

else {

for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1

vertice[i]=1;

}

q.add (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.isEmpty()){

int tmp = q.element(); //рассматриваемая вершина

q.remove();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.add(tmp1);

vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int a = sc.nextInt();

int b = sc.nextInt();

bfs(a, b);

}

Решение

Для решения данной задачи я решил использовать алгоритм BFS (поиск в ширину). Обычно, данный алгоритм применяется для поиска пути от одной вершины к другой, причём длина пути должна быть минимальной.

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

Related Images:

e-olimp 5080. Количество висячих вершин 1

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

Код:

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

int gr[1001][1001]; // матрица смежности
int n; //кол-во вершин
	
//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице 
//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int ans = 0; //предположим, что граф не имеет висячих вершин 
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> gr[i][j];	//ввод матрицы смежности
	for (int i=0; i<n; i++){
		int cnt = 0; //счётчик
		for (int j=0; j<n; j++){
			if (gr[i][j] == 1) cnt++;  //подсчёт степени
		}
		if (cnt==1) ans++;  //проверка на висячую вершину
	}
	cout << ans << endl;	//вывод ответа
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int gr[1001][1001]; // матрица смежности

int n; //кол-во вершин

//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во

//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.

//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице

//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {

ios::sync_with_stdio(false);

cin >> n;

int ans = 0; //предположим, что граф не имеет висячих вершин

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

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

cin >> gr[i][j]; //ввод матрицы смежности

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

int cnt = 0; //счётчик

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

if (gr[i][j] == 1) cnt++; //подсчёт степени

}

if (cnt==1) ans++; //проверка на висячую вершину

}

cout << ans << endl; //вывод ответа

return 0;

}

Related Images:

AA17

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

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

Решение: Заводим цикл от первого символа, в цикле сравниваем каждый символ с предыдущим. Если они совпадают — удаляем один из них.

Код C++:

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

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 1; i < s.length(); i++){
        if (s[i] == s[i-1]){
            s.erase(s.begin()+i);
        }
    }
    cout << s << endl;
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

for (int i = 1; i < s.length(); i++){

if (s[i] == s[i-1]){

s.erase(s.begin()+i);

}

cout << s << endl;

return 0;

}

Код Java:

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

class Ideone {
	public static void main (String[] args) {
		String st;
		Scanner sc = new Scanner (System.in);
		st = sc.next();
		StringBuilder s = new StringBuilder(st);
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i-1)){
				s.deleteCharAt(i);
			}
		}
		System.out.println(s.toString());
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

String st;

Scanner sc = new Scanner (System.in);

st = sc.next();

StringBuilder s = new StringBuilder(st);

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == s.charAt(i-1)){

s.deleteCharAt(i);

}

System.out.println(s.toString());

}

Тесты:

Строка	Результат
aassddff	asdf
1122345566	123456

Related Images:

Ю12.19

24/11/2014 by Марченко Філіп Олександрович

Задача: В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

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

using namespace std;
int count_words (string s) //функция подсчитывает слова в строке
{
    s+=' ';
    int a = 0;
    for (size_t i=0; i<s.length(); i++)
        if (s[i]==' ') a++;
    return a;
}
string * cut_words (string s) //функция разрезает строку на слова и возвращает массив
{
    s+=' ';
    int c = 0;
    int p = 0;
    int i=0;
    string *s_return = new string [count_words(s)];
    while (s.length() != 0)
        {
            if (s[i] != ' ')
            {
                c++;
                i++;
            }
            else
            {
                i=0;
                s_return[p] = s.substr(0, c);
                s.erase(0, c+1);
                c = 0;
                p++;
            }
        }
   return s_return;
}

int main ()
{
    string s;
    getline (cin, s);
	string *s_return;
	s_return = cut_words(s);
	for (int i=0; i<count_words(s); i++)
    {
    	string s_tmp = s_return[i];
        if (s_tmp.empty())					//если ячейка пуста, то продолжаем дальше
            {
                continue;
            }
        else				//а если нет, то ищем перестановки.
        {
        	int p = 0;
            for (int j=i+1; j<count_words(s); j++)
            {
                if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin()))	//если перестановка
                    if (s_tmp.length() == s_return[j].length())		//и если одинаковая длина слов
                    {
                        cout<<s_return[j]<<endl;		//выводим на экран
                        s_return[j].clear(); //очищаем строку
                        p++;
                    }
            }
            if (p>=1) cout<<s_tmp<<endl;	
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string>

using namespace std;

int count_words (string s) //функция подсчитывает слова в строке

{

s+=' ';

int a = 0;

for (size_t i=0; i<s.length(); i++)

if (s[i]==' ') a++;

return a;

}

string * cut_words (string s) //функция разрезает строку на слова и возвращает массив

{

s+=' ';

int c = 0;

int p = 0;

int i=0;

string *s_return = new string [count_words(s)];

while (s.length() != 0)

{

if (s[i] != ' ')

{

c++;

i++;

}

else

{

i=0;

s_return[p] = s.substr(0, c);

s.erase(0, c+1);

c = 0;

p++;

}

return s_return;

}

int main ()

{

string s;

getline (cin, s);

string *s_return;

s_return = cut_words(s);

for (int i=0; i<count_words(s); i++)

{

string s_tmp = s_return[i];

if (s_tmp.empty()) //если ячейка пуста, то продолжаем дальше

{

continue;

}

else //а если нет, то ищем перестановки.

{

int p = 0;

for (int j=i+1; j<count_words(s); j++)

{

if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin())) //если перестановка

if (s_tmp.length() == s_return[j].length()) //и если одинаковая длина слов

{

cout<<s_return[j]<<endl; //выводим на экран

s_return[j].clear(); //очищаем строку

p++;

}

if (p>=1) cout<<s_tmp<<endl;

}

return 0;

}

Тесты:

Исходный словарь	Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy	no on three there own now how who thing night its sit name mean
Все слова

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation . Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

Для проверки правильности работы программы, воспользуйтесь ссылкой .

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.

Related Images:

А410б

12/11/2014 by Марченко Філіп Олександрович

Задача: Дана целочисленная матрица [latex][a_{i,j},\ i=1,\ldots,n;\ j=1,\ldots,m][/latex]. Получить [latex]b_{1},\ldots,b_{n}[/latex], где

[latex]{b}_{i}=\sum_{j=1}^{n}(-1)^{i+j}a_{ij}[/latex]

Код на С++:

#include <iostream>
#include <stdio.h>

using namespace std;

int main () {
    int n, m; cin>>n>>m; //вводим размер матрицы
    int A[n][m];    //основная матрица
    int B[n];   //результаты
    for (int i=0; i<n; i++) {
         for (int j=0; j<m; j++) {
            cin>>A[i][j];
         }
    }
    for (int i=0; i<n; i++){
    	B[i]=0;        //обнуляем элементы массива для подсчёта суммы
        for (int j=0; j<m; j++){
            B[i] += ((i+j)%2==0? 1: -1) * A[i][j]; 
        }
    }
    for (int i=0; i<n; i++)
            cout<<B[i]<<" "; //Результаты на экран

    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main () {

int n, m; cin>>n>>m; //вводим размер матрицы

int A[n][m]; //основная матрица

int B[n]; //результаты

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

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

cin>>A[i][j];

}

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

B[i]=0; //обнуляем элементы массива для подсчёта суммы

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

B[i] += ((i+j)%2==0? 1: -1) * A[i][j];

}

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

cout<<B[i]<<" "; //Результаты на экран

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Count{
	public static void main (String[] args) {
		int n, m; 
		Scanner sc = new Scanner (System.in);
		n = sc.nextInt();
		m = sc.nextInt();
 
	    int[][] A = new int [n][m];    
	    int[] B;   
	 	B = new int [n];
 
	    for (int i=0; i<n; i++) {
	         for (int j=0; j<m; j++) {
	            A[i][j] = sc.nextInt();
	         }
	    }
	    for (int i=0; i<n; i++){
	    	B[i] = 0;       
	        for (int j=0; j<m; j++){
	            B[i] += ((i+j)%2==0? 1: -1) * A[i][j]; 
	        }
	    }
	    for (int i=0; i<n; i++)
	            System.out.println (B[i] + " "); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Count{

public static void main (String[] args) {

int n, m;

Scanner sc = new Scanner (System.in);

n = sc.nextInt();

m = sc.nextInt();

int[][] A = new int [n][m];

int[] B;

B = new int [n];

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

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

A[i][j] = sc.nextInt();

}

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

B[i] = 0;

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

B[i] += ((i+j)%2==0? 1: -1) * A[i][j];

}

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

System.out.println (B[i] + " ");

}

Тесты:

[latex]n*m[/latex]	[latex]\begin{bmatrix}{a}_{ij}\end{bmatrix}[/latex]	[latex]b_{i}[/latex]
3*3	1 2 3 4 5 6 7 8 9	2 -5 8
1*6	2 -4 6 -8 10 -12	42
3*5	1 3 5 7 9 11 13 15 17 19 21 23 25 27 29	5 -15 25

Алгоритм: Чтобы решить эту задачу, необходимо было создать два массива: входной массив (матрицу) и массив результатов (который надо инициализировать нулями). Далее, необходимо завести цикл, в котором будет проводится, собственно говоря, подсчёт. В зависимости от суммы номеров строки и столбца исходной матрицы, -1 в степени этой суммы будет принимать положительное или отрицательное значение. Соответственно, к результату будет прибавляться или отниматься значение, стоящее на i-том j-том месте.

Для проверки правильности работы программы, воспользуйтесь ссылкой.

Related Images:

А137а

02/11/2014 by Марченко Філіп Олександрович

Задача: Даны натуральное число [latex]n[/latex] и действительные числа [latex]a_{1},\ldots,a_{n}[/latex].

Вычислить:

[latex]a_{1},a_{1}+a_{2},\ldots,a_{1}+a_{2}+\ldots+a_{n}[/latex].

Тесты:

Кол-во элементов [latex]n[/latex]	[latex]a_{1},a_{2},\ldots,a_{n}[/latex]	result в каждой итерации
7	1, 2, 3, 4, 5, 6, 7	1, 3, 6, 10, 15, 21, 28
10	10, 12, 14, 16, 18, 20, 21, 23, 25, 27	10, 22, 36, 52, 70, 90, 111, 134, 159, 186
5	0.1, 0.2, 0.3, 0.4, 0.5	0.1, 0.3, 0.6, 1.0, 1.5
5	-1, -2, 3, 4, -5	-1, -3, 0, 4, -1

Код на С++:

#include <iostream>
#include <stdio.h>

using namespace std;

int main () {
    double a, result = 0; // заводим переменные для считывания числа и подсчёта суммы
    int n;  //кол-во элементов в ряду
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>a; //вводим число
        result+=a; //прибавляем к результату
        cout<<result<<endl; //выводим на экран результат сложения
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main () {

double a, result = 0; // заводим переменные для считывания числа и подсчёта суммы

int n; //кол-во элементов в ряду

cin>>n;

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

cin>>a; //вводим число

result+=a; //прибавляем к результату

cout<<result<<endl; //выводим на экран результат сложения

}

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Count{
	public static void main (String[] args) {
		double a, result = 0; 
		Scanner sc = new Scanner (System.in);
	    int n;  
	    n = sc.nextInt();
	    for (int i=1; i<=n; i++){
	        a = sc.nextDouble(); 
	        result+=a; 
	        System.out.println (result);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Count{

public static void main (String[] args) {

double a, result = 0;

Scanner sc = new Scanner (System.in);

int n;

n = sc.nextInt();

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

a = sc.nextDouble();

result+=a;

System.out.println (result);

}

Решение: Для подсчёта суммы в данной задаче надо было организовать цикл for (поскольку указано количество элементов в ряду), и с каждой итерацией прибавлять к результату result (которому предварительно придано значение 0) введённое с клавиатуры значение, потом выводить результат на экран.

Для проверки правильности работы программы, воспользуйтесь ссылкой.

Related Images:

А116а

01/11/2014 by Марченко Філіп Олександрович

Задача: Даны натуральное число [latex]n[/latex] и действительное [latex]x[/latex]. Найти:

[latex]\sum_{i=1}^{n}\frac{x^{i}}{i!}[/latex]

Тесты:

Число [latex]x[/latex], возводимое в степень	Кол-во шагов [latex]n[/latex]	Результат result
5	3	38.(3)
4	12	53.5832
20	5	34886.7
0	0	0
10	10	12841.3

Решение: Для решения данной задачи надо было провести численный анализ. Каждый раз высчитывать и прибавлять результат нельзя, т.к программа будет работать очень долго. По-этому стоит рассмотреть два значения: текущее и последующее, [latex]x_{n}[/latex] и [latex]x_{n+1}[/latex]. Поделим одно на другое:

[latex]\frac{x_{n+1}}{x_{n}}=\frac{x^{i+1}*i!}{(i+1)*i!*x^{i}}=\frac{x}{i+1}[/latex]

Поскольку сумму ряда считаем с 1, то делить будем на [latex]i[/latex], а не на [latex](i+1)[/latex].

Код на С++:

#include <iostream>
#include <stdio.h>

using namespace std;

int main () {
   double result=0, x, x_tmp=1; //заводим счётчик суммы, x, n
   int n;
   cin>>x>>n; //вводим x и n
   for (int i=1; i<=n; i++ ){ //умножаем временную переменную на x/i. прибавляем её к сумме ряда.
        x_tmp*=x/i;
        result += x_tmp;
   }
   cout<<result; //выводим результат
   return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main () {

double result=0, x, x_tmp=1; //заводим счётчик суммы, x, n

int n;

cin>>x>>n; //вводим x и n

for (int i=1; i<=n; i++ ){ //умножаем временную переменную на x/i. прибавляем её к сумме ряда.

x_tmp*=x/i;

result += x_tmp;

}

cout<<result; //выводим результат

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
 
class Count {
	public static void main (String[] args) {
   	   double result = 0, x, x_tmp = 1; 
	   int n;
	   Scanner sc = new Scanner (System.in);
	   x = sc.nextDouble();
	   n = sc.nextInt();
	   for (int i=1; i<=n; i++ ){ 
	        x_tmp*=x/i;
	        result += x_tmp;
	   }
	   System.out.println (result);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Count {

public static void main (String[] args) {

double result = 0, x, x_tmp = 1;

int n;

Scanner sc = new Scanner (System.in);

x = sc.nextDouble();

n = sc.nextInt();

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

x_tmp*=x/i;

result += x_tmp;

}

System.out.println (result);

}

Для проверки правильности работы кода, воспользуйтесь ссылкой.

Related Images:

Ю4.18

01/11/2014 by Марченко Філіп Олександрович

Задача: В массиве [latex]Z(2n)[/latex] каждый элемент с чётным индексом поменять местами с предыдущим, то есть получить последовательность чисел [latex]z_{2}[/latex], [latex]z_{1}[/latex], [latex]z_{4}[/latex], [latex]z_{3}[/latex], \ldots ,[latex]z_{2n}[/latex], [latex]z_{2n-1}[/latex].

Тесты:

[latex]n[/latex]	Входной массив	Обработанный массив
5	1 2 3 4 5 6 7 8 9 10	2 1 4 3 6 5 8 7 10 9
7	2 4 6 8 10 12 14 16 18 20 22 24 26 28	4 2 8 6 12 10 16 14 20 18 24 22 28 26

Код на С++:

#include <iostream>
#include <stdio.h>

using namespace std;

int main () {
    int n;
    cin>>n;  //задаём размерность массива
    n*=2;
    int A[n+1]; //VLA
    for (int i=1; i<=n; i++) { //присваиваем каждому элементу массива свой порядковый номер (для удобства проверки работы алгоритма) 
        cin>>A[i];
        cout<<A[i]<<' ';
    }
    for (int i=2; i<=n; i++) {
        if (i%2==0) { //если номер элемента чётный,
            int tmp = A[i];  //то меняем местами чётный и нечётный элементы
            A[i]=A[i-1];
            A[i-1] = tmp;
        }
    }
    for (int i=1; i<=n; i++) { //вывод изменённого массива
        cout<<A[i]<<' ';
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main () {

int n;

cin>>n; //задаём размерность массива

n*=2;

int A[n+1]; //VLA

for (int i=1; i<=n; i++) { //присваиваем каждому элементу массива свой порядковый номер (для удобства проверки работы алгоритма)

cin>>A[i];

cout<<A[i]<<' ';

}

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

if (i%2==0) { //если номер элемента чётный,

int tmp = A[i]; //то меняем местами чётный и нечётный элементы

A[i]=A[i-1];

A[i-1] = tmp;

}

for (int i=1; i<=n; i++) { //вывод изменённого массива

cout<<A[i]<<' ';

}

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Nums {
	public static void numSwap (int[] A, int a, int b) {
		int tmp = A[a];
		A[a] = A[b];
		A[b]= tmp;
	}
	public static void main (String[] args) {
		Scanner sc = new Scanner (System.in);
		int n;
		n = sc.nextInt();
		int[] A;
		A = new int [2*n];
		for (int i=0; i<2*n; i++)  A[i] = sc.nextInt();
		for (int i=1; i<2*n; i+=2){
			numSwap (A, i-1, i);
		}
		for (int i=0; i<2*n; i++) System.out.print (A[i] + " ");
		System.out.print ("\n");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Nums {

public static void numSwap (int[] A, int a, int b) {

int tmp = A[a];

A[a] = A[b];

A[b]= tmp;

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int n;

n = sc.nextInt();

int[] A;

A = new int [2*n];

for (int i=0; i<2*n; i++) A[i] = sc.nextInt();

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

numSwap (A, i-1, i);

}

for (int i=0; i<2*n; i++) System.out.print (A[i] + " ");

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

}

Решение: Для того, чтобы поменять местами чётный и нечётный по порядковому номеру элементы массива, надо определить чётность порядкового номера. Для этого надо проверить остаток от деления на 2, т.е если [latex]imod2=0[/latex], то меняем предыдущий элемент с текущим.

Для проверки правильности работы программы, воспользуйтесь ссылкой.

Related Images:

Ю3.20

01/11/2014 by Марченко Філіп Олександрович

Задача: Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]x = \sqrt[p]{a}[/latex] по рекуррентному соотношению Ньютона:

[latex]x_{n+1}=\frac{1}{p}*\left[(p-1)x_{n}+\frac{a}{x_{n}^{p-1}}\right][/latex] [latex]x_{0} = a[/latex]

Сколько итераций надо выполнить, чтобы для достижения заданной погрешности [latex]\varepsilon[/latex] выполнялось соотношение:

[latex]\left|x_{n+1}-x_{n}\leq\varepsilon\right|[/latex]?

Тесты:

[latex]a[/latex]	[latex]p[/latex]	Значение корня [latex]x[/latex]	Значение корня [latex]x[/latex], подсчитанного с помощью соотношения	Количество итераций
57	5	2.24479	2.24479	18
16	2	4	4	5
230	2	15.1658	15.1658	7
9	3	2.08008	2.08008	7

Код на С++:

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

using namespace std;
double pow_b (double a, int n){
    if (n==0) return 1;
    double result = 1;
    while (n>0) {
        if (n%2==0) {
            n/=2;
            a*=a;
        }
        else {
            n--;
            result*=a;
        }
    }
    return result;
}
int main () {
    double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность
    cin>>a>>p;
    double x=pow(a, 1/p);  //подсчитываем значение
    double xn=a, x_prev;
    int i=0;
    while (fabs(x-xn) > eps){  //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона
        x_prev=xn;
        xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));
        i++;
    }
    cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <math.h>

using namespace std;

double pow_b (double a, int n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

int main () {

double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность

cin>>a>>p;

double x=pow(a, 1/p); //подсчитываем значение

double xn=a, x_prev;

int i=0;

while (fabs(x-xn) > eps){ //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона

x_prev=xn;

xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));

i++;

}

cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.

return 0;

}

Код на Java:

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


class Ideone {
	public static double bPow (double a, double n){
		if (n==0) return 1;
	    double result = 1;
	    while (n>0) {
	        if (n%2==0) {
	            n/=2;
	            a*=a;
	        }
	        else {
	            n--;
	            result*=a;
	        }
	    }
    	return result;
	}
	public static void main (String[] args)	{
		Scanner sc = new Scanner (System.in);
		int Iterations = 0;
		double eps = sc.nextDouble();
		double a = sc.nextDouble();
		double p = sc.nextDouble();
		double x = a;
		double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;
		while (Math.abs(x_next - x) > eps) {
			x = x_next;
			x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );
			Iterations++;
		}
		System.out.println("Result: " + x_next + "; Iterations: " + Iterations);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static double bPow (double a, double n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int Iterations = 0;

double eps = sc.nextDouble();

double a = sc.nextDouble();

double p = sc.nextDouble();

double x = a;

double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;

while (Math.abs(x_next - x) > eps) {

x = x_next;

x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );

Iterations++;

}

System.out.println("Result: " + x_next + "; Iterations: " + Iterations);

}

Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn, подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.

UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.

Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации:

Когда степень чётна;
Когда степень не чётна;

Ситуация 1 : Проведя несложный анализ можно заметить, что [latex]{a}^{p}[/latex] можно представить в виде

[latex](a^{\frac{p}{2}})^{2}[/latex].

Ситуация 2: В этой ситуации необходимо перейти в степень [latex]p-1[/latex], которая является чётной.

[latex]a^{p}=a^{p-1} * a[/latex]

И в результате получим алгоритм, который работает за [latex]O(\log n)[/latex].

Проверить правильность работы программы можно здесь (UPD): http://ideone.com/VBLGKO

Related Images:

А60б

23/09/2014 by Марченко Філіп Олександрович

Задача: Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом ( запись [latex](x, y)\epsilon D[/latex] означает, что точка с координатами [latex]x[/latex], [latex]y[/latex] принадлежит [latex]D[/latex]):

[latex]u=\left\{\begin{matrix}-3, \text{if} (x, y)\epsilon D\\ y^{2} \end{matrix}\right.[/latex]

Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Определить [latex]u[/latex].

Код на С++:

#include <iostream>
using namespace std;

int main() {
	double x, y;  
	scanf (" %lf%lf ", &x, &y); // чтение из стандартного потока ввода.
	if (( x*x + y*y <= 1) && (y<=x/2)) {	//утверждение
		printf ("u=-3");		//истина
	}
	else {
		printf ("u = %2.2lf", y*y); 	//ложь
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y;

scanf (" %lf%lf ", &x, &y); // чтение из стандартного потока ввода.

if (( x*x + y*y <= 1) && (y<=x/2)) { //утверждение

printf ("u=-3"); //истина

}

else {

printf ("u = %2.2lf", y*y); //ложь

}

return 0;

}

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат [latex]u[/latex]
[latex]0[/latex]	[latex]0[/latex]	[latex]-3[/latex]
[latex]0[/latex]	[latex]1[/latex]	[latex]1. 00[/latex]
[latex]1[/latex]	[latex]0[/latex]	[latex]-3[/latex]
[latex]-1[/latex]	[latex]0[/latex]	[latex]0. 00[/latex]
[latex]0[/latex]	[latex]-1[/latex]	[latex]-3[/latex]
[latex]0,6[/latex]	[latex]0,8[/latex]	[latex]0. 64[/latex]
[latex]0,5[/latex]	[latex]-0,5[/latex]	[latex]-3[/latex]

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class circle {
	public static void main (String [] args){
		Scanner sc = new Scanner (System.in);
		double x, y;
		x = sc.nextDouble();
		y = sc.nextDouble();
		System.out.println ((( x*x + y*y <= 1) && (y <= x/2))? ("u = -3"):("u = " + y*y));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class circle {

public static void main (String [] args){

Scanner sc = new Scanner (System.in);

double x, y;

x = sc.nextDouble();

y = sc.nextDouble();

System.out.println ((( x*x + y*y <= 1) && (y <= x/2))? ("u = -3"):("u = " + y*y));

}

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

Отсюда следует, что если [latex]x^{2}+y^{2}\leqslant1[/latex] и [latex]y\leqslant\frac{x}{2}[/latex], то точка принадлежит заштрихованной части круга.

Результат [latex]u[/latex] выводится с точностью до двух знаков после запятой.

Запустить код и проверить тесты можно тут: http://ideone.com/N3UoQ7.

Related Images:

Ю1.9

21/09/2014 by Марченко Філіп Олександрович

Кубическое уравнение. Заданы три корня кубического уравнения : [latex]x_{1},x_{2},x_{3}[/latex] . Найти коэффициенты этого уравнения.

[latex] x_{1}[/latex]	[latex] x_{2}[/latex]	[latex] x_{3}[/latex]	Результат [latex]b[/latex]	Результат [latex] c[/latex]	Результат [latex] d[/latex]	Комментарий:
1	2	3	-6.00	11.00	-6.00	Тест пройден
0.5	6	0.78	-7.28	8.07	-2.34	Тест пройден
-1	-2	-2.25	5.25	8.75	4.50	Тест пройден
-0.24	-1	2.24	-1.00	-2.54	-0,54	Тест пройден

#include <iostream>
using namespace std;

int main () {
	double x1, x2, x3;
	scanf ( " %lf %lf %lf ", &x1, &x2, &x3 ); // чтение из стандартного потока ввода.
	double b = -( x1 + x2 + x3 ); // вычисление коэф. b, c, d кубического уравнения.
	double c = x1*x2 + x2*x3 + x3*x1;
	double d = -( x1 * x2 * x3 );
	printf ("b = %2.2lf, c = %2.2lf, d = %2.2lf.", b, c, d); //вывод результата.
	return 0;
}

#include <iostream>

using namespace std;

int main () {

double x1, x2, x3;

scanf ( " %lf %lf %lf ", &x1, &x2, &x3 ); // чтение из стандартного потока ввода.

double b = -( x1 + x2 + x3 ); // вычисление коэф. b, c, d кубического уравнения.

double c = x1*x2 + x2*x3 + x3*x1;

double d = -( x1 * x2 * x3 );

printf ("b = %2.2lf, c = %2.2lf, d = %2.2lf.", b, c, d); //вывод результата.

return 0;

}

Дано кубическое уравнение типа [latex](x — x_{1})(x-x_{2})(x-x_{3})=0[/latex]. После недолгих преобразований я получаю такое выражение:

[latex]x^{3}-(x_{1}+x_{2}+x_{3})x^{2}+(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1})x-x_{1}x_{2}x_{3}=0[/latex].

Потом присваиваю трём переменным выражения для коэффициентов:

[latex]\begin{cases} & \ x_{1}+x_{2}+x_{3}=-b \\ & \ x_{1}*x_{2}+x_{2}*x_{3}+x_{1}*x_{3}= c \\ & \ x_{1}*x_{2}*x_{3}=-d \end{cases}[/latex]

где [latex]b[/latex] — коэффициент при [latex]x^{2}[/latex], [latex] c[/latex] — при [latex]x[/latex], а [latex] d[/latex] — свободный коэффициент.

В итоге, все решение задачи свернулось в 3 этапа:

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

Результат выводится с точностью до двух знаков после запятой.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A {
	public static void main (String [] args){
		double x1, x2, x3;
		Scanner sc = new Scanner (System.in);
		x1 = sc.nextDouble();
		x2 = sc.nextDouble();
		x3 = sc.nextDouble();
		double b = -( x1 + x2 + x3 ); 
		double c = (x1*x2 + x2*x3 + x3*x1);
		double d = -( x1 * x2 * x3 );
		System.out.println (b);
		System.out.println (c);
		System.out.println (d);
	}	
}