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

[ammaximus]

Час назад закончился 2 этап Росиийской олимпиады школьников по информатике. Будем ждать результатов, а пока...
Задача 1.
Даны два слова А и В. Проверьте, можно ли из букв слова А составаить В. Каждый символ из А использовать не более 1 раза.

Задача 2.
Очки на игральных кубиках располагаются так, чтобы совпадали суммы чисел на противоположных гранях:1+6=2+5=3+4=7. Составьте программу, которая по заданному (неупорядоченному) набору из 6 целых чисел из диапазона 1 .. 10 000 проверяла бы, можно ли разместить их на гранях кубика таким образом, чтобы выполнялось это правило. Если можно - вывести сумму, иначе символ N.
Пример: 1,2,3,4,5,6; Результат 7.

Задача 3.
Числом Армстронга называется число из n цифр, если сумма его цифр, возведенных в n-ю степень равна самому числу. Найти все n-значные числа Армстронга (1<n<10).
Пример: 153=1^3+5^3+3^3 - число Армстронга.

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

[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 14:21

[Vinchkovsky]

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

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

[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 ответ чуть-чуть вылазит за лонгинт.