e-olimp 4000. Обход в глубину

30/04/2015 by Ковальський Олександр Дмитрович

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

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

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

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

Пример:

Входные данные	Выходные данные
5 1	3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

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

int main()
	{
		int n;
		int s;
		cin>>n>>s;
		s--;
		int matrix[n][n];
		stack<int> st;
		int counter=1;
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						cin>>matrix[i][j];
					}
			}
		for(int j=0;j<n;j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s]=1;
		while(!st.empty())
			{
				int a=st.top();
				st.pop();
				if(matrix[a][a]!=1)
					{
						for(int j=0;j<n;j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a]=1;
					}
				
			}
		cout<<counter<<endl;
	}

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

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

{

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

{

cin>>matrix[i][j];

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt(), s = in.nextInt()-1, counter = 1;
		int[][] matrix = new int[n][n];
		Stack st = new Stack();
		for(int i = 0;i < n; i++)
			{
				for(int j = 0;j < n; j++)
					{
						matrix[i][j] = in.nextInt();
					}
			}
		for(int j = 0; j < n; j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s] = 1;
		while(!st.empty())
			{
				int a = (int) st.peek();
				st.pop();
				if(matrix[a][a] != 1)
					{
						for(int j = 0; j < n; j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a] = 1;
					}
				
			}
		System.out.println(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

int[][] matrix = new int[n][n];

Stack st = new Stack();

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

{

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

{

matrix[i][j] = in.nextInt();

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex], и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

Related Images:

e-olimp 695. Range Variation Query

30/04/2015 by Недомовний Владислав

Задача e-olimp 695.

Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex];
присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex].

Технические условия.

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

Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_{i},y_{i}[/latex].

Если [latex]x_{i}>0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{x_{i}}…a_{y_{i}}[/latex]. При этом [latex]1\leq x_{i}\leq y_{i}\leq 100000[/latex].

Если [latex]x_{i}<0[/latex], то требуется присвоить элементу [latex]a_{-x_{i}}[/latex] значение[latex]y_{i}[/latex]. При этом[latex]-100000\leq x_{i}\leq 1[/latex] и [latex]\left | y_{i} \right |\leq 100000[/latex].

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

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

Пример.

Пример входных данных

Пример выходных данных

1 3

2 4

-2 -100

8 9

-3 -101

2 3

250

234

Решение.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <climits>
using namespace std;
#define length    100000



int main() {
   int a[length];
   for(long long i=1;i<=length;i++)
   {
       a[i-1]=((i%12345)*(i%12345))%12345+((i%23456)*(i%23456)%23456*i%23456)%23456; //заполнение массива
   }
   int k,x,y,result;
   cin>>k; 
   int mmax,mmin; //переменные для хранения максимума и минимума на отрезке
   for(int i=0;i<k;i++)
   {
       cin >> x >> y;
       mmax=INT_MIN;
       mmin=INT_MAX;
       if(x>0)
       {
           for(int i=x-1;i<y;i++) //поиск максимума и минимума на отрезке [x,y]
           {
               if(mmax<a[i]) mmax=a[i];
               if(mmin>a[i]) mmin=a[i];
           }
           cout << mmax-mmin << endl;
       }
       else
       {
           x*=-1;
           a[x-1]=y; //замена x-го элемента на y
       }
   }
}

#include <iostream>

#include <math.h>

#include <algorithm>

#include <climits>

using namespace std;

#define length 100000

int main() {

int a[length];

for(long long i=1;i<=length;i++)

{

a[i-1]=((i%12345)*(i%12345))%12345+((i%23456)*(i%23456)%23456*i%23456)%23456; //заполнение массива

}

int k,x,y,result;

cin>>k;

int mmax,mmin; //переменные для хранения максимума и минимума на отрезке

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

{

cin >> x >> y;

mmax=INT_MIN;

mmin=INT_MAX;

if(x>0)

{

for(int i=x-1;i<y;i++) //поиск максимума и минимума на отрезке [x,y]

{

if(mmax<a[i]) mmax=a[i];

if(mmin>a[i]) mmin=a[i];

}

cout << mmax-mmin << endl;

}

else

{

x*=-1;

a[x-1]=y; //замена x-го элемента на y

}

Так как количество запросов [latex]k\leq 100000[/latex] сначала считаем значение всех элементов последовательности и сохраняем их в массив. Если требуется найти разность между максимумом и минимумом,то находим их проверяя все элементы отрезка и выводим разность. Если требуется заменить элемент, то заменяем соответствующий элемент последовательности на новый.

Ссылка на засчитанное решение.

Данный код на ideone.

В скором времени будет добавлено более эффективное решение с помощью дерева отрезков.

Related Images:

I. Новорічні іграшки

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

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала.

Формулировка

«У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його цікавить чи можна перекласти всі іграшки у одну з коробок (кожна коробка вміщує усі іграшки), якщо з одної коробки у іншу можна перекладати стільки іграшок, скільки у іншій коробці.

Вхідні дані:
Два числа N і M — кількість іграшок у першій та другій коробці (1 ≤ N, М ≤ 2000000000).
Вихідні дані:
Bиведіть 1 – якщо можна перекласти іграшки у одну коробку, або 0 – якщо такої можливості немає.»

Алгоритм

Ограничение на входные данные.
Предположим, что при некоторых [latex]N[/latex], [latex]M[/latex] ответ положительный. Пусть [latex]c = N + M[/latex].
Будем выстраивать последовательность шагов от конца к началу. Стартовая позиция — [latex]\left(c \quad 0 \right)[/latex](подарков в коробках). Очевидно, что прийти в неё можно только из [latex]\left( \frac {c}{2} \quad \frac {c}{2} \right)[/latex]. Определим вид предыдущей позиции: [latex]\begin{cases} a+b=c, \\ a-b=\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} 2a=c+\frac { c }{ 4 } , \\ b=a-\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} a=\frac { 3c }{ 4 } , \\ b=\frac { c }{ 4 } ; \end{cases}[/latex]. Принципиально важно, что показатель знаменателя на каждом шаге монотонно возрастает. В силу конечности [latex]c[/latex], процесс конечен. Меньший член пары имеет общий вид [latex]\frac {c}{2^{n}}[/latex], следовательно, [latex]c = N + M = 2k[/latex] (здесь и далее предполагается, что все переменные — некоторые натуральные числа).
Заметим, что постоянный множитель [latex]k[/latex] не влияет на сходимость. Следовательно, на него можно сократить и суммы [latex]N + M[/latex]. Максимальный из таких [latex]k[/latex] будет [latex]gcd \left(N, M \right)[/latex].
Полученный результат позволяет сформулировать необходимое условие: если решение есть, то сумма чисел [latex]N[/latex] и [latex]M[/latex] равна некоторой степени двойки с точностью до НОД([latex]N, M[/latex]).
Достаточно условие сходимости.
Пусть [latex]N, M[/latex] — некоторые числа, удовлетворяющие необходимому условию. Тогда [latex]\exists n: N=2^{ n }-M[/latex].
Рассмотрим следующий шаг, предполагая, что [latex]N \ge M[/latex]: [latex]\left(2N \quad 2^{n}-2N\right) \sim \left(N \quad 2^{n-1}-N \right)[/latex]) — задачу удалось свести к подзадаче. Повторяя аналогичную процедуру, на [latex]n[/latex]-м шаге придём в позицию, эквивалентную [latex]\left(1 \quad 2^{0}-1 \right) \sim \left(1 \quad 0 \right)[/latex], т.е. последнему шагу. Следовательно, для любого набора данных, удовлетворяющих необходимому условию, решение существует. Следовательно, условие является необходимым и достаточным, с поправкой на тривиальный случай [latex]N = M[/latex].

Реализация

ideone: http://ideone.com/OxWVLi

#include <cstdio>
inline int gcd(int a, int b){
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = (a + b)/gcd(a, b);
    printf("%d\n", (a == b || c == (c & (-c))));
    return 0;
}

#include <cstdio>

inline int gcd(int a, int b){

while(b) b ^= a ^= b ^= a %= b;

return a;

}

int main()

{

int a, b, c;

scanf("%d %d", &a, &b);

c = (a + b)/gcd(a, b);

printf("%d\n", (a == b || c == (c & (-c))));

return 0;

}

ideone: http://ideone.com/Xnupjz

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static int gcd(int a, int b){
        while(b != 0) b ^= a ^= b ^= a %= b;
        return a;
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(); int b = in.nextInt();
        int c = (a + b)/gcd(a, b);
        System.out.println((a == b || c == (c & (-c))) ? 1 : 0);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static int gcd(int a, int b){

while(b != 0) b ^= a ^= b ^= a %= b;

return a;

}

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int a = in.nextInt(); int b = in.nextInt();

int c = (a + b)/gcd(a, b);

System.out.println((a == b || c == (c & (-c))) ? 1 : 0);

}

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

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

Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

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

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

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

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

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

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

for (int i=0; i<G[v].size(); i++) {

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

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

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

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

Related Images:

e-olimp 3837. Выражения

05/04/2015 by Вустянюк Ігор Дмитрович

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

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

push: число кладется на верх стека.
pop: число снимается с вершины стека.

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

a := pop();

b := pop();

push(b O a);

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

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.

Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?

Пояснения к решению

Если задана правильная строка в постфиксной нотации, то алгоритм её вычисления на основе стека выглядит следующим образом:

Просматриваем строку слева направо
Если встречаем переменную, помещаем её в конец стека/очереди
Если встречаем символ оператора * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b и кладём на стек b * a.

По условию задачи, мы должны обрабатывать строки, используя вместо стека очередь, поэтому описанные выше действия примут следующий вид: снимаем с очереди a, снимаем с очереди b и кладём в конец очереди b * a.

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция get_levels генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу. Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

Код на С++

Ссылка на программу в ideone.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем
 index - текущий символ в строке Expr
 depth - текущий уровень дерева разбора
 Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {
	Answer[depth] += Expr[index];
	index--;
	if (isupper(Expr[index+1])) {
		get_levels(Expr, index, depth + 1, Answer);
		get_levels(Expr, index, depth + 1, Answer);
	}
}


int main() {
	int n, index;
	cin >> n;
	string Expr;
	for (int k = 0; k < n; k++) {
		cin >> Expr;						
		vector<string> Answer(Expr.size(), "");
		index = Expr.size() - 1;
		get_levels(Expr, index, 0, Answer);
		for (int k = Expr.size() - 1; k >= 0; k--)
			cout << Answer[k];
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем

index - текущий символ в строке Expr

depth - текущий уровень дерева разбора

Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {

Answer[depth] += Expr[index];

index--;

if (isupper(Expr[index+1])) {

get_levels(Expr, index, depth + 1, Answer);

}

int main() {

int n, index;

cin >> n;

string Expr;

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

cin >> Expr;

vector<string> Answer(Expr.size(), "");

index = Expr.size() - 1;

get_levels(Expr, index, 0, Answer);

for (int k = Expr.size() - 1; k >= 0; k--)

cout << Answer[k];

cout << endl;

}

return 0;

}

Код на Java

Ссылка на программу в ideone.

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

class Index {
	int in;
	public Index(int a) {
		in = a;
	}
}

class Main
{
	public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {
		Answer[depth] += Expr[index.in];
		index.in--;
		if (Character.isUpperCase(Expr[index.in + 1])) {
			get_levels(Expr, index, depth + 1, Answer);
			get_levels(Expr, index, depth + 1, Answer);
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String str = in.nextLine();

		for (int k = 0; k < n; k++) {
			str = in.nextLine();
			char[] Expr = str.toCharArray();
			String[] Answer = new String[Expr.length];
			Arrays.fill(Answer, "");
			Index index = new Index(Expr.length - 1);
			get_levels(Expr, index, 0, Answer);
			for (int j = Expr.length - 1; j >= 0; j--)
				System.out.print(Answer[j]);
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Index {

int in;

public Index(int a) {

in = a;

}

class Main

{

public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {

Answer[depth] += Expr[index.in];

index.in--;

if (Character.isUpperCase(Expr[index.in + 1])) {

get_levels(Expr, index, depth + 1, Answer);

}

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String str = in.nextLine();

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

str = in.nextLine();

char[] Expr = str.toCharArray();

String[] Answer = new String[Expr.length];

Arrays.fill(Answer, "");

Index index = new Index(Expr.length - 1);

get_levels(Expr, index, 0, Answer);

for (int j = Expr.length - 1; j >= 0; j--)

System.out.print(Answer[j]);

System.out.println();

}

Related Images:

e-olimp 4475. Часы

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

4475. Часы

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

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

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

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

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

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

Реализация:

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

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

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

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

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

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

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

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

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

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

#include <iostream>

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

#include <deque>

#include <stack>

#include <cmath> //floor()

#include <map>

using namespace std;

//НОД

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

while(b){

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

swap(a, b);

}

return a;

}

//НОК

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

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

}

int main()

{

int S, M, H, K;

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

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

deque<int> clock;

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

clock.push_back(i);

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

stack<int> s, m, h;

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

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

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

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

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

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

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

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

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

}

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

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

m.pop();

while(!m.empty()){

clock.push_back(m.top());

m.pop();

}

while(!h.empty()){

clock.push_back(h.top());

h.pop();

}

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

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

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

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

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

permutation[i] = clock.front();

clock.pop_front();

}

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

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

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

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

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

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

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

used[x] = true;

cycle_length++;

}

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

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

permutation_order = lcm(permutation_order, cycle_length);

}

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

return 0;

}

Примечания

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

Related Images:

e-olimp 3809. ГАС Очередь

02/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №3809. Ссылка на засчитанное решение.

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

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

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен [latex]w[/latex], то через [latex]t[/latex] часов ожидания в очереди этот человек обрушит на голову чиновника ровно [latex]wt[/latex] единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно [latex]2w[/latex].

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

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

В первой строке задано одно целое число [latex]t[/latex] — количество случаев, которые вам предстоит обработать. Далее следуют [latex]t[/latex] описаний самих случаев.

Описание каждого случая состоит из: числа [latex]n[/latex] в первой строке — количества посетителей, и [latex]n[/latex] описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа [latex]r_{i}[/latex] и [latex]w_{i}[/latex] [latex]\left(1\leq r_{i},w_i\leq {10}^{6} \right)[/latex] — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит [latex]10^{5}[/latex].

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

Для каждого случая в отдельной строке выведите ответ — минимальное суммарное количество негатива, которое получит чиновник.

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

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению
priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {
	long long t;
	scanf("%lld", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		long long ans=0;
		for (int i=0; i<n; i++) {
			long long r, w;
			scanf("%lld%lld", &r, &w);
			v[i]=make_pair(r,w);
		}
		sort (v, v+n); // сортируем по времени прибытия
		long long k=0;
		long long tim=1;
		for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших
			while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени
				q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)
				k++;
				if (k==n) break; // выходим из циклов, если прошли все возможные люди
			}
			if (k==n) break;
			if (q.empty()) {
				if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE
				else tim++;
			}
			else {
				ans+=(long long)q.top().first*(tim-q.top().second);
				tim++;
				q.pop();
			}
		}
		while (!q.empty()) {
			ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному
			tim++;
			q.pop();
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению

priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {

long long t;

scanf("%lld", &t);

while (t--) {

long long n;

scanf("%lld", &n);

long long ans=0;

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

long long r, w;

scanf("%lld%lld", &r, &w);

v[i]=make_pair(r,w);

}

sort (v, v+n); // сортируем по времени прибытия

long long k=0;

long long tim=1;

for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших

while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени

q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)

k++;

if (k==n) break; // выходим из циклов, если прошли все возможные люди

}

if (k==n) break;

if (q.empty()) {

if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE

else tim++;

}

else {

ans+=(long long)q.top().first*(tim-q.top().second);

tim++;

q.pop();

}

while (!q.empty()) {

ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному

tim++;

q.pop();

}

printf("%lld\n", ans);

}

return 0;

}

Алгоритм состоит в том, чтобы на каждом моменте времени забирать к себе самого агрессивного из людей в очереди.

Для реализации наиболее подходящей структурой хранения данных является очередь с приоритетом, максимум из которой можно извлечь за [latex]O \left( \log n \right)[/latex], тогда суммарное асимптотическое время решения задачи займёт [latex]O \left( \ n log n \right)[/latex].

Related Images:

e-olimp 2510. Сортировка очередями

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

e-olimp 2510. Сортировка очередями

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

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

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

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

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

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

Реализация:

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

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

int main()
{
    unsigned n; scanf("%u", &n);    //количество команд
    int* to_sort = new int[n];      //исходный массив
    for(int i = 0; i < n; i++)
        scanf("%d", to_sort + i);

    unsigned k; scanf("%u", &k);    //количество очередей
    queue<int>* sorting_machine = new queue<int>[k];    //массив очередей

    int *order = new int[n];    //порядок размещения чисел по очередям
    for(int i = 0; i < n; i++){
        //подходящая очередь либо пуста, либо имеет последний элемент, меньший данного
        //найти её номер в массиве
        int available = find_if(sorting_machine, sorting_machine + k,
            [&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine;
        //если таких очередей нет, то сортировка невозможна
        if(available >= k){
            puts("NO");
            return 0;
        }
        //добавить элемент массива в одну из очередей
        sorting_machine[available].push(to_sort[i]);
        order[i] = available + 1;
    }

    puts("YES");
    for(int i = 0; i < n; i++){
        //вывод порядка размещения исходного массива чисел по очередям
        printf("I(%d)\n", order[i]);
    }
    for(int i = 0; i < n; i++){
        //так как и очередей, и элементов мало, найти минимальный доступный элемент
        queue<int>* minimum = min_element(sorting_machine, sorting_machine + k,
        [&](const queue<int> x, const queue<int> y){
            return !x.empty() && !y.empty() && x.front() < y.front();
        });
        minimum->pop(); //удалить его
        //и вывести номер соответствующей очереди
        printf("R(%d)\n", minimum-sorting_machine+1);
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <algorithm>

using namespace std;

int main()

{

unsigned n; scanf("%u", &n); //количество команд

int* to_sort = new int[n]; //исходный массив

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

scanf("%d", to_sort + i);

unsigned k; scanf("%u", &k); //количество очередей

queue<int>* sorting_machine = new queue<int>[k]; //массив очередей

int *order = new int[n]; //порядок размещения чисел по очередям

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

//подходящая очередь либо пуста, либо имеет последний элемент, меньший данного

//найти её номер в массиве

int available = find_if(sorting_machine, sorting_machine + k,

[&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine;

//если таких очередей нет, то сортировка невозможна

if(available >= k){

puts("NO");

return 0;

}

//добавить элемент массива в одну из очередей

sorting_machine[available].push(to_sort[i]);

order[i] = available + 1;

}

puts("YES");

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

//вывод порядка размещения исходного массива чисел по очередям

printf("I(%d)\n", order[i]);

}

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

//так как и очередей, и элементов мало, найти минимальный доступный элемент

queue<int>* minimum = min_element(sorting_machine, sorting_machine + k,

[&](const queue<int> x, const queue<int> y){

return !x.empty() && !y.empty() && x.front() < y.front();

});

minimum->pop(); //удалить его

//и вывести номер соответствующей очереди

printf("R(%d)\n", minimum-sorting_machine+1);

}

return 0;

}

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

В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.

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

Related Images:

e-olimp 1667. Конденсация графа

29/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

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

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

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

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

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

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

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

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

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

e-olimp 6130. Дек неограниченного размера (как список деков)

26/03/2015 by Вустянюк Ігор Дмитрович

Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.):

— хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения);

— хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый массив и копировать туда содержимое старого);

— хранить дек в виде многих малых массивов, добавляя новые массивы с того или другого конца при необходимости.

Здесь приведу свою реализацию третьим способом: малые деки хранятся в виде двусвязного списка и добавляются/удаляются в соответствующих ситуациях.; конструктор основного дека создаёт единственный малый дек, который заполняется от центра к краям.

Соответствующая задача на e-olimp: 6130 и зачтённое решение.

В этом блоге можно увидеть картинку, иллюстрирующую рассматриваемый метод, и краткое описание того, как можно снабдить дек индексированием, чтобы быстро получать доступ к элементу дека по его индексу (как в массиве).

О плюсах и минусах

Расширения нужно (в теории) производить чаще, чем при первом подходе, но зато не нужно полностью копировать содержимое дека при расширении.

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

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

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

const int Max = 1000;		// максимально допустимое число элементов в малом деке

struct node {
	node* prev;
	node* next;
	int* dequeue;
	
	node(node* Pr, node* Ne) {
		prev = Pr;
		next = Ne;
		dequeue = new int[Max]();
	}
	
	void print() {
		for(int k = 0; k < Max; k++)
			cout << dequeue[k] << " ";
		cout << endl;
	}
};

struct Dequeue {
	node* first;
	node* last;
	int f;		// индекс первого свободного элемента в первой деке
	int l;		// индекс последнего свободного элемента в последней деке
	int Size;

	Dequeue() {
		node* N = new node(nullptr, nullptr);
		first = N;
		last = N;
		f = Max/2 - 1;
		l = Max/2;
		Size = 0;
	}

// Управление двусвязным списком
	void add_first () {			// добавляет новый узел в начало списка
		node* N = new node(nullptr, first);
		first -> prev = N;
		first = N;
		f = Max - 1;
	}
	
	void add_last () {		// добавляет новый узел в конец списка
		node* N = new node(last, nullptr);
		last -> next = N;
		last = N;
		l = 0;
	}
	
	void delete_first () {		// удаляет первый узел списка
		node* N = first -> next;
		delete first;
		first = N;
		first -> prev = nullptr;
		f = 0;
	}
	
	void delete_last () {		// удаляет последний узел списка
		node* N = last -> prev;
		delete last;
		last = N;
		last -> next = nullptr;
		l = Max - 1;
	}

// Управление деком
	void push_front (int n) {
		(first -> dequeue)[f] = n;
		f--;
		Size++;
		if (f == -1)		// если первый дек переполнен
			add_first();	// добавляем в начало списка новый дек
	}
	
	void push_back (int n) {
		(last -> dequeue)[l] = n;
		l++;
		Size++;
		if (l == Max)		// если последний дек переполнен
			add_last();		// добавляем в конец списка новый дек
	}
	
	int pop_front () {
		Size--;
		if (f == Max - 1)
			delete_first();
		else
			f++;
		return (first -> dequeue)[f];
	}
	
	int pop_back () {
		Size--;
		if (l == 0)
			delete_last();
		else
			l--;
		return (last -> dequeue)[l];
	}
	
	int front () {
		if (f == Max - 1)
			return ((first -> next) -> dequeue)[0];
		else
			return (first -> dequeue)[f+1];
	}
	
	int back () {
		if (l == 0)
			return ((last -> prev) -> dequeue)[Max - 1];
		else
			return (last -> dequeue)[l-1];
	}
	
	int size() {
		return Size;
	}
	
	bool empty() {return (Size == 0);}
	
	void clear() {
		node* N = first;
		while (N) {
			node* M = N -> next;
			delete N->prev;
			delete N;
			N = M;
		}
		
		N = new node(nullptr, nullptr);
		
		first = N;
		last = N;
		Size = 0;
		f = Max/2 - 1;
		l = Max/2;
	}
	
	void print() {
		node* N = first;
		while (N) {
			N -> print();
			N = N->next;
		}
	}
};


int main() {
	Dequeue D;
	string comand;
	int x;
	while(cin >> comand) {
		if (comand == "push_front") {
			cin >> x;
			D.push_front(x);
			cout << "ok\n";
		}
		if (comand == "push_back") {
			cin >> x;
			D.push_back(x);
			cout << "ok\n";
		}
		
		if (comand == "pop_front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_front() << "\n";
		}
		if (comand == "pop_back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_back() << "\n";
		}

		if (comand == "front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.front() << "\n";
		}
		if (comand == "back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.back() << "\n";
		}
		
		if (comand == "size") {
			cout << D.size() << "\n";
		}
		if (comand == "clear") {
			D.clear();
			cout << "ok\n";
		}
		if (comand == "exit") {
			cout << "bye\n";
			return 0;
		}
		if (comand == "print") {
			D.print();
		}
	}
	return 0;
}

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

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

#include <iostream>

#include <string>

using namespace std;

const int Max = 1000; // максимально допустимое число элементов в малом деке

struct node {

node* prev;

node* next;

int* dequeue;

node(node* Pr, node* Ne) {

prev = Pr;

next = Ne;

dequeue = new int[Max]();

}

void print() {

for(int k = 0; k < Max; k++)

cout << dequeue[k] << " ";

cout << endl;

}

};

struct Dequeue {

node* first;

node* last;

int f; // индекс первого свободного элемента в первой деке

int l; // индекс последнего свободного элемента в последней деке

int Size;

Dequeue() {

node* N = new node(nullptr, nullptr);

first = N;

last = N;

f = Max/2 - 1;

l = Max/2;

Size = 0;

}

// Управление двусвязным списком

void add_first () { // добавляет новый узел в начало списка

node* N = new node(nullptr, first);

first -> prev = N;

first = N;

f = Max - 1;

}

void add_last () { // добавляет новый узел в конец списка

node* N = new node(last, nullptr);

last -> next = N;

last = N;

l = 0;

}

void delete_first () { // удаляет первый узел списка

node* N = first -> next;

delete first;

first = N;

first -> prev = nullptr;

f = 0;

}

void delete_last () { // удаляет последний узел списка

node* N = last -> prev;

delete last;

last = N;

last -> next = nullptr;

l = Max - 1;

}

// Управление деком

void push_front (int n) {

(first -> dequeue)[f] = n;

f--;

Size++;

if (f == -1) // если первый дек переполнен

add_first(); // добавляем в начало списка новый дек

}

void push_back (int n) {

(last -> dequeue)[l] = n;

l++;

Size++;

if (l == Max) // если последний дек переполнен

add_last(); // добавляем в конец списка новый дек

}

int pop_front () {

Size--;

if (f == Max - 1)

delete_first();

else

f++;

return (first -> dequeue)[f];

}

int pop_back () {

Size--;

if (l == 0)

delete_last();

else

l--;

return (last -> dequeue)[l];

}

int front () {

if (f == Max - 1)

return ((first -> next) -> dequeue)[0];

else

return (first -> dequeue)[f+1];

}

int back () {

if (l == 0)

return ((last -> prev) -> dequeue)[Max - 1];

else

return (last -> dequeue)[l-1];

}

int size() {

return Size;

}

bool empty() {return (Size == 0);}

void clear() {

node* N = first;

while (N) {

node* M = N -> next;

delete N->prev;

delete N;

N = M;

}

N = new node(nullptr, nullptr);

first = N;

last = N;

Size = 0;

f = Max/2 - 1;

l = Max/2;

}

void print() {

node* N = first;

while (N) {

N -> print();

N = N->next;

}

};

int main() {

Dequeue D;

string comand;

int x;

while(cin >> comand) {

if (comand == "push_front") {

cin >> x;

D.push_front(x);

cout << "ok\n";

}

if (comand == "push_back") {

cin >> x;

D.push_back(x);

cout << "ok\n";

}

if (comand == "pop_front") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_front() << "\n";

}

if (comand == "pop_back") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_back() << "\n";

}

if (comand == "front") {

if (D.empty())

cout << "error\n";

else

cout << D.front() << "\n";

}

if (comand == "back") {

if (D.empty())

cout << "error\n";

else

cout << D.back() << "\n";

}

if (comand == "size") {

cout << D.size() << "\n";

}

if (comand == "clear") {

D.clear();

cout << "ok\n";

}

if (comand == "exit") {

cout << "bye\n";

return 0;

}

if (comand == "print") {

D.print();

}

return 0;

}

Related Images:

Какой треугольник?

01/12/2014 by Зелінський Вячеслав Олександрович

Задача: 905. Какой треугольник? с сайта http://www.e-olimp.com.ua Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон. Существование треугольника и корректность исходных данных гарантируется. Технические условия Входные данные В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100. Выходные данные В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Первая сторона	Вторая сторона	Третья сторона	Результат
2	2	2	1
3	4	3	2
4	7	14	3

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

#include <iostream>

using namespace std;

int main()
{
  int n = 3;
  int a[n];
  for( int i=0 ; i<n ; i++ )
  {
      cin >> a[i];
  }
  if( a[0] == a[1] && a[1] == a[2] )
  {
      cout << 1 << endl;
  }
  else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])
  {
      cout << 2 << endl;
  }
  else
  {
      cout << 3 << endl;
  }
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n = 3;

