Форум Всеукраїнської інтернет-олімпіади NetOI

      Так-с, на меня возложена гигантская ответственность описания моих решений задач № 1 и 4 (OldTask1 и Skyscraper). Предупреждаю заранее: текст писался ещё до того, как станут (стали) известными результаты, так что за правильность и т. п. я не ручаюсь (хотя и очень надеюсь). Ещё одно предостережение: для меня привычным языком является Си, но зная, что тут бывают всякие глюки с int64 и строками, я перестраховался и переписал всё на Паскаль.
      Последнее напутствие: «>:3 Господи Иисусе! Да это же ЛевЪ! Скорее в машину!!!11»


1. OldTask1

      Итак, для начала скажу, что считать факториал напрямую — это конечно будет на 100 % верным решением, но слишком долгим и жрущим много памяти, так что оно отпадает.
      Следующим шагом будет то, что из бесконечности простых чисел единственные два, которые при перемножении дают число, оканчивающееся на нолик, — это 2 и 5.
      Далее, вспоминая, что любое число можно разложить на произведение простых и то, что факториал — это произведение всех натуральных чисел до данного, я понял, что можно считать всю эту муть так:
      1.  Учитывать двойки и пятёрки отдельно, а всё остальное множить между собой так, как будто мы ничего не знаем.
      2.  Так как нас волнуют только последняя цифра, то надо оставлять только её. Но тут в голову лезет мысль: каким макаром? Естественно, надо делать каждый раз вычисление остатка от деления. Некоторые могут сказать, что это будет неэффективно, что надо делать всё умнее и делать вычисление модуля тогда, когда произведение будет переваливать за какую-то границу и всё такое, но вот подумав, что после того, как мы перевалим к числам за 1000, то это будет случаться чуть ли не каждый раз, так что на эффективность это не будет сильно влиять в отрицательную сторону.
      Проблема учёта двоек и пятёрок решается так: одна двойка × одну пятёрку = один нолик в конце, а значит двойки и пятёрки, смешанные в любой пропорции дают в результате количество ноликов, равное меньшему из количеств двоек и пятёрок. Тут ещё (я не привожу, какого чёрта, — сами догадаетесь) становится понятным, что двоек всегда будет больше чем пятёрок.
      Итак, вводится счётчик, который ведёт учёт количества двоек. Как только мы начинаем множить свой чудо-результат на новое число, мы его (число) предварительно делим на 2 пока делится и увеличиваем счётчик, а потом делим его на пять (тоже, пока делится) и уменьшаем счётчик. То, что осталось, множим на результат и вычисляем модуль от результата по основанию 10. (Блин, как я хочу десятичные машины!)
      После этого у нас есть одна цифра и одна степень двойки. Вспоминая, что последняя цифра любой натуральной степени любой цифры повторяется с периодом 4 (для двойки период: 6, 2, 4, 8), мы находим последнюю цифру степени двойки, множим её на ту цифру результата и вычисляем модуль. Та-дам!..
      Множить числа для факториала можно в любом порядке, мне приглянулся обратный. Плюс, можно чуть оптимизировать вычисление последней цифры степени двойки, здыхавшись case’а. Итак, привожу свой код:

program OldTask1;

var
  n, t, result, twoC: longint; {На всяк пожарный, я не считал максимумы значений}

begin
  result := 1;
  twoC := 0;
  read(n);
  while (n > 1) do begin {Цикл по всем числам}
    t := n;
    while (t mod 2 = 0) do begin
      t := t div 2;
      twoC := twoC + 1;
    end;
    while (t mod 5 = 0) do begin
      t := t div 5;
      twoC := twoC - 1;
    end;
    {Сократили на двойки и пятёрки}
    result := (result * t) mod 10;
    n := n - 1;
  end;
  if (twoC > 0) then
    result := (result shl (1 + (twoC - 1) mod 8)) mod 10; {Вот этот оптимизированный вариант. Спасибо, что двойки, а то бы пришлось писать case, а так можно shl (двоичный сдвиг влево — для тех, кто не знает).}
  write(result);
