Форум DL

Мой профиль

у меня не получается решить задачу "Разложение на простые множители" помогите пожалуйста !

Мой профиль

Я абсолютно не понимаю задачу "Числа с делителями 2, 3, 5"631. Помогите, пожалуйста.

Мой профиль

Всё, решила))

Мой профиль

Я не могу решить задачу "iCow". Подскажите, пожалуйста, как приравнять конкретное число из массива к нулю.

Мой профиль

У меня ответ такой же, как в тесте, но задача не засчитывается.

"iCow "60877 Original
30.5 14:16 08_Jan. iCow 0 / 401 не пройден 1-й тест (неверный ответ) D.PAS DelTA3 at Nit4 Turbo Pascal 7.0
30.5 14:15 08_Jan. iCow 0 / 401 не пройден 1-й тест (неверный ответ) D.PAS DelTA3 at Nit3 Turbo Pascal 7.0
30.5 14:15 08_Jan. iCow 0 / 401 не пройден 1-й тест (неверный ответ) D.PAS DelTA3 at Nit_server Turbo Pascal 7.0
30.5 14:09 08_Jan. iCow 0 / 401 не пройден 1-й тест (неверный ответ) D.PAS DelTA3(Beta) at NewIT Turbo Pascal 7.0

Мой профиль

Попробуй отправлять не на Turbo Pascal 7.0 а на FP Win v2.2.0

Мой профиль

Спасибо, Паша за совет.
Только НАШИХ проблем (системы тестирования) это не снимает ...
Он проверяла в Turbo Pascal и отсылала в Turbo Pascal.

Мой профиль

Михаил Долинский:

Спасибо, Паша за совет.
Только НАШИХ проблем (системы тестирования) это не снимает ...
Он проверяла в Turbo Pascal и отсылала в Turbo Pascal.

Скорее всего система тестирования здесь ни при чем.
Меняем readln на read
read(n,t);
for i:=1 to n do read(a[i]);
и первый тест проходит и на Turbo Pascal.
На файлы с тестами надо внимательно посмотреть скорее всего.

Мой профиль

"Dining Cows (Bronze)"61263 Ionescu Victor and Brian Dean, 2007

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

Мой профиль

Прежде всего, для USACO задач у нас есть оригинальные разборы решений вот здесь

Индекс форума ->Олимпиадное программирование ->USACO Analyses
http://dl/NForum/forum/list/21.dl
Разбор задачи всегда содержит и исходный текст одного или нескольких решений этой задачи.

Вот ссылка на оригинальный разбор этой задачи:
http://dl/NForum/posts/topicshow/488.dl?postid=1817#1817

Основная идея заключается в том, что надо С НАЧАЛА массива (слева) переворачивать все двойки в единицы, а С КОНЦА массива (справа) переворачивать все единицы в двойки.

Вопрос - а ДО КАКОЙ позиции 2 заменять на 1 слева, а 1 заменять на 2 справа?

Ответ на такие вопросы часто ищется ПЕРЕБОРОМ ВСЕХ возможных положений этой позиции.

А какие возможны положения?
От 1 до n+1, то есть
первая двойка может появится в позиции 1,2, ..., n+1
(первая двойка в позиции n+1 означает, что все n цифр - единицы)

Мы для каждой позиции k от 1 до n+1
считаем, сколько двоек нужно перевернуть в единицы до позиции k-1 включительно и сколько единиц нужно перевернуть в двойки, после позиции k-1 и до конца.

Ответ - МИНИМАЛЬНОЕ количество переворотов, для всех возможных k.

var
  a             : array [1..30000] of longint;
  i,k,n,j,t,min : longint;
begin
  assign(input,'diningb.in'); reset(input);
  assign(output,'diningb.out'); rewrite(output);
  read(n);
  for i:=1 to n do read(a[i]);
  min:=n;
  for k:=1 to n+1 do
    begin
      t:=0;
      for i:=1 to k-1 do
        if a[i]=2 then inc(t);
      for i:=k to n do
        if a[i]=1 then inc(t);
      if t<min then min:=t;
    end;
  writeln(min);
  close(input); close(output);
end.

Такое решение проходит 9 тестов и не проходит два последних теста по времени.
Добавление строки
{$r-} в начало программы (для отключения контроля индексов)
и отсылка на Delphi на тест-машину Delta3 at NewIT
обеспечивают прохождение 10-го теста, но 11-ый тест все равно не пройден по времени.

Почему?

Всего в массиве 30 000 элементов, а у нас двойной ВЛОЖЕННЫЙ цикл - что дает порядка 30 000 * 30 000 = 900 000 000 операций. (o(n^2))

Для прохождения как правило нужно ориентироваться на 60 миллионов операций.

Можно ли наше решение УСКОРИТЬ.
ДА - немного усложнив.

Двойной цикл можно заменить на ТРИ одинарных.
И сложность станет порядка 30 тысяч операций (o(n))...

Первый цикл будет считать количество замененных c НАЧАЛА двоек до позиции k включительно

  k2[0]:=0;
  for k:=1 to n+1 do
    if a[k]=2
      then k2[k]:=k2[k-1]+1
      else k2[k]:=k2[k-1];

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

  k1[n+1]:=0;
  for k:=n downto 1 do
    if a[k]=1
      then k1[k]:=k1[k+1]+1
      else k1[k]:=k1[k+1];

А уже третий цикл будет искать МИНИМАЛЬНУЮ из сумм заменных двоек и единиц, если первая двойка стоит на позиции k

  min:=n;
  for k:=0 to n do
    if k2[k]+k1[k+1]<min then min:=k2[k]+k1[k+1];

И полное решение, которое проходит все тесты, выглядит так:

{$r-}
const
  MaxN = 30000;
var
  a             : array [1..MaxN] of byte;
  k1,k2         : array [0..MaxN+1] of longint;
  i,k,n,j,t,min : longint;
begin
  assign(input,'diningb.in'); reset(input);
  assign(output,'diningb.out'); rewrite(output);
  read(n);
  for i:=1 to n do read(a[i]);
{
  k1[k]  - количество 1 заменных на 2 ПОСЛЕ позиции k
  k2[k]  - количество 2 заменных на 1 ДО    позиции k включительно
}
  k2[0]:=0;
  for k:=1 to n+1 do
    if a[k]=2
      then k2[k]:=k2[k-1]+1
      else k2[k]:=k2[k-1];

  k1[n+1]:=0;
  for k:=n downto 1 do
    if a[k]=1
      then k1[k]:=k1[k+1]+1
      else k1[k]:=k1[k+1];

  min:=n;
  for k:=0 to n do
    if k2[k]+k1[k+1]<min then min:=k2[k]+k1[k+1];

  writeln(min);
  close(input); close(output);
end.

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

Мой профиль

"Решение вручную"60063 Добрыдин Владислав, июль 2007
Я эти формулы не очень понимаю.

Мой профиль

Добавлено обучение для задачи "Бег на 100 метров" (для Анастасии Андрухович).
Надеюсь, с формулами разберешься - пробуй.

Мой профиль

"Числа Фибоначчи"1059 Гом. обл. 2002 день2 младшие

Я прошла всё обучение и всёравно не вру билась в эту задачу

Это всё до чего я додумалась:

readln(n);
for i:=1 to n do f:=a[n-2]+a[n-1];
writeln(f);

Мой профиль

"Бег на 100 метров"3766
Спасибо!Я решила эту задачу благодоря вам!

Мой профиль

"Сумма"62090 Добрыдин Владислав
(Мистер Слон).
Я не могу решить эту задачу.