int a[n];

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

{

cin >> a[i];

}

if( a[0] == a[1] && a[1] == a[2] )

{

cout << 1 << endl;

}

else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])

{

cout << 2 << endl;

}

else

{

cout << 3 << endl;

}

return 0;

}

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо проверить каким является треугольник: равносторонним, равнобедренным или разносторонним. Для этого создаем массив из трех элементов(сторон треугольника), считываем его. Далее, если все элементы массива равны, то треугольник равносторонний, иначе, если две стороны равны, то он равнобедренный, если ни то, ни то не выполняется, то он разносторонний. Для проверки работы программы можно воспользоваться объектом. Ссылка на e-olimp: http://www.e-olymp.com/ru/submissions/2319469 Второй вариант:

#include <iostream>

using namespace std;

int main()
{
   int n = 3;
   int a[n];
   int j = 3;
   for( int i=0 ; i<n ; i++ )
   {
      cin >> a[i];
   }
   if( a[0] == a[1] && a[1] == a[2] )
   {
      cout << 1 << endl;
      return 0;
   }
   int b=0;
   for( int i=0 ; i<n ; i++ )
   {
      if( i+1 != n )
      {
         if( a[i] == a[i+1] )
         {
            b=1;
         }
      }
      else
      {
         if( a[0] == a[2] )
         {
            b=1;
         }
      }
   }
   if( b!=0)
   {
      cout << 2 << endl;
   }
   else
   {
      cout << 3 << endl;
   }
}

