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

09/12/2015 by Швандт Максим Альбертович

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

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

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

Условие

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

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

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

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

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

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

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

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

Результат

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

Пример

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

Результат

6register vasya 12345

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.TreeMap;
import java.lang.NumberFormatException;

public class Timus2002App
{

   //структура, описывающая атрибуты учетной записи
   public class AccountInfo
   {
      public String password;
      public boolean loggedIn;

      public AccountInfo(String argPassword, boolean argLoggedIn)
      {
         password = argPassword;
         loggedIn = argLoggedIn;
      }
   }

   
   //база данных учетной записи
   public class AccountDatabase
   {
      public static final int OK = 0;
      public static final int NOT_REGISTERED = 1;
      public static final int WRONG_PASSWORD = 2;
      public static final int ALREADY_LOGGED_IN = 3;
      public static final int ALREADY_LOGGED_OUT = 4;

      private TreeMap<String, AccountInfo> map;

      //конструктор
      public AccountDatabase()
      {
         map = new TreeMap<String, AccountInfo>();
      }

      //регистрация новой учетной записи
      public boolean register(String name, String password)
      {
         AccountInfo info = map.get(name);

         if (info != null)
         {
            return false;
         }

         map.put(name, new AccountInfo(password, false));

         return true;
      }

      //вход в систему
      public int login(String name, String password)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if (info != null)
         {
            if (!info.password.equals(password))
            {
               result = WRONG_PASSWORD;
            }
            else if (info.loggedIn)
            {
               result = ALREADY_LOGGED_IN;
            }
            else
            {
               map.put(name, new AccountInfo(info.password, true));
               result = OK;
            }
         }

         return result;
      }

      //выход из системы
      public int logout(String name)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if ( info != null )
         {
            if ( info.loggedIn )
            {
               map.put(name, new AccountInfo(info.password, false));
               result = OK;
            }
            else
            {
               result = ALREADY_LOGGED_OUT;
            }
         }

         return result;
      }

   }

   public static void main(String[] args)
   {
      int loginCount = 0;
      String line = null;
      
      Scanner in = new Scanner(System.in);
      //System.out.println("please enter number of logins: ");
      line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
      try
      {
         loginCount = Integer.parseInt(line.trim());
      }
      catch( NumberFormatException e )
      {
      }
      
      if ( loginCount < 1 || loginCount > 100 )
      {
         System.out.println("**** ERROR: wrong number of logins ****");
         in.close();
         return;
      }
      
      Timus2002App mainObj = new Timus2002App();
      AccountDatabase accounts = mainObj.new AccountDatabase();
      
      for( int i = 0; i < loginCount; i++ )
      {
         //System.out.println("please enter command:");
         
         line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
         if ( line == null || line.isEmpty() )
         {
            System.out.println("**** ERROR: empty input, abort processing ****");
            break;
         }
         
         //превращение введенной строки текста в вектор лексем
         StringTokenizer st = new StringTokenizer(line, " ");
         Vector<String> tokens = new Vector<String>();
         while (st.hasMoreTokens())
         {
            tokens.add( st.nextToken() );
         }

         //превращение вектора лексем в команду с аргументами
         String command   = ( tokens.size() > 0 ) ? tokens.get(0) : null;
         String name      = ( tokens.size() > 1 ) ? tokens.get(1) : null;
         String password  = ( tokens.size() > 2 ) ? tokens.get(2) : null;
         String message = null;
        
        //выполнение команд
         if ( command.equals("register"))
         {
            if ( name != null || password != null )
            {
               if ( accounts.register(name, password) )
               {
                  message = "success: new user added";
               }
               else
               {
                  message = "fail: user already exists";
               }
            }
            else
            {
               message = "fail: missing user name or password";
            }
         }
         else if ( command.equals("login"))
         {
            if ( name != null || password != null )
            {
               switch( accounts.login(name, password) )
               {
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  case AccountDatabase.WRONG_PASSWORD:
                     message = "fail: incorrect password";
                  break;
                  case AccountDatabase.ALREADY_LOGGED_IN:
                     message = "fail: already logged in";
                  break;
                  default:
                     message = "success: user logged in";
                  break;
              }
           }
           else
           {
              message = "fail: missing user name or password";
           }
         }
         else if ( command.equals("logout"))
         {
            if ( name != null )
            {
               switch( accounts.logout(name) )
               {
                  case AccountDatabase.ALREADY_LOGGED_OUT:
                     message = "fail: already logged out";
                  break;
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  default:
                     message = "success: user logged out";
                  break;
               }
            }
            else
            {
               message = "fail: missing user name";
            }
         }
         
         if ( message != null )
         {
            System.out.println(message);
         }
      }
      in.close();
   } 
}

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

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

import java.util.Scanner;

import java.util.StringTokenizer;

import java.util.Vector;

import java.util.TreeMap;

import java.lang.NumberFormatException;

public class Timus2002App

