Подготовка к региональной олимпиаде

[New man]

Я уже 2 года участвую в региональных олимпиадах, но всегда без должной подготовки. У нас в районе нормальных учителей информатики, способных обучить программировать на этом уровне нет, а учителя математики уже достали меня со своей подготовкой к ЕГЭ, а там умение составлять математические модели не нужно, а на олимпиаде просто необходимо.
В общем, я решил попросить помощи у вас, дорогие форумчане. Я буду пытаться решать задачи предыдущих олимпиад, и в случае успеха выкладывать их сюда. В таких случаях, пожалуйста, производите конструктивную критику и найдите возможные ошибки.
Если же у меня не будет получаться, я буду просить у вас помощи, а именно подскажите верный ход решения.


Первая задача:

Ограничения: время – 2s/Java 4s, память – 256MiB Послать решение Посылки Темы Где Обсудить (0)
Вася готовит инвентарь для ролевой игры. В игре должны принять участие n игроков, каждый из которых будет изображать персонажа фантастического мира. В процессе игры каждый персонаж будет обладать некоторым уровнем x, который представляет собой целое число от 1 до m.
Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок — k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых значков и b красных значков, чтобы сумма (a + bk) была равна x. При этом персонажу не разрешается иметь более чем (k – 1) белых значков.
Значки для игры готовятся заранее, однако уровни персонажей заранее неизвестны. Для успешного проведения игры всем персонажам необходимо выдать соответствующее их уровням количество значков. Возникает вопрос: какое минимальное суммарное количество значков необходимо подготовить для успешного проведения игры при любых уровнях участвующих персонажей.
Требуется написать программу, которая по заданным числам n, m и k вычисляет минимальное количество значков, которое необходимо подготовить для успешного проведения игры.
Формат входного файла
Входной файл содержит расположенные в одной строке три целых числа: n, m и k (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 1 ≤ k ≤ 105).
Формат выходного файла
В выходном файле должно содержаться одно целое число — минимальное количество значков, которое требуется подготовить.

тут все просто и я составил формулу, по который можно вычислить кол-во шариков

balls:=n*((k-1)+m div k)

[New man]

Формулировка

Ограничения: время – 2s/Java 4s, память – 256MiB Послать решение Посылки Темы Где Обсудить (2)
Развлекательный телеканал транслирует шоу "Колесо Фортуны". В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.
Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X.

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду.
Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш.
Формат входного файла
Первая строка входного файла содержит целое число n — количество секторов колеса (3 ≤ n ≤ 100).
Вторая строка входного файла содержит n положительных целых чисел, каждое из которых не превышает 1000 — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.
Третья строка содержит три целых числа: a, b и k (1 ≤ a ≤ b ≤ 109, 1 ≤ k ≤ 109).
Формат выходного файла
В выходном файле должно содержаться одно целое число — максимальный выигрыш.

вот мое решение

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n, a,b,k,i:Longword;
  arr:array of  word;//сектора
  p1,p2:word;
function maxarr(d,s:longword):word;
var i: integer;
begin
  result:=0;
  for i:=d to s do if arr[i]>result then result:=arr[i];
end;
function po_chas:word;
var i:longword;
begin
   result := maxarr(a div k,b div k);
end;
function protiv_chas:word;
var a_New:longword;
begin
  if a<k then a_New:=k+1 else a_New:=a;   // для тех случаевминимальная //скорость слишком мала, чтобы преодолеть рубеж, а большая(b) для //этого достаточна
  result:= maxarr(n-1-b div k,n-a_new div k);
  if (a<=k)and (arr[0]>result)then result:=arr[0];
end;
procedure External_Speed_To_Normal_Speed; {скорости приводит в состояние, когда круг уже несколько раз провернулся вокруг своей оси}
begin
  a:=a-(a div (n*k)*n*k);
  b:=b-(b div (n*k)*n*k);
end;
begin
  AssignFile(input,'f1.txt');
  assignfile(output,'f2.txt');
  readln(n);
  setlength(arr,n);
  for i:=0 to n-1 do read(arr[i]);
  read(a);
  read(b);
  read(k);
  { TODO -oUser -cConsole Main : Insert code here }
  
  if (b div (k*n)>=1)and(b-a>n*k) then writeln(maxarr(0,n-1)) // если мы //можем выбрать любой элемент
    else
    begin
      External_Speed_To_Normal_Speed; //проворачиваем круг несколько //раз
      p1:=po_chas;
      p2:=protiv_chas;
      if p1>p2 then writeln(p1) else writeln(p2);
    end;


end.

По-моему, задача сводиться к тому, чтобы найти максимальный элемент на некотором куске массива.
Сейчас начну третью

[DiemonStar]

Условие лучше оформить тегами цитаты, а не кода - тогда переносы работать будут...

[Utkin]

ОФТОП Всегда бессили такие вот задания:

Юный участник шоу заметил

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

Вася готовит инвентарь для ролевой игры.

Ну, Вася...

В игре должны принять участие n игроков

Да у них там по-ходу оргия намечается со значками.

[DiemonStar]

Вообще не понимаю, чего сложного в данной задаче:

количество секторов, на которое повернётся барабан, вычисляется по формуле:
L = Int(V/K), где v - угловая скорость, а K - момент торможения на каждый из секторов.
т.е. вычисляем L(a) и L(b) по формуле и смотрим условие L(b)-L(a) >= N - тогда выигрышем будет максимальное значение на колесе, иначе проводим сравнение:
L(a) mod N - L(b) mod N > 0, то опять-таки выигрышем будет максимальное значение на колесе, иначе это будет сектор номер L(b) mod N
и не нужны никакие циклы (при условии сортировки значений в секторах по возрастанию )

[New man]

Сообщение от Utkin

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

Ну, Вася...
Да у них там по-ходу оргия намечается со значками.

На шоу мозги отключаются, так что этот юный участник шоу походу сидит перед телевизором

А Вася может поскромничать: только одну девушку позвать.


DiemonStar, я же говорю, подготовки к созданию мат моделей у меня нет.
Первую формулу я получил
L(b)-L(a)>=N

объясните, пожалуйста, как вы получили последующие.

[DiemonStar]

L = Int(V/K)

у вас есть угловая скорость движения барабана. Он остановится, когда скорость упадёт до нуля. Если бы торможение действовало постоянно, то это произошло бы по аналогичной формуле, но без вычисления целой части, а в дискретном замедлении важно лишь целое количество торможений - остатка угловой скорости не хватит для перехода в новый сектор. Вот таким образом мы вычисляем количество "сеансов торможения" (т.е. переходов между секторами).

з.ы. здесь больше физика, чем математика...

L(a) mod N - L(b) mod N > 0

Согласитесь, в приведённом условии задачи появляется вариант, когда барабан может сделать полный оборот и более и этот случай тоже нужно учесть. Поэтому формула трактуется так:
- если количество секторов (без учёта полных оборотов) при меньшем пути будет больше количества секторов (без учёта полных оборотов) при большем пути - в этом случае будет браться значение максимального сектора на барабане

т.е. проверки (во избежание косяков) нужно делать так:
1. IF L(b) - L(a) >=N - разница между путями больше одного оборота
2. ELSE IF L(a) mod N > L(b) mod N - финальная точка большего пути лежит в меньшем секторе
3. ELSE обработка варианта, когда обе точки находятся на одном обороте и сектор большего пути находится дальше

[New man]

2. ELSE IF L(a) mod N > L(b) mod N - финальная точка большего пути лежит в меньшем секторе

По условию этого быть не может


Третья задача

. Форматирование текста