#include <iostream>

using namespace std;

int main()

{

int n = 3;

int a[n];

int j = 3;

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

{

cin >> a[i];

}

if( a[0] == a[1] && a[1] == a[2] )

{

cout << 1 << endl;

return 0;

}

int b=0;

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

{

if( i+1 != n )

{

if( a[i] == a[i+1] )

{

b=1;

}

else

{

if( a[0] == a[2] )

{

b=1;

}

if( b!=0)

{

cout << 2 << endl;

}

else

{

cout << 3 << endl;

}

http://www.e-olymp.com/ru/submissions/2319474

Код на Java:

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


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
           Scanner in = new Scanner(System.in);
           int a, b, c;
           a = in.nextInt(); 
           b = in.nextInt(); 
           c = in.nextInt(); 
           System.out.println(a==b && b==c? 1: a==b || b==c || a==c? 2: 3);	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int a, b, c;

a = in.nextInt();

b = in.nextInt();

c = in.nextInt();

System.out.println(a==b && b==c? 1: a==b || b==c || a==c? 2: 3);

}

Второй вариант:

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	   int n = 3;
	   Scanner in = new Scanner(System.in);
	   int []a = new int [n];
	   int j = 3;
	   for( int i=0 ; i<n ; i++ )
	   {
	      a[i] = in.nextInt(); 
	   }
	   if( a[0] == a[1] && a[1] == a[2] )
	   {
	      System.out.println(1);
	      return;
	   }
	   int b=0;
	   for( int i=0 ; i<n ; i++ )
	   {
	      if( i+1 != n )
	      {
	         if( a[i] == a[i+1] )
	         {
	            b=1;
	         }
	      }
	      else
	      {
	         if( a[0] == a[2] )
	         {
	            b=1;
	         }
	      }
	   }
	   if( b!=0)
	   {
	      System.out.println(2);
	   }
	   else
	   {
	      System.out.println(3);
	   }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n = 3;

Scanner in = new Scanner(System.in);

int []a = new int [n];

int j = 3;

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

{

a[i] = in.nextInt();

}

if( a[0] == a[1] && a[1] == a[2] )

{

System.out.println(1);

return;

}

int b=0;

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

{

if( i+1 != n )

{

if( a[i] == a[i+1] )

{

b=1;

}

else

{

if( a[0] == a[2] )

{

b=1;

}

if( b!=0)

{

System.out.println(2);

}

else

{

System.out.println(3);

}

Related Images:

e-olymp 6277. Покупка воды

18/11/2014 by Зелінський Вячеслав Олександрович

Задача №6277 с сайта e-olimp.com.

Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет 1 грн 20коп., а стоимость пустой бутылки 20 коп.
Сколько бутылок воды можно выпить на [latex]n[/latex] грн, учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды.

Входные данные
Натуральное число [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 1000).

Выходные данные
Количество бутылок воды, которое можно выпить на [latex]n[/latex] грн.

[latex]n[/latex]	Результат
2	1
10	9
0.7	0

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

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n; //Чтение из стандартного потока.
  int j=0;
  while( n>(1.2) )
  {
     n--;
     j++;
  }
  cout << j << endl;
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n; //Чтение из стандартного потока.

int j=0;

while( n>(1.2) )

{

n--;

j++;

}

cout << j << endl;

return 0;

}

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо узнать сколько можно выпить бутылок имея [latex]n[/latex] грн. Для этого описываем и считываем количество денег [latex]n[/latex], а также создаем счетчик, определяющий сколько бутылок воды в итоге можно купить. Затем создаем цикл, в котором пока мы имеем достаточно средств покупаем воду за 1.2 грн и сразу же сдаем бутылку за 0.2 грн, в результате количество денег уменьшается на 1, а счетчик увеличивается на 1. Когда количество денег станет меньше 1.2 грн выходим из цикла и печатаем количество купленных бутылок.
Для проверки работы программы можно воспользоваться объектом.

Имеется альтернативный линейный вариант решения:

#include <iostream>
using namespace std;
 
int main()
{
  long long n;
  cin >> n;
  n=n-0.2;
  cout << n << endl;
}

#include <iostream>

using namespace std;

int main()

{

long long n;

cin >> n;

n=n-0.2;

cout << n << endl;

}

http://ideone.com/ClAaK4
Решение принято

Код на Javа:

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


class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
           Scanner in = new Scanner(System.in);
           int n;
           n = in.nextInt();
           System.out.println(n-1); 
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

System.out.println(n-1);

}

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


class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt(); 
        int j=0;
        while( n>(1.2) )
        {
            n--;
            j++;
        }
        System.out.println(j);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

int j=0;

while( n>(1.2) )

{

n--;

j++;

}

System.out.println(j);

}

Related Images:

e-olimp 2392. Интересная сумма

27/10/2014 by Ілларіонова Марія Валеріївна

Ссылка на задачу.

Дано трёхзначное натуральное число [latex]N[/latex]. Определить сумму наибольшего и наименьшего трёхзначных чисел, которые могут быть образованы из числа [latex]N[/latex] перестановкой цифр.

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

Натуральное число [latex]N[/latex] [latex]\left(100\leq N\leq 999 \right)[/latex].

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

Ответ к задаче.

Пройденные тесты (C++).

Java.

Код программы (C++):

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

int main() {
	int N, b[3], c[3];
	cin >> N;
	for (int i=0; i<3; i++) {
		b[i]=N%10; c[i]=N%10;
		N=N/10;
	}
	sort(b,b+3);
	sort(c,c+3); reverse (c,c+3);
	if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);
	else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);
	int b1=100*b[0]+10*b[1]+b[2];
	int c1=100*c[0]+10*c[1]+c[2];
	cout << b1+c1 << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int N, b[3], c[3];

cin >> N;

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

b[i]=N%10; c[i]=N%10;

N=N/10;

}

sort(b,b+3);

sort(c,c+3); reverse (c,c+3);

if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);