{

//структура, описывающая атрибуты учетной записи

public class AccountInfo

{

public String password;

public boolean loggedIn;

public AccountInfo(String argPassword, boolean argLoggedIn)

{

password = argPassword;

loggedIn = argLoggedIn;

}

//база данных учетной записи

public class AccountDatabase

{

public static final int OK = 0;

public static final int NOT_REGISTERED = 1;

public static final int WRONG_PASSWORD = 2;

public static final int ALREADY_LOGGED_IN = 3;

public static final int ALREADY_LOGGED_OUT = 4;

private TreeMap<String, AccountInfo> map;

//конструктор

public AccountDatabase()

{

map = new TreeMap<String, AccountInfo>();

}

//регистрация новой учетной записи

public boolean register(String name, String password)

{

AccountInfo info = map.get(name);

if (info != null)

{

return false;

}

map.put(name, new AccountInfo(password, false));

return true;

}

//вход в систему

public int login(String name, String password)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if (info != null)

{

if (!info.password.equals(password))

{

result = WRONG_PASSWORD;

}

else if (info.loggedIn)

{

result = ALREADY_LOGGED_IN;

}

else

{

map.put(name, new AccountInfo(info.password, true));

result = OK;

}

return result;

}

//выход из системы

public int logout(String name)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if ( info != null )

{

if ( info.loggedIn )

{

map.put(name, new AccountInfo(info.password, false));

result = OK;

}

else

{

result = ALREADY_LOGGED_OUT;

}

return result;

}

public static void main(String[] args)

{

int loginCount = 0;

String line = null;

Scanner in = new Scanner(System.in);

//System.out.println("please enter number of logins: ");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

try

{

loginCount = Integer.parseInt(line.trim());

}

catch( NumberFormatException e )

{

}

if ( loginCount < 1 || loginCount > 100 )

{

System.out.println("**** ERROR: wrong number of logins ****");

in.close();

return;

}

Timus2002App mainObj = new Timus2002App();

AccountDatabase accounts = mainObj.new AccountDatabase();

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

{

//System.out.println("please enter command:");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

if ( line == null || line.isEmpty() )

{

System.out.println("**** ERROR: empty input, abort processing ****");

break;

}

//превращение введенной строки текста в вектор лексем

StringTokenizer st = new StringTokenizer(line, " ");

Vector<String> tokens = new Vector<String>();

while (st.hasMoreTokens())

{

tokens.add( st.nextToken() );

}

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

String command = ( tokens.size() > 0 ) ? tokens.get(0) : null;

String name = ( tokens.size() > 1 ) ? tokens.get(1) : null;

String password = ( tokens.size() > 2 ) ? tokens.get(2) : null;

String message = null;

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

if ( command.equals("register"))

{

if ( name != null || password != null )

{

if ( accounts.register(name, password) )

{

message = "success: new user added";

}

else

{

message = "fail: user already exists";

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("login"))

{

if ( name != null || password != null )

{

switch( accounts.login(name, password) )

{

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

case AccountDatabase.WRONG_PASSWORD:

message = "fail: incorrect password";

break;

case AccountDatabase.ALREADY_LOGGED_IN:

message = "fail: already logged in";

break;

default:

message = "success: user logged in";

break;

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("logout"))

{

if ( name != null )

{

switch( accounts.logout(name) )

{

case AccountDatabase.ALREADY_LOGGED_OUT:

message = "fail: already logged out";

break;

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

default:

message = "success: user logged out";

break;

}

else

{

message = "fail: missing user name";

}

if ( message != null )

{

System.out.println(message);

}

in.close();

}

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы	Выделено памяти
0.124	1 928 КБ

Ссылка на Ideone: https://ideone.com/3Y2W4z

Related Images:

А1042

01/06/2015 by Швандт Максим Альбертович

Условие:

В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.

Тесты:

Число элементов в заданной последовательности	Заданная последовательность	Найденная подпоследовательность
20	1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48	3 6 9 12 15 18
20	1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40	1 9 17 25
20	155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0	-60 -40 -20 0 20 40 60

Код:

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <deque>

using namespace std;

// вспомогательные типы
typedef vector< double > tValues;
typedef map< double, bool > tSortedValues;
typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)
bool containValues( tValues& where, tValues& what )
{
   if ( what.size() > 0 )
   {
      for( int i = 0; i < where.size(); i++ )
      {
         if ( where[ i ] == what[ 0 ] )
         {
            int k = i + 1;
            int j = 1;
            for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );
            return ( j == what.size() );
         }
      }
   }
   
   return false;
}

// вспомогательная функция печати последовательности
void printSequence( tValues& seq )
{
   if ( seq.size() > 1 )
   {
      double diff = seq[ 1 ] - seq[ 0 ];
      cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";
      for( int i = 0; i < seq.size(); i++ )
      {
        cout << seq[ i ] << " ";
      }
      cout << "}\n";
   }
   else
   {
      cout << "NOT a sequence" << endl;
   }
}

int main(void)
{

   int n;
   cin >> n;
   if ( n <= 0 )
   {
      cout << "Input error: wrong length of the sequence" << endl;
      return 0;
   }   

   tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность
   for( int i = 0; i < n; i++ ) // ввод входных значений
   {
      double val;
      cin >> val;
      sourceValues.push_back( val );
   }

   // нахождение всех возможные разностей между входными значениями
   tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями
   for( int i = 0; i < sourceValues.size(); i++ )
   {
      tSortedValues sortedValues;
      for( int j = 0; j < sourceValues.size(); j++ )
      {
         if ( j != i )
         {
            double diff =
               ( i < j ) ?
                  sourceValues[ j ] - sourceValues[ i ] :
                  sourceValues[ i ] - sourceValues[ j ] ;
            if ( diff > 0 )
            {
               sortedValues[ diff ] = true;
            }
        }
      }
      for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )
      {
        diffValues.push_back( it->first );
      }
   }

   // главный цикл по входным значениям
   tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности
   for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )
   {
      double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности
      // цикл по вектору разности
      for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )
      {
         double diffVal = diffValues[ diffValIdx ];
         double lastVal;
         tValues candidateSeq;
         candidateSeq.push_back( seedVal );

         // поиск последовательности влево от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx - 1; j >= 0; j-- )
         {
            double prevVal = sourceValues[ j ];
            if ( prevVal == lastVal - diffVal )
            {
               candidateSeq.insert( candidateSeq.begin(), prevVal );
               lastVal = prevVal;
            }
         }

         // поиск последовательности вправо от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )
         {
            double nextVal = sourceValues[ j ];
            if ( nextVal == lastVal + diffVal )
            {
               candidateSeq.push_back( nextVal );
               lastVal = nextVal;
            }
         }
         
         if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух
         {
            foundSequences.push_back( candidateSeq );
         }
      }
   }

   // удаляем последовательности, которые включают в себя другие
   //  Удалённые последовательности заменяются на пустышки
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      if ( ! foundSequences[ i ].empty() )
      {
         for( int j = 0; j < foundSequences.size(); j++ )
         {
            if ( i != j
               && foundSequences[ i ].size() >= foundSequences[ j ].size() 
               && containValues( foundSequences[ i ], foundSequences[ j ] ) )
            {
               foundSequences[ j ].clear();
            }
         }
      }
   }

    // удаляем из вектора пустышки из прошлого шага
   {
      tSequences tmp;
      for( int i = 0; i < foundSequences.size(); i++ )
      {
         if ( ! foundSequences[ i ].empty() )
         {
            tmp.push_back( foundSequences[ i ] );
         }
      }
      foundSequences = tmp;
   }
   // ищем максимальную последовательность среди найденных
   int maxSize = -1;
   int maxIndex = -1;
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      int size = foundSequences[ i ].size();
      if ( size > maxSize )
      {
         maxSize  = size;
         maxIndex = i;
      }
     // printSequence( foundSequences[ i ] ); // debug 
   }

   if ( maxIndex >= 0 )
   {
      cout << "max size sequence:\n";
      printSequence( foundSequences[ maxIndex ] ); 
   }

   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

#include <stdio.h>

#include <iostream>

#include <map>

#include <string>

#include <vector>

#include <deque>

using namespace std;

// вспомогательные типы

typedef vector< double > tValues;

typedef map< double, bool > tSortedValues;

typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)

bool containValues( tValues& where, tValues& what )

{

if ( what.size() > 0 )

{

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

{

if ( where[ i ] == what[ 0 ] )

{

int k = i + 1;

int j = 1;

for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );

return ( j == what.size() );

}

return false;

}

// вспомогательная функция печати последовательности

void printSequence( tValues& seq )

{

if ( seq.size() > 1 )

{

double diff = seq[ 1 ] - seq[ 0 ];

cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";

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

{

cout << seq[ i ] << " ";

}

cout << "}\n";

}

else

{

cout << "NOT a sequence" << endl;

}

int main(void)

{

int n;

cin >> n;

if ( n <= 0 )

{

cout << "Input error: wrong length of the sequence" << endl;

return 0;

}

tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность

for( int i = 0; i < n; i++ ) // ввод входных значений

{

double val;

cin >> val;

sourceValues.push_back( val );

}

// нахождение всех возможные разностей между входными значениями

tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями

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

{

tSortedValues sortedValues;

for( int j = 0; j < sourceValues.size(); j++ )

{

if ( j != i )

{

double diff =

( i < j ) ?

sourceValues[ j ] - sourceValues[ i ] :

sourceValues[ i ] - sourceValues[ j ] ;

if ( diff > 0 )

{

sortedValues[ diff ] = true;

}

for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )

{

diffValues.push_back( it->first );

}

// главный цикл по входным значениям

tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности

for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )

{

double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности

// цикл по вектору разности

for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )

{

double diffVal = diffValues[ diffValIdx ];

double lastVal;

tValues candidateSeq;

candidateSeq.push_back( seedVal );

// поиск последовательности влево от исходного значения

lastVal = seedVal;

for( int j = srcValIdx - 1; j >= 0; j-- )

{

double prevVal = sourceValues[ j ];

if ( prevVal == lastVal - diffVal )

{

candidateSeq.insert( candidateSeq.begin(), prevVal );

lastVal = prevVal;

}

// поиск последовательности вправо от исходного значения

lastVal = seedVal;

for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )

{

double nextVal = sourceValues[ j ];

if ( nextVal == lastVal + diffVal )

{

candidateSeq.push_back( nextVal );

lastVal = nextVal;

}

if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух

{

foundSequences.push_back( candidateSeq );

}

// удаляем последовательности, которые включают в себя другие

// Удалённые последовательности заменяются на пустышки

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

{

if ( ! foundSequences[ i ].empty() )

{

for( int j = 0; j < foundSequences.size(); j++ )

{

if ( i != j

&& foundSequences[ i ].size() >= foundSequences[ j ].size()

&& containValues( foundSequences[ i ], foundSequences[ j ] ) )

{

foundSequences[ j ].clear();

}

// удаляем из вектора пустышки из прошлого шага

{

tSequences tmp;

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

{

if ( ! foundSequences[ i ].empty() )

{

tmp.push_back( foundSequences[ i ] );

}

foundSequences = tmp;

}

// ищем максимальную последовательность среди найденных

int maxSize = -1;

int maxIndex = -1;

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

{

int size = foundSequences[ i ].size();

if ( size > maxSize )

{

maxSize = size;

maxIndex = i;

}

// printSequence( foundSequences[ i ] ); // debug

}

if ( maxIndex >= 0 )

{

cout << "max size sequence:\n";

printSequence( foundSequences[ maxIndex ] );

}

return 0;

}

План

План программы:

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

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

Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.

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

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

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

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

Related Images:

А709

24/05/2015 by Швандт Максим Альбертович

Условие:

Дана квадратная матрица [latex]A[/latex], порядка [latex]m[/latex], натуральное число [latex]n[/latex], действительные числа [latex]p_{n},p_{n-1},\ldots,p_{0}[/latex]. Получить матрицу [latex]p_{n}A^{n}+p_{n-1}A^{n-1}+\ldots p_{1}A+p_{0}E[/latex], где [latex]E[/latex]- единичная матрица порядка [latex]m[/latex].

Тесты:

Ввод количества p	Ввод размерности матрицы А и одновременно Е
6	3

Ввод коэффициентов

Матрица А:

1	2	3
3	2	1
2	1	3

Результат:

544308	445319	692718
544281	445354	692710
544277	445315	692753

Код:

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

using namespace std;

// класс, реализующий матрицу
class Matrix
{
   public:

      // конструктор по умолчанию
      Matrix()
      : mNumRows(0)
      , mNumCols(0)
      , mArr(0)
      {
      }

      // конструктор, создающий реальную матрицу ненулевой размерности и заполняет начальным значением
      Matrix( int numRows, int numCols, double initValue )
      : mNumRows( 0 )
      , mNumCols( 0 )
      , mArr( 0 )
      {
         initArr( numRows, numCols, initValue );
      }
      
      // конструктор копии - создающий матрицу как копию матрици-источника
      Matrix( Matrix& source )
      : mNumRows( source.mNumRows )
      , mNumCols( source.mNumCols )
      , mArr( 0 )
      {
         swap( source );
      }

      // деструктор, необходим для удаления выделенного на куче двумерного массива
      ~Matrix()
      {
         resetArr();
      }

      // переопределённый оператор присваивания, необходим для корректного присваивания матриц
      Matrix& operator=( Matrix& rhs )
      {
         swap( rhs );
      }

      // возвращает число строк в матрице
      int getNumRows() { return mNumRows; };

      // возвращает число колонок в матрице
      int getNumCols() { return mNumCols; };

      // возвращает указатель на двумерный массив на куче, содержащий саму матрицу
      double** getArr() { return mArr; };

      // копирует матрицу-источник в себя
      void swap( Matrix& another );

      // создает левую диагональ, заполненную заданным значением
      void setLeftDiag( double value );

      // суммирует другую матрицу с собой
      void sum( Matrix& another );

      // возводит себя в n-ю степень
      void power( int n );

      //выполняет произведение себя и другой матрицы, метод используется в методе power
      void product( Matrix& another );

      // умножает себя на заданное значение
      void multiply( double& value );

      // выводит на консоль содержимое себя, придворенное заголовком
      void show( const char* title );

      // создает заново свой двумерный массив и заполняет заданным значеним, исп. в конструкторе
      void initArr( int numRows, int numCols, double initValue );

      // удаляет двумерный массив из кучи и обнуляет указатель, исп. в деструкторе а также в initArr
      void resetArr();

   private:

      int mNumRows;
      int mNumCols;
      double** mArr;
};

void Matrix::swap( Matrix& another )
{
   initArr( another.mNumRows, another.mNumCols, 0 );
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] = another.mArr[ row ][ col ];
      }
   }
}

void Matrix::setLeftDiag( double value )
{
   int n = min( mNumRows, mNumCols );
   for( int i = 0; i < n; i++ )
   {
      mArr[ i ][ i ] = value;
   }
}

void Matrix::sum( Matrix& another )
{
   int numRows = min( mNumRows, another.getNumRows() );
   int numCols = min( mNumCols, another.getNumCols() );

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] += another.mArr[ row ][ col ];
      }
   }
}

void Matrix::power( int n )
{
   for( int i = 1; i < n; i++ )
   {
      product( *this );
   }
}

void Matrix::product( Matrix& another )
{

   if ( mNumCols != another.mNumRows )
   {
      printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );
      return;
   }

   Matrix result( mNumRows, another.mNumCols, 0 ); 

   for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )
   {
      for( int colResult = 0; colResult < result.mNumCols; colResult++ )
      {
         result.mArr[ rowResult ][ colResult ] = 0;
         for( int col = 0; col < mNumCols; col++ )
         {

            result.mArr[ rowResult ][ colResult ] +=
               ( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );
         }
      }
   }

   swap( result );
} 

void Matrix::multiply( double& value )
{
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] *= value;
      }
   }
}

void Matrix::show( const char* title )
{
   printf("%s:\n", title);

   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         printf("%10.04lf ", mArr[ row ][ col ] );
      }
      printf("\n");
   }
}

void Matrix::initArr( int numRows, int numCols, double initValue )
{
   resetArr();
   mNumRows = numRows;
   mNumCols = numCols;
   mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок
   for( int row = 0; row < mNumRows; row++ )
   {
      mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки
      for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям
      {
         mArr[ row ][ col ] = initValue;
      }
   }
}

void Matrix::resetArr()
{
   if ( mArr!= 0 )
   {
      for( int row = 0; row < mNumRows; row++ )
      {
         delete[] mArr[ row ];
      }
      delete [] mArr;
      mArr = 0;
   }
}

//==============================================================================

// ввыд с консоли какого либо целого числа
static int inputNumber( const char *title )
{
   int n = 0;

   printf("input %s:\n", title);

   if ( scanf("%d", &n ) <= 0 )
   {
      printf("error input of %s\n",title);
   }
   else
   if ( n <= 0 )
   {
      printf("wrong %s value, must be positive\n", title);
   }

   return n;
}

// ввод с консоли содержимого какой либо матрицы
static bool inputMatrixData( const char *title, Matrix& x )
{
   printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );

   for( int row = 0; row < x.getNumRows(); row++ )
   {
      for( int col = 0; col < x.getNumCols(); col++ )
      {
         double val = 0;
         if ( scanf("%lf", &val ) <= 0 )
         {
            printf("error input of %s\n",title);
            return false;
         }
         x.getArr()[ row ][ col ] = val;

      }
   }
   return true;
}

//==============================================================================

