Обсуждение некоторых задач, + сравнение уровня сложности(Россия И Украина) Опции

[Vinchkovsky]

Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу (хотя тогда, наверное, я знал несколько меньше, чем сейчас), а здесь сходу за пять минут накатал решение первой из предыдущего поста.

program Zadacha1;
uses Crt;
var c:boolean;
    a,b:string;
 function Sovmestimost(a,b:string):boolean;
 var len1,len2,i,ii,res:integer;
     aM,bM:array [1..20] of string;
     d3:boolean;
  begin
   res:=0;
   len1:=length(a);
   len2:=length(b);
   for i:=1 to len1 do aM[i]:=copy(a,i,1);
   for i:=1 to len2 do bM[i]:=copy(b,i,1);
   for i:=1 to len2 do
    for ii:=1 to len1 do
     if bM[i]=aM[ii] then begin res:=res+1; aM[ii]:=''; bM[i]:='*' end;
   if res=len2 then d3:=true else d3:=false;
   Sovmestimost:=d3
  end;
begin
clrscr;
writeln('Vvedite pervoe slovo');
readln(a);
writeln('Vvedite vtoroe slovo');
readln(b);
if length(a)>length(b) then c:=Sovmestimost(a,b) else c:=Sovmestimost(b,a);
if c=true then writeln('YES') else writeln('NO');
readln
end.

В общем, можно сделать все намного изящнее (напр., процедуру проверки, есть ли "меньшее слово в старшем", сравнить слова и применить процедуру на меньшем), но, так как в задаче ничего не сказано, делал все по проще, так что не судите строго

Ну а вот вторая:

program Zadacha2;
uses Crt;
const n=6;
type masyv=array [1..n] of integer;
var a,b:masyv;
    i,ii,x:integer;
begin
clrscr;
writeln('Vvedite 6 chusel');
for i:=1 to n do readln(a[i]);
for i:=1 to n-1 do
 for ii:=i+1 to n do
  begin
   if a[i]>a[ii] then
    begin
     x:=a[i];
     a[i]:=a[ii];
     a[ii]:=x
    end
   end;
if (a[1]+a[6]=a[2]+a[5])and(a[2]+a[5]=a[3]+a[4]) then writeln(a[1]+a[6])
 else writeln('N');
readln
end.

А это третья . Знаю, написано плохо в плане стиля, но на доработку и оптимизацию нет времени да и желания (главное, что верно, об чем я надеюсь).
Это верно, что этих чисел Армстронга так немного? Например, при н=2 нуль, при н=3 четыре (153,370,371,407), при н=4 три, а при н=5 нуль?

program zadaha3;
uses Crt;
var n,d5,k,ii:integer;
    min,max,i,control:longint;
    iText:string;
    iLetter:array [1..10] of string;
    iDigit:array [1..10] of integer;

function Stepin(x,y:integer):integer;
 var d1:integer;
     d2:integer;
  begin
   d2:=x;
   for d1:=1 to y-1 do d2:=d2*x;
   Stepin:=d2
  end;

function Minimal(n:integer):longint;
 var d3:integer;
     d4:longint;
  begin
   d4:=1;
   if n=0 then d4:=1 else for d3:=1 to n-1 do d4:=d4*10;
   Minimal:=d4
  end;


begin
 clrscr;
 writeln('Vvedite n');
 readln(n);
 min:=Minimal(n);
 max:=Minimal(n+1)-1;
 for i:=min to max do
  begin
   control:=0;
   str(i,iText);
   for ii:=1 to n do begin iLetter[ii]:=copy(iText,ii,1);
                           val(iLetter[ii],iDigit[ii],d5) end;
   for ii:=1 to n do control:=control+Stepin(iDigit[ii],n);
   if control=i then begin writeln(i); k:=k+1 end
  end;
 writeln('Vsego chusel Armstronga   ',k);
 readln
end.

Сообщение отредактировано: Vinchkovsky - 12.01.2007 10:21

[Айра]

так что не судите строго

Попробуй ввести в свою первую прогу "стст" и "стср" и посмотри, что она выдаст. Мне выдала "Mozhno". И в условии вроде не сказано, что слова не могут иметь одинаковое кол-во символов.
Так что, как мне уже говорили:

такие задачи в лоб не решаются

[Malice]

Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу (хотя тогда, наверное, я знал несколько меньше, чем сейчас), а здесь сходу за пять минут накатал решение первой из предыдущего поста.

Не переживай, все равно не правильно накатал (131, 231 к примеру)
Попробуй 4-ую порешай, первые 3 решаются в уме..

Сообщение отредактировано: Malice - 10.01.2007 15:07

[Michael_Rybak]

Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу

Особенно смешно слово "намного".