else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

cout << b1+c1 << endl;

return 0;

}

Java:

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

class Main
{
	public static void swap (int []a, int i, int j) {
		int tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}
	public static void main (String[] args)
	{
		int N;
		int []b = new int [3];
		int []c = new int [3];
		Scanner in = new Scanner (System.in);
		N=in.nextInt();
		for (int i=0; i<3; i++) {
			b[i]=N%10; 
			c[i]=N%10;
			N/=10;
		}
		Arrays.sort(b);
		Arrays.sort(c);
		swap (c,0,2);
		if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);
		else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);
		int b1=100*b[0]+10*b[1]+b[2];
		int c1=100*c[0]+10*c[1]+c[2];
		System.out.println (b1+c1);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap (int []a, int i, int j) {

int tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

public static void main (String[] args)

{

int N;

int []b = new int [3];

int []c = new int [3];

Scanner in = new Scanner (System.in);

N=in.nextInt();

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

b[i]=N%10;

c[i]=N%10;

N/=10;

}

Arrays.sort(b);

Arrays.sort(c);

swap (c,0,2);

if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);

else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

System.out.println (b1+c1);

}

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

Затем я сортирую первый массив по возрастанию, а второй по убыванию.

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

После чего я перевожу элементы массива в одно трёхзначное число и наконец-то получаю сумму.

Сложность задачи 66%.

Related Images:

Ю3.33

25/10/2014 by Швандт Максим Альбертович