int main()
{
   int numIter = inputNumber( "Number of iterations 'n'" );
   int sizeA   = inputNumber( "matrix size 'm'" );

   if ( numIter <= 0 || sizeA <= 0 )
   {
      return 0;
   }

   Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n
   if ( ! inputMatrixData( "P matrix values", mxP ) )
   {
      return 0;
   }

   Matrix mxA( sizeA, sizeA, 0 );
   if ( ! inputMatrixData( "A matrix values", mxA ) )
   {
      return 0;
   }

   Matrix mxE( sizeA, sizeA, 0 );
   mxE.setLeftDiag( 1 );

   // печатаем исходные данные перед вычислением
   mxE.show("============= matrix E ==============");
   mxP.show("============= matrix P ==============");
   mxA.show("============= matrix A ==============");

   Matrix s; // это будет общая сумма полинома

   s.swap( mxE );

   s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования

   // главный цикл суммирования полинома
   for( int i = 1; i < numIter; i++ )
   {
    
      Matrix x;  // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)
      x.swap( mxA ); // копируем содержимое матрицы A

      x.power( i );  // возводим x в степень i, т.е. pow(A,i)

      x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)

      s.sum( x ); // накапливаем сумму полинома

   }

   s.show("============= result: ==============");// печатаем результат вычисления полинома
   
   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

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

#include <iostream>

#include <stdint.h>

#include <stdio.h>

using namespace std;

// класс, реализующий матрицу

class Matrix

{

public:

// конструктор по умолчанию

Matrix()

: mNumRows(0)

, mNumCols(0)

, mArr(0)

{

}

// конструктор, создающий реальную матрицу ненулевой размерности и заполняет начальным значением

Matrix( int numRows, int numCols, double initValue )

: mNumRows( 0 )

, mNumCols( 0 )

, mArr( 0 )

{

initArr( numRows, numCols, initValue );

}

// конструктор копии - создающий матрицу как копию матрици-источника

Matrix( Matrix& source )

: mNumRows( source.mNumRows )

, mNumCols( source.mNumCols )

, mArr( 0 )

{

swap( source );

}

// деструктор, необходим для удаления выделенного на куче двумерного массива

~Matrix()

{

resetArr();

}

// переопределённый оператор присваивания, необходим для корректного присваивания матриц

Matrix& operator=( Matrix& rhs )

{

swap( rhs );

}

// возвращает число строк в матрице

int getNumRows() { return mNumRows; };

// возвращает число колонок в матрице

int getNumCols() { return mNumCols; };

// возвращает указатель на двумерный массив на куче, содержащий саму матрицу

double** getArr() { return mArr; };

// копирует матрицу-источник в себя

void swap( Matrix& another );

// создает левую диагональ, заполненную заданным значением

void setLeftDiag( double value );

// суммирует другую матрицу с собой

void sum( Matrix& another );

// возводит себя в n-ю степень

void power( int n );

//выполняет произведение себя и другой матрицы, метод используется в методе power

void product( Matrix& another );

// умножает себя на заданное значение

void multiply( double& value );

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

void show( const char* title );

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

void initArr( int numRows, int numCols, double initValue );

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

void resetArr();

private:

int mNumRows;

int mNumCols;

double** mArr;

};

void Matrix::swap( Matrix& another )

{

initArr( another.mNumRows, another.mNumCols, 0 );

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] = another.mArr[ row ][ col ];

}

void Matrix::setLeftDiag( double value )

{

int n = min( mNumRows, mNumCols );

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

{

mArr[ i ][ i ] = value;

}

void Matrix::sum( Matrix& another )

{

int numRows = min( mNumRows, another.getNumRows() );

int numCols = min( mNumCols, another.getNumCols() );

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] += another.mArr[ row ][ col ];

}

void Matrix::power( int n )

{

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

{

product( *this );

}

void Matrix::product( Matrix& another )

{

if ( mNumCols != another.mNumRows )

{

printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );

return;

}

Matrix result( mNumRows, another.mNumCols, 0 );

for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )

{

for( int colResult = 0; colResult < result.mNumCols; colResult++ )

{

result.mArr[ rowResult ][ colResult ] = 0;

for( int col = 0; col < mNumCols; col++ )

{

result.mArr[ rowResult ][ colResult ] +=

( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );

}

swap( result );

}

void Matrix::multiply( double& value )

{

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

mArr[ row ][ col ] *= value;

}

void Matrix::show( const char* title )

{

printf("%s:\n", title);

for( int row = 0; row < mNumRows; row++ )

{

for( int col = 0; col < mNumCols; col++ )

{

printf("%10.04lf ", mArr[ row ][ col ] );

}

printf("\n");

}

void Matrix::initArr( int numRows, int numCols, double initValue )

{

resetArr();

mNumRows = numRows;

mNumCols = numCols;

mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок

for( int row = 0; row < mNumRows; row++ )

{

mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки

for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям

{

mArr[ row ][ col ] = initValue;

}

void Matrix::resetArr()

{

if ( mArr!= 0 )

{

for( int row = 0; row < mNumRows; row++ )

{

delete[] mArr[ row ];

}

delete [] mArr;

mArr = 0;

}

//==============================================================================

// ввыд с консоли какого либо целого числа

static int inputNumber( const char *title )

{

int n = 0;

printf("input %s:\n", title);

if ( scanf("%d", &n ) <= 0 )

{

printf("error input of %s\n",title);

}

else

if ( n <= 0 )

{

printf("wrong %s value, must be positive\n", title);

}

return n;

}

// ввод с консоли содержимого какой либо матрицы

static bool inputMatrixData( const char *title, Matrix& x )

{

printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );

for( int row = 0; row < x.getNumRows(); row++ )

{

for( int col = 0; col < x.getNumCols(); col++ )

{

double val = 0;

if ( scanf("%lf", &val ) <= 0 )

{

printf("error input of %s\n",title);

return false;

}

x.getArr()[ row ][ col ] = val;

}

return true;

}

//==============================================================================

int main()

{

int numIter = inputNumber( "Number of iterations 'n'" );

int sizeA = inputNumber( "matrix size 'm'" );

if ( numIter <= 0 || sizeA <= 0 )

{

return 0;

}

Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n

if ( ! inputMatrixData( "P matrix values", mxP ) )

{

return 0;

}

Matrix mxA( sizeA, sizeA, 0 );

if ( ! inputMatrixData( "A matrix values", mxA ) )

{

return 0;

}

Matrix mxE( sizeA, sizeA, 0 );

mxE.setLeftDiag( 1 );

// печатаем исходные данные перед вычислением

mxE.show("============= matrix E ==============");

mxP.show("============= matrix P ==============");

mxA.show("============= matrix A ==============");

Matrix s; // это будет общая сумма полинома

s.swap( mxE );

s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования

// главный цикл суммирования полинома

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

{

Matrix x; // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)

x.swap( mxA ); // копируем содержимое матрицы A

x.power( i ); // возводим x в степень i, т.е. pow(A,i)

x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)

s.sum( x ); // накапливаем сумму полинома

}

s.show("============= result: ==============");// печатаем результат вычисления полинома

return 0;

}

Программа базируется на классе Matrix. Этот класс необходим для представления алгоритма вычисления полинома в естественной математической форме. Класс реализует следующие операции:

Создание матрицы заданного размера заполненной заданным числом
Умножение матрицы на число
Сложение матриц
Произведение матриц
Возведение матрицы в степень
Вывод содержимого матрицы на консоль

Класс Matrix содержит 3 члена – число строк, колонок и двумерный массив, который создается на куче. Главный модуль содержит две вспомогательный функции для ввода данных.

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

Ввод данных: число итераций, размерности матрицы , списка коэфф. P и самой матрицы А
Создание единичной матрицы Е и далее – начального значения суммы E*P_0
Вывод исходных данных: E, A и P
Цикл суммирования, где вычисляется i-й элемент суммы
Вывод результата

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

Related Images:

e-olimp 4847. Очередь с приоритетами

07/04/2015 by Швандт Максим Альбертович

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции:

Добавление элемента в очередь.
Удаление из очереди элемента с наибольшим приоритетом.
Изменение приоритета для произвольного элемента, находящегося в очереди.

Тесты:

input data	output data
add eight 8	<вывод не предусмотрен>
add three 3	<вывод не предусмотрен>
add eleven 11	<вывод не предусмотрен>
add one 1	<вывод не предусмотрен>
add five 5	<вывод не предусмотрен>
add neun 9	<вывод не предусмотрен>
add forteen 14	<вывод не предусмотрен>
add six 6	<вывод не предусмотрен>
add ten 10	<вывод не предусмотрен>
add twelve 12	<вывод не предусмотрен>
add fifteen 15	<вывод не предусмотрен>
add seven 7	<вывод не предусмотрен>
add thirteen 13	<вывод не предусмотрен>
change eleven 1100	<вывод не предусмотрен>
change eleven 1101	<вывод не предусмотрен>
change one 111	<вывод не предусмотрен>
pop	eleven 1101
pop	one 111
pop	fifteen 15
pop	forteen 14
pop	thirteen 13
pop	twelve 12
pop	ten 10
pop	neun 9
pop	eight 8
pop	seven 7
pop	six 6
pop	five 5
pop	three 3
pop	error

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

#include <iostream>

using namespace std;

// шаблонный класс, описывающий узел списка

template <typename KeyType>
class ListNode
{
public:
	ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };
	KeyType& getKey() { return mKey; };
	ListNode* getNext() { return mNext; };
	void setNext( ListNode* node ) { mNext = node; };
protected:
	KeyType mKey;
	ListNode *mNext;
};

// шаблонный класс, описывающий список
template <typename KeyType, typename ListNodeType>
class List
{
public:
	List() { mHead = NULL; };
	virtual ~List() { clear(); };
	void clear();
	bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );
	bool remove( KeyType& key );
	void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };
	bool pop( KeyType& key );
	ListNodeType* getHead() { return mHead; };
	bool isEmpty() { return mHead == NULL; };
protected:
	ListNodeType* mHead;
};

// очищает все элементы списка и высвобождает память
template <typename KeyType, typename ListNodeType>
void List<KeyType,ListNodeType>::clear()
{
	ListNodeType *n =  mHead;
	while( NULL != n )
	{
	   ListNodeType *prev = n;
	   n = n->getNext();
	   delete prev;
	}
	mHead = NULL;
};

// находит узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )
{
	ListNodeType *n =  mHead;
	ListNodeType *prev = NULL;
	while( NULL != n )
	{
	   if ( n->getKey() == key )
	   {
	      foundNode = n;
	      foundPrevNode = prev;
	      return true;
	   }
	   prev = n;
	   n = n->getNext();
	}
	return false;
}

// удаляет узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::remove( KeyType& key )
{
	ListNodeType *n = NULL;
	ListNodeType *prev = NULL;

	if ( find( key, n, prev ) )
	{
	   if ( NULL != prev )
	   {
	      prev->setNext( n->getNext() );
	   }
	   else
	   {
	      mHead = n->getNext();
	   }
	   delete n;
	   return true;
	}
	return false;
};

// удаляет первый элемент
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::pop( KeyType& key )
{
	if ( mHead != NULL )
	{
	   key = mHead->getKey();
	   ListNodeType* n = mHead;
	   mHead = n->getNext();
	   delete n;
	   return true;
	}
	return false;
};

// Шаблонный класс, описывающий узел дерева двоичного поиска

template <typename KeyType, typename ValueType>
class TreeNode {
public:
	TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};
	TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};
	~TreeNode() { };
	void setLeft( TreeNode* left ) { mLeft = left; };
	void setRight( TreeNode* right ) { mRight = right; };
	void setParent( TreeNode* parent ) { mParent = parent; };
	KeyType getKey() { return mKey; };
	ValueType& getValue() { return mValue; };
	void setValue( ValueType& value ) { mValue = value; };
	TreeNode* getLeft() { return mLeft; };
	TreeNode* getRight() { return mRight; };
	TreeNode* getParent() { return mParent; };
	virtual string getValueAsText() { return ""; };