Ограничения: время – 2s/Java 4s, память – 256MiB Послать решение Посылки Темы Где Обсудить (0)
Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: ",", ".", "?", "!", "-", ":" и "’" (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из строчных и заглавных (прописных) букв латинского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк.
Дальнейшее использование исходного текста предполагает его форматирование, которое осуществляется следующим образом. Каждый абзац должен быть разбит на строки, каждая из которых имеет длину не больше w. Первая строка каждого абзаца должна начинаться с отступа, состоящего из b пробелов. Слова внутри одной строки должны быть разделены ровно одним пробелом. Если после слова идет один или несколько знаков препинания, они должны следовать сразу после слова без дополнительных пробелов. Если очередное слово вместе со следующими за ним знаками препинания помещается на текущую строку, оно размещается на текущей строке. В противном случае, с этого слова начинается новая строка. В отформатированном тексте абзацы не должны разделяться пустыми строками. В конце строк не должно быть пробелов.
Требуется написать программу, которая по заданным числам w и b и заданному тексту выводит текст, отформатированный описанным выше образом.
Формат входного файла
Первая строка входного файла содержит два целых числа: w и b (5 ≤ w ≤ 100, 1 ≤ b ≤ 8, b < w).
Затем следует одна или более строк, содержащих заданный текст. Длина слова в тексте вместе со следующими за ними знаками препинания не превышает w, а длина первого слова любого абзаца вместе со следующими за ним знаками препинания не превышает (w – b).
Размер входного файла не превышает 100 Кбайт. Длина каждой строки во входном файле не превышает 250.
Формат выходного файла
Выходной файл должен содержать заданный текст, отформатированный в соответствии с приведенными в условии задачи правилами.

Пример ввода

20 4
Yesterday,
All my troubles seemed so far away,
Now it looks as though they're here to stay,
Oh, I believe in yesterday.

Suddenly,
I'm not half the man I used to be,
There's a shadow hanging over me,
Oh, yesterday came suddenly...

Пример вывода

Yesterday, All
my troubles seemed
so far away, Now it
looks as though
they' re here to
stay, Oh, I believe
in yesterday.
Suddenly, I' m
not half the man I
used to be, There' s
a shadow hanging
over me, Oh,
yesterday came
suddenly...

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

[New man]

Попытка решения(Внимание!!! Быдлокод - опасно для мозга!!!)

program Project1;

{$APPTYPE CONSOLE}
const lengthSpec=8; //кол-во знаков препинания и пр.
  Spec_symbols: array [1..lengthSpec]of char = ('.', ',', '?', '!', '-', ':', #39, ' ');
  Spec_symbols_set:set of char=['.', ',', '?', '!', '-', ':', #39] ;
var w,b,last: word;
  i,j,m,{счетчики} Abzac_Count:longword;
  strs:array of string;
  {как бы массив, каждый элемент которого - абзац}
  pointer_j:^longword;
  s:string;
  f1,f2:textfile;
begin
  Assignfile(f1, 'f1');
  AssignFile(f2,'f2');
  reset(f1);
  rewrite(f2);
  readln(f1,w,b);
  Setlength(strs,1);
  strs[0]:='';
  pointer_j:=@j;
  i:=0;
  writeln('we started');
  readln;

  // читаем из файла массив строк

  while not eof(f1) do
    begin
      readln(f1,s);
      if s<>'' then strs[i]:=strs[i]+' '+s  // пробел нужен, чтобы случайно не сцепить два слова
        else
        begin
          setLength(strs, i+2);
          inc(i);
          strs[i]:='';
        end;
    end;
  closefile(f1);
  writeln('We has read text');
  readln;
  Abzac_Count:=i;//Я привык считать с нуля

   // убираем ненужные повторения символов, вроде двух подряд идущих пробелов
   // добавляем символы после заяпятых и прочее
   for i:= 0 to Abzac_Count do
     begin
     for j:=1 to lengthSpec do
      while pos(' '+Spec_symbols[j],strs[i])>0 do
          Delete(strs[i],pos(' '+Spec_symbols[j],strs[i]),1);
     for j:=1 to length(strs[i])-1 do
        if strs[i][j] in Spec_symbols_set then
            if not(strs[i][j+1] in (Spec_symbols_set+[' ']))and (strs[i][j+1] in ['A'..'Z','a'..'z','0'..'9'])then
               begin Insert(' ',strs[i],j+1); dec(pointer_j^); end;

     end;
  writeln('we deleted symbols');
  readln;
  s:='';
  for i:=1 to b do s:=s+' ';
  for i:=0 to Abzac_Count do
    begin
       if  strs[i][1]=' ' then delete(strs[i],1,1);
       strs[i]:=s+strs[i];
       j:=0;
       m:=0;
       while m<length(strs[i]) do
          begin
            while (j<w)and (m<length(strs[i])) do
              begin inc(j);inc(m); end;
            if (m<length(strs[i])) then
            if (strs[i][j+1] in (['A'..'Z','a'..'z','0'..'9']+Spec_Symbols_Set))and
                (strs[i][j] in (['A'..'Z','a'..'z','0'..'9']+Spec_Symbols_Set)) then
              begin
                while strs[i,j] in (['A'..'Z','a'..'z','0'..'9']+Spec_Symbols_Set) do
                  begin dec(j);dec(m);end;
                delete(strs[i],j,1);
                insert(#13#10,strs[i],j);// перевод строки
                inc(j,2);inc(m,2);
              end else if (strs[i][j+1] =' ') then 

             else
              if m<length(strs[i]) then
               begin
                delete(strs[i],j,1);
                insert(#13#10,strs[i],j);
                inc(j,2);inc(m,2);
               end

          end;

    end;
  writeln('We make string');
  readln;
  s:=strs[1];
  for i:=0 to Abzac_Count do
    writeln(f2,strs[i]);
  flush(f2);
  Closefile(f2);
  writeln('That''''s all',strs[0],strs[1]);
  readln;
end.

работает только разделение на абзацы,
Каждый абзац - элемент массива strs. Планировал решить задачу так - там где надо перевести строку, добавить символы #13#10, но не получилось

[Poma][a]

У нас в районе нормальных учителей информатики, способных обучить программировать на этом уровне нет

Возможно они есть, но Вы о них не знаете. (Например кружок в каком-нить центре дополнительного образования, или так же кружок, который ведет какой-нибудь учитель информатики в школе, в универе (я, например, хожу к преподу из ПЕДа))

Да, кстати, Вы нацелены только на практику? (теорию Вы преодолеваете в легкую?)
Или просто логические задачи (1 этап) у Вас отсутствует.
Так же есть очень много сайтов с олимпиадной тематикой. Навскидку acmp.ru , или вот informatics.mccme.ru (вот он мне очень нравится там даже баллы начисляются не за полностью правильное решение, а за кол-во пройденных тестов)