Ты ошибаешься. Задачи в России даже теоретически ничем не могут уступать задачам из Украины. Кроме того, второй этап - совсем уж не показатель, т.к. зачастую их составляют (а еще чаще - берут) совсем не те люди, которые состоят в комитете всероссийской/всеукраинской олимпиады.

В одном и том же городе (я, в частности, про Киев) районные олимпиады могут проходить на разных задач в разных районах; в прошлом году районная соломенского района была сложнее городской, потому что отвечали за это совершенно некомпетентные люди - просто взяли городские прошлых лет, и повыбирали задачи, у которых балл повыше.

P.S. В данном конкретном случае первые три действительно очень простые. А вот с четвертой (супер-решение которой, кстати, недавно показывал volvo) - похитрее.

[Vinchkovsky]

Айра, Malice, ну я же написал, что для упрощения сделал по умолчанию первое слово больше второго:

В общем, можно сделать все намного изящнее (напр., процедуру проверки, есть ли "меньшее слово в старшем", сравнить слова и применить процедуру на меньшем), но, так как в задаче ничего не сказано, делал все по проще, так что не судите строго

то есть, я показывал принцип, завтра поправлю и выложу полностью верное решение, если это принципиально. Ну а пока тестируйте при слово1>слово2.

Попробуй 4-ую порешай, первые 3 решаются в уме..

Я про это и говорил! На российских олимпидах большинство задач решаються в уме, ИМХО, где-то выложу наши задачи, вот и сравните. У нас в уме решается только первая А над последней подумаю, обязательно.

Michael_Rybak, у нас в городе (Львовской области) стабильно все задачи на одном уровне и тяжелее от этих. Да и во всей области задачи ОДИНАКОВЫЕ со всех олимпиад, и складает их какой-то институт ЛОИППО (что-то связано с последипломной учебой). Это все мое личное мнение. Если сделал поспешное заключение, сравнивая лишь одну рос.олимпиаду, то извините. Постараюсь выложить наши задачи, сравните.

И я знаю про недоработки в своих задачах: громоздкий код, большее слово должно быть первым(з1), очень долго считает при н больше 7(з.3);извините, я это постараюсь исправить (задачи делал на скорую руку).

to All - допустился досадной очепятки, вместо НАМОГО должно быть НЕМНОГО, а не намного (хотя последнее, в принципе, вернее)
____________________________________________________________________________
Вот к примеру вторая задача из четырех, 20 баллов (всего-130)

Городок состоит из n домов, которые стоят вдоль прямого шоссе на одном расстоянии один от одного. В городке проводят телефонное подключение, в каждом доме нужно поставить k (0<=k<=30000).
В первом рядке файла TEL.DAT содержится количество домов (1<=n<=1000). В следующем рядке через пропуск - количество телефонов, которые должы быть установлены в домах.
Вывести на экран и в первый рядок файла TEL.SOL номер дома, в котором нужно поставить АТС, чтобы общее количество кабеля от каждого телефона к АТС было минимальным. Если таких домов несколько, то написать их в порядке увеличения черех пропуск.
Каждый телефон соединен отдельным кабелем. Если телефон находится в том доме, что АТС, то считать, что кабеля не ведем.
Пример входных данных:
5
1 2 3 2 1
Пример выходных данных:
3
_______________________________________________________________________

Может я и ошибаюсь, но как на меня, то это небо и земля в сравнении с вашей второй задачей

Сообщение отредактировано: Vinchkovsky - 10.01.2007 18:28

[мисс_граффити]

а можно условия задач, код к которым содержится в первом сообщении?

[Michael_Rybak]

Michael_Rybak, у нас в городе (Львовской области) стабильно все задачи на одном уровне и тяжелее от этих. Да и во всей области задачи ОДИНАКОВЫЕ со всех олимпиад, и складает их какой-то институт ЛОИППО (что-то связано с последипломной учебой).

Ну вот во львовской - так, а в других - по разному. Я думаю, что наиболее показательны городские/областные и всероссийские/всеукраинские. Кроме того, сложность, когда речь идет о задачах уровня IOI и выше, не самое ценное качество; главное, на мой взгляд, в задаче - свежесть, оригинальность. А сложность можно получать разными путями.

Вот к примеру вторая задача из четырех, 20 баллов (всего-130)

Городок состоит из n домов, которые стоят вдоль прямого шоссе на одном расстоянии один от одного. В городке проводят телефонное подключение, в каждом доме нужно поставить k (0<=k<=30000).
В первом рядке файла TEL.DAT содержится количество домов (1<=n<=1000). В следующем рядке через пропуск - количество телефонов, которые должы быть установлены в домах.
Вывести на экран и в первый рядок файла TEL.SOL номер дома, в котором нужно поставить АТС, чтобы общее количество кабеля от каждого телефона к АТС было минимальным. Если таких домов несколько, то написать их в порядке увеличения черех пропуск.
Каждый телефон соединен отдельным кабелем. Если телефон находится в том доме, что АТС, то считать, что кабеля не ведем.
Пример входных данных:
5
1 2 3 2 1
Пример выходных данных:

3

Может я и ошибаюсь, но как на меня, то это небо и земля в сравнении с вашей второй задачей

Я бы сказал, трава и земля ;) Код-то (особенно учитывая, что O(N^2) должен проходить) ненамного длиннее будет, чем твоя program zadacha2. Даже короче, наверное. Как решать - знаешь?

а можно условия задач, код к которым содержится в первом сообщении?

Олимпиадные задачи.

[Vinchkovsky]

to All, вы меня неверно поняли.
Я своими постами не создавал межнациональную неприязнь.
Я просто указывал на своё мнение.
Я не имел ввиду, что украинцам и мне в частности все задачки "по зубам" и я щелкаю даже самые сложные задачи.
Скорее наоборот - я признал, что смог решить ТОЛЬКО ОДНУ ЗАДАЧУ из нашей олимпиады. Я не указываю на то, что крут, тем, что решил (и то криво!!!) 3 ваших задач.
Последюю задачу, которую я запостил, не знаю, как решать.
Кто увидел в моих постах неприязнь к россиянам, или то, что хвалюсь своей крутостью - если не трудно, очень прошу зацитировать.
Не обращайте внимание на условное деление задач и олимпиад на "ВАШИ" и "НАШИ". Повторюсь, это условно, сделано без какого-либо намерения и не подчеркивает разность народов.
Прошу извинить меня, если кто-то заметил двузначность в моих словах. Это значит, что вы меня не поняли; я не имел ввиду ничего плохого, и, собственно, такие слова принимайте в лучшей стороне.
Прошу извинить меня за вынужденный оффтоп и не очень хороший русский.
В принципе, "в кожній хаті-своя правда ", но я прошу избавится от стереотипа того, что все россияне украинцам враги. Это не так; социальная обстановка не должна совпадать с политической.
И вобще - я за "мир во всем мире" и равенство словянских народов, и если кто-то подумал совсем по-другому, прошу внимательно перечитать мои посты
Michael_Rybak, если можешь, запости решение в топик с задачами (я про свою задачу)
И ЕЩЕ-все решения - полностью и на 100% мои собственные, я не использовал материалы других сайтов или уже готовые решения.

Сообщение отредактировано: Vinchkovsky - 10.01.2007 20:01

[мисс_граффити]

Vinchkovsky, перебором можно решать.... но с учетом того, что работаем с файлами - это будет весьма медленно...
никаких ограничений по времени и памяти нет?

[Vinchkovsky]

Ограничений нет никаких, в принципе, можно попробовать перебором . Хотя должен быть какой-то более рациональный способ? Действительно, при 30000 телефонов на дом и 1000 домов програма будет работать достаточно долго.
Я не совсем понял это: особенно учитывая, что O(N^2) должен проходить???

[мисс_граффити]

так.... смотри:
если у нас телефоны распределены равномерно (ну например 2 2 2 2 2), то рационально размещать АТС по центру.
В общем же случае это не так => надо искать "центр тяжести" системы...

[Michael_Rybak]

to All, вы меня неверно поняли.

Нет, это *ты* неправильно понял Я и не считаю что ты

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

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

Скорее наоборот - я признал, что смог решить ТОЛЬКО ОДНУ ЗАДАЧУ из нашей олимпиады. Я не указываю на то, что крут, тем, что решил (и то криво!!!) 3 ваших задач.
Последюю задачу, которую я запостил, не знаю, как решать.
Кто увидел в моих постах неприязнь к россиянам, или то, что хвалюсь своей крутостью - если не трудно, очень прошу зацитировать.

Не обращайте внимание на условное деление задач и олимпиад на "ВАШИ" и "НАШИ". Повторюсь, это условно, сделано без какого-либо намерения и не подчеркивает разность народов.
Прошу извинить меня, если кто-то заметил двузначность в моих словах. Это значит, что вы меня не поняли; я не имел ввиду ничего плохого, и, собственно, такие слова принимайте в лучшей стороне.
Прошу извинить меня за вынужденный оффтоп и не очень хороший русский.
В принципе, "в кожній хаті-своя правда ", но я прошу избавится от стереотипа того, что все россияне украинцам враги. Это не так; социальная обстановка не должна совпадать с политической.
И вобще - я за "мир во всем мире" и равенство словянских народов, и если кто-то подумал совсем по-другому, прошу внимательно перечитать мои посты

Не переймайся, брате ;)

Я не совсем понял это: особенно учитывая, что O(N^2) должен проходить

Это означает, что решение с временной оценкой O(N^2) должно набирать полный балл по этой задаче. Это следует из того, что n <= 1000.