protected:
	KeyType mKey;
	ValueType mValue;
	TreeNode* mParent;
	TreeNode* mLeft;
	TreeNode* mRight;
};

// шаблонный класс, описывающий дерево
template <typename KeyType, typename NodeType>
class Tree {
	NodeType* mRoot;
public:
	Tree() { mRoot = NULL; };
	~Tree() { clear(); };
	void clear() { dispose( mRoot ); mRoot = NULL; };
	bool isEmpty() { return mRoot == NULL; };
	NodeType* getRoot() { return mRoot; };
	NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );
	void exclude( NodeType* node );
	void remove( NodeType* node ) { exclude( node ); dispose( node ); };
	bool remove( KeyType& key, NodeType* removedNodeCopy );
	bool remove( KeyType& key ) { return( key, NULL ); };
	NodeType* findMax( NodeType* node );
	NodeType* findMax() { return findMax( mRoot ); };
protected:
	void dispose( NodeType* node );
};

// находит узел двоичного дерева по ключу или всталяет, если не найдено
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )
{
	enum EInsertAction
	{
	   eNONE,
	   eROOT,
	   eLEFT,
	   eRIGHT
	};

	EInsertAction doInsert = eNONE;
	NodeType *p = mRoot;

	if ( p != NULL )
	{
	   for(;;)
	   {
	      if ( key < p->getKey() )
	      {
	         if ( p->getLeft() != NULL )
	         {
	            p = p->getLeft();
	         }
	         else
	         {
	            doInsert = eLEFT;
	            break;
	         }
	      }
	      else
	      if ( key > p->getKey() )
	      {
	         if ( p->getRight() != NULL )
	         {
	            p = p->getRight();
	         }
	         else
	         {
	            doInsert = eRIGHT;
	            break;
	         }
	      }
	      else
	      {
	         return p;
	      }
	   }
	}
	else
	{
	   doInsert = eROOT;
	}

	if ( doInsert != eNONE && insertIfAbsent )
	{
	   NodeType* q = new NodeType( key );
	   switch( doInsert )
	   {
	      case eLEFT : p->setLeft( q ); break;
	      case eRIGHT: p->setRight( q ); break;
	      case eROOT : mRoot = q; break;
	      default: break;
	   }
	   q->setParent( p );
	   return q;
	}

	return NULL;
}

// находит узел двоичного дерева с максимальным значением ключа
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )
{
	if ( node != NULL )
	{
	   NodeType* n = node;
	   while( NULL != n->getRight() )
	   {
	      n = n->getRight();
	   }
	   return n;
	}
	return NULL;
}

// исключает узел двоичного дерева из дерева, не удаляя
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::exclude( NodeType* node )
{
	if ( NULL != node )
	{
	   NodeType* successor = NULL;

	   if ( node->getLeft() == NULL )
	   {
	      successor = node->getRight();
	   }
	   else
	   if ( node->getRight() == NULL )
	   {
	      successor = node->getLeft();
	   }
	   else
	   {
	      successor = node->getRight();
	      NodeType* left = successor->getLeft();

	      while( left != NULL )
	      {
	         successor = left;
	         left = successor->getLeft();
	      }

	      if ( successor->getParent() != node )
	      {
	     	NodeType* right = successor->getRight();
	         successor->getParent()->setLeft( right );
	         if ( NULL != right)
	         {
	         	successor->getRight()->setParent( successor->getParent() );
	         }
	         successor->setRight( node->getRight() );
	         node->getRight()->setParent( successor );
	      }

	      successor->setLeft( node->getLeft() );
	      node->getLeft()->setParent( successor );
	   }
	   
	   if ( node->getParent() == NULL )
	   {
	      mRoot = successor;
	   }
	   else
	   if ( node->getParent()->getLeft() == node )
	   {
	      node->getParent()->setLeft( successor );
	   }
	   else
	   if ( node->getParent()->getRight() == node )
	   {
	      node->getParent()->setRight( successor );
	   }
	   else
	   {
	      cout << "fatal error: orphaned# " 
	         << "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()
	         << endl;
	      return;
	   }
	   
	   if ( NULL != successor )
	   {
	      successor->setParent( node->getParent() );
	   }
	   
	   node->setParent( NULL );
	   node->setLeft( NULL );
	   node->setRight( NULL );
	}
}

// находит и удаляет узел дерева по ключу
template <typename KeyType, typename NodeType>
bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )
{
	NodeType* node = findOrInsert( key, false );
	if ( node != NULL )
	{
	   exclude( node );
	   if ( removedNodeCopy != NULL )
	   {
	      *removedNodeCopy = node;
	   }
	   dispose( node );
	   return true;
	}
	return false;
}

// удаляет узел из памяти
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::dispose( NodeType* node )
{
	if ( node != NULL ) 
	{
	    dispose( node->getLeft() );
	    dispose( node->getRight() );
	    delete node;
	}
}

// класы-контейнеры на основе высше описанных шаблонных классов

class PrioTreeNode;
typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;
class IdTreeNode : public IdTreeNodeBase
{
public:
	IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};
	virtual ~IdTreeNode() { mValue = NULL; };
	IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };
	IdTreeNode* getRight() { return (IdTreeNode*)mRight; };
	IdTreeNode* getParent() { return (IdTreeNode*)mParent; };
};
typedef Tree<string,IdTreeNode> IdTree;

typedef ListNode<IdTreeNode*> IdListNode;
typedef List<IdTreeNode*,IdListNode> IdList;

typedef TreeNode<int,IdList*> PrioTreeNodeBase;
class PrioTreeNode : public PrioTreeNodeBase
{
public:
	PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };
	virtual ~PrioTreeNode() { delete mValue; };
	PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };
	PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };
	PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };
};
typedef Tree<int,PrioTreeNode> PrioTree;

// класс, реализующий очередь с приоритетами

class PrioQueue
{

public:

	PrioQueue() { }
	~PrioQueue() { }

	bool add( string& id, int prio  );
	bool pop( string& id, int& prio );
	bool change( string& id, int prio );
	void clear();

private:

	IdTree mIdTree;
	PrioTree mPrioTree;

};

bool PrioQueue::add( string& id, int prio  )
{
	IdTreeNode *idNode = mIdTree.findOrInsert( id, true );
	if ( NULL != idNode )
	{
	   PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );
	   if ( NULL != prioNode )
	   {
	      prioNode->getValue()->push( idNode );
	      idNode->setValue( prioNode );
	      return true;
	   }
	}
	return false;
}

bool PrioQueue::pop( string& id, int& prio )
{
	bool result = false;
	PrioTreeNode* prioNode = mPrioTree.findMax();
	if ( NULL != prioNode )
	{
	   prio = prioNode->getKey();
	   if ( ! prioNode->getValue()->isEmpty() )
	   {
	      IdTreeNode* idNode;
	      if ( prioNode->getValue()->pop( idNode ) )
	      {
	         id = idNode->getKey();
	         mIdTree.remove( idNode );
	         if ( prioNode->getValue()->isEmpty() )
	         {
	            mPrioTree.remove( prioNode );
	         }
	         result = true;
	      }
	   }
	}
	return result;
}

bool PrioQueue::change( string& id, int prio )
{
	bool result = false;
	IdTreeNode* idNode = mIdTree.findOrInsert( id, false );
	if ( NULL != idNode )
	{
	   PrioTreeNode* oldPrioNode = idNode->getValue();
	   (void)oldPrioNode->getValue()->remove( idNode );
	   if ( oldPrioNode->getValue()->isEmpty() )
	   {
	      mPrioTree.remove( oldPrioNode );
	   }
	   PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );
	   idNode->setValue( newPrioNode );
	   newPrioNode->getValue()->push( idNode );
	   result = true;
	}
	return result;
}

void PrioQueue::clear()
{
	mIdTree.clear();
	mPrioTree.clear();
}

int main( int argc, char** argv )
{
	PrioQueue q;

	string command;
	string id;
	int prio;

	while ( cin >> command )
	{
	   if ( command.compare( 0, 1, "#" ) == 0 ) continue;
	   else
	   if ( command == "add" || command == "ADD" )
	   {
	      cin >> id;
	      cin >> prio;

	      q.add( id, prio );
	   }
	   else
	   if ( command == "change" || command == "CHANGE" )
	   {
	      cin >> id;
	      cin >> prio;

	      q.change( id, prio );
	   }
	   else
	   if ( command == "pop" || command == "POP" )
	   {
	      if ( q.pop( id, prio ) )
	      {
	         cout << id << " " << prio << endl;
	      }
	      else
	      {
	         cout << "error" << endl;
	      }
	   }
	   else
	   if ( command == "clear" || command == "CLEAR" )
	   {
	      q.clear();
	   }
	   else
	   if ( command == "exit" || command == "EXIT" )
	   {
	      cout << "bye" << endl;
	      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

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

#include <iostream>

using namespace std;

// шаблонный класс, описывающий узел списка

template <typename KeyType>

class ListNode

{

public:

ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };

KeyType& getKey() { return mKey; };

ListNode* getNext() { return mNext; };

void setNext( ListNode* node ) { mNext = node; };

protected:

KeyType mKey;

ListNode *mNext;

};

// шаблонный класс, описывающий список

template <typename KeyType, typename ListNodeType>

class List

{

public:

List() { mHead = NULL; };

virtual ~List() { clear(); };

void clear();

bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );

bool remove( KeyType& key );

void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };

bool pop( KeyType& key );

ListNodeType* getHead() { return mHead; };

bool isEmpty() { return mHead == NULL; };

protected:

ListNodeType* mHead;

};

// очищает все элементы списка и высвобождает память

template <typename KeyType, typename ListNodeType>

void List<KeyType,ListNodeType>::clear()

{

ListNodeType *n = mHead;

while( NULL != n )

{

ListNodeType *prev = n;

n = n->getNext();

delete prev;

}

mHead = NULL;

};

// находит узел списка по ключу

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )

{

ListNodeType *n = mHead;

ListNodeType *prev = NULL;

while( NULL != n )

{

if ( n->getKey() == key )

{

foundNode = n;

foundPrevNode = prev;

return true;

}

prev = n;

n = n->getNext();

}

return false;

}

// удаляет узел списка по ключу

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::remove( KeyType& key )

{

ListNodeType *n = NULL;

ListNodeType *prev = NULL;

if ( find( key, n, prev ) )

{

if ( NULL != prev )

{

prev->setNext( n->getNext() );

}

else

{

mHead = n->getNext();

}

delete n;

return true;

}

return false;

};