Задача: В задаче задана функция и её разложение в ряд или произведение. Численно убедится в справедливости равенства, для чего для заданного значения аргумента [latex] x [/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]\varepsilon\[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex] n [/latex] (слагаемых или сомножателей), необходимых для достижения заданной точности.
[latex]\sin \left(x \right) = x \left(1 — \frac{x^{2}}{\pi^{2}} \right) \left( 1 — \frac{x^{2}}{4\pi^{2}} \right) \ldots \left(1 — \frac{x^{2}}{ \left( n-1 \right)^{2}\pi^{2}} \right)[/latex]

Тесты:

x	n-Excel	sin — Excel	deviation — Excel	e — input	exact sinus	n — program	deviation — program
12	22	-1,029367	0.56	0.56	-0.536573	22	0.524789
5	7	-1,346966	0.54	0.54	-0.958924	7	0.461469
2.5	2	0,771704	-1.15	-1.15	0.598472	2	-0.318384
1	2	0,875915	-1.38	-1.38	0.841471	2	-0.057208
0	2	0	-0.53	-0.53	0	2	0
-1	2	-0,875915	0.3	0.3	-0.841471	2	0.057208
-2.5	6	-0,659746	0.08	0.08	-0.598472	6	0.073087
-5	4	1,700161	-1.62	-1.62	0.958924	4	-1.061024
-12	12	1,755690	-1.63	-1.63	0.536573	12	-1.417062

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

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

double pow2( double x ) //вторая степень
{
   return x*x;
}

int main()
{
   // рабочие переменные
   double x, e, d, r;
   unsigned int n, nMax = 0xffffffff; // лимит числа итераций чтобы избежать бесконечного цикла
  
   // ввод данных - аргумента функции и заданной погрешности
   scanf("%lf", &x);  
   scanf("%lf", &e);

   for( r = x, n = 2; n < nMax; n++ ) // основной цикл вычислений
   {
      r = r * ( 1 - pow2( x ) / ( pow2( n - 1 ) * pow2( M_PI ) ) );
      d = sin( x ) - r ;  
      if( fabs( d ) <= fabs( e ) ) break;
   }      
   
   // вывод результата
   printf("sin(x) = %lf\n", sin( x ) );
   printf("calculated sinus = %lf\n", r );
   printf("inaccuracy = %lf\n", d );
   printf("number of iterations: %d\n", n );
   
   return 0;
}

#include <stdio.h>

#include <math.h>

double pow2( double x ) //вторая степень

{

return x*x;

}

int main()

{

// рабочие переменные

double x, e, d, r;

unsigned int n, nMax = 0xffffffff; // лимит числа итераций чтобы избежать бесконечного цикла

// ввод данных - аргумента функции и заданной погрешности

scanf("%lf", &x);

scanf("%lf", &e);

for( r = x, n = 2; n < nMax; n++ ) // основной цикл вычислений

{

r = r * ( 1 - pow2( x ) / ( pow2( n - 1 ) * pow2( M_PI ) ) );

d = sin( x ) - r ;

if( fabs( d ) <= fabs( e ) ) break;

}

// вывод результата

printf("sin(x) = %lf\n", sin( x ) );

printf("calculated sinus = %lf\n", r );

printf("inaccuracy = %lf\n", d );

printf("number of iterations: %d\n", n );

return 0;

}

Код программы на языке Java:

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

class SinusApp
{
   public static Double scanDouble( Scanner in )
   {
       return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );
   }
   
   public static double pow2( double x ) //вторая степень
   {
      return x*x;
   }
   
   public static void main( String[] args )
   {
      // рабочие переменные
      double x, e, d, r;
      long n, nMax = Long.MAX_VALUE; // лимит числа итераций чтобы избежать бесконечного цикла
     
     
      // ввод данных - аргумента функции и заданной погрешности
      Scanner in = new Scanner(System.in);
      
      x = scanDouble( in );
      e = scanDouble( in );
   
      in.close(); 
   
      for( d = 0, r = x, n = 2; n < nMax; n++ ) // основной цикл вычислений
      {
         r = r * ( 1 - pow2( x ) / ( pow2( n - 1 ) * pow2( Math.PI ) ) );
         d = Math.sin( x ) - r ;  
         if( Math.abs( d ) <= Math.abs( e ) ) break;
      }      
      
      // вывод результата
      System.out.printf("sin(x) = %f\n", Math.sin( x ) );
      System.out.printf("calculated sinus = %f\n", r );
      System.out.printf("inaccuracy = %f\n", d );
      System.out.printf("number of iterations: %d\n", n );

   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class SinusApp

{

public static Double scanDouble( Scanner in )

{

return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );

}

public static double pow2( double x ) //вторая степень

{

return x*x;

}

public static void main( String[] args )

{

// рабочие переменные

double x, e, d, r;

long n, nMax = Long.MAX_VALUE; // лимит числа итераций чтобы избежать бесконечного цикла

// ввод данных - аргумента функции и заданной погрешности

Scanner in = new Scanner(System.in);

x = scanDouble( in );

e = scanDouble( in );

in.close();

for( d = 0, r = x, n = 2; n < nMax; n++ ) // основной цикл вычислений

{

r = r * ( 1 - pow2( x ) / ( pow2( n - 1 ) * pow2( Math.PI ) ) );

d = Math.sin( x ) - r ;

if( Math.abs( d ) <= Math.abs( e ) ) break;

}

// вывод результата

System.out.printf("sin(x) = %f\n", Math.sin( x ) );

System.out.printf("calculated sinus = %f\n", r );

System.out.printf("inaccuracy = %f\n", d );

System.out.printf("number of iterations: %d\n", n );

}

Ссылка:http://ideone.com/nZluY8

Программа состоит из следующих частей:

Определение вспомогательной функции
Рабочие переменные
Определяем лимит числа итераций чтобы избежать бесконечного цикла
Ввод данных — аргумента функции и заданной погрешности
Условие выполнения
Вывод результата

Правильность результата проверялась на калькуляторе. тестирование показало, что правильные значения получаются только при очень большом n . Только начиная с десятков тысяч результат близок к показанию калькулятора.

Данные для проверки подготавливались в Excel ввиду относительно большого количества итераций, необходимых для расчётов. Полученная погрешность с точным значением синуса использовались как входное [latex]e[/latex]. Результирующее количество итераций программы сравнивалось с числом итераций, сделанных в Excel. Ввиду того, что double намного точнее чем значения в Excel, возможны различия в числе итераций ( назначенных ).

Ссылка на ideone.com: http://ideone.com/fork/Wh91nH

Related Images:

e-olymp 3. Спичечная модель

22/10/2014 by Осецимський Анатолій Вадимович

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Задача.

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.

Для построения модели трех кубиков он использовал [latex]28[/latex] спичек.

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?

Все числа в задаче не превышают [latex]2*10^9[/latex].

Технические условия

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

Одно число [latex] N [/latex] – количество кубиков.

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

Одно число – количество спичек.

Ссылка на саму задачу.

Пройденные тесты программы.

Input	Output	Comments
0	0	Смотрим,что выдает при 0 кубов
3	28	Проверяем пример данный в задаче
[latex]2*10^9[/latex]	6.00953Е9	Не вылезает ли за рамки переменных

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

Для лучшего понимания сколько нам понадобится спичек, рекомендую представить на бумаге как будут выглядеть «этажи» нашего куба.

Первый этаж будет выглядеть так. (Для примера берем куб [latex]444[/latex], т.к. он самый наглядный и не громоздкий)

8	5	5	5
8	5	5	5
8	5	5	5
12	8	8	8

Для построения самого первого куба нам понадобится 12 спичек, для достройки к нему второго и третьего понадобится по 8, для достройки четвертого куба уже понадобится 5 и так далее.

Второй этаж будет выглядеть так. (аналогично для последующих)

5	3	3	3
5	3	3	3
5	3	3	3
8	5	5	5

Поскольку у нас уже есть основание, то последующие этажи требуют меньшего количества спичек. Зная это, выведем формулу, по которой можно вычеслить необходимое количество спичек для построения куба [latex]n[/latex]-ой размерности.

Получаем [latex]8i+4+5i(i-1)2+3(i-1)2+3i(i-1)^2+2(i-1)^2[/latex] (Где i — это «размерность» куба. К примеру: подставив i=4, мы найдем необходимое количество спичек для построение куба [latex]44*4[/latex]).

Теперь возник вопрос, как в задаче определить размерность куба? Очень просто. Максимальное количество возможных кубов равно [latex]i^3[/latex], следовательно зная количество кубов (Дано в начале задачи) можно определить [latex]i[/latex]. Описываем цикл, увеличивающий [latex]i[/latex] пока [latex]i^3<n[/latex].

Задаем функцию с тремя параметрами. ([latex]u[/latex] — определяет, в какую степень возводить)

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}

int bit(int i,int n,int u)

{

i=i+1;

}while(pow(i,u)<n);

return i;

}

Имея размерность, можно узнать, сколько нам надо спичек для построения куба прошлой размерности по формуле. Следовательно мы знаем, сколько кубов принадлежит размерности [latex]i[/latex] ([latex]p=n-i^3[/latex]). Разобьем на этапы построение куба размерности [latex]i[/latex] из куба размерности [latex]i-1[/latex]. Пример:

Имея куб [latex]333[/latex] мы начнем достраивать к нему боковую стенку, потом заднюю, и в самом конце так называемую «крышу».

При построении боковой стены мы получаем куб равный [latex] 433[/latex](увеличилась его длинна).