end.

4. Skyscraper

      Итак, сразу даю задачу: нам надо найти количество различных вариантов укладки стен здания (m × n) с помощью кирпичей размерами (1 × 1 × a) и (1 × 1 × b). Вопрос стоит так: как это сделать?
      Так-с… перечитывая условие задачи понимаем, что кирпичи не гнутся и не ломаются, так что тут ясно (тут и далее я буду рассматривать не всё здание, а только его какой-то слой толщиной 1, понятие стен остаётся то же, что и у здания), что кирпичи надо уложить так, чтобы все четыре стены были непрерывны. То есть так, чтобы весь слой можно было разрезать вертикально на четыре стены так, чтобы не поломать ко всем чертям ни один кирпич.
      Знаю, это звучить чуть запутанно, но я пока не понял, как сюда можно запостить картинку, так что буду объяснять на словах. Да и лень мне постить картинку.
      Итак, у здания четрые угла (ну надо же), каждый угол может быть «разрезан стенами» двумя способами: если смотреть сверху и так, что стены здания параллельны двум осям координат соответственно, то это горизонтально и вертикально. А так как углов четыре, то способов всю стену разрезать на куски аж 16. Я их тут не привожу, сами в тетрадке себе нарисуйте.
      Далее замечаем, что куски стены, которые мы получим в результате разрезания, могут быть длины (m), (m − 1), (m − 2), (n), (n − 1) или (n − 2). И плюс, подключая мозг, понимаем, что способов уложить весь слой здания при данном способе разрезания есть столько, сколько получим, перемножив количества способов уложить каждый из кусков стен.
      И последняя проблема: как узнать это количество способов? Итак, мы знаем, что если мы хотим уложить кирпичами длиной a и b стену длиной x, то нам надо их количество подобрать так, чтобы то, что мы сложим, было в точности по длине равно x, ни больше и не меньше. А значит нам надо найти все способы представления числа x в виде A × a + B × b, где A и B — это искомые количества. Мне ничего умнее в голову не пришло, как перебрать (естественно, с отсеиванием всего, что в принципе не может подойти) все возможные варианты (нам они всё равно нужны).
      А следующая проблема (количество способов разместить A кирпичей длиной a и B кирпичей длиной b так, чтобы все комбинации были уникальны [кирпичи взаимозаменяемые и равные, если у нас рядом стоит два кирпича длиной a и мы их поменяем местами — это та же самая комбинация]) решается легко: это количество способов выбрать A из (A + B), то есть (A + B)! / (A! × B!), что есть, приведя к другому виду, [(B + 1) × (B + 2) × … (A + B)] / A! если A < B.
      Я не буду здесь рассказывать, почему это всё должно влезть в int64 и не надо делать длинную арифметику, так как это будет долговато, а я уже устал колотить по клавишам, поэтому приведу свой исходник:

program Skyscraper;

var
  m, n, a, b: longint;
  m0, m1, m2, n0, n1, n2, res: int64;

function C(a: integer; b: integer): int64;
var
  result666: extended; {У меня компилятор чего-то ругался на просто «result»}
  i: integer;
begin
  if (a > b) then begin
    i := a;
    a := b;
    b := i;
  end;
  result666 := 1;
  for i := (b + 1) to (b + a) do
    result666 := result666 * (i / (i - b));
  C := round(result666); {Вдруг чего будет}
end;

function dispatch(x: integer): int64;
var
  sum: int64;
  i, j: longint;
begin
  sum := 0;
  i := 0;
  while (i <= x) do begin
    if (i = x) then begin
      sum := sum + 1;
      break;
    end;
    j := 0;
    while (i + j <= x) do begin
      if (i + j = x) then begin
        sum := sum + C(i div a, j div b);
        break;
      end;
      j := j + b;
    end;
    i := i + a;
  end;
  dispatch := sum;