Вообще я не понимаю проблемы: спрашивают,

номер дома, в котором нужно поставить АТС

Всего домов n, а значит

перебором можно решать....

Для каждого дома вычисляем общую длину кабеля и выбираем лучшие дома: (псевдопаскаль)

...
function CalcCabel(i)
begin
  cabel := 0;
  for j := 1 to n do
    cabel := cabel + Abs(i - j) * phones[j];
  CalcCabel := cabel;
end;

...

best := 10^12;
for i := 1 to n do 
  best := min(best, CalcCabel(i));
for i := 1 to n do
  if CalcCabel(i) = best then
    Write(i, ' ');

...

Небольшая, но очень важная деталь: с таким выводом легко получить 0 баллов по задаче, потому что в условии сказано "написать их в порядке увеличения через пропуск", т.е. после последнего номера не нужно выводить пробел. Это вообще жутко юзаные грабли.

Ну и другие тут грабли тоже скрыты - для теста n = 1000 и в каждом доме по 30000 ответ чуть-чуть вылазит за лонгинт.

[мисс_граффити]

т.е. после последнего номера не нужно выводить пробел.

Собираем в строку, и перед выводом в файл удаляем последний пробел....
А вот со вторым хуже....

Но на 1000 домов это будет работать довольно долго (с учетом, что файл текстовый...)
Попробую насчет центра тяжести додумать.

[Michael_Rybak]

Собираем в строку, и перед выводом в файл удаляем последний пробел....

В общем случае так лучше не делать; 1) строки медленно собираются вроде бы (каждый раз строится новая строка), 2) сама конвертация время занимает. При больших данных и то и другое (особенно первое) критично.

Проще с флагом: if not first then Write(' '); Write(i); first := false;

А вот со вторым хуже....

Тоже ничего страшного; comp ведь никто не отменял.

Но на 1000 домов это будет работать довольно долго (с учетом, что файл текстовый...)

Так мы ж сначала массив заводим, а потом по нему бегаем. Быстро должно работать.

Вообще задача решается за O(N), без внутреннего цикла - просто бежим сначала слева-направо, накапливая кабель, а потом справа-налево. Но здесь и N^2 покатит.

[Vinchkovsky]

Нет, это *ты* неправильно понял Я и не считаю что ты...

Мне это приятно. Получается, только админ считает так и меня неверно понял
Спасибо тебе и мисс_граффити за помощь в решении задачи
___________________________________
Чтобы не засорять форум и не создавать лишних тем, пару слов об следующей задаче:

Задача 4.
Числа от 1 до n расставлены по кругу. Вычеркиваем каждое второе число, начиная с 1. Написать программу, которая определит какое число останется последним и напечатает его. Исходное натуральное число - 1<n=<=1 000 000. Общий случай: определите количество шагов для произвольного числа.

Например, н=7. Тогда что делаем - это:

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

(выделеная цифра, которая вычеркивается)
или как?
Тоесть, я прошу пример выводных данных (на верное решение не толкайте, хочу сам понять)

[Malice]

Нет, вот так:

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

Ааа, пока тебе пример писал дошло как в 3 строки сделать ! Пойду попробую

[мисс_граффити]

Поиск->Казнь или Считалка.
Решалось на массивах.

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

Сообщение отредактировано: мисс_граффити - 11.01.2007 17:09

[Vinchkovsky]

Да я не хочу решение, а просто утачниваю условие задачи. Но все равно спасибо.

Есть в общем идейка - написать процедуру смещения тех чисел, которые остаются, на места тех, которые будем стирать (в динамическом массиве, ведь n-потенциальное longint), а лишним елементам присуждаем "0". И собственно применять эту процедуру, пока не останется 1 символ, отличный от нуля. Только в процедуре надо сделать отдельно старт с нулевой ситуации (ведь стираем с единницы) и отдельно последующие операции, анализируя парность количества елементов, которые остались (тоесть, новых n). Уже большую половину реализовал, завтра буду доканчивать.

[мисс_граффити]

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

[Malice]

Поиск->Казнь или Считалка.
Решалось на массивах.

Решение усложняется максимальным значением n=1 000 000. На на массивах тоже можно при желании. Допустим для того, чтобы знать вычеркнут/не вычеркнут достаточно 1-го бита, т.е. размер сокращается до 1000000/8 =125000. Пока еще не хватает. Но, учитывая, что при первом проходе быдут вычеркнуты все четные элементы, мы точно знаем, что младший бит=1 и его хранить не надо. Тогда размер массива сокращается до 125000/2 = 62500. Такой массив запросто организуется в tp.
Кстати, на счет 3-х строк выше я погорячился слегка, вышло побольше, но не намного. Пока не выкладываю, чтоб не мешать..

Сообщение отредактировано: Malice - 12.01.2007 10:03