На чём и как писать (часть 1. Eclipse и Java)

  • Tutorial
image
image
В продолжение предыдущего поста.

Оговорюсь сразу: нет, я не пытаюсь унизить этими картинками Java или C++. Или вообще сказать, что такой-то язык лучше сякого-то языка. Я лишь хочу показать, что для разных задач разные языки являются удобнее. В этом топике можно прочесть советы по выбору IDE для олимпиадного программмирования и Будет рассмотрена часть случаев, когда Java удобнее.

IDE

Казалось бы, к чему тут IDE? А вот к чему: компьютер, на котором Вы будете писать на ACM, будет совсем не ваш. И совсем такой же, как у ещё 9000 соревнующихся. И вполне возможно, что Вашей любимой, возможно экзотической, среды разработки там не будет. А будет там вот что:
  • Borland Delphi 7.0 — с 2009 года отсутствует
  • Microsoft Visual Studio 2005 Express Edition, C/C++
  • Java 2 SDK 6.0
  • Eclipse
  • Far Manager 1.7b5
  • MinGW (GNU C/C++)

Итак, выбор не велик. Морально устаревшая версия MS VS и Eclipse. Кстати, всегда последней версии. Ну и Far, но это не IDE. Поэтому я наберусь наглости и буду писать исключительно об Eclipse.

Шаблоны

Пожалуй, первое, чему нас учили — создавать шаблон в Eclipse. Шаблоны позволяют быстро, очень быстро создать каркас для написания программы. Такой, что достаточно написать три-четыре буквы от имени шаблона, нажать сочетание кнопок(Ctrl + Spacebar) и обнаружить в окне редактора уже полностью готовый каркас для программы. О том, как их создавать, можно почитать тут.

Кнопочки + другие кнопочки ( + ещё другие кнопочки)

Комбинации клавиш — то, за что олимпиадники любят Eclipse. Всегда есть возможность нажать Ctrl + Spacebar и воспользоваться великой автоподстановкой (пользователи Visual Studio знают это под именем IntelliSense). Можно выделить код, нажать Ctrl + / И за/раскоментировать его. Можно нажать Ctrl + Alt + ↓ или чтобы скопировать текущую строку вверх или вниз, можно нажать Ctrl + D чтобы удалить текущую строчку… А можно залезть в настройки, отыскать там список сочетаний, и запомнить нужные.

Как и когда писать на Java

Первое, с чем нужно разобраться при олимпиадном программировании на Java — это захапать себе большой стек, для чего запускаться в отдельном потоке. Второе — научиться быстро читать и писать данные. Я приведу свой текущий шаблон для Eclipse, снабдив его предварительно комментариями. Если что-то непонятно, то я могу пояснить.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
// ${primary_type_name} - имя класса, его подставляет Eclipse. Очень хорошая идея - создавать класс с именем входного и выходного файлов.
// Правда они почти всегда с маленькой буквы, но это можно пережить.
public class ${primary_type_name} implements Runnable {
  StringTokenizer st; // Этот класс быстро умеет разбивать скормленную ему строчку. По умолчанию разделитель - пробел
  BufferedReader in; // Этот класс ОЧЕНЬ быстро умеет считывать данные из какого-либо потока
  PrintWriter out; // Этот класс умеет писать данные, тоже быстро.

  public static void main(String[] args) {
    new Thread(new ${primary_type_name}()).start(); //Нам нужен большой стек, так что заведём новый поток.
  }

  public void run() {
    try {
      in = new BufferedReader(new FileReader("${primary_type_name}.in"));
      out = new PrintWriter(new FileWriter("${primary_type_name}.out"));
      solve();
    } catch (Exception e) {
      //Если есть исключение - выходим с кодом ошибки. Вместо 9000 может быть что угодно, не равное нулю.
      System.exit(9000);
    } finally {
      //Не забываем про закрытие файла.
      out.flush();
      out.close();
    }
  }
  //Получаем следующий токен
  String nextToken() throws IOException {
    while (st == null || !st.hasMoreTokens()) {
      st = new StringTokenizer(in.readLine());
    }
    return st.nextToken();
  }
  //Следующее 32-битное целое число
  int nextInt() throws NumberFormatException, IOException {
    return Integer.parseInt(nextToken());
  }
  //...
  long nextLong() throws NumberFormatException, IOException {
    return Long.parseLong(nextToken());
  }
  //... Что бы вы думали?
  double nextDouble() throws NumberFormatException, IOException {
    return Double.parseDouble(nextToken());
  }

  void solve() throws NumberFormatException, IOException {
    //А тут уже пишем решение задачи.
  }
}

Отлично! Теперь мы готовы решить нашу (возможно, первую) олимпиадную задачу на Java. Выберем что-нибудь простое, но требующее именно этого языка. Путь это будет №1196 с Тимуса. Внимательно прочитайте условие и немного подумайте над решением, прежде чем возвращаться к этой статье. Предположим на секунду, что среди читателей какой-то умник энтузиаст сразу попытался решить задачу; и решить её вот таким вот образом:
int n = nextInt();
int[] teachers = new int[n];
for(int i = 0; i < n; i ++)
  teachers[i] = nextInt();
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++) {
  int students = nextInt();
  for(int j = 0; j < n; j ++)
    if(teachers[j] == students) {
      result ++; break;
    }
}
out.println(result);
Разумеется, он получил TL (Time Limit exceeded), потому что его программа работает за O(n⋅m). Кстати, если предыдущее высказывание ничего Вам не говорит, хорошо бы почитать об O-символике. Наш энтузиаст решил подумать получше, почитал соответствующую литературу, или поглядел на разных сайтах (см. прошлый пост), и нашёл аж два способа решить задачу быстрее. Первый из них использует встроенное в Java сбалансированное двоичное дерево:
int n = nextInt();
TreeSet<Integer> teachers = new TreeSet<Integer>();
for(int i = 0; i < n; i ++)
  teachers.add(nextInt());
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++)
  if(teachers.contains(nextInt()))
    result ++;
out.println(result);

Как видите, получилось даже меньше кода, чем при решении «в лоб». Второй же способ использует встроенные быструю сортировку и двоичный поиск Java:
int n = nextInt();
int[] teachers = new int[n];
for(int i = 0; i < n; i ++)
  teachers[i] = nextInt();
Arrays.sort(teachers);
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++) {
  int students = nextInt();
  int pos = Arrays.binarySearch(teachers, students);
  if(pos > 0 && pos < teachers.length && teachers[pos] == students)
    result ++;
}
out.println(result);
Этот метод немного объёмистее, так как binarySearch возвращает или положение элемента в массиве, или то место, куда бы его следовало вставить, если его нет; но всё равно вполне проходит.
Оба решения, очевидно, работают за O(n⋅logn + m⋅logn) = O((m + n)logn). А если не очевидно, то нужно было почитать про двоичные деревья, быструю сортировку и двоичный поиск.

To be Continued


… Нажав на кнопку «предпросмотр» я ужаснулся обилию текста, и решил, что стоит разнести эту тему на два топика. Так что ждите во второй части рассказ о том, как и когда писать на C/C++ и разбор характерной задачи.

* All source code was highlighted with Source Code Highlighter.
Поделиться публикацией

Комментарии 91

    +2
    Я бы добавил, что часто бывают довольно простые задачи (пара циклов и несколько арифметических операций), но где числа не влезают в обычные типы данных. А в джаве длинная арифметика встроена)) Сам об этом вспомнил, когда на недавнем контесте были баги в реализации длинной арифметики на C++)
      0
      Спасибо, что напомнил. Будет)
      +1
      Немного отвлеченный вопрос от Java, но по теме…
      Помню еще до получения хорошего опыта работы, я ездил на олимпиаду и мне надолго запомнилась одна задача, которую мало кто решил. Кому хочется размяться, может попробовать.
      Условие:
      Есть число n. Нужно вывести все возможные наборы положительных чисел (больше нуля), сумма которых равна числу n.
      Пример: kirill533.ho.ua/proga.php

      Задача не сложная для программиста с опытом. Интересно, сколько времени уйдет на ее решение.
        0
        Небось перебором решаете? Зачем такое глупое ограничение от 1 до 15,
          0
          что б не загрузили хостинг. Большие числа оно считает больше 30 секунд и скрипт завершается.
          Кода в задаче очень мало
            0
            А как задачу поиска всех возможных наборов можно без перебора решить?
              +1
              Восходящей динамикой. Мы знаем, что для числа 1 только один такой набор, и знаем, какой он. Для числа n есть \sum_{i=0}^{n/2}(f(i) + f(n - i))наборов, при этом мы уже сгенерировали наборы для i и для n-i.
                0
                Слово «динамика» — это первое, что мелькнуло у меня в голове во время прочтения задачи :) Но увы, у нас не количество спрашивают, а все возможные наборы. Сложно вывести все возможные наборы, не перебирая их.

                Эта задачка вообще мало похожа на ACM ICPC-задачку, но условие есть условие, так его автор сформулировал.
                  0
                  Кто-то невнимательно прочитал комментарий. При динамике никто не мешает получить и сами наборы.
                    0
                    Получить то можно. Но как тогда вы предлагаете их выводить?

                    Если их вывести перечислением наборов чисел, то тогда в динамике вообще не будет смысла, поскольку при выводе вы все-равно будете все решения перебирать.
                      +1
                      При выводе «решения» перебирать мы будем не все, а только верные.
                        +1
                        Ну перебирать тоже надо правильно, что не отменяет самого факта перебора. Я предлагаю перебирать только правильные решения (см. код ниже). Оценка по времени выполнения — приблизительно O(N), где N — размер вывода, поэтому быстрее уже никак не получится. Собственно и оптимизировать тут уже нечего, поскольку главный тормоз здесь — вывод.

                        #include <iostream>
                        #include <vector>
                        #include <cstdio>
                        
                        using namespace std;
                        
                        void output(vector <int> &s)
                        {
                        	// Используем printf для большей скорости вывода по сравнению с cout
                        	for(int i=1; i<s.size(); i++)
                        		printf(" %d", s[i]);
                        	printf("\n");
                        }
                        
                        void bruteforce (vector <int> &s, int sumLeft)
                        {
                        	if (sumLeft == 0) 
                        		output (s);
                        
                        	// max(1, s[s.size()-1]) - последний елемент из стека s, 
                        	//                         или 1, если последний елемент равен 0.
                        	for (int i=max(1, s[s.size()-1]); i<=sumLeft; i++)
                        	{
                        		s.push_back(i);
                        		bruteforce(s, sumLeft - i);
                        		s.pop_back();
                        	}
                        }
                        
                        int main()
                        {
                        	int N;
                        	vector <int> s; // Стэк для перебора
                        
                        	cin >> N;	
                        	s.push_back(0);
                        	bruteforce(s, N);
                        
                        	return 0;
                        }
                        
                          +1
                          //В общем-то у меня похожее решение (на javascript):
                          var res = "";
                          function  f(x,  y,  t)  {
                                  
                                  if  (y  !=  "")  {
                                          res  +=  ''  +  y  +  x  +  "\n";
                                  }

                                  for(var  i=1;  i<x  ;i++)  {
                                          if(i>=t  &&  2*i<=x)  {
                                                  f(x-i,  ''  +  y  +  i  +  "+",  i);
                                          }
                                  }
                          }

                          var a = prompt(«Please, enter the value»);
                          f(a, '', 0);
                          alert(res);

                          Для выполнения можно скопировать в адресную строку:
                          javascript:var res="";function f(x,y,t){if(y!="")res+=''+y+x+"\n";for(var i=1;i<x;i++)if(i>=t&&2*i<=x)f(x-i,''+y+i+"+",i);}f(prompt(«Please, enter the value»),'',0);alert(res);
                            0
                            javascript:var res="";function f(x,y,t){if(y!="")res+=''+y+x+"\n";for(var i=1;i<x;i++)if(i>=t&&2*i<=x)f(x-i,''+y+i+"+",i);}f(prompt('Please, enter the value'),'',0);alert(res);

                            Вторая попытка
                              0
                              Спасибо за подсказку :) В моей программе я забыл учесть ситуации, когда bruteforce вызывается с параметрами, что последний елемент больше оставшейся суммы, которые можно отсечь, потому-что к решению они не ведут. Если внести небольшие правки, тогда мой перебор будет только правильные варианты сразу искать.

                              Но все-равно, из-за тормозов вывода, на практике разницы мы почти не увидим.
                        +2
                        Скорее всего не ошибусь, если предположу, что под перебором Kotter понимает не поиск с возвратом, а необходимость обработать все возможные варианты (что так или иначе должно произойти). Потому ваша динамика, кстати, ощутимого прироста в скорости не даст по сравнению с аккуратным поиском с возвратом, только добавит хлопот с хранением промежуточных наборов (для чего в поиске с возвратом автоматически послужит стек).
                0
                Задача, по моему опыту, решается элементарно — в спокойном режиме прогоняется на рабочей машинке для самого максимального n, с записью результатов в файл. А на контест выдается этот самый файл, из которого, безо всяких вычислений, просто берется нужное решение…
                  0
                  Размер исходного кода программы ограничен специально для подобных хитрецов.
                  +1
                  Сразу на ум приходит такое понятие как разбиение.
                    0
                    Тоже правда.
                    0
                    У меня получилось такое решение:
                    #include <stdio.h>
                    #include <math.h>

                    void solution(int number) {
                      int count; // Количество слагаемых
                      int free; // Количество свободных едениц
                      int increase; // Коэффициент приращения
                      int current_free, current_increase, item;
                      // Перебор количества слагаемых
                      for(count = 2; count <= number; count++) {
                        // Слагаемых может быть от 2 (одно это и есть число)
                        // до собственно самого числа (1+...+1)
                        free = number - count; // Количество свободных едениц для данного числа слагаемых
                        // Минимальный коэффициент приращения для слагаемого
                        increase = ceil((float)free / (float)count); // Округляется до макс.целого
                        // Перебор коэффициентов приращения
                        do {
                          // Выполнять до тех пор пока коэффициент приращения не сравняется
                          // С макс. кол-вом свободных едениц
                          current_free = free; // Текущее кол-во свободных едениц
                          current_increase = increase; // Текущее коэффициент приращения
                          // Перебор слагаемый и вывод их на экран
                          for(item = 0; item < count; item++) {
                            if(current_free - current_increase < 0) {
                              // Если коэффициент приращения превышает кол-во имеющихся едениц
                              // Приравнять его кол-ву оставшихся
                              current_increase = current_free;
                              // Количество единиц обнуляем, они все использованы
                              current_free = 0;
                            } else {
                              // Вычитаем из имеющихся единиц коэффициент приращения
                              current_free -= current_increase;
                            }
                            // Выводим на экран
                            printf("[%d]", 1 + current_increase);
                          }
                          printf("\n");
                          increase++; // Увеличение коэффициента приращения
                        } while(increase <= free);
                      }
                    }

                    int main() {
                      solution(5);
                      printf("---\n");
                      solution(10);
                      printf("---\n");
                      solution(15);
                      return 0;
                    }


                    * This source code was highlighted with Source Code Highlighter.
                    Вроде и считает что нужно, и не брутфорс.
                    –3
                    >IDE
                    ТАК, Я НЕ ПОНЯЛ?
                    а где сетевые бобы?
                      +1
                      Вопрос не по адресу. Это, пожалуйста, к организаторам контестов.
                      0
                      Есть вопрос, правда не по ACM, а по TopCoder SRM's.
                      На оф. сайте в списке языков заявлен C# но, в отличие от C++, не указано окружение.
                      Какая версия языка там используется? Разрешён ли C# 3.0 (LINQ, lambdas, type inference, etc)?
                        0
                        В FAQ сказано:
                        Microsoft Windows 2003 5.2.3790 SP2, .NET Framework version 2.0.50727
                          0
                          Тут возможна неоднозначность. Есть версии Фреймворка: 2.0, 3.5, 4.0. Есть версии языка C#: 2.0, 3.0, 4.0 соответственно. Есть версии CLR: 2.0.50727, 2.0.50727 (sic!), 4.0.20506 соответственно.
                          Но — да, наверное, они имели в виду вторую версию версию фреймворка, языка и рантайма.
                        0
                        А можно залезть в настройки, отыскать там список сочетаний, и запомнить нужные.
                        А лучше не запомнить, а изменить на нормальные, потому что то, что предлагает по умолчанию эклипс —тихий ужас. Где поиск по F3, где переключение файлов по ctrl+tab?
                          0
                          На олимпиадах у вас только один файл (а вообще я привык переключаться между табами мышкой). Ну а клавиша для поиска — вопрос привычки (меня ctrl+shift+g не напрягает, a ctrl+F я очень редко пользуюсь). Лично я меняю в eclipse только 2 комбинации клавиш — делаю удаление строк по ctrl+Y (ибо привык к Delphi и bred3) и redo по ctrl+shift+Z (ибо конфликтует с предыдущим).
                          +4
                          Автор, да вы — маньяк! Третий пост за сутки! А говорили: «не робот»! =)
                          Спасибо за статьи, интересно читать! ;)
                            +1
                            Да ладно, написать пост — минут тридцать.
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Специфика задачи.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  +1
                                  Задача была одна и та же. Просто именно в данной конкретной задаче Java жрёт очень много памяти.
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Всего лишь на 9 мегабайт. Оверхед по памяти на джаве есть в олимпиадных задачах, но не на порядки точно.
                                0
                                У меня вопрос. Какие ОС любят устроители контестов?
                                  +1
                                  Региональных — Windows XP на компах соревнующихся и какую-то винду на проверяющем серваке. На финале — Linux не-знаю-что.
                                  0
                                  Почему Java vs C++? Это же совершенно разные языки для совершенно разных областей. Почему не Java vs C#?
                                    0
                                    Среди доступных языков ACM ICPC, C# вроде как нету.
                                      0
                                      C# пока не очень популярен в олимпиадной среде. Он есть только на топкодере и паре архивов задач
                                      0
                                      Интересно зачем придумывать отвлеченную историю про профессора и.т.д., а потом во входных данных писать, что число не должно превышать 10 в 9й степени. То есть тратят время на ненужную чепуху или я не прав?
                                        +3
                                        Это специфика олимпиадных задач — надо уметь вычленять только главное. Сам видел задачи на полный лист А4, написанные высокохудожественным языком, где вся суть могла уместиться в три строки :)
                                          +1
                                          Так интереснее!
                                          Бывает перегибают палку (см. задачу 1088 на acm.timus.ru), но в целом бывает даже смешно )
                                          Почитайте на том же acm.timus.ru задачи с одного и того же контеста, там зачастую развивается сюжет со своими главными героями от задачи к задаче =)
                                            0
                                            Чтобы было интереснее и непонятнее. Так, в этом году в CBOSS была задача, где давались излишние данные, которые при решении абсолютно никак не учитывались.

                                            А квинтэссенцией была идея нанять для написания текстов профессионального психолога. Чтобы люди реально боялись писать задачу на сложение 2 чисел.

                                            Кстати, с этим есть действенный способ борьбы. Как можно убедиться по ссылке, всегда в конце задачи идёт описание формата входных и выходных данных и примеры. Так вот, начинать чтение надо с них (и с ограничений по времени/памяти). Если там значения пугающие, то тогда надо задуматься =)
                                            +6
                                            с каких это по Microsoft Visual Studio 2005 Express Edition, C/C++ считается устаревшей?
                                              0
                                              Опередили :)
                                                0
                                                Компилятор 2005й не слишком соответствует стандарту. И писать в ней, по крайней мере олимпиадные задачи — гораздо менее удобно, чем в поздних версиях. Возможно, слово «Морально» было лишним, но сути не меняет — версия старая.
                                                  0
                                                  А судья все равно на gcc работает :)
                                                  Вроде мелочь, а вещи на вроде int64 vs long long и pragma с установкой размера стека много кровушки попортили.
                                                    0
                                                    Да, много слышал. К счастью, сам придерживался стандарта всегда.
                                                    +4
                                                    >> гораздо менее удобно, чем в поздних версиях.
                                                    А что именно в 2008 стало более удобным для native с++, чем в 2005?
                                                      0
                                                      >Компилятор 2005й не слишком соответствует стандарту.

                                                      Я это слышу начиная с MSVS 5.0 %)
                                                      Праздное любопытство: а в более поздних версиях что-то изменилось?
                                                        0
                                                        Между 6 и последующими версиями изменения были колоссальными)
                                                        Достаточно вспомнить, что 6 версия по умолчанию компилила такой код:
                                                          0
                                                          for (int i = 0; i < n; ++i) {
                                                          //...
                                                          }
                                                          printf("%d\n", &i);
                                                            0
                                                            Да, ещё нельзя было дважды определять переменную:

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

                                                            Я знаю людей, у которых из-за долгого использования 6 студии выработалась вредная привычка определять все счётчики циклов заранее в начале функции :)
                                                              0
                                                              Собственно, это «фишки» из одной и той же оперы: область видимости переменной. И в примере winger-а, и в Вашем примере переменная i, объявленная внутри объявления цикла, оказывалась принадлежащей не области видимости цикла, а области «уровнем выше». Поэтому первый код был вполне рабочим, а второй — наоборот :)
                                                                +1
                                                                кстати из-за этого появился такой креатив :)))

                                                                if (1) for (int i =…
                                                    +3
                                                    Насчет устарелости MS VS — в контексте C/C++ 2005 и 2008 студии не особо отличаются, а если не лезть в GUI, то и Express от полной не сразу отличить :)
                                                      –1
                                                      Замечательная информативная подборка статей!
                                                      Спасибо.
                                                      Наконец-то можно показать руководству факультета о бесперспективности обучения на Delphi 7.
                                                        0
                                                        Справедливости ради — перспективность обучения не зависит от использования ide/языка на соревнованиях ACM.
                                                        gvsmirnov, в одном из сегодняшних постов вы писали, что тема взаимоотношения спортивного и «промышленного» программирования уже заезжена. Можете показать, где почитать об этом?
                                                          0
                                                          Практически в каждом топике блога Спортивное программирование можно отыскать кучу комментов.
                                                          Но я имел в виду не заезженность, а холиварность.
                                                            +1
                                                            Хорошо.
                                                            А вы можете написать о том, как приобретённые в соревнованиях навыки помогли вашим знакомым в реальной работе?
                                                              0
                                                              Я подумаю.
                                                        0
                                                        Решение на C++:
                                                        #include <iostream>
                                                        #include <vector>
                                                        #include <algorithm>
                                                        
                                                        using namespace std;
                                                        
                                                        int main()
                                                        {
                                                            int N, M, t, count = 0;
                                                            cin >> N;
                                                            
                                                            vector<int> prof(N);
                                                            while(N--) cin >> prof[N];
                                                            
                                                            sort(prof.begin(), prof.end());
                                                            
                                                            cin >> M;
                                                            while (M--)
                                                            {
                                                                cin >> t;
                                                                if (binary_search(prof.begin(), prof.end(), t))
                                                                    ++count;
                                                            }
                                                            
                                                            cout << count;  
                                                            return 0;
                                                        };
                                                        
                                                          +1
                                                          Возможно я чего-то не понял, но нужно ли сортировать вектор prof, если в условии сказано, что данные отсортированы по условию?=)
                                                            0
                                                            Пардон, читал условие по диагонали)
                                                          –2
                                                          Предлагаю не изобретать велосипед и использовать Scanner для чтения входных данных
                                                            0
                                                            Об это далее расскажу. Можете заглянуть в исходники Scanner и понять, почему некоторые ругают Java за тормознутость.
                                                              0
                                                              хм, неужели ввод будет узким местом?
                                                                +1
                                                                Ввод всегда узкое место:)
                                                                  +2
                                                                  да ну ладно… вывод еще могу понять, но ввод?
                                                                    0
                                                                    Когда нужно прочитать несколько мегабайт, а время сильно ограниченно — конечно, это узкое место.
                                                              +1
                                                              Scanner для большей гибкости реализован на RegExp'ах, из-за этого страдает производительность
                                                                0
                                                                Этой гибкости можно было добиться и без них. Вообще, очень большая часть функций, работающих со строками, в текущей версии JDK реализована плоховато. Стоит уповать на Java 7.
                                                                  0
                                                                  Гибкость в scanner нужна для простоты локализации (чтобы при смене локали не менялся код, а только сами регэкспы для парсинга ввода)
                                                                    0
                                                                    Разница же не настолько велика. Всего-навсего разделители в числах, деньгах, даты и ещё что-нибудь такое. Для разделителя, скажем, можно было спец. константу завести, и так далее. Впрочем, что спорить — это ничего не изменит)
                                                                0
                                                                Сканер можно использовать лишь тогда, когда размер входных данных крайне мал, когда же он пропорционален размерности задачи — ни в коем разе. Падать будет по времени, не успев ещё файл дочитать.
                                                                0
                                                                Ну или с использованием деревьев:

                                                                #include <iostream>
                                                                #include <set>
                                                                
                                                                using namespace std;
                                                                
                                                                int main()
                                                                {
                                                                    int N, M, t, count = 0;
                                                                    cin >> N;
                                                                    
                                                                    set<int> prof;
                                                                    while(N-- && cin >> t) prof.insert(t);
                                                                    
                                                                    cin >> M;
                                                                    while (M-- && cin >> t)
                                                                        count += prof.count(t);
                                                                    
                                                                    cout << count;  
                                                                    return 0;
                                                                };
                                                                
                                                                  0
                                                                  Хм… А буст не дают использовать? Visual Assist? Вообще иметь грамотно настроенную среду (настройка кнопок, отладка) критично для олимпиадного типа задач.

                                                                  Когда-то давно участвовал в олимпиадах ACM, но как не нравился мне этот процесс. Задрачивание типовых алгоритмических задачек не имело ничего общего к тому программированию которым бы я хотел заниматься.
                                                                    0
                                                                    Нет, буста, конечно же, нет. Если войдёт в стандарт — то через некоторое время появится, я думаю. VisualAssist нет. Вообще, IDE — коробочная.
                                                                      +1
                                                                      Среда — далеко не самое главное. Например Топкодеровские контесты я пишу прямо в арене (правда с плагином для локального тестирования), которая умеет лишь базовые функции (в основном подсветка синтаксиса).

                                                                      А отлаживать дебаггером вообще почти во всех случаях противопоказано (в ACM лучше освободить компьютер для другого человека и вычитывать код по распечатке, а в личных контестах во многих случаях гораздо быстрее получается отладить с помощью грамотного debug-output'а)
                                                                        0
                                                                        А вы на чем пишите? В С++, на сколько я помню, дебаггер не может вычислить выражение, если используются коллекции или #define'ы (не все еще поняли прелести const). Но в java такой проблемы нет. Соотвественно вместо debug-output'a можно использовать debug-функции (и .toString()) проверяющие инварианты и/или подсчитывающие важную информацию в выражениях или условиях для точек останова. Единственная проблема — условные точки останова работают очень медленно. Их можно применять только на маленьких тестах. На больших тестах я использую if (условие точки останова) { System.out.print("");} и ставлю брейкопинт на print (можно ли считать это отладочной печатью? ;) ). Впрочем, случаи в которых быстрее всего разобраться с помощью грамотного debug-output'a тоже бывают. А в ACM отладочная печать просто необходима для экономии on-line времени.
                                                                          0
                                                                          Андрей, а не проще conditional breakpoint использовать? И VS, и Eclipse, если я всё не позабыл, это умеют.
                                                                            +1
                                                                            Говорю же — медленные они (что в VS, что в Eclipse). Когда количество проходов через точку останова не большое — использую.
                                                                              +1
                                                                              По-моему, вместо conditional breakpoint-ов можно быстрее написать выражение вида:

                                                                              if (some_expression) {
                                                                                  bool stopHere = true;
                                                                              }
                                                                              

                                                                              и поставить обычный breakpoint. И тормозить не будет.

                                                                              Главное — потом не забыть убрать это, а то могут обвинить в написании индусского кода :)
                                                                        0
                                                                        Для тренировок дома настроенная среда — хорошо. Но на сколь бы то ни было важном контесте (будь то хоть 1/4 ACM ICPC, хоть Открытая Всесибирская) у пользователей в доступе голый компьютер с системой и средами, установленными с нуля. Ну и настройки сделаны для компиляции из командной строки. Всё. Больше — ничего. И всю удобную настройку приходится делать за 5 минут до начала контеста. Мы в своё время насобачились на скорость набивать стаб и настраивать перспективу в Эклипсе.
                                                                        +1
                                                                        Замечание автору — никогда, никогда, никогда не используйте TreeSet и TreeMap. Я использую java в спортивном программировании уже не первый год и ни разу не сталкивался с задачами где они нужны. Даже на работе я ни разу не использовал эти классы. В 99% случаев вместо них нужно использовать на много более быстрые HashSet и HashMap, а в оставшемся 0.9% случаев — деревья отрезков после сжатия координат или бинарный поиск после сортировки.
                                                                          0
                                                                          TreeSet и TreeMap поддерживают поиск минимального/максимального элементов и headSet/tailSet, так что их можно использовать в качестве PriorityQueue с возможностью удаления или в некоторых случаях вместо самодельного BST
                                                                            0
                                                                            Лично я PriorityQueue пишу не приходя в сознание (сказывается многократное написание heap sort в паскале) и использовать для этого тормозные TreeSet и TreeMap мне бы никогда не пришло в голову. Ну и начиная с версии 1.6 в java есть стандартный класс для PriorityQueue.
                                                                              0
                                                                              тормозные TreeSet и TreeMap

                                                                              чочо?
                                                                            0
                                                                            Ну я бы на вашем месте так горячо не утвержлал «никогда». Вообще хороший вопрос для собеседования — В каких случаях бинарное дерево эффективнее чем хеш-таблица, не в джаве, а вообще теоретически.

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

                                                                          Самое читаемое