e-olymp 2171. Поиск набора образцов

19/05/2016 by Женя Максимова

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

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

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

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

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

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

Тесты

Test	Input	Output
1	3 gr sud abc lksh sudislavl kostroma summer group b	sudislavl group b
2	4 a b + + xxx ababa dfs c + + qwerty xxxx	ababa c + + xxxx
3	1 a a b a c a d	a a a
4	2 bab aba aabba w w w

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

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)
typedef long long ll;

int find_subctr(string t, string s)
{
  const int p = 97;  // основание системы счисления для хеширования строк
  // вычисляем степени числа P, чтобы ускорить процесс хеширования
  vector<ll> p_pow (s.length());
  p_pow[0] = 1;
  for (size_t i=1; i<p_pow.size(); ++i)
    p_pow[i] = p_pow[i-1] * p;
  // вычисляем хеши всех префиксов строки S
  vector<ll> h (s.length());
  for (size_t i=0; i<s.length(); ++i)
    {
      h[i] = (s[i] - 't' + 1) * p_pow[i];
      if (i)  h[i] += h[i-1];
    }
  // посчитаем хеш строки Т
  ll h_t = 0;
  for (size_t i=0; i<t.length(); ++i)
    h_t += (t[i] - 't' + 1) * p_pow[i];
  // сравниваем хеши строки T и подстрок S длины |T|
  for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)
    {
      ll cur_h = h[i+t.length()-1];
      if (i)  cur_h -= h[i-1];
      // если равенство выполняется хотя бы один раз, мы прекращаем поиск
      if (cur_h == h_t * p_pow[i])
        return int(i);
    }
  return -1;
}

int main()
{
  vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C
  int n;
  cin >> n;
  string tmp;
  getline(cin,tmp);
  in_range(i,0,n)
    {
      getline(cin,tmp);
      if(tmp.length()==1) C.push_back(tmp);
      T.push_back(tmp);
    }
  while(getline(cin,tmp))
    {
      S.push_back(tmp);
    }
  in_range(i,0,S.size())
    {
      string s=S[i];
      if(s=="") continue; // отсекаем случай пустой строки
      if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором
        {
          in_range(j,0,C.size())
          {
            string c=C[j];
            if(s==c)
              {
                cout << s << "\n";
                break;
              }
          }
          continue;
        }
      in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа
      {
        string t=T[j];
        int pos = find_subctr(t,s);
        if(pos>=0)
          {
            cout << s << "\n";
            break;
          }
      }
    }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)

typedef long long ll;

int find_subctr(string t, string s)

{

const int p = 97; // основание системы счисления для хеширования строк

// вычисляем степени числа P, чтобы ускорить процесс хеширования

vector<ll> p_pow (s.length());

p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i)

p_pow[i] = p_pow[i-1] * p;

// вычисляем хеши всех префиксов строки S

vector<ll> h (s.length());

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

{

h[i] = (s[i] - 't' + 1) * p_pow[i];

if (i) h[i] += h[i-1];

}

// посчитаем хеш строки Т

ll h_t = 0;

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

h_t += (t[i] - 't' + 1) * p_pow[i];

// сравниваем хеши строки T и подстрок S длины |T|

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

{

ll cur_h = h[i+t.length()-1];

if (i) cur_h -= h[i-1];

// если равенство выполняется хотя бы один раз, мы прекращаем поиск

if (cur_h == h_t * p_pow[i])

return int(i);

}

return -1;

}

int main()