Вид сверху:

[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]

При построении задней стены он расшириться в ширине [latex]443[/latex].

[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]

На третьем этапе увеличиться высота куба. Следовательно куб будет иметь такую форму [latex]444[/latex].

Определяем этап. Если мы находимся на третьем этапе, то разность между количеством кубов([latex]n[/latex]) и количеством кубов нашей размерности без крыши([latex]i^2(i-1)[/latex] должно быть больше нуля — [latex]n-i^2(i-1)>0[/latex]. Если больше нуля, то переходим к третьем этапу, иначе смотрим, не на первом ли мы этапе случайно? Для этого количество кубов([latex]n[/latex]) должно быть меньше или равно количеству кубов на первом этапе нашей размерности([latex]i(i-1)(i-1)[/latex]) — [latex]i(i-1)(i-1)>=n[/latex]. Если это выполняется, то переходим к первому этапу, иначе ко второму этапу.

Этап определён. Осталось придумать самый экономный способом построения оставшихся кубов. (В этом и заключается подвох задачи) Самый экономный способ, это если мы будем строить боковую стенку (заднюю или «крышу») в такой последовательности:

16	15	14	13
9	8	7	12
4	3	6	11
1	2	5	10

В количестве затраченных спичек выглядит вот так:

3	3	3	5
3	3	5	3
3	5	3	3
8	5	5	5

По диагонали и по основанию мы тратим по 5 спичек, остальные кубы требуют по 3 (для построения первого куба необходимо 8 спичек). Можно заметить, что номера кубов, для построения которых надо 5 спичек, имеют зависимость, которую можно использовать. По размерности боковой плоскости можно определить количество спичек необходимых для построения плоскости прошлой размерности по формуле [latex]8+(g-2)25+3((g-1)(g-1)-1-(g-2)2)[/latex]. Формула при размерности 1 выдаст неправильный ответ, по этому ставим условие, если [latex]g=1[/latex], то результат увеличиваем на 8, иначе на всю эту формулу. После этого у нас осталость некое количество кубов. Запускаем цикл от номера последнего элемента нашей прошлой разрмерности latex(g-1)+i<=p[/latex].

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
{
    if ((i == 1 || i == g) && g != 1)
    {
        result+=5;
    }
    else if (g != 1)
    {
        result+=3;
    }
}

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g != 1)

{

result+=3;

}

Разобравшись во всех нюансах задачи, приступаем к напсианию кода.

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

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}


int main() {
double n,result,p;//переменные для результата и количество кубиков,на всякий случай большой размерности
long long int i=0,g=0;//объявляем переенные для разрядностей
cin>>n;
i=bit(i,n,3);//находим разрядность куба
if ((i*i*(i-1))>=n)//проверка третьего этапа
    {
        if (((i-1)*(i-1)*i)>=n)//проверка первого этапа и если правда,то решение первого этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1);//результату присваем прошылй куб
            p=n-o*o*o;//количество оставшихся кубов
            g=bit(g,p,2);//разрядность плоскости
            if (g==1)//проверка разрядности на 1
                result+=8;//увеличение результата на 8 при разрядности 1
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);//увеличение результата по формуле
            for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g != 1)
                {
                    result+=3;
                }
            }
             
        }
        else//решение второго этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1)+o*o*3+5+2*2*(o-1);//результат по формуле+ещё достроеная на первом этапе стенка
            p=n-o*o*(o+1);
            g=bit(g,p,2);
            if (g==1)
                result+=8;
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
            for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g!=1)
                {
                    result+=3;
                }
            }
        }
    }
    else//решение третьего этапа
    {
        double o=i;
        result=8*(o-1)+4+5*(o-1)*(o-1)*2+3*(o-1)*2+3*(o-1)*(o-1)*(o-1)+2*(o-1)*(o-1);//результат по формуле разрядности,только на высоту раную i-1
        p=n-(o-1)*o*o;
            g=bit(g,p,2);
        if (g==1)
            result+=8;
        else
            result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
        for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
        {
            if ((i == 1 || i == g) && g != 1)
            {
                result+=5;
            }
                else if (g!=1)
            {
                result+=3;
            }
        }
    }
 cout <<result<< endl;
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <math.h>

using namespace std;

int bit(int i,int n,int u)

{

i=i+1;

}while(pow(i,u)<n);

return i;

}

int main() {

double n,result,p;//переменные для результата и количество кубиков,на всякий случай большой размерности

long long int i=0,g=0;//объявляем переенные для разрядностей

cin>>n;

i=bit(i,n,3);//находим разрядность куба

if ((i*i*(i-1))>=n)//проверка третьего этапа

{

if (((i-1)*(i-1)*i)>=n)//проверка первого этапа и если правда,то решение первого этапа

{

double o=i-1;

result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1);//результату присваем прошылй куб

p=n-o*o*o;//количество оставшихся кубов

g=bit(g,p,2);//разрядность плоскости

if (g==1)//проверка разрядности на 1

result+=8;//увеличение результата на 8 при разрядности 1

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);//увеличение результата по формуле

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g != 1)

{

result+=3;

}

else//решение второго этапа

{

double o=i-1;

result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1)+o*o*3+5+2*2*(o-1);//результат по формуле+ещё достроеная на первом этапе стенка

p=n-o*o*(o+1);

g=bit(g,p,2);

if (g==1)

result+=8;

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);

for (long int i=1;((g-1)*(g-1)+i)<=p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g!=1)

{

result+=3;

}

else//решение третьего этапа

{

double o=i;

result=8*(o-1)+4+5*(o-1)*(o-1)*2+3*(o-1)*2+3*(o-1)*(o-1)*(o-1)+2*(o-1)*(o-1);//результат по формуле разрядности,только на высоту раную i-1

p=n-(o-1)*o*o;

g=bit(g,p,2);

if (g==1)

result+=8;

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);

for (long int i=1;((g-1)*(g-1)+i)<=p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g!=1)

{

result+=3;

}

cout <<result<< endl;

return 0;

}

Ссылка на программу

Related Images:

WoW 3. Идем к ним?

19/10/2014 by Куленюк Денис Віталійович

Задача:
https://cpp.mazurok.com/word-of-the-week/идём-к-ним/

Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины зерен, а так же для той задаче в которой максимальное съеденное число зерен задавалось пользователем. Я реализовал это достаточно просто: если m равна нулю во-второй задаче, то задача просто не имеет решения(как и смысла вообщем-то), именно поэтому я решил использовать нулевое m как показатель того что заданы параметры или для первой задачи.

if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

1	if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

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

Число зерен	Сколько нужно отнять зерен	Комментарий	Число зерен	Сколько нужно отнять зерен	Комментарий
1	0	П	9	2	В
2	1	В	10	3	В
3	0	П	11	4	В
4	1	В	12	5	В
5	2	В	13	6	В
6	3	В	14	7	В
7	0	П	15	0	П
8	1	В	…

В — Выигрышный вариант существует
П — Нет выигрышного варианта

Исходя из выше описанной таблицы вполне ясно виден алгоритм, так как выигрышный вариант отсутствовал только в случаях, где число зерен соответсвовало данной формуле: [latex]{ 2 }^{ n }-1[/latex]. тогда все что от нас требуется это найти найти такое число по этой формуле при котором количество зерен будет равно или меньше данного числа.

for( int i=1 ; r<n ; i++ ){
									r++;
									r=r<<1;
									r--;    // 2^i-1
						 		  }

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

r++;

r=r<<1;

r--; // 2^i-1

}

Если изначальное число зерен будет меньше полученного числа, то выигрышный вариант существует и все что от нас требуется, так это найти предыдущее число ( иными словами нужно найти [latex]{ 2 }^{ n-1 }-1[/latex]) и узнать сколько же зерен нужно отнять чтобы сделать выигрышный ход:

if ( r!=n ) // если существет  выигрышный ход
		{
			r++;
			r=r>>1; // ... то мы находим 2^(i-1)-1
			r--;
		}
		n-=r; // находим количество зерен которые нужно отнять

if ( r!=n ) // если существет выигрышный ход

{

r++;

r=r>>1; // ... то мы находим 2^(i-1)-1

r--;

}

n-=r; // находим количество зерен которые нужно отнять

Это все что касается первой задачи, но как оказалось вторая задача была совершенно аналогична:
Решение задачи я опять начал с расписывания нескольких вариантов, на этот раз если максимум съеденных зерен равен двум и соответственно трем:

2			3
Число зерен	Сколько нужно отнять зерен	Комментарий	Число зерен	Сколько нужно отнять зерен	Комментарий
1	0	П	1	0	П
2	1	В	2	1	В
3	2	В	3	2	В
4	0	П	4	3	В
5	1	В	5	0	П
6	2	В	6	1	В
7	0	П	7	2	В
…			…

Как вы могли уже заметить здесь тоже можно заметить очевидную тенденцию, в которой выигрышного варианта нет в тех случаях, когда число зерне соответствует этой формуле [latex]1+i(m+1)[/latex], а это значит что нам нужно всего лишь видоизменить алгоритм решения первой задачи просто подставив эту формулу вместо предыдущей.