// удаляет первый элемент

template <typename KeyType, typename ListNodeType>

bool List<KeyType,ListNodeType>::pop( KeyType& key )

{

if ( mHead != NULL )

{

key = mHead->getKey();

ListNodeType* n = mHead;

mHead = n->getNext();

delete n;

return true;

}

return false;

};

// Шаблонный класс, описывающий узел дерева двоичного поиска

template <typename KeyType, typename ValueType>

class TreeNode {

public:

TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};

TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};

~TreeNode() { };

void setLeft( TreeNode* left ) { mLeft = left; };

void setRight( TreeNode* right ) { mRight = right; };

void setParent( TreeNode* parent ) { mParent = parent; };

KeyType getKey() { return mKey; };

ValueType& getValue() { return mValue; };

void setValue( ValueType& value ) { mValue = value; };

TreeNode* getLeft() { return mLeft; };

TreeNode* getRight() { return mRight; };

TreeNode* getParent() { return mParent; };

virtual string getValueAsText() { return ""; };

protected:

KeyType mKey;

ValueType mValue;

TreeNode* mParent;

TreeNode* mLeft;

TreeNode* mRight;

};

// шаблонный класс, описывающий дерево

template <typename KeyType, typename NodeType>

class Tree {

NodeType* mRoot;

public:

Tree() { mRoot = NULL; };

~Tree() { clear(); };

void clear() { dispose( mRoot ); mRoot = NULL; };

bool isEmpty() { return mRoot == NULL; };

NodeType* getRoot() { return mRoot; };

NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );

void exclude( NodeType* node );

void remove( NodeType* node ) { exclude( node ); dispose( node ); };

bool remove( KeyType& key, NodeType* removedNodeCopy );

bool remove( KeyType& key ) { return( key, NULL ); };

NodeType* findMax( NodeType* node );

NodeType* findMax() { return findMax( mRoot ); };

protected:

void dispose( NodeType* node );

};

// находит узел двоичного дерева по ключу или всталяет, если не найдено

template <typename KeyType, typename NodeType>

NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )

{

enum EInsertAction

{

eNONE,

eROOT,

eLEFT,

eRIGHT

};

EInsertAction doInsert = eNONE;

NodeType *p = mRoot;

if ( p != NULL )

{

for(;;)

{

if ( key < p->getKey() )

{

if ( p->getLeft() != NULL )

{

p = p->getLeft();

}

else

{

doInsert = eLEFT;

break;

}

else

if ( key > p->getKey() )

{

if ( p->getRight() != NULL )

{

p = p->getRight();

}

else

{

doInsert = eRIGHT;

break;

}

else

{

return p;

}

else

{

doInsert = eROOT;

}

if ( doInsert != eNONE && insertIfAbsent )

{

NodeType* q = new NodeType( key );

switch( doInsert )

{

case eLEFT : p->setLeft( q ); break;

case eRIGHT: p->setRight( q ); break;

case eROOT : mRoot = q; break;

default: break;

}

q->setParent( p );

return q;

}

return NULL;

}

// находит узел двоичного дерева с максимальным значением ключа

template <typename KeyType, typename NodeType>

NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )

{

if ( node != NULL )

{

NodeType* n = node;

while( NULL != n->getRight() )

{

n = n->getRight();

}

return n;

}

return NULL;

}

// исключает узел двоичного дерева из дерева, не удаляя

template <typename KeyType, typename NodeType>

void Tree<KeyType,NodeType>::exclude( NodeType* node )

{

if ( NULL != node )

{

NodeType* successor = NULL;

if ( node->getLeft() == NULL )

{

successor = node->getRight();

}

else

if ( node->getRight() == NULL )

{

successor = node->getLeft();

}

else

{

successor = node->getRight();

NodeType* left = successor->getLeft();

while( left != NULL )

{

successor = left;

left = successor->getLeft();

}

if ( successor->getParent() != node )

{

NodeType* right = successor->getRight();

successor->getParent()->setLeft( right );

if ( NULL != right)

{

successor->getRight()->setParent( successor->getParent() );

}

successor->setRight( node->getRight() );

node->getRight()->setParent( successor );

}

successor->setLeft( node->getLeft() );

node->getLeft()->setParent( successor );

}

if ( node->getParent() == NULL )

{

mRoot = successor;

}

else

if ( node->getParent()->getLeft() == node )

{

node->getParent()->setLeft( successor );

}

else

if ( node->getParent()->getRight() == node )

{

node->getParent()->setRight( successor );

}

else

{

cout << "fatal error: orphaned# "

<< "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()

<< endl;

return;

}

if ( NULL != successor )

{

successor->setParent( node->getParent() );

}

node->setParent( NULL );

node->setLeft( NULL );

node->setRight( NULL );

}

// находит и удаляет узел дерева по ключу

template <typename KeyType, typename NodeType>

bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )

{

NodeType* node = findOrInsert( key, false );

if ( node != NULL )

{

exclude( node );

if ( removedNodeCopy != NULL )

{

*removedNodeCopy = node;

}

dispose( node );

return true;

}

return false;

}

// удаляет узел из памяти

template <typename KeyType, typename NodeType>

void Tree<KeyType,NodeType>::dispose( NodeType* node )

{

if ( node != NULL )

{

dispose( node->getLeft() );

dispose( node->getRight() );

delete node;

}

// класы-контейнеры на основе высше описанных шаблонных классов

class PrioTreeNode;

typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;

class IdTreeNode : public IdTreeNodeBase

{

public:

IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};

virtual ~IdTreeNode() { mValue = NULL; };

IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };

IdTreeNode* getRight() { return (IdTreeNode*)mRight; };

IdTreeNode* getParent() { return (IdTreeNode*)mParent; };

};

typedef Tree<string,IdTreeNode> IdTree;

typedef ListNode<IdTreeNode*> IdListNode;

typedef List<IdTreeNode*,IdListNode> IdList;

typedef TreeNode<int,IdList*> PrioTreeNodeBase;

class PrioTreeNode : public PrioTreeNodeBase

{

public:

PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };

virtual ~PrioTreeNode() { delete mValue; };

PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };

PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };

PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };

};

typedef Tree<int,PrioTreeNode> PrioTree;

// класс, реализующий очередь с приоритетами

class PrioQueue

{

public:

PrioQueue() { }

~PrioQueue() { }

bool add( string& id, int prio );

bool pop( string& id, int& prio );

bool change( string& id, int prio );

void clear();

private:

IdTree mIdTree;

PrioTree mPrioTree;

};

bool PrioQueue::add( string& id, int prio )

{

IdTreeNode *idNode = mIdTree.findOrInsert( id, true );

if ( NULL != idNode )

{

PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );

if ( NULL != prioNode )

{

prioNode->getValue()->push( idNode );

idNode->setValue( prioNode );

return true;

}

return false;

}

bool PrioQueue::pop( string& id, int& prio )

