Эксперимент

Очевидно, что данную задачу следует решать моделированием процесса проведения эксперимента. Для хранения текущей информации о газах в колбах будем использовать два массива a и b. В a[i] будем хранить общее количество газа, который первоначально находился в колбе с номером i. b[i] будем использовать для запоминания номера газа, располагаемого в колбе с номером i. Первоначально b[i]=i, в то время как a[i] соответствует данным второй строки входного файла.

На каждом шаге будем рассматривать две колбы, которые необходимо объединить. Пусть g1 и g2 – номера объединяемых колб. Если газы в рассматриваемых колбах совпадают, то ничего не изменится (если b[g1]=b[g2], в частности, когда мы имеем только одну колбу: g1=g2). Для определенности будем считать, что номер второго газа выше (в противном случае мы можем поменять g1 и g2), т.е. b[g2]>b[g1]. Далее, во избегании путаницы и возможных ошибок, проще использовать дополнительные переменные b1 и b2, в которых будем хранить первоначальные номера газов объединяемых колб. Понятно, что в процессе объединения газов в рассматриваемых колбах газ колбы g2 вытеснит газ колбы g1, что приведет к обнулению количества газа g1 (a[b1]=0) и увеличению объема газа колбы g2 на старое значение a[b1] (a[b2]=a[b2]+a[b1]). После переопределения объемов газов в массиве a следует изменить значения элементов массива b со старыми значениями b1 на значение b2, так как газ b2 полностью занял все колбы, в которых был газ с номером b1.

По завершении вышеописанного процесса объединения колб из m шагов в массиве a мы получим необходимые значения для формирования ответа. Таким образом, общий алгоритм решения данной задачи можно представить следующим кодом:

  read(n,m)

  for i=1..n{
    read(a[i])
    b[i]=i
  }

  while(m--){
    read(g1,g2)
    if(b[g1] <> b[g2]){
      if(b[g1]>b[g2]) g1^=g2^=g1^=g2
      b1=b[g1]; b2=b[g2]
      a[b2]+=a[b1]; a[b1]=0
      for i=1..n
	  if(b[i]=b1) b[i]=b2
    }
  }

  for i=1..n
    if(a[i]) writeln(i, ' ', a[i])

[Обсуждение] [Все попытки] [Задача]