#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main()
{
	int n, m, r=1;
	cin >> n >> m;
	if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n
	{
		--r;    
		for( int i=1 ; r<n ; i++ ){
									r++;
									r=r<<1;
									r--;    // 2^i-1
						 		  }
		if ( r!=n ) // если существует  выигрышный ход
		{
			r++;
			r=r>>1; // ... то мы находим 2^(i-1)-1
			r--;
		}
		n-=r; // находим количество зерен которые нужно отнять
		if(!n)n=-1;
	}
 
	else	// если введено m
	{
			while( r<n ){
							r += m+1; //1+i*(m+1)
 
					 	}
			if( r!=n )r -= m+1; // если существует  выигрышный ход, то возвращаемся к 1+(i-1)*(m+1)
			n -= r;				// находим количество зерен которые нужно отнять
			if(!n)n=-1;
	}
	cout << n << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main()

{

int n, m, r=1;

cin >> n >> m;

if( m == 0 ) //если m равна нулю, то игроки могут съесть не более половины заданного n

{

--r;

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

r++;

r=r<<1;

r--; // 2^i-1

}

if ( r!=n ) // если существует выигрышный ход

{

r++;

r=r>>1; // ... то мы находим 2^(i-1)-1

r--;

}

n-=r; // находим количество зерен которые нужно отнять

if(!n)n=-1;

}

else // если введено m

{

while( r<n ){

r += m+1; //1+i*(m+1)

}

if( r!=n )r -= m+1; // если существует выигрышный ход, то возвращаемся к 1+(i-1)*(m+1)

n -= r; // находим количество зерен которые нужно отнять

if(!n)n=-1;

}

cout << n << endl;

}

Related Images:

WoW 2. В следующее измерение!

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

Задача
Две землеройки постоянно находятся на спине питона в точках [latex]A[/latex] и [latex]C[/latex]. Однако, по неизвестной причине в момент времени [latex]t_A[/latex] первая землеройка отправляется в пункт [latex]B[/latex] с расчётным временем прибытия [latex]t_B[/latex]. Поскольку такое поведения является характерным для землероек вообще, вторая поступила также и в момент времени [latex]t_C[/latex] отправилась в пункт [latex]D[/latex] с расчётным временем прибытия [latex]t_D[/latex]. На новом месте землеройки в дальнейшем планирует находиться постоянно. Известно, что землеройки обычно движутся по питонам с постоянной скоростью стараясь держаться центра спины, чтобы не соскальзывать. Питоны же во время движения землероек спокойно лежат без самопересечений.
Дано:
Точки [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex] задаются расстоянием от кончика хвоста питона, измеренным вдоль обычного маршрута землероек. Время старта и прибытия землероек также задано. Входные данные задаются целыми числами не превосходящими по модулю 10000 в следующем формате:

A	t_A
B	t_B
C	t_C
D	t_D

Найти:
Необходимо определить, удастся ли землеройкам проделать этот маневр или в результате столкновения они свалятся с питона. Если питону удастся избавиться от докучливых землероек выведите “Yes”, в противном питону случае – “No”.
Continue reading →

Related Images:

WoW 3: Идем к ним?

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

Задача Идем к ним?
«У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен. На каждом шаге можно съедать не более [latex]m[/latex]-й части оставшихся зёрен. Составьте программу, которая определяет величину первого выигрышного хода по заданным числам n и m. Если выигрышного хода нет, то нужно вывести [latex]-1[/latex].»

Анализ задачи:

Первыми в голову приходят методы решения, основанные на полном переборе или на поиске производящей функции (к примеру, для [latex]m = 2[/latex] все позиции [latex]n = 2^{k}-1[/latex] — проигрышные), но количество стратегий растет достаточно быстро, а выделение закономерностей в рекурсивных последовательностях — задача нетривиальная. Следовательно, имеет смысл продолжить анализ, но уже с применением теории игр.
Предложенная игра представляет собой версию игры ним. Отличие в том, что множество объектов одно, а количество допустимых на данном шаге ходов зависит от ситуации на игровом поле.
Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.
Выигрышные позиции отличаются только расстоянием до проигрышной для противника (в зернах), следовательно, можно воспользоваться выигрышно-проигрышным разбиением позиций и ввести соответстенные характеристики позиций: [latex]\left\{ 1, -1 \right\}[/latex].
Если все позиции, в которые можно попасть из данной, являются выигрышными для противника (при условии, что он не играет в поддавки), считать её проигрышной.

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

Построение базы анализа: позиция [latex]n = m[/latex] — выигрышная (единственным доступным ходом мы заканчиваем игру), следовательно, [latex]n = m + 1[/latex] — проигрышная.
Если на расстоянии [latex]\left\lfloor \frac {step}{m} \right\rfloor [/latex] от текущей позиции [latex]step[/latex] все значения равны [latex]1[/latex], пометить [latex]step[/latex] как [latex]-1[/latex]. В противном случае пометить как [latex]1[/latex].
Если значение для [latex]step = n-1[/latex], то вывести на экран [latex]-1[/latex]. В противном случае вывести расстояние до ближайшей проигрышной для противника позиции.

Результаты тестирования:
Для всех [latex]n[/latex] при [latex]m = 2[/latex] программа предсказуемо выдает последовательность проигрышных ходов при [latex]n = 2^{k}-1[/latex].
На малых значениях [latex]n[/latex] при [latex]m > 2[/latex] установлена корректность алгоритма.

n	m	Результат
7	2	-1
8	2	1
10	3	3
7	3	-1
12	4	2
10	4	-1

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

/*Решение WoW_3 при помощи выигрышно-проигрышного разбиения позиций*/
#include <iostream>
using namespace std;
 
int main()
{
    int n; cin >> n; //количество зерен
    int m; cin >> m; //часть, которую можно съесть за ход
    int result[n + 1]; //массив значений
    for(int i = 0; i < m + 1; i++)
        result[i] = -1;	    //все позиции с n = [0; m) - проигрышные
    int take_to_win = 0;    //расстояние до ближайшей выигрышной позиции
    for(size_t step = m; step < n + 1; step++)  //заполнение массива result[]
    {
        bool good = false;  //есть ли возможность перейти на выигрышную позицию из данной
        //проверка всех позиций, в которые можно попасть за ход
        for(int i = step - 1; i >= step - step / m && !good; i--)
        {
            if(result[i] == -1){  //если выигрышная позиция достижима
                good = true;        //уведомить об этом программу
                take_to_win = n - i; //зафиксировать расстояние до позиции
            }
        }
        if(good) result[step] = 1; //если возможно, пометить позицию как выгрышную
        else result[step] = -1;    //иначе пометить как прогрышную
    }
    if(result[n] == 1) //вывести на экран оптимальное количество зерен на первом шаге
        cout << take_to_win << endl;
    else    //или указать, что позиция проигрышная
        cout << -1 << endl;
    return 0;
}

/*Решение WoW_3 при помощи выигрышно-проигрышного разбиения позиций*/

#include <iostream>

using namespace std;

int main()

