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

[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

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

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

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

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

[Malice]

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

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

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

[Michael_Rybak]

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

Всеукраинки (и вроде бы областные) уже достаточно давно тестируются на fp. Так что не думаю, что эта проблема стоит.

Но!

Нам это на самом деле не нужно. Можно просто помнить, какие числа сейчас есть, и с какого числа (первого или второго) начинаем вычеркивать.

Пример:

1 2 3 4 5 6 7 8 9 10 11 - есть числа вида K+1, где 0 <= K <= 10, вычеркиваем, начиная со 2го
1 2 3 4 5 6 7 8 9 10 11 - четность меняется, теперь начнем вычеркивать с первого

1 3 5 7 9 11 - есть числа вида 2K+1, где 0 <= K <= 5, вычеркиваем, начиная с 1го
1 3 5 7 9 11 - опять начнем вычеркивать с 1го

3 7 - есть числа вида 4K+3, где 0 <= K <= 1, вычеркиваем, начиная с 1го:
3 7

7 - есть числа вида 8К+7, где 0 <= K <= 0, вычеркиваем, начиная с 1го.


После каждого прохода будут оставаться числа вида (2^p)K + t, где 1 <= t <= 2^p (чтобы выполнялось 0<=t<2^p, надо вести нумерацию с 0), а К лежит в пределах от 0 до некоторого q. Поэтому их можно хранить не массивом, а тройкой (p, t, q).

[Гость]

Вот как сделал я:

var i,first, last,pred,y,n:longint;
begin
readln(n); y:=0;
first:=0; last:=n; pred:=n;
repeat
for i:=1 to n do
if (i and y) xor first=0 then
begin write (i,' '); last:=i; end;
writeln;
first:=first+(y+1)*byte(last=pred);
pred:=last;
y:=y shl 1+1;
until (first=last) or (first>n);
writeln (last);
end.

Как мне кажется, очень логично получилось

[Michael_Rybak]

Как мне кажется, очень логично получилось

Логично, только у тебя сложность O(N log N), а можно O(log N). Зачем цикл for внутри?