end;

begin
  read(m, n, a, b);
  m0 := dispatch(m);
  m1 := dispatch(m - 1);
  m2 := dispatch(m - 2);
  n0 := dispatch(n);
  n1 := dispatch(n - 1);
  n2 := dispatch(n - 2);
  res := m0 * m0 * n2 * n2 +
         4 * m0 * m1 * n1 * n2 +
         2 * m0 * m2 * n1 * n1 +
         4 * m1 * m2 * n0 * n1 +
         m2 * m2 * n0 * n0 +
         2 * m1 * m1 * n0 * n2 +
         2 * m1 * m1 * n1 * n1; {Тут уже приведены подобные, так как есть симметричные комбинации разрезания}
  write(res);
end.

В общем, я думаю, вы мне простите некоторые вольности (типа ЛевЪа).

кстати могу сказать про факториал, так как у нас последнее допустимое число 32000+, то чтоб найти последнюю цыфру надо то что у нас есть после умножения делить так чтоб мы получали НЕ последнюю цыфру, А последние 5 цыфр, иначе идет збой

+ чтобы найти последнюю/последнии цыфры числа в паскале делаеться так:
число:=число mod 1000(кол нулей = кол последних чисел)
mod - деление с остатком

число:=число div 1000(кол нулей = кол первых чисел)  - получаем первые цыфры числа
div - деление нацело

Відредаговано Cris (2008-11-29 07:35:44)

Задача Oldtask1
1)0 на конце мы можем получить только при произведении 2 на 5.
2)Так-же на последнюю цифру произведения влияет только последняя цифра числа.
3)при умножени на 10 последняя ненулевая цифра произведения равна последней ненулевой цифре исходного числа
4)Следовательно чтобы получить последнюю ненулевую цифру факториала перемножаем все последние цифры чисел от 1 до n, но если число а делится на 5, то умножаем на последнюю цифру а/(5^n), где n- максимальная степень 5 на которую делится а, и убираем такое-же количество 2 в последствии

Oldtask2

var q,a,d,f,j,i:longint;
s1,s2,s3:string;
function sr(s1,s2:string;q,i:longint):boolean;
var l,k,m,n:longint;
begin
n:=0;
k:=i-1;
for l:=1 to d do begin
k:=k+1;
if s1[k]=s2[l] then begin
n:=n+1;
end;
end;
sr:=false;
if n=d then begin
sr:=true;
end;
end;
 begin
 readln(s1);
 readln(s2);
 readln(s3);
 f:=length(s1);
 d:=length(s2);
 q:=length(s3);
 i:=1;
  if f>0 then begin
 while i<=f do begin
if sr(s1,s2,q,i)=false then begin
write(s1[i]);
i:=i+1;
end;
if sr(s1,s2,q,i)=true then begin
for j:=1 to q do begin
write(s3[j]);
end;
i:=i+d;
end;
end;
end;
writeln;
 end.

Ну вот еще довольно короткое решение скайскрейпер:

#include <iostream>
#include <cstdlib>
using namespace std;
int v1,v2,a,b,c,d,i,j,n,m,k;
unsigned long long mas[51],res,cur;
inline void um(unsigned long long &cur,int a,bool r,int c1,int c2)
{
    r?cur*=mas[a+(c1!=0)+(c2!=0)]:cur*=mas[a+(c1==0)+(c2==0)];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&v1,&v2);
    mas[0]=1;
    for (int i=1;i<=max(n,m);i++)
    {
        a=i-v1; b=i-v2;
        if (a>=0) mas[i]+=mas[a];
        if (b>=0) mas[i]+=mas[b];
    }
    res=0;
    for (int i=0;i<16;i++)
    {
        cur=1;
        um(cur,m-2,1,i&1,i&2);
        um(cur,m-2,1,i&4,i&8);
        um(cur,n-2,0,i&2,i&4);
        um(cur,n-2,0,i&1,i&8);
        res+=cur;
    }
    cout<<res<<endl;
}