{

int n; cin >> n; //количество зерен

int m; cin >> m; //часть, которую можно съесть за ход

int result[n + 1]; //массив значений

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

result[i] = -1; //все позиции с n = [0; m) - проигрышные

int take_to_win = 0; //расстояние до ближайшей выигрышной позиции

for(size_t step = m; step < n + 1; step++) //заполнение массива result[]

{

bool good = false; //есть ли возможность перейти на выигрышную позицию из данной

//проверка всех позиций, в которые можно попасть за ход

for(int i = step - 1; i >= step - step / m && !good; i--)

{

if(result[i] == -1){ //если выигрышная позиция достижима

good = true; //уведомить об этом программу

take_to_win = n - i; //зафиксировать расстояние до позиции

}

if(good) result[step] = 1; //если возможно, пометить позицию как выгрышную

else result[step] = -1; //иначе пометить как прогрышную

}

if(result[n] == 1) //вывести на экран оптимальное количество зерен на первом шаге

cout << take_to_win << endl;

else //или указать, что позиция проигрышная

cout << -1 << endl;

return 0;

}

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static void main(String args[]) {
    	Scanner in = new Scanner(System.in);
    	int n = in.nextInt();	//количество зерен
    	int m = in.nextInt();	//часть, которую можно съесть за ход
    	int[] result = new int[n-m+1];	//массив значений
    	for(int i = 0; i < n-m+1; i++) result[i] = 0;
    	result[0] = 1;	//в позиции n = m следуте взять одно зерно и выиграть
    	result[1] = -1; //в позиции n = m + 1 выиграть нельзя
    	int takeToWin = 0;
    	for(int step = m+1; step < n+1; step++){
    		boolean good = false;	//есть ли возможность перейти на выигрышную позицию из данной
    		//проверка всех позиций, в которые можно попасть за ход
    		for(int i = step-m; i >= ((step - step/m)-m) && !good; i--){
    			if(result[i] == -1){	//если выигрышная позиция достижима
    				good = true;		//уведомить об этом программу
    				takeToWin = n-m-i;	//зафиксировать расстояние до позиции
    			}
    		}
    		if(good) result[step-m] = 1;	//если возможно, пометить позицию как выгрышную
    		else result[step-m] = -1;		//иначе - пометить как проигрышную
    	}
    	for(int i = 0; i < n-m+1; i++)		//вывод типа позиции
    		System.out.println(i+m+":\t"+result[i]);
    	if(result[n-m] == 1)	//вывести на экран оптимальное количество зерен на первом шаге
    		System.out.println(takeToWin);
    	else	//или указать, что выигрышных ходов нет
    		System.out.println(-1);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int n = in.nextInt(); //количество зерен

int m = in.nextInt(); //часть, которую можно съесть за ход

int[] result = new int[n-m+1]; //массив значений

for(int i = 0; i < n-m+1; i++) result[i] = 0;

result[0] = 1; //в позиции n = m следуте взять одно зерно и выиграть

result[1] = -1; //в позиции n = m + 1 выиграть нельзя

int takeToWin = 0;

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

boolean good = false; //есть ли возможность перейти на выигрышную позицию из данной

//проверка всех позиций, в которые можно попасть за ход

for(int i = step-m; i >= ((step - step/m)-m) && !good; i--){

if(result[i] == -1){ //если выигрышная позиция достижима

good = true; //уведомить об этом программу

takeToWin = n-m-i; //зафиксировать расстояние до позиции

}

if(good) result[step-m] = 1; //если возможно, пометить позицию как выгрышную

else result[step-m] = -1; //иначе - пометить как проигрышную

}

for(int i = 0; i < n-m+1; i++) //вывод типа позиции

System.out.println(i+m+":\t"+result[i]);

if(result[n-m] == 1) //вывести на экран оптимальное количество зерен на первом шаге

System.out.println(takeToWin);

else //или указать, что выигрышных ходов нет

System.out.println(-1);

}

Детали реализации:
Для хранения характеристик позиций использован динамически объявляемый массив (VLA — Variable Length Array). Для упрощения анализа использована булева переменная [latex]good[/latex].При решении применялись методы динамического программирования.
Протестировать работу программы можно по ссылке: http://ideone.com/5nmDxl.
Реализация на Java: http://ideone.com/D5R49n

Related Images:

e-olymp 3. Спичечная модель

25/09/2014 by Куленюк Денис Віталійович

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Условие задачи:
http://www.e-olimp.com.ua/problems/3
Прохождение тестов данной программой:
http://www.e-olimp.com.ua/
solutions/1591163
Я разделил задачу на три подэтапа: построение боковой, верхней и задней стен.

Ввод Вывод Комментарий Вердикт

0 0 Проверка на нуль: Пройдено

3 28 Тот же пример что и в условии к задаче: Сходится Проверка пройдена

9 62 1 этап Пройдено

13 83 2 этап Пройдено

19 112 3 этап Пройдено

2Е9 6.00953Е9 Проверка на переполнение максимальным возможным числом: Пройдено

Вначале увидев эту задачу я понял что самое главное в этой задаче это понять какую фигуру лучше строить и как строить. С фигурой все было очевидно: в данном случае самая экономичная фигура это куб, а это значит что нам нужно найти как лучше всего его строить, а если быть более точным как из кубов с величиной стены [latex]I[/latex] построить куб с величиной стены [latex]I+1[/latex]. Я решил что нужно последовательно наращивать стены: вначале боковую, потом верхнюю и напоследок заднюю. Здесь было замечено что количество кубов входящих в нашу фигуру можно найти просто возведя сторону в кубическую степень, с этого и пошли эти строчки:

C++

for(; k<n ; ++i){ k=pow(i+1,3); }

13
14
15

for(; k<n ; ++i){
       k=pow(i+1,3);
   }

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

Первый этап(строительство боковой стены):

C++

if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )

18

if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )

Второй этап(строительство верхней стены):

C++

else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )

23

else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )

Или третий(строительство задней стены):

C++

else if ( (i-1)*i*i < n && n<= i*i*i )

28

else if ( (i-1)*i*i < n && n<= i*i*i )

И мы сразу приступаем к делу: я вывел формулу зависимости количества спичек от фигуры, вот она:
[latex]3xyz+2xy+2xz+2yz+x+y+z[/latex] и из неё я уже вывел эти формулы:
1) Если все стороны равны: [latex]3n(n+1)^2[/latex];

C++

r=3*(i-1)*pow(i,2);

20

r=3*(i-1)*pow(i,2);

2) Если две стороны равны, а третья на единицу больше: [latex]3n^3 + 9n^2 + 7n + 1[/latex];

C++

r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1;

25

r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1;

3) Если две стороны равны, а третья на единицу меньше: [latex]3n^3 + 3n^2 -n-1[/latex].

C++

r= 3*(pow(i,3) + pow(i,2))-i-1;

30

r= 3*(pow(i,3) + pow(i,2))-i-1;

Зачем? Первая формула пригодится нам для первого этапа, когда к уже готовому кубу добавляются еще кубы. Вторая: когда после первого этапа одна сторона стала больше чем остальные. И конечно же третья: которая соответственно строится когда две стороны больше третьей.
Теперь нам осталось только достроить недостающие кубы, для этого вначале нужно узнать сколько кубов нужно достроить:
1)Для первого этапа:

C++

n-=pow(i-1,3);

21

n-=pow(i-1,3);

2)Для второго:

C++

n-=pow(i-1,2)*i;

26

n-=pow(i-1,2)*i;

3)И конечно же для третьего:

C++

n-=pow(i,2)*(i-1);

31

n-=pow(i,2)*(i-1);

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

C++

for( int i1=1 ; n ; i1+=2 )for( int i2=0 ; i2<i1 && n ; i2++,n-- )

37

for( int i1=1 ; n ; i1+=2  )for( int i2=0 ; i2<i1 && n ; i2++,n-- )

Зачем нам это нужно? Просто, я заметил что достройка идет по такому принципу(начиная с левого нижнего угла):

3 3 3 5

3 3 5 3

3 5 3 3

8 5 5 5

и в таком порядке:

16 15 14 13

9 8 7 12

4 3 6 11

1 2 5 10

Как вы видите +8 мы видим только на первом кубе, а +5 на первом кубе треугольного и в середине треугольного . Осталось только описать это и мы получаем:

C++

#include <cstdlib> #include <iostream> #include <cmath> using namespace std; int main() { double n, k=1, i=0,r,r1; cin>>n; for(; k<n ; ++i){ k=pow(i+1,3); } if(!i)i++; if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i ) { r=3*(i-1)*pow(i,2); // 3n(n+1)^2 n-=pow(i-1,3); } else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i ) { r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1; // 3n^3 + 9n^2 + 7n + 1 n-=pow(i-1,2)*i; } else if ( (i-1)*i*i < n && n<= i*i*i ) { r= 3*(pow(i,3) + pow(i,2))-i-1; // 3n^3 + 3n^2 -n-1 n-=pow(i,2)*(i-1); } else{ cout << i << "???"; return 0; } for( int i1=1 ; n ; i1+=2 ) { for( int i2=0 ; i2<i1 && n ; i2++,n-- ) { if( i1 == 1 ){ r+=8; } else if( i2 == 0 || i2 == i1/2 ){ r+=5; } else{ r+=3; } } } cout << r << endl; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

int main()
{


   double n, k=1, i=0,r,r1;
   cin>>n;
   for(; k<n ; ++i){
       k=pow(i+1,3);
   }
   if(!i)i++;

   if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )
   {
        r=3*(i-1)*pow(i,2);                                    // 3n(n+1)^2
        n-=pow(i-1,3);
   }
   else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )
   {
               r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1; // 3n^3 + 9n^2 + 7n + 1
               n-=pow(i-1,2)*i;
   }
   else if ( (i-1)*i*i < n && n<= i*i*i )
   {
        r= 3*(pow(i,3) + pow(i,2))-i-1;             // 3n^3 + 3n^2 -n-1
        n-=pow(i,2)*(i-1);
   }
   else{
       cout << i << "???";
       return 0;
   }
    for( int i1=1 ; n ; i1+=2  )
               {
                   for( int i2=0 ; i2<i1 && n ; i2++,n-- )
                   {
                       if( i1 == 1 ){
                                       r+=8;
                                    }
                       else if( i2 == 0 || i2 == i1/2 ){
                                                           r+=5;
                                                        }
                       else{
                               r+=3;
                           }
                   }

               }
        cout << r << endl;

return 0;
}

Related Images:

Posted in Творческие задачи. Tagged Жадные алгоритмы, Олимпиадные задачи.

Post navigation

Newer posts →

Search

1. Линейные вычисления

2. Программы с ветвлением

3. Циклы

4. Потоковая обработка

5. Массивы

6. Многомерные массивы

7. Строки c-string

8. Строки string

9. Последовательные контейнеры

A. Сортировки и жадность

B. Стеки-деки-очереди

C. Ассоциативные контейнеры

D. Графы

E. Дерево отрезков

F. Динамическое программирование

Игры программистов

Спортивное программирование

Творческие задачи

Численный анализ

⌂ Организационные

Студенты 2020

Введите адрес для отправки новостей

E-mail

Іванов Вячеслав Володимирович (22)
Ілларіонова Марія Валеріївна (20)
Вустянюк Ігор Дмитрович (19)
Зелінський Вячеслав Олександрович (19)
Сплошнов Кирилл (18)
Таран Таня (17)
Гордийчук Вадим (15)
Калачьов Андрій Сергійович (14)
Сорокіна Поліна Юріївна (14)
Царев Николай Александрович (14)
Студенты 2019

Студенты 2018

Студенты 2017

Студенты 2016

Студенты 2015

Студенты 2014

Proudly powered by WordPress | Theme: Sunspot by WordPress.com.

Ввод	Вывод	Комментарий	Вердикт
0	0	Проверка на нуль:	Пройдено
3	28	Тот же пример что и в условии к задаче: Сходится	Проверка пройдена
9	62	1 этап	Пройдено
13	83	2 этап	Пройдено
19	112	3 этап	Пройдено
2Е9	6.00953Е9	Проверка на переполнение максимальным возможным числом:	Пройдено