{

bool result = false;

PrioTreeNode* prioNode = mPrioTree.findMax();

if ( NULL != prioNode )

{

prio = prioNode->getKey();

if ( ! prioNode->getValue()->isEmpty() )

{

IdTreeNode* idNode;

if ( prioNode->getValue()->pop( idNode ) )

{

id = idNode->getKey();

mIdTree.remove( idNode );

if ( prioNode->getValue()->isEmpty() )

{

mPrioTree.remove( prioNode );

}

result = true;

}

return result;

}

bool PrioQueue::change( string& id, int prio )

{

bool result = false;

IdTreeNode* idNode = mIdTree.findOrInsert( id, false );

if ( NULL != idNode )

{

PrioTreeNode* oldPrioNode = idNode->getValue();

(void)oldPrioNode->getValue()->remove( idNode );

if ( oldPrioNode->getValue()->isEmpty() )

{

mPrioTree.remove( oldPrioNode );

}

PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );

idNode->setValue( newPrioNode );

newPrioNode->getValue()->push( idNode );

result = true;

}

return result;

}

void PrioQueue::clear()

{

mIdTree.clear();

mPrioTree.clear();

}

int main( int argc, char** argv )

{

PrioQueue q;

string command;

string id;

int prio;

while ( cin >> command )

{

if ( command.compare( 0, 1, "#" ) == 0 ) continue;

else

if ( command == "add" || command == "ADD" )

{

cin >> id;

cin >> prio;

q.add( id, prio );

}

else

if ( command == "change" || command == "CHANGE" )

{

cin >> id;

cin >> prio;

q.change( id, prio );

}

else

if ( command == "pop" || command == "POP" )

{

if ( q.pop( id, prio ) )

{

cout << id << " " << prio << endl;

}

else

{

cout << "error" << endl;

}

else

if ( command == "clear" || command == "CLEAR" )

{

q.clear();

}

else

if ( command == "exit" || command == "EXIT" )

{

cout << "bye" << endl;

return 0;

}

return 0;

}

Компилировать под Gnu C++ 4.7.1

План программы:

При решении задачи учитывалась необходимость быстрого поиска по двум независимым параметрам — ид и приоритета.

Задача решалась в два этапа, сначала был написан вариант с упорядоченным списком, который позволял мгновенный pop, но add и change не удовлетворили тестам на скорость т.к. основывались на поиску путем перебора. Было приято решение использовать алгоритм поиска в двоичном дереве, учитывая, что условия задачи позволяли большой объем памяти.

Текущий вариант основывается шаблонном классе, реализующем двоичное дерево. Очередь содержит два объекта – дерево со строковыми ключами для хранения Id и дерево с числовыми ключами для хранения приоритетов. Каждый узел дерева Id указывает на узел дерева приоритетов. Это позволяет немедленно получить приоритет данного Id без поиска, что необходимо для операции change. В свою очередь, каждый узел дерева приоритетов указывает на узлы дерева Id с данным приоритетом. Это позволяет немедленно определить какой Id надо удалять при выполнении pop. Для обслуживания нескольких Id с равным приоритетом пришлось ввести еще один шаблонный класс – список.

Краткое описание операций

Add
1. Находим или добавляем узел дерева Id (ситуацию если он есть игнорируем по условию задачи)
2. Находим или добавляем узел дерева приоритетов
3. Для узла дерева Id устанавливаем указатель на узел дерева приоритетов
4. Для узла дерева приоритетов добавляем в его список узел дерева Id

Pop
1. Находим узел дерева приоритетов с максимальным ключом
2. Удаляем из списка найденного узла первый попавшийся указатель на узел дерева Id, если список
3. Если список уже пуст, удаляем узел дерева приоритетов

Change
1. Находим узел дерева Id (ситуацию если его нет игнорируем по условию задачи)
2. Берем узел дерева приоритетов, на который указывает узел Id и удаляем из его списка этот узел Id (т.к. приоритет уже будет новый), если список оказался пуст, удаляем также узел приоритета
3. Находим или добавляем узел дерева приоритетов с новым приоритетом и устанавливаем связь с узлом Id как в случае добавления.

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

Related Images:

АА20

20/03/2015 by Швандт Максим Альбертович

Условие: В заданной строке удалить последнюю пару символов «:=», которая найдется в строке.

Тесты:

Ввод	Вывод
sdfsd fdg :=sdrgs := :+:=:= sdf FUHIUh := sdfdf	sdfsd fdg :=sdrgs := :+:=:= sdf FUHIUh sdfdf
фыпва :+вап:=аоап:=вр := в	фыпва :+вап:=аоап:=вр в

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

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string text; // входная строка
  string subStr ( ":=" ); // искомая подстрока
  
  getline ( cin, text ); // считывание входной строки

  size_t pos = text.rfind( subStr ); // нахождение последней позиции искомой подстроки
  
  if ( pos != string::npos )
  {
      text.replace ( pos, subStr.length(), "" ); // замена подстроки
  }
  
  cout << text << '\n'; // вывод результата

  return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

string text; // входная строка

string subStr ( ":=" ); // искомая подстрока

getline ( cin, text ); // считывание входной строки

size_t pos = text.rfind( subStr ); // нахождение последней позиции искомой подстроки

if ( pos != string::npos )

{

text.replace ( pos, subStr.length(), "" ); // замена подстроки

}

cout << text << '\n'; // вывод результата

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class SeqApp
{ 
   public static void main( String[] args )
   { 
      String subStr = ":=" ; // искомая подстрока
      
      // считывание входной строки
      Scanner in = new Scanner(System.in); 
      // входная строка
      String text = in.nextLine();     
      in.close();
      
      int pos  = text.lastIndexOf( subStr ); // нахождение последней позиции искомой подстроки

      if ( pos >= 0 ) // меняем текст только если нашли подстроку
      {
         String left = "";
         if ( pos > 0 ) // выделяем левую чать до найденной подстроки, может быть пустой 
         {
            left = text.substring( 0, pos );
         }
         String right = text.substring( pos + subStr.length() ); // выделяемм правую чать после подстроки
         text = left + right; // результирующий текст
      }

      // вывод результата
      System.out.println( text );
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class SeqApp

{

public static void main( String[] args )

{

String subStr = ":=" ; // искомая подстрока

// считывание входной строки

Scanner in = new Scanner(System.in);

// входная строка

String text = in.nextLine();

in.close();

int pos = text.lastIndexOf( subStr ); // нахождение последней позиции искомой подстроки

if ( pos >= 0 ) // меняем текст только если нашли подстроку

{

String left = "";

if ( pos > 0 ) // выделяем левую чать до найденной подстроки, может быть пустой

{

left = text.substring( 0, pos );

}

String right = text.substring( pos + subStr.length() ); // выделяемм правую чать после подстроки

text = left + right; // результирующий текст

}

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

System.out.println( text );

}

Ссылка на ideone.com: https://ideone.com/Z94AwR

План программы:

Ввод строки из стандартного потока ввода. Здесь используется getline, чтобы можно было вводить символы-разделители
Используется метод rfind класса string, позволяющий найти подстроку, начиная с конца
Результат поиска — позиция символа, с которого начинается искомая построка
Если позиция найдена, то используется метод replace, который заменяет все символы найденной подстроки на пустую строку

Ссылка на программу http://ideone.com/x5AtbG

Related Images:

А812б

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

Задача: Дан текст, каждый символ которого может быть малой буквой, цифрой или одним из знаков «+», «-«, «*». Группой букв будем называть такую совокупность последовательно расположенных букв, которой непосредственно не предшествует и за которой непосредственно не следует буква. Аналогично определим группу цифр и группу знаков.

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

Задача решена в двух вариантах — с использованием класса string и и с использованием массива символов, завершающихся нулём ( char[], null terminated string ).

Тесты ( для двух вариантов ):

№	тестовые данные	количество посчитанных слов	результат по условию задачи
1.	afsf1213**++	letterWordCount = 1 digitWordCount = 1 symbolWordCount = 1	в данном тексте одинаковое количество групп букв и групп знаков
2.	afsf1213++asfs2434gfh21+++—dhf++vg	letterWordCount = 5 digitWordCount = 3 symbolWordCount = 3	в данном тексте больше групп букв, чем групп знаков
3.	abcd+++—123efgh++—123367++-sdf—+754+-bmwazs++834hello++—***	letterWordCount = 5 digitWordCount = 4 symbolWordCount = 7	в данном тексте групп букв меньше, чем групп знаков

Вариант 1: решение с использованием класса string

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

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

using namespace std; 

// объявление переменных - флаги и счетчики для всех видов слов
int letterWordCount = 0, letterWordOngoing = 0;
int digitWordCount  = 0, digitWordOngoing  = 0;
int symbolWordCount = 0, symbolWordOngoing = 0;
 
// функция завершения чтения слова и увеличение счетчика слова на единицу
void countLastWord(void)
{
   if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }
   else if ( digitWordOngoing != 0 ) { digitWordOngoing  = 0; digitWordCount++; }
   else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }
}
 
int main(void)
{
   string text; // стандартный строковый объект класса string
 
   cin >> text; // вводим текст из стандартного потока ввода

   // проход по символам текста
   for( unsigned int i = 0; i < text.length(); i++ )
   {
       // анализ символов: к какой группе они относятся и проверка состояний
       if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов
       {
          if ( symbolWordOngoing == 0 )
          {
             countLastWord();
             symbolWordOngoing = 1;
          }
       }
       else if ( isdigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)
       {
          if ( digitWordOngoing == 0 )
          {
             countLastWord();
             digitWordOngoing = 1;
          }
       }
       else if ( islower( text[i] ) ) // проверка принадлежности к данному типу символов (буква)
       {
          if ( letterWordOngoing == 0 )
          {
             countLastWord();
             letterWordOngoing = 1;
          }
       }
       else
       {
          printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);
          return 0;
       }
   }
 
   countLastWord(); // финальное завершение текущего слова
 
   // вывод количества посчитанных слов
   printf("letterWordCount = %d\n", letterWordCount);
   printf("digitWordCount  = %d\n", digitWordCount );
   printf("symbolWordCount = %d\n", symbolWordCount);
  
   // вычисление конечного результата
   if( letterWordCount > symbolWordCount ) { printf("в данном тексте больше групп букв, чем групп знаков\n"); }
   else if ( letterWordCount == symbolWordCount ) { printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }
   else { printf("в данном тексте групп букв меньше, чем групп знаков\n"); }
 
   return 0;
}

#include <iostream>

#include <string>

#include <stdio.h>

#include <ctype.h>

using namespace std;

// объявление переменных - флаги и счетчики для всех видов слов

int letterWordCount = 0, letterWordOngoing = 0;

int digitWordCount = 0, digitWordOngoing = 0;

int symbolWordCount = 0, symbolWordOngoing = 0;

// функция завершения чтения слова и увеличение счетчика слова на единицу

void countLastWord(void)

{

if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }

else if ( digitWordOngoing != 0 ) { digitWordOngoing = 0; digitWordCount++; }

else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }

}

int main(void)

{

string text; // стандартный строковый объект класса string

cin >> text; // вводим текст из стандартного потока ввода

// проход по символам текста

for( unsigned int i = 0; i < text.length(); i++ )

{

// анализ символов: к какой группе они относятся и проверка состояний

if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов

{

if ( symbolWordOngoing == 0 )

{

countLastWord();

symbolWordOngoing = 1;

}

else if ( isdigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)

{

if ( digitWordOngoing == 0 )

{

countLastWord();

digitWordOngoing = 1;

}

else if ( islower( text[i] ) ) // проверка принадлежности к данному типу символов (буква)

{

if ( letterWordOngoing == 0 )

{

countLastWord();

letterWordOngoing = 1;

}

else

{

printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);

return 0;

}

countLastWord(); // финальное завершение текущего слова

// вывод количества посчитанных слов

printf("letterWordCount = %d\n", letterWordCount);

printf("digitWordCount = %d\n", digitWordCount );

printf("symbolWordCount = %d\n", symbolWordCount);

// вычисление конечного результата

if( letterWordCount > symbolWordCount ) { printf("в данном тексте больше групп букв, чем групп знаков\n"); }

else if ( letterWordCount == symbolWordCount ) { printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }

else { printf("в данном тексте групп букв меньше, чем групп знаков\n"); }

return 0;

}

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

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

class StringApp
{   

   // объ¤вление переменных - флаги и счетчики дл¤ всех видов слов
   private int letterWordCount = 0; 
   private int letterWordOngoing = 0;
   private int digitWordCount = 0;
   private int digitWordOngoing = 0;
   private int symbolWordCount = 0;
   private int symbolWordOngoing = 0;
   
   // функци¤ завершени¤ чтени¤ слова и увеличение счетчика слова на единицу
   private void countLastWord()
   {
      if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }
      else if ( digitWordOngoing != 0 ) { digitWordOngoing  = 0; digitWordCount++; }
      else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }
   }
   
   public void run()
   {
      // загрузка текста в массив - цикл считывани¤ одного символа текста
      Scanner in = new Scanner(System.in); 
      String text = in.next();     
      in.close();
      
      if ( text.isEmpty() )
      {
         return;
      }
      
      // проход по символам текста загруженного в массив
      for( int i = 0; i < text.length() && text.charAt(i) != 0; i++ )
      {
         // анализ символов: к какой группе они относ¤тс¤ и проверка состо¤ний
          if ( text.charAt(i) == '*'|| text.charAt(i) == '-'|| text.charAt(i) == '+' ) // проверка принадлежности к данному типу символов
          {
             if ( symbolWordOngoing == 0 )
             {
                countLastWord();
                symbolWordOngoing = 1;
             }
          }
          else if ( Character.isDigit( text.charAt(i) ) ) // проверка принадлежности к данному типу символов (цифра)
          {
             if ( digitWordOngoing == 0 )
             {
                countLastWord();
                digitWordOngoing = 1;
             }
          }
          else if ( Character.isLowerCase( text.charAt(i) ) ) // проверка принадлежности к данному типу символов (буква)
          {
             if ( letterWordOngoing == 0 )
             {
                countLastWord();
                letterWordOngoing = 1;
             }
          }
          else
          {
             System.out.printf("error: illegal character: %c / 0x%x\n", text.charAt(i), text.charAt(i));
             return;
          }
      }
      
      countLastWord(); // финальное завершение текущего слова
      
      // вывод количества посчитанных слов
      System.out.printf("letterWordCount = %d\n", letterWordCount);
      System.out.printf("digitWordCount  = %d\n", digitWordCount );
      System.out.printf("symbolWordCount = %d\n", symbolWordCount);
      
      // вычисление конечного результата
      if( letterWordCount > symbolWordCount ) { System.out.printf("в данном тексте больше групп букв, чем групп знаков\n"); }
      else if ( letterWordCount == symbolWordCount ) { System.out.printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }
      else { System.out.printf("в данном тексте групп букв меньше, чем групп знаков\n"); }
   }
   
   public static void main( String[] args )
   {
       StringApp app = new StringApp();
       app.run();
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class StringApp

{

// объ¤вление переменных - флаги и счетчики дл¤ всех видов слов

private int letterWordCount = 0;

private int letterWordOngoing = 0;

private int digitWordCount = 0;

private int digitWordOngoing = 0;

private int symbolWordCount = 0;

private int symbolWordOngoing = 0;

// функци¤ завершени¤ чтени¤ слова и увеличение счетчика слова на единицу

private void countLastWord()

{

if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }

else if ( digitWordOngoing != 0 ) { digitWordOngoing = 0; digitWordCount++; }

else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }

}

public void run()

{

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

Scanner in = new Scanner(System.in);

String text = in.next();

in.close();

if ( text.isEmpty() )

{

return;

}

// проход по символам текста загруженного в массив

for( int i = 0; i < text.length() && text.charAt(i) != 0; i++ )

{

// анализ символов: к какой группе они относ¤тс¤ и проверка состо¤ний

if ( text.charAt(i) == '*'|| text.charAt(i) == '-'|| text.charAt(i) == '+' ) // проверка принадлежности к данному типу символов

{

if ( symbolWordOngoing == 0 )

{

countLastWord();

symbolWordOngoing = 1;

}

else if ( Character.isDigit( text.charAt(i) ) ) // проверка принадлежности к данному типу символов (цифра)

{

if ( digitWordOngoing == 0 )

{

countLastWord();

digitWordOngoing = 1;

}

else if ( Character.isLowerCase( text.charAt(i) ) ) // проверка принадлежности к данному типу символов (буква)

{

if ( letterWordOngoing == 0 )

{

countLastWord();

letterWordOngoing = 1;

}

else

{

System.out.printf("error: illegal character: %c / 0x%x\n", text.charAt(i), text.charAt(i));

return;

}

countLastWord(); // финальное завершение текущего слова

// вывод количества посчитанных слов

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

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

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

// вычисление конечного результата

if( letterWordCount > symbolWordCount ) { System.out.printf("в данном тексте больше групп букв, чем групп знаков\n"); }

else if ( letterWordCount == symbolWordCount ) { System.out.printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }

else { System.out.printf("в данном тексте групп букв меньше, чем групп знаков\n"); }

}

public static void main( String[] args )

{

StringApp app = new StringApp();

app.run();

}

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

План программы:

Объявление переменных — флаги и счетчики для всех видов слов
Функция завершения чтения слова и увеличение счетчика слова на единицу
Стандартный строковый объект класса string
Ввод текст из стандартного потока ввода
Проход по символам текста
Анализ символов: к какой группе они относятся и проверка состояний
Проверка принадлежности к данному типу символов ( +, — , * / цифра / буква )
Финальное завершение текущего слова
Вывод количества посчитанных слов
Вычисление конечного результата

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

Цикл выполняется по всем символам string, вплоть до нулевого символа и анализирует принадлежность каждого символа к группе символов. Согласно условию задачи это — мал. буквы, цифры и символы + , — , * . В программе использованы 3 переменных-флага, описывающих текущие состояние чтение одного слова данной группы. Также есть переменные-счётчики для каждой группы слов. Каждый счётчик наращивается при сбрасывании флага, то есть, по завершении чтения группы.

Для проверки типа символа используются стандартные макросы isdigit и islower из библиотеки ctype .

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

Вариант 2: решене с использованием строки символов с завершающим нулём char[]

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

#include <stdio.h>
#include <ctype.h>

#define TEXT_SIZE_MAX 4096

char text[TEXT_SIZE_MAX+1]; // символьный массив для загрузки текста
 
// объявление переменных - флаги и счетчики для всех видов слов
int letterWordCount = 0, letterWordOngoing = 0;
int digitWordCount  = 0, digitWordOngoing  = 0;
int symbolWordCount = 0, symbolWordOngoing = 0;
 
// функция завершения чтения слова и увеличение счетчика слова на единицу
void countLastWord(void)
{
   if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }
   else if ( digitWordOngoing != 0 ) { digitWordOngoing  = 0; digitWordCount++; }
   else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }
}
 
int main(void)
{
   int i, n, c;

   // загрузка текста в массив - цикл считывания одного символа текста
   n = 0;
   while( ( c = getchar() ) != EOF && c != 0 )
   {
      if ( n <= TEXT_SIZE_MAX - 1 ) 
         text[ n++ ] = (char)c;
      else
         break;
   }
   text[ n ] = 0;  // завершаем нулевым символом 

   // проход по символам текста загруженного в массив
   for( i = 0; text[i] != 0; i++ )
   {
      // анализ символов: к какой группе они относятся и проверка состояний
       if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов
       {
          if ( symbolWordOngoing == 0 )
          {
             countLastWord();
             symbolWordOngoing = 1;
          }
       }
       else if ( isdigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)
       {
          if ( digitWordOngoing == 0 )
          {
             countLastWord();
             digitWordOngoing = 1;
          }
       }
       else if ( islower( text[i] ) ) // проверка принадлежности к данному типу символов (буква)
       {
          if ( letterWordOngoing == 0 )
          {
             countLastWord();
             letterWordOngoing = 1;
          }
       }
       else
       {
          printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);
          return 0;
       }
   }
 
   countLastWord(); // финальное завершение текущего слова
 
   // вывод количества посчитанных слов
   printf("letterWordCount = %d\n", letterWordCount);
   printf("digitWordCount  = %d\n", digitWordCount );
   printf("symbolWordCount = %d\n", symbolWordCount);
  
   // вычисление конечного результата
   if( letterWordCount > symbolWordCount ) { printf("в данном тексте больше групп букв, чем групп знаков\n"); }
   else if ( letterWordCount == symbolWordCount ) { printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }
   else { printf("в данном тексте групп букв меньше, чем групп знаков\n"); }
 
   return 0;
}

#include <stdio.h>

#include <ctype.h>

#define TEXT_SIZE_MAX 4096

char text[TEXT_SIZE_MAX+1]; // символьный массив для загрузки текста

// объявление переменных - флаги и счетчики для всех видов слов

int letterWordCount = 0, letterWordOngoing = 0;

int digitWordCount = 0, digitWordOngoing = 0;

int symbolWordCount = 0, symbolWordOngoing = 0;

// функция завершения чтения слова и увеличение счетчика слова на единицу

void countLastWord(void)

{

if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }

else if ( digitWordOngoing != 0 ) { digitWordOngoing = 0; digitWordCount++; }

else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }

}

int main(void)

{

int i, n, c;

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

n = 0;

while( ( c = getchar() ) != EOF && c != 0 )

{

if ( n <= TEXT_SIZE_MAX - 1 )

text[ n++ ] = (char)c;

else

break;

}

text[ n ] = 0; // завершаем нулевым символом

// проход по символам текста загруженного в массив

for( i = 0; text[i] != 0; i++ )

{

// анализ символов: к какой группе они относятся и проверка состояний

if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов

{

if ( symbolWordOngoing == 0 )

{

countLastWord();

symbolWordOngoing = 1;

}

else if ( isdigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)

{

if ( digitWordOngoing == 0 )

{

countLastWord();

digitWordOngoing = 1;

}

else if ( islower( text[i] ) ) // проверка принадлежности к данному типу символов (буква)

{

if ( letterWordOngoing == 0 )

{

countLastWord();

letterWordOngoing = 1;

}

else

{

printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);

return 0;

}

countLastWord(); // финальное завершение текущего слова

// вывод количества посчитанных слов

printf("letterWordCount = %d\n", letterWordCount);

printf("digitWordCount = %d\n", digitWordCount );

printf("symbolWordCount = %d\n", symbolWordCount);

// вычисление конечного результата

if( letterWordCount > symbolWordCount ) { printf("в данном тексте больше групп букв, чем групп знаков\n"); }

else if ( letterWordCount == symbolWordCount ) { printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }

else { printf("в данном тексте групп букв меньше, чем групп знаков\n"); }

return 0;

}

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

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

class CharArrApp
{   

   // объ¤вление переменных - флаги и счетчики дл¤ всех видов слов
   private int letterWordCount = 0; 
   private int letterWordOngoing = 0;
   private int digitWordCount = 0;
   private int digitWordOngoing = 0;
   private int symbolWordCount = 0;
   private int symbolWordOngoing = 0;
   
   // функци¤ завершени¤ чтени¤ слова и увеличение счетчика слова на единицу
   private void countLastWord()
   {
      if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }
      else if ( digitWordOngoing != 0 ) { digitWordOngoing  = 0; digitWordCount++; }
      else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }
   }
   
   public void run()
   {
      // загрузка текста в массив - цикл считывани¤ одного символа текста
      Scanner in = new Scanner(System.in); 
      String s = in.next();     
      in.close();
      
      if ( s.isEmpty() )
      {
         return;
      }
      
      char[] text = s.toCharArray();
      
      // проход по символам текста загруженного в массив
      for( int i = 0; i < text.length && text[i] != 0; i++ )
      {
         // анализ символов: к какой группе они относ¤тс¤ и проверка состо¤ний
          if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов
          {
             if ( symbolWordOngoing == 0 )
             {
                countLastWord();
                symbolWordOngoing = 1;
             }
          }
          else if ( Character.isDigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)
          {
             if ( digitWordOngoing == 0 )
             {
                countLastWord();
                digitWordOngoing = 1;
             }
          }
          else if ( Character.isLowerCase( text[i] ) ) // проверка принадлежности к данному типу символов (буква)
          {
             if ( letterWordOngoing == 0 )
             {
                countLastWord();
                letterWordOngoing = 1;
             }
          }
          else
          {
             System.out.printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);
             return;
          }
      }
      
      countLastWord(); // финальное завершение текущего слова
      
      // вывод количества посчитанных слов
      System.out.printf("letterWordCount = %d\n", letterWordCount);
      System.out.printf("digitWordCount  = %d\n", digitWordCount );
      System.out.printf("symbolWordCount = %d\n", symbolWordCount);
      
      // вычисление конечного результата
      if( letterWordCount > symbolWordCount ) { System.out.printf("в данном тексте больше групп букв, чем групп знаков\n"); }
      else if ( letterWordCount == symbolWordCount ) { System.out.printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }
      else { System.out.printf("в данном тексте групп букв меньше, чем групп знаков\n"); }
   }
   
   public static void main( String[] args )
   {
       CharArrApp app = new CharArrApp();
       app.run();
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class CharArrApp

{

// объ¤вление переменных - флаги и счетчики дл¤ всех видов слов

private int letterWordCount = 0;

private int letterWordOngoing = 0;

private int digitWordCount = 0;

private int digitWordOngoing = 0;

private int symbolWordCount = 0;

private int symbolWordOngoing = 0;

// функци¤ завершени¤ чтени¤ слова и увеличение счетчика слова на единицу

private void countLastWord()

{

if ( letterWordOngoing != 0 ) { letterWordOngoing = 0; letterWordCount++; }

else if ( digitWordOngoing != 0 ) { digitWordOngoing = 0; digitWordCount++; }

else if ( symbolWordOngoing != 0 ) { symbolWordOngoing = 0; symbolWordCount++; }

}

public void run()

{

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

Scanner in = new Scanner(System.in);

String s = in.next();

in.close();

if ( s.isEmpty() )

{

return;

}

char[] text = s.toCharArray();

// проход по символам текста загруженного в массив

for( int i = 0; i < text.length && text[i] != 0; i++ )

{

// анализ символов: к какой группе они относ¤тс¤ и проверка состо¤ний

if ( text[i] == '*'|| text[i] == '-'|| text[i] == '+' ) // проверка принадлежности к данному типу символов

{

if ( symbolWordOngoing == 0 )

{

countLastWord();

symbolWordOngoing = 1;

}

else if ( Character.isDigit( text[i] ) ) // проверка принадлежности к данному типу символов (цифра)

{

if ( digitWordOngoing == 0 )

{

countLastWord();

digitWordOngoing = 1;

}

else if ( Character.isLowerCase( text[i] ) ) // проверка принадлежности к данному типу символов (буква)

{

if ( letterWordOngoing == 0 )

{

countLastWord();

letterWordOngoing = 1;

}

else

{

System.out.printf("error: illegal character: %c / 0x%x\n", text[i], text[i]);

return;

}

countLastWord(); // финальное завершение текущего слова

// вывод количества посчитанных слов

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

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

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

// вычисление конечного результата

if( letterWordCount > symbolWordCount ) { System.out.printf("в данном тексте больше групп букв, чем групп знаков\n"); }

else if ( letterWordCount == symbolWordCount ) { System.out.printf("в данном тексте одинаковое количество групп букв и групп знаков\n"); }

else { System.out.printf("в данном тексте групп букв меньше, чем групп знаков\n"); }

}

public static void main( String[] args )

{

CharArrApp app = new CharArrApp();

app.run();

}

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

План программы:

Объявление символьного массива для загрузки текста
Объявление переменных — флаги и счетчики для всех видов слов
Функция завершения чтения слова и увеличение счетчика слова на единицу
Загрузка текста в массив — цикл считывания одного символа текста
Завершение нулевым символом
Проход по символам текста загруженного в массив
Анализ символов: к какой группе они относятся и проверка состояний
Проверка принадлежности к данному типу символов ( +, — , * / цифра / буква )
Финальное завершение текущего слова
Вывод количества посчитанных слов
Вычисление конечного результата

Программа читает непрерывный поток текстовых символов и загружает их в символьный массив text . По окончанию ввода добавляется нулевой символ, чтобы символьный массив выглядел, как строка, завершающаяся нулём (null terminated string). При вводе учитывается возможность появления мулевого символа, что также прекращает ввод.

Цикл выполняется по символьному массиву, вплоть до нулевого символа и анализирует принадлежность каждого символа к группе символов. Согласно условию задачи это — мал. буквы, цифры и символы + , — , * . В программе использованы 3 переменных-флага, описывающих текущие состояние чтение одного слова данной группы. Также есть переменные- счётчики для каждой группы слов. Каждый счётчик наращивается при сбрасывании флага, то есть, по завершении чтения группы.

Для проверки типа символа используются стандартные макросы isdigit и islower из библиотеки ctype .

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

Related Images:

А397б

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

Задача: Дана действительная квадратная матрица порядка [latex]n[/latex]. В строках с отрицательным элементом на главной диагонали найти наибольший из всех элементов.

Тесты:

matrix

results the biggest element in line

-1	3	4	5
2	3	6	7
1	4	-2	7
2	3	4	2

—

-1	2	3	4	5
6	7	8	9	10
2	4	-5	7	8
11	-1	0	5	9
1	8	-33	2	-1

—

error: wrong value of n

0	1	3
-2	-5	-1
-4	-9	-4

—

-1

-4

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

#include <stdio.h>
#include <float.h>
  
   // назначение макросов
#define MAX 10
#define X_INIT (-DBL_MAX)

int main(void)
{
   // рабочие переменные
   int n;
   int i;
   int j;
   double x;
   double arr[MAX][MAX];
   
   // проверка ввода порядка n
	if( scanf("%d", &n ) <= 0 )
   {
      printf("error: incomplete input of n\n");
      return 0;
   }
   if( n <= 1 || n > MAX )
   {
      printf("error: wrong value of n\n");
      return 0;
   }
   
   // ввод матрицы с проверкой
	for( i = 0; i < n; i++)
	{
		for( j = 0; j < n; j++)
	   {
         if( scanf("%lf", &arr[i][j] ) < 1 )
         {
            printf("error: incomplete input of array\n");
            return 0;
         }

      }      
	}
   // печать введённой матрицы для отладки
   printf("input array:\n");
   for( i = 0; i < n; i++)
	{
 		for( j = 0; j < n; j++)
	   {
         printf("\t%2.2lf", arr[i][j]);        
         
      } 
      printf("\n");   
	}
   // вывод результата, содержит номер строки, где необходимо было искать наибольший элемент
   printf("result:\n");
   for( i = 0; i < n; i++)
	{
      x = X_INIT;   
      if( arr[i][i] < 0 )
      {
	      for( j = 0; j < n; j++)
	      {   
		      if( arr[i][j] > x ) x = arr[i][j];             
         }
         printf("line = %d, max = %2.2lf\n", i, x); 
	   }  
	}
   
   return 0;
}

#include <stdio.h>

#include <float.h>

// назначение макросов

#define MAX 10

#define X_INIT (-DBL_MAX)

int main(void)

{

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

int n;

int i;

int j;

double x;

double arr[MAX][MAX];

// проверка ввода порядка n

if( scanf("%d", &n ) <= 0 )

{

printf("error: incomplete input of n\n");

return 0;

}

if( n <= 1 || n > MAX )

{

printf("error: wrong value of n\n");

return 0;

}

// ввод матрицы с проверкой

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

{

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

{

if( scanf("%lf", &arr[i][j] ) < 1 )

{

printf("error: incomplete input of array\n");

return 0;

}

// печать введённой матрицы для отладки

printf("input array:\n");

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

{

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

{

printf("\t%2.2lf", arr[i][j]);

}

printf("\n");

}

// вывод результата, содержит номер строки, где необходимо было искать наибольший элемент

printf("result:\n");

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

{

x = X_INIT;

if( arr[i][i] < 0 )

{

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

{

if( arr[i][j] > x ) x = arr[i][j];

}

printf("line = %d, max = %2.2lf\n", i, x);

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class MatrixApp
{
   private static final int  X_INIT = -Integer.MAX_VALUE;
   
   public static Integer scanInteger( Scanner in )
   {
       return ( ( in.hasNextInt() ) ? in.nextInt() : null );
   }
 
   public static Double scanDouble( Scanner in )
   {
       return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );
   }
   
   public static void main( String[] args )
   {       
      // проверка ввода порядка n
      Scanner in = new Scanner(System.in); 
      
      int n = scanInteger( in );
      
      if( n <= 0 )
      {
         System.out.printf("error: incomplete input of n\n");
         return;
      }
      
      if( n <= 1 )
      {
         System.out.printf("error: wrong value of n\n");
         return;
      }
      
      // создаем массив нужной размерности
      double arr[][] = new double[n][n];

      // ввод матрицы с проверкой
      for( int i = 0; i < n; i++ )
      {
          for( int j = 0; j < n; j++ )
         {
           arr[i][j] = scanDouble( in );
        }      
      }
      
      in.close();
      
      // печать введённой матрицы для отладки
      System.out.printf("input array:\n");
      for( int i = 0; i < n; i++ )
      {
         for( int j = 0; j < n; j++ )
         {
            System.out.printf("\t%2.2f", arr[i][j]);        
         } 
         System.out.printf("\n");   
      }

      // вывод результата, содержит номер строки, где необходимо было искать наибольший элемент
      System.out.printf("result:\n");
      for( int i = 0; i < n; i++ )
       {
         if( arr[i][i] < 0 )
         {
            double x = arr[i][0]; 
            for( int j = 1; j < n; j++ )
            {   
               if( arr[i][j] > x ) x = arr[i][j];             
            }
            System.out.printf("line = %d, max = %2.2f\n", i, x); 
          }  
       }
 
   
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class MatrixApp

{

private static final int X_INIT = -Integer.MAX_VALUE;

public static Integer scanInteger( Scanner in )

{

return ( ( in.hasNextInt() ) ? in.nextInt() : null );

}

public static Double scanDouble( Scanner in )

{

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

}

public static void main( String[] args )

{

// проверка ввода порядка n

Scanner in = new Scanner(System.in);

int n = scanInteger( in );

if( n <= 0 )

{

System.out.printf("error: incomplete input of n\n");

return;

}

if( n <= 1 )

{

System.out.printf("error: wrong value of n\n");

return;

}

// создаем массив нужной размерности

double arr[][] = new double[n][n];

// ввод матрицы с проверкой

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

{

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

{

arr[i][j] = scanDouble( in );

}

in.close();

// печать введённой матрицы для отладки

System.out.printf("input array:\n");

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

{

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

{

System.out.printf("\t%2.2f", arr[i][j]);

}

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

}

// вывод результата, содержит номер строки, где необходимо было искать наибольший элемент

System.out.printf("result:\n");

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

{

if( arr[i][i] < 0 )

{

double x = arr[i][0];

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

{

if( arr[i][j] > x ) x = arr[i][j];

}

System.out.printf("line = %d, max = %2.2f\n", i, x);

}

Ссылка:https://ideone.com/kCDer9

План программы:

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

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

Для поиска наибольшего значения в строке используется макрос X_INIT. Он используется в качестве начального значения максимума. Этим наименьшим значением является взятый с отрицательным знаком макрос DBL_MAX из библиотеки float.h , обозначающий наибольшее значение.

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

Related Images:

Ю4.4

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

Задача: Вычислить среднее значение [latex]x[/latex] и дисперсию [latex]d_{x}[/latex] для заданного массива [latex]X(k)[/latex] наблюдений:

[latex]x_{avg}=\frac{1}{k}\sum_{i=1}^{k}{x_{i}}[/latex]; [latex]d_{x}=\frac{1}{k-1}\sum_{i=1}^{k}{\left(x_{i}-x_{avg^{}} \right)^{2}}[/latex]

Тесты:

k	x	среднее	дисперсия
3	4, 5, 8	5,66666666666667	4,333333
5	2, 3, 6, 13, 22	9,2	69,7
6	0, 5, 23, 7, 11, 1	7,83333333333333	71,366667
2	—	—	error: incomplete input x
0	—	—	error: wrong value k
—	—	—	error: incomplete input k
1	5	5	error: wrong value k

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

#include <stdio.h>

#define ARRAY_SIZE_MAX 1024

int main(void)
{
   // рабочие переменные
   double avg = 0;
   double disp = 0;
   int i;
   int k;
   double x[ARRAY_SIZE_MAX];
   
   // проверка ввода числа итераций
   if( scanf("%d", &k ) < 1 )
   {
      printf("error: incomplete input of k\n");
      return 0;
   }
   if( k <= 1 || k > ARRAY_SIZE_MAX )
   {
      printf("error: wrong value of k\n");
      return 0;
   }
   
   // вычисление среднего значения
   for( i = 0; i < k; i++ )
   {
      if( scanf("%lf", &x[i] ) < 1 )
      {
         printf("error: incomplete input of x\n");
         return 0;
      }
      avg += x[i];
   }
   avg /= k;
   
   // вычисление дисперсии
   for( i = 0; i < k; i++ )
   {
     disp += ( x[i] - avg ) * ( x[i] - avg );
   }
   disp /= ( k - 1 );
   
   // вывод результата
   printf("%lf\n", avg);
   printf("%lf", disp);
   
   return 0;
}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Швандт Максим Альбертович

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

Условие

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

Результат

Пример

Related Images:

А1042

Related Images:

А709

Related Images:

e-olimp 4847. Очередь с приоритетами

Related Images:

АА20

Related Images:

А812б

Related Images:

А397б

Related Images:

Ю4.4