Решение фибо бинпоиском:

#include <iostream>
#include <cstdlib>
using namespace std;
int n,m,c,d,i,j,k;
long long a,b,l,p,xx,cur,next;
inline long long check(long long xx)
{
    long long last=a,cur=xx;
    for (int i=m+2;i<=n;i++)
    {
        long long next=last+cur;
        last=cur; cur=next;
        if (cur>1000000000000000000LL || cur<-1000000000000000000LL) return cur;
    }
    return cur;
}
int main()
{
    cin>>m>>a>>n>>b;
    if (n!=m+1)
    {
        l=-1000000000000000000LL; p=-l;
        while (p-l>1)
        {
            xx=(p+l)>>1;
            if (check(xx)>b) p=xx; else l=xx;
        }
        if (check(l)!=b) l=p;
        if (check(l)!=b) { printf("Impossible\n"); exit(0); }
    } else l=b;
    cur=a; next=l;
    for (int i=m-1;i>=1;i--)
    {
        long long prev=next-cur;
        next=cur; cur=prev;
        if (cur>1000000000000000000LL || cur<-1000000000000000000LL) { printf("Impossible\n"); exit(0); }
    }
    cout<<cur<<endl;
}

Oldtask1:

#include <iostream>
#include <cstdlib>
using namespace std;
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define rep(i,n) FOR(i,1,n)
#define C(a) memset((a),0,sizeof(a))
const int s5[]={1,5,25,125,625,3125,3125*5,3125*25};
int a,b,c,d,i,j,n,m,k;
int st2[40000];
int st5[40000];
int main()
{
    scanf("%d",&n);
    C(st2); C(st5);
    st2[1]=0;
    st5[1]=0;
    a=1;
    c=0;
    rep(i,n)
    {
        if (i%2==0)    st2[i]=st2[i>>1]+1;
        if (i%5==0)    st5[i]=st5[i/5]+1;
        c+=st2[i]-st5[i];
        a=(a*(i/((1<<st2[i])*(s5[st5[i]]))))%10;
    }
    if (c>0) 
    {
        rep(i,c) a=(a<<1)%10;
    } else if (c<0) a=(a*s5[-c])%10;
    printf("%d\n",a);
}

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

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

Вопросы формулируются достаточно просто: какие точные версии компиляторов используются, каким стандартам должен подчиняться код (название и год) и с какими ключами компилирутся программы (включена ли оптимизация и всё такое)?

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

И соцопрос-прикол: что делает этот Си-код и почему он так делает?

#include <stdio.h>
#include <math.h>

int main(void){
  int i = 5;
  double j;
  i = i++ + i++;
  j = ((i % 2) ? sin : cos)(PI / 3);
  printf("%d %lf", i, j);
/*
  А что будет, если написать вот так:
  printf("%d %lf", i, j, ++i);
*/
  return 0;
}

А вот этот что делает?

#include   <stdlib.h>
#include    <stdio.h>
#define   P    printf
#define   I      atoi
int main(int a,char*v
[]){int r=5, i;if(a>1
) r=I(v[1]); if(r<=0)
r=5;if(r%2==0)++r;for
(i=0; i<r*r; P(i/r==(
3*r)/2-(i%r+1)||i/r==
r/2 - i%r||i/r==r/2+i
%r||i/r==i%r-r/2?"*":
" "),i++, i % r==0?P(
"\n") : 0);return 0;}

Відредаговано Cardinal Nightingale (2008-11-30 13:59:02)

> Кстати, на задаче Fibo таймлимит какой-то странный, один раз выдаёт 0.13 секунд, другой раз — 0.03 секунд... (по одному и тому же тесту)
Сервер перевантажений, тому і час різний виходить.