{

vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C

int n;

cin >> n;

string tmp;

getline(cin,tmp);

in_range(i,0,n)

{

getline(cin,tmp);

if(tmp.length()==1) C.push_back(tmp);

T.push_back(tmp);

}

while(getline(cin,tmp))

{

S.push_back(tmp);

}

in_range(i,0,S.size())

{

string s=S[i];

if(s=="") continue; // отсекаем случай пустой строки

if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором

{

in_range(j,0,C.size())

{

string c=C[j];

if(s==c)

{

cout << s << "\n";

break;

}

continue;

}

in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа

{

string t=T[j];

int pos = find_subctr(t,s);

if(pos>=0)

{

cout << s << "\n";

break;

}

return 0;

}

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex] со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство, строка [latex]t[/latex] не является подстрокой [latex]s[/latex] и мы переходим к следующему образцу.

Однако данный алгоритм не целесообразно использовать для строк единичной длины. Про большом количестве таких строк неэффективность алгоритма становится очень заметной. Поэтому мы создаем отдельный набор образцов, состоящих ровно из одного символа. Если на вход поступает строка единичной длины, мы просто ищем ее в этом наборе за [latex]O(n)[/latex].

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

Засчитанное решение на сайте e-olymp.com

Related Images:

e-olymp 982. Связность

15/05/2016 by Женя Максимова

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

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex] каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test	Input	Output
1	3 2 1 2 3 2	YES
2	3 1 1 3	NO

Мои тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	4 5 1 2 2 1 2 4 2 4 4 2	NO
3	5 4 1 2 5 1 3 5 4 3	YES

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

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()
{
  int m,n;
  cin >> n >> m;
  vector < vector<int> > g(n); // граф
  int s=0; // начальная вершина
  in_range(i,0,m) // считывание графа
    {
      int u,v;
      cin >> u >> v;
      g[u-1].push_back(v-1);
      g[v-1].push_back(u-1);
    }
  queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе
  q.push (s);
  vector<bool> used (n); // логический массив, указывающий, посещена ли вершина
  used[s] = true;
  while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной
    {
      int v = q.front();
      q.pop(); // достаем из головы очереди одну вершину
      for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины
        {
          int to = g[v][i];
          if (!used[to]) // если текущая вершина еще не была посещена
            {
              used[to] = true; //отмечаем, что мы ее посетили
              q.push (to); // помещаем в очередь
            }
        }
    }
  vector<bool>::iterator it;
  it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины
  if (it == used.end())
    cout << "YES"; // если все вершины посещены, то граф связный
  else
    cout << "NO";
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()

{

int m,n;

cin >> n >> m;

vector < vector<int> > g(n); // граф

int s=0; // начальная вершина

in_range(i,0,m) // считывание графа

{

int u,v;

cin >> u >> v;

g[u-1].push_back(v-1);

g[v-1].push_back(u-1);

}

queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе

q.push (s);

vector<bool> used (n); // логический массив, указывающий, посещена ли вершина

used[s] = true;

while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной

{

int v = q.front();

q.pop(); // достаем из головы очереди одну вершину

for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины

{

int to = g[v][i];

if (!used[to]) // если текущая вершина еще не была посещена

{

used[to] = true; //отмечаем, что мы ее посетили

q.push (to); // помещаем в очередь

}

vector<bool>::iterator it;

it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины

if (it == used.end())

cout << "YES"; // если все вершины посещены, то граф связный

else

cout << "NO";

return 0;

}

Алгоритм

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

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

Засчитанное решение на сайте e-olymp.com

Related Images:

A295

12/03/2016 by Женя Максимова

Задача. Даны целые числа [latex]a_{1},\ldots, a_{n}[/latex]. Наименьший член последовательности [latex]a_{1}, \ldots, a_{n}[/latex] заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько членов со значением min [latex](a_{1}, \ldots, a_{n})[/latex], то заменить последний по порядку.

Тесты

Test	Input	Output
1	2 4 8 16 2 4	2 4 8 16 6 4
2	1 1 1 1	1 1 1 1
3	-5 5 -10 10 -10 5 5	-5 5 -10 10 0 5 5
4	2 6 9 -4 -5 7 13	2 6 9 -4 4 7 13
5	0 0 0 0 0 1	0 0 0 0 0 1
6	0 1 0 0 2 0 25	0 1 0 0 2 4 25

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

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

int main()
{
  vector<int>a;
  int el; //supporting variable for saving input values
  while(cin >> el)
    {
      a.push_back(el); //adding value to the vector
    }
  int min = a[0]; // minimal value
  int num = 0; // number of the minimal value
  double sum = 0; 
  for(int i=0; i<a.size(); i++)
    {
      if(a[i]<=min) //finding the number of the minimal value
        {
          min = a[i]; 
          num = i;
        }
      sum += a[i];
    }
  int average = floor(sum/a.size()); //calculing the average of vector elements
  a[num] = average; //replacing minimal value by the average
  for(int i = 0; i < a.size(); i++)
    {
      cout << a[i] << " ";
    }
  return 0;
}

#include<iostream>

#include<cmath>

#include<vector>

using namespace std;

int main()

{

vector<int>a;

int el; //supporting variable for saving input values

while(cin >> el)

{

a.push_back(el); //adding value to the vector

}

int min = a[0]; // minimal value

int num = 0; // number of the minimal value

double sum = 0;

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

{

if(a[i]<=min) //finding the number of the minimal value

{

min = a[i];

num = i;

}

sum += a[i];

}

int average = floor(sum/a.size()); //calculing the average of vector elements

a[num] = average; //replacing minimal value by the average

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

{

cout << a[i] << " ";

}

return 0;

}

Алгоритм

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

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

Related Images:

e-olymp 1077. Java против C++

27/02/2016 by Женя Максимова

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

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

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

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

Тесты

Test	Input	Output
1	java_word	javaWord
2	cppWorD	cpp_wor_d
3	simpleword	simpleword
4	two__underscores	Error!
5	_underscore_in_the_beginning	Error!
6	underscore_in_the_end_	Error!
7	UppercaseInTheBeginning	Error!
8	mixed_Style	Error!

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

#include <iostream>
#include <cstring>
using namespace std;
const int START = 0; //start state
const int CONTINUE = 1; //common prefix identifier state
const int JAVAWORD = 2; //2-4 intermediate states
const int CPPWORD = 3;
const int CPPDEL = 4; //CPP-delimeter
const int JAVA = 5; //5-10 final states
const int CPP = 6;
const int UNIVERSAL = 7;
const int JAVAERR = 8; //Error in JAVA
const int CPPERR = 9; //Error in CPP
const int ERROR = 10;
char var[101];
char result[203] = {'\0'}; //fill the resulting string with zero code characters
int reslen = 0; //the length of the resulting string
int state;
bool is_small(char c) //supporting function
{
  return ('a'<= c && c <= 'z');
}
bool is_big(char c) //supporting function
{
  return ('A'<= c && c <= 'Z');
}
bool is_underscore(char c) //supporting function
{
  return (c == '_');
}
int selection_of_style(char * var, size_t len) //determines preliminary type of string
{
  char c=var[0];
  state = START;
  if(is_small(c))
    {
      state = CONTINUE;
    }
  if(is_big(c))
    {
      state = ERROR;
      return state;
    }
  if(is_underscore(c))
    {
      state = ERROR;
      return state;
    }
  for (int i=1; i<len; i++)
    {
      c=var[i];
      if(is_small(c)) state = state;
      if(is_big(c))
        {
          state = JAVAWORD;
          return state;
        }
      if(is_underscore(c))
        {
          state = CPPWORD;
          return state;
        }
    }
  //if(state == CONTINUE)
  //in the end os the word we are still in the state CONTINUE
  state = UNIVERSAL;
  return state;
}
int is_java(char * var, size_t len)//check if the word is a correct java variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          state = state;
        }
      if(is_big(c))
        {
          state = state;
        }
      if(is_underscore(c))
        {
          state = JAVAERR;
          return state;
        }
    }
  if(state == JAVAWORD)
    {
      state = JAVA;
    }
  return state;
}
int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          if(state == CPPDEL)
            {
              state = CPPWORD;
            }
          else
            state = state;
        }
      if(is_big(c))
        {
          state = JAVAERR;
          return state;
        }

      if(is_underscore(c))
        {
          if(state == CPPDEL)
            {
              state = CPPERR;
              return state;
            }
          state = CPPDEL;
        }
    }
  if(state == CPPWORD)
    {
      state = CPP;
    }
  if(state == CPPDEL) //underscore in the end is an error too
    {
      state = CPPERR;
    }
  return state;
}
void java_to_cpp(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i]; //append character to resulting string
        }
      if(is_big(c))
        {
          result[reslen++] = '_';
          result[reslen++] = var[i]+32;
        }
    }
}
void cpp_to_java(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i];
        }
      if(is_underscore(c))
        {
          result[reslen++]=var[++i]-32;
        }
    }
}
int main()
{
  cin >> var;
  size_t len = strlen(var);
  state = selection_of_style(var, len);
  if(state == ERROR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVAWORD)
    state = is_java(var,len);
  if(state == CPPWORD)
    state = is_cpp(var,len);
  if (state == UNIVERSAL)
    {
      cout << var << endl;
      return 0;
    }
  if(state == JAVAERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == CPPERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVA)
    {
      java_to_cpp(var,len);
      cout << result;
      return 0;
    }
  if(state==CPP)
    {
      cpp_to_java(var,len);
      cout << result;
      return 0;
    }
  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

#include <iostream>

#include <cstring>

using namespace std;

const int START = 0; //start state

const int CONTINUE = 1; //common prefix identifier state

const int JAVAWORD = 2; //2-4 intermediate states

const int CPPWORD = 3;

const int CPPDEL = 4; //CPP-delimeter

const int JAVA = 5; //5-10 final states

const int CPP = 6;

const int UNIVERSAL = 7;

const int JAVAERR = 8; //Error in JAVA

const int CPPERR = 9; //Error in CPP

const int ERROR = 10;

char var[101];

char result[203] = {'\0'}; //fill the resulting string with zero code characters

int reslen = 0; //the length of the resulting string

int state;

bool is_small(char c) //supporting function

{

return ('a'<= c && c <= 'z');

}

bool is_big(char c) //supporting function

{

return ('A'<= c && c <= 'Z');

}

bool is_underscore(char c) //supporting function

{

return (c == '_');

}

int selection_of_style(char * var, size_t len) //determines preliminary type of string

{

char c=var[0];

state = START;

if(is_small(c))

{

state = CONTINUE;

}

if(is_big(c))

{

state = ERROR;

return state;

}

if(is_underscore(c))

{

state = ERROR;

return state;

}

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

{

c=var[i];

if(is_small(c)) state = state;

if(is_big(c))

{

state = JAVAWORD;

return state;

}

if(is_underscore(c))

{

state = CPPWORD;

return state;

}

//if(state == CONTINUE)

//in the end os the word we are still in the state CONTINUE

state = UNIVERSAL;

return state;

}

int is_java(char * var, size_t len)//check if the word is a correct java variable

{

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

{

char c = var[i];

if(is_small(c))

{

state = state;

}

if(is_big(c))

{

state = state;

}

if(is_underscore(c))

{

state = JAVAERR;

return state;

}

if(state == JAVAWORD)

{

state = JAVA;

}

return state;

}

int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable

{

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

{

char c = var[i];

if(is_small(c))

{

if(state == CPPDEL)

{

state = CPPWORD;

}

else

state = state;

}

if(is_big(c))

{

state = JAVAERR;

return state;

}

if(is_underscore(c))

{

if(state == CPPDEL)

{

state = CPPERR;

return state;

}

state = CPPDEL;

}

if(state == CPPWORD)

{

state = CPP;

}

if(state == CPPDEL) //underscore in the end is an error too

{

state = CPPERR;

}

return state;

}

void java_to_cpp(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i]; //append character to resulting string

}

if(is_big(c))

{

result[reslen++] = '_';

result[reslen++] = var[i]+32;

}

void cpp_to_java(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i];

}

if(is_underscore(c))

{

result[reslen++]=var[++i]-32;

}

int main()

{

cin >> var;

size_t len = strlen(var);

state = selection_of_style(var, len);

if(state == ERROR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVAWORD)

state = is_java(var,len);

if(state == CPPWORD)

state = is_cpp(var,len);

if (state == UNIVERSAL)

{

cout << var << endl;

return 0;

}

if(state == JAVAERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == CPPERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVA)

{

java_to_cpp(var,len);

cout << result;

return 0;

}

if(state==CPP)

{

cpp_to_java(var,len);

cout << result;

return 0;

}

return 0;

}

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

*круговая стрелочка означает, что мы остаемся в этом же состоянии.

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

Когда мы считываем очередной символ, мы переходим в другое состояние либо остаемся в предыдущем. В состояние Error(отмечено красным) мы переходим, если считаем какую-любо последовательность символов, не подходящую ни под один из стандартов.

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния. Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

Определив стандарт, к которому принадлежит переменная, мы вызываем блок перевода. Результат всегда записываем в отдельную переменную. В случае Java мы снова последовательно перебираем все символы строки и заменяем каждую встретившуюся большую букву на подчеркивание и эту же букву в маленьком регистре. Размер строки в этом случае увеличивается на количество больших букв в ее исходном варианте. В случае же С++ мы удаляем каждое подчеркивание, сдвигая все последующие символы, а первый из них переводим в большой регистр. Очевидно, что размер строки в этом случае будет уменьшен на количество подчеркиваний.

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

Засчитаное решение на сайте e-olymp

Related Images:

Mloops 21

11/11/2015 by Женя Максимова

Задача.Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

1+12+33+64+105+156+217+288
12+33+64+105+156+217+288+1
33+64+105+156+217+288+1+12
64+105+156+217+288+1+12+33
105+156+217+288+1+12+33+64
156+217+288+1+12+33+64+105
217+288+1+12+33+64+105+156

Тесты

№	[latex]m[/latex]	[latex]n[/latex]	Результат
1	5	13	1+12+33+64+10 12+33+64+105+ 33+64+105+1+1 64+105+1+12+3 105+1+12+33+6
2	8	11	1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+ 1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+
3	11	20	1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+ 105+156+217+1+12+33+ 156+217+1+12+33+64+1 217+1+12+33+64+105+1 1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+

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

#include <iostream>
#include <stdio.h>
#include<cmath>
using namespace std;
int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности
{
 i++;
 return i*i+4*(i*i-i); 
}
int length_of_element(int el) // длина i-того элемента
{
 if( el==0|| el==1 ) 
   return 1;
 return ceil(log10(el));
}

int max_quantity() // максимальное количество чисел в строке
{
 int max_q=0;
 int length=0;
 for(int j=0; true; j++) 
  {
	 int elem = element(j);
	 int  length_el = length_of_element(elem);
	 if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число 
    {
      length += length_el;
      max_q++;
      if(length == n)
        return max_q;
    }
	 else // если число не "влезает", добавляем "+"
	{
	  max_q++;
	  return max_q;
	}
   if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"
    {
     length += 1;
     if(length == n)
      return max_q;
    }
  }
 return max_q; // такая ситуация невозможна
}

int line(int i) // печать i-той строки
{
 int length=0;
 for(int jj=i; true; jj++)
    {
     int j = jj % max_q; // формула циклического сдвига чисел в строке
     int  elem = element(j); // число которое мы будем выводить
     int  length_el = length_of_element(elem); // длина числа
     if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число 
        {
         length += length_el;
         cout << elem;
         if(length == n)
            {
             cout << endl;
             return length;
            }
        }
     else // если длина получается больше, мы "отрезаем" от числа нужное количество символов
        {
         int excess = length+length_el-n;
         for(int z = 0; z < excess; ++z) elem /= 10;
         cout << elem << endl;
         return length;
        }

     if(length + 1 <= n) // проверяем, нужно ли выводить "+"
      {
        length += 1; cout << "+";
        if(length == n)
        {
          cout << endl;
          return length;
        }
      }
    }
return 0;
}

int main()
{
 cin >> m >> n; // параметры таблицы
 max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке
 for(int i=0; i<m; i++) line(i); // вывод таблицы
 return 0;
}

#include <iostream>

#include <stdio.h>

#include<cmath>

using namespace std;

int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности

{

i++;

return i*i+4*(i*i-i);

}

int length_of_element(int el) // длина i-того элемента

{

if( el==0|| el==1 )

return 1;

return ceil(log10(el));

}

int max_quantity() // максимальное количество чисел в строке

{

int max_q=0;

int length=0;

for(int j=0; true; j++)

{

int elem = element(j);

int length_el = length_of_element(elem);

if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число

{

length += length_el;

max_q++;

if(length == n)

return max_q;

}

else // если число не "влезает", добавляем "+"

{

max_q++;

return max_q;

}

if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"

{

length += 1;

if(length == n)

return max_q;

}

return max_q; // такая ситуация невозможна

}

int line(int i) // печать i-той строки

{

int length=0;

for(int jj=i; true; jj++)

{

int j = jj % max_q; // формула циклического сдвига чисел в строке

int elem = element(j); // число которое мы будем выводить

int length_el = length_of_element(elem); // длина числа

if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число

{

length += length_el;

cout << elem;

if(length == n)

{

cout << endl;

return length;

}

else // если длина получается больше, мы "отрезаем" от числа нужное количество символов

{

int excess = length+length_el-n;

for(int z = 0; z < excess; ++z) elem /= 10;

cout << elem << endl;

return length;

}

if(length + 1 <= n) // проверяем, нужно ли выводить "+"

{

length += 1; cout << "+";

if(length == n)

{

cout << endl;

return length;

}

return 0;

}

int main()

{

cin >> m >> n; // параметры таблицы

max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке

for(int i=0; i<m; i++) line(i); // вывод таблицы

return 0;

}

Алгоритм

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

[latex]n^2+4\cdot(n^2-n)[/latex]

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

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

Чтобы число столбцов [latex]n[/latex] соответствовало числу символов в каждой строке, мы выводим числа по одному, каждый раз проверяя, не превысила ли общая длина строки заданное число [latex]n[/latex]. Если длина все-таки получается больше, мы выводим то количество символов, которое помещается в данную строку, а остальные отбрасываем.

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

Related Images:

MLoop 2

02/11/2015 by Женя Максимова

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

Тесты(найдено с помощью математической системы WolframAlpha):

[latex]A[/latex]

[latex]B[/latex]

[latex]x\approx[/latex]

-20

-11.6945378230838209122818536587051434153…

-1.25741503276862309237205903178504130394…

0.547316310185252929580383582338832450320…

10.9948442206261587135425985750810372810…

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

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

const int max_iterations=100;
const double interval = 0.001;  // interval length for roots subdivision
bool is_root = false;  // is false if function has a second type break in root candidate point
double delta; //precision of root search
double A, B;

double f(double x)//our function
{
 double r = DBL_MAX;
 try
  {
   r =  x / (2*sin(x)+1) - tan(log(x*x+1));  
  }
 catch(...)
  {
   //nothing to do for arithmetic exception
  }
 return r;
}

bool is_change_sign(double fa, double fb)
{
 return fa*fb<0;
}

double find_root(double a, double b, double delta,  bool *yes)
{
 double fa;
 double fb;
 double fc;
 double c;
 int l=0;
 fa=f(a);
 fb=f(b);
 double dy,dy1; //old and new OY projections of chord
 dy=fabs(fa-fb);
 dy1=DBL_MAX;
 while(true)
   {
    l++;
    if(l > max_iterations)
      {
       *yes=false;
       return (a+b)/2;
      }
    c = a - (b - a) * fa/(fb - fa);
    fc = f(c);
    if(fa*fc>0)
      {
       a=c;
       fa=fc;
      }
    else
      {
       b=c;
       fb=fc;
      }
    if(fabs(fa)<delta)
      {
       *yes=true;
       return a;
      }
    if(fabs(fb)<delta)
      {
       *yes=true;
       return b;
      }
    if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)
      {
       if(dy1>dy) //checking if there's break of second kind(pole)
         {
          *yes=false;
          return (a+b)/2;
         }
       if(fabs(b-a)<delta) //else we are near the root
         {
          *yes=true;
          return (a+b)/2;
         }
      }
    dy=dy1; //change old chord height
    dy1=fabs(fa-fb); //calculate new chord height
   }
 // we can't get here
 *yes=false;
 return c;
}

int main()
{
 scanf("%lf %lf %lf",&A,&B,&delta);
 double a,b;
 double fa, fb;
 /*
 test interval for finding roots
 int k=2;
 A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;
 B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;
 delta = 1e-12;
 printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);
 */
 fb = f(A);
 for(a = A, b = A + interval; b<=B; a += interval, b += interval)
  {
   fa = fb;
   fb = f(b);
   if(is_change_sign(fa,fb))
     {
      double r=find_root(a,b,delta, &is_root);
      if(is_root)
       {
        printf("%14.15lf \n",r);
       }
     }
  }
 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

#include <stdio.h>

#include <math.h>

#include <iostream>

#include<cfloat>

using namespace std;

const int max_iterations=100;

const double interval = 0.001; // interval length for roots subdivision

bool is_root = false; // is false if function has a second type break in root candidate point

double delta; //precision of root search

double A, B;

double f(double x)//our function

{

double r = DBL_MAX;

try

{

r = x / (2*sin(x)+1) - tan(log(x*x+1));

}

catch(...)

{

//nothing to do for arithmetic exception

}

return r;

}

bool is_change_sign(double fa, double fb)

{

return fa*fb<0;

}

double find_root(double a, double b, double delta, bool *yes)

{

double fa;

double fb;

double fc;

double c;

int l=0;

fa=f(a);

fb=f(b);

double dy,dy1; //old and new OY projections of chord

dy=fabs(fa-fb);

dy1=DBL_MAX;

while(true)

{

l++;

if(l > max_iterations)

{

*yes=false;

return (a+b)/2;

}

c = a - (b - a) * fa/(fb - fa);

fc = f(c);

if(fa*fc>0)

{

a=c;

fa=fc;

}

else

{

b=c;

fb=fc;

}

if(fabs(fa)<delta)

{

*yes=true;

return a;

}

if(fabs(fb)<delta)

{

*yes=true;

return b;

}

if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)

{

if(dy1>dy) //checking if there's break of second kind(pole)

{

*yes=false;

return (a+b)/2;

}

if(fabs(b-a)<delta) //else we are near the root

{

*yes=true;

return (a+b)/2;

}

dy=dy1; //change old chord height

dy1=fabs(fa-fb); //calculate new chord height

}

// we can't get here

*yes=false;

return c;

}

int main()

{

scanf("%lf %lf %lf",&A,&B,&delta);

double a,b;

double fa, fb;

test interval for finding roots

int k=2;

A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;

B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;

delta = 1e-12;

printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);

fb = f(A);

for(a = A, b = A + interval; b<=B; a += interval, b += interval)

{

fa = fb;

fb = f(b);

if(is_change_sign(fa,fb))

{

double r=find_root(a,b,delta, &is_root);

if(is_root)

{

printf("%14.15lf \n",r);

}

return 0;

}

Алгоритм

Для начала запишем данное нам уравнение в виде функции [latex]y=f(x)[/latex] и построим ее график:

[latex]y=\frac{x}{2 \cdot sin x +1}-tan(ln(x^2+1))[/latex]

Задача о нахождении приближённых значений действительных корней уравнения [latex]f(x)=0[/latex] предусматривает предварительное отделение корня, то есть установление интервала, в котором других корней данного уравнения нет.

Метод хорд предусматривает замену функции на интервале на секущую, и поиск ее пересечения с осью [latex]OX[/latex]. На заданном интервале [latex][a,b][/latex] с точностью [latex]\varepsilon[/latex] корень будет вычисляться согласно итерационному выражению, которое имеет вид:

[latex]x_{i+1}=x_{i-1}-\frac{f(x_{i-1}) \cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1}) ) }[/latex]

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

В точке, где находится предполагаемый корень, имеется разрыв второго рода. Здесь метод хорд обнаруживает перемену знака и начинает сужать отрезок. Однако расстояние между крайними точками отрезка не уменьшается, а увеличивается. А именно увеличивается проекция отрезка на ось [latex]OY[/latex]. И чем ближе мы находимся к точке разрыва, тем она больше, а в самой точке стремится к бесконечности. В качестве примера приведем функцию [latex]\frac{(x-5)^2}{x-4}[/latex], имеющую разрыв второго рода в точке [latex]x=4[/latex].
Аналогичный случай — точка разрыва первого рода, где наша хорда стремится к некоторой константе — величине разрыва. Пример — функция [latex]\frac{\sin x\cdot(x-2.5)}{\left | x-2,5 \right |}[/latex], имеющая разрыв первого рода в точке [latex]x=2,5[/latex].
Функция не является разрывной и даже имеет корень, однако в точке корня производная стремится к бесконечности. Например, функция [latex]\sqrt[3]{x-1,2}[/latex], имеющая корень в точке [latex]x=1,2[/latex]. Для функций подобного рода длина проекции отрезка на ось [latex]OY[/latex] будет очень медленно меняться, вследствие чего для разумного числа итераций она будет превосходить заранее выбранную точность [latex]\varepsilon[/latex].

Функция равна нулю или очень близка к нулю на некотором интервале(например, функция [latex]y=rect(x-1,5)\cdot(x-1)\cdot(x-2)^2[/latex]). Здесь метод хорд найдет пересечение с осью [latex]OX[/latex] в интервале, где находятся корни(одна из сторон отрезка будет корнем), но все последующие итерации будут выдавать эту же точку. Поэтому хорда не будет уменьшаться, и даже этот один корень не будет найден(если будет использоваться стандартная [latex]\delta[/latex]-оценка точности по оси [latex]OX[/latex]).

Функция вида [latex]y=x^{2k}[/latex] или ей подобная, например, [latex]y=1+\sin x[/latex], к которой метод хорд вообще не применим, так как нарушается начальное условие применимости этого метода. Здесь нужно ввести дополнительную проверку. Изменим значение функции на небольшую константу — нашу точность [latex]\varepsilon[/latex] и повторим процедуру поиска корней. В результате мы получим [latex]2k[/latex] корней, каждую пару из которых мы можем считать краями интервала, в котором лежит настоящий корень.

К счастью, в данной нам функции присутствует только один из этих случаев, а именно разрыв второго рода. Аналитически рассмотрев нашу функцию, мы обнаружили, что корни следует искать в окрестности точек[latex]\sqrt{e^{\frac{\pi}{2}+\pi \cdot k}-1}[/latex] с отклонением [latex]\pm\pi[/latex]. В корнях функции ее производная быстро растет с ростом [latex]k[/latex].

Критерием отбрасывания кандидата на корень будет рост длины хорды при сужении интервала. Критерием останова будет сужение интервала до заданной точности [latex]\delta[/latex].
Код программы

Related Images:

Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

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

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

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

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

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

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

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

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

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

Related Images:

Mif 17.9

30/09/2015 by Женя Максимова

Задача. Принадлежит ли точка (х;y) фигуре на рисунке?

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

Тесты

[latex]x[/latex]	0	3	0	6	6	-1000
[latex]y[/latex]	0	2	6	0	6	48000
Результат	NO	YES	YES	YES	NO	NO

Алгоритм

По рисунку видно, что заданная фигура ограничена осями координат и двумя прямыми: [latex] y = 6 — x [/latex] сверху и [latex] y = 4 — 2 \cdot x [/latex] снизу. То есть, решением является пересечение решений неравенств:
[latex]x \geq 0, y \geq 0, y \leq 6 — x, y \geq 4 — 2 \cdot x[/latex]

Если координаты точки удовлетворяют всем этим условиям, программа выводит «YES», в противном случае — «NO».

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

#include<iostream>
using namespace std;
int main()
{
  int x,y;
  cin >> x >> y;
  if ( x >= 0 && y >= 0 && y <= 6 - x && y >= 4 - 2*x ) //условие принадлежноcти точки данной фигуре
    {
     cout << "YES";
     return 0;
    }
  cout << "NO"; 
  return 0;
}

#include<iostream>

using namespace std;

int main()

{

int x,y;

cin >> x >> y;

if ( x >= 0 && y >= 0 && y <= 6 - x && y >= 4 - 2*x ) //условие принадлежноcти точки данной фигуре

{

cout << "YES";

return 0;

}

cout << "NO";

return 0;

}

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

Related Images:

e-olymp 128. Счастливые билеты

21/09/2015 by Женя Максимова

Задача. Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

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

Тесты

Число [latex]N[/latex]	3	27	26	1	10
Количество билетов	100	1	9	9	3969

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

#include <iostream>
using namespace std;
int main() 
{
  int N, c = 0;
  cin >> N;
  for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  {
     for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     {
        if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры
        { c++; } //подсчет подходящих номеров
     }
  }
  cout << c*c; //увеличение количества в c раз для шестизначного числа
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N, c = 0;

cin >> N;

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры

{ c++; } //подсчет подходящих номеров

}

cout << c*c; //увеличение количества в c раз для шестизначного числа

return 0;

}

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

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

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

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

Related Images:

e-olymp 138. Банкомат

20/09/2015 by Женя Максимова

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма	130	999	7360	3	80	123450	567	440
Число купюр	3	-1	18	-1	3	249	-1	4

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

#include <stdio.h>
int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры
int main()
{
 int n, q, x; //q - вспомогательная переменная в цикле
 scanf("%d",&n); 
 x=0; //количество купюр,  ему по умолчанию присваивается 0
 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему
 {
    q = Q[i]; 
    x += n / q; //считаем, сколько раз входит купюра в сумму
    n %= q;  //сумме присваивается остаток от деления на данную купюру
 }
 if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать
 printf("%d",x); 
 return 0;
}

#include <stdio.h>

int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры

int main()

{

int n, q, x; //q - вспомогательная переменная в цикле

scanf("%d",&n);

x=0; //количество купюр, ему по умолчанию присваивается 0

for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему

{

q = Q[i];

x += n / q; //считаем, сколько раз входит купюра в сумму

n %= q; //сумме присваивается остаток от деления на данную купюру

}

if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать

printf("%d",x);

return 0;

}

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].

Решение

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

Related Images:

ML15

18/09/2015 by Женя Максимова

Задача. Определить силу притяжения [latex]F[/latex] между телами массы [latex]m_1[/latex] и [latex]m_2[/latex], находящимися на расстоянии [latex]r[/latex] друг от друга.

Тесты

Масса первого тела(кг)	Масса второго тела(кг)	Расстояние(м)	Сила притяжения
2e15	1.5e10	1e3	2.00215e+09 Н
3e20	2.5	1e5	4.00430e+05 Н
7e-1	9	2	1.05113e-10 Н
3e20	0	1e5	0.00000e+00 Н
20	50	9e5	8.23931e-20 Н

Алгоритм

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

[latex]F=G\cdot \frac{m1\cdot m2}{r^2}[/latex],

где [latex]m_1[/latex], [latex]m_2[/latex] — массы тел, [latex]r[/latex] — расстояние, а [latex]G[/latex] — гравитационная постоянная, значение которой задается в виде константы. Остальные значения вводятся с клавиатуры, в системе СИ.

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

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

#include <stdio.h>
#include <cmath>
using namespace std;
int main()
 { 
   double m1, m2, r, F; //объявление переменных
   const double G = 6.67384e-11; //задается константа G
   scanf("%lg %lg %lg", &m1, &m2, &r); //ввод данных с клавиатуры
   F = G*m1*m2/r/r; //расчет силы по формуле
   printf("%.5le H\n", F); //вывод результата на экран
   return 0;
}

#include <stdio.h>

#include <cmath>

using namespace std;

int main()

{

double m1, m2, r, F; //объявление переменных

const double G = 6.67384e-11; //задается константа G

scanf("%lg %lg %lg", &m1, &m2, &r); //ввод данных с клавиатуры

F = G*m1*m2/r/r; //расчет силы по формуле

printf("%.5le H\n", F); //вывод результата на экран

return 0;

}

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

Related Images:

e-olymp 1. Простая задача

14/09/2015 by Женя Максимова

Задача. Программа считывает двузначное число и выводит через пробел каждую цифру отдельно.

Тесты

Ввод	10	12	45	99
Вывод	1 0	1 2	4 5	9 9

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

#include <iostream>
using namespace std;
int main() {
  int n = 0; //объявление переменной
  cin >> n; //ввод значения с клавиатуры
  cout << n/10 << " " << n%10 << endl; //вывод двух цифр заданного числа по отдельности
}

#include <iostream>

using namespace std;

int main() {

int n = 0; //объявление переменной

cin >> n; //ввод значения с клавиатуры

cout << n/10 << " " << n%10 << endl; //вывод двух цифр заданного числа по отдельности

}

Алгоритм

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

Решение

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