QBMAX – spoj

19/06/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • Quy hoạch động!

Code:

uses    math;
const   fi = '';
        fo = '';
var     n,m,i,j,maxf : integer;
        a,f : array[0..301,0..301] of integer;
 
begin
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
        readln(m,n);
        for i := 1 to m do
                for j := 1 to n do
                        read(a[i,j]);
        for j := 0 to n+1 do begin
                f[0,j] := -maxint;
                f[m+1,j] := -maxint;
        end;
        for i := 1 to m do f[i,1] := a[i,1];
        for j := 2 to n do
                for i := 1 to m do
                        f[i,j] := max(f[i-1,j-1],max(f[i,j-1],
                                       f[i+1,j-1])) + a[i,j];
        maxf := -maxint;
        for i := 1 to m do
                maxf := max(maxf,f[i,n]);
        writeln(maxf);
        close(input);
        close(output);
end.
Chủ đề: SPOJ

MDIGITS2 – spoj

18/06/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • Bạn chỉ cần tạo 1 xâu st[] với thứ tự các số tự nhiên như đề bài nhé.
  • Các bạn xem code của mình để dễ hiểu hơn nhé

Code:

Var
  n :Int64;
 
  function Solve :Int64;
  var
    S,T,X :AnsiString;
    i :Int64;
  begin
    S:=''; Str(n,X); i:=1;
    while i<=n do
      begin
        Str(i,T); S:=S+T; Inc(i);
      end;
    Solve:=Pos(X,S);
  end;
 
Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  ReadLn(n); 
  Write(Solve);
  Close(Input); Close(Output);
End.
Chủ đề: SPOJ

QBHV – spoj

18/06/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • Sắp xếp các kí tự trong xâu S tăng dần theo thứ tự bảng chữ cái Alphabet.
  • Quay lui liệt kê các hoán vị của xâu S, với mỗi hoán vị mới sinh ra kiểm tra xem có trùng với xâu vừa viết ra hay không.

Code:

Const
  maxN =9;
  maxSL =362880;
Var
  n,m :LongInt;
  S,X :String[9];
  D :Array['A'..'Z'] of ShortInt;
  A :Array[0..maxSL] of String[9];
  Free :Array[1..maxN] of Boolean;
 
  procedure QSort(l,r :LongInt);
  var
    i,j :LongInt;
    Key,Tmp :Char;
  begin
    if (l>=r) then Exit;
    i:=l; j:=r; Key:=S[(l+r) div 2];
    repeat
      while (S[i]<Key) do Inc(i); 
     while (S[j]>Key) do Dec(j);
      if (i<=j) then
        begin
          if (i<j) then begin Tmp:=S[i]; S[i]:=S[j]; S[j]:=Tmp; end; Inc(i); Dec(j); end; until (i>j);
    QSort(l,j); QSort(i,r);
  end;
 
  function Factorial(i :LongInt) :LongInt;
  var
    j,tmp :LongInt;
  begin
    if (i=0) then Exit(1);
    tmp:=1;
    for j:=2 to i do tmp:=tmp*j;
    Exit(tmp);
  end;
 
  procedure Enter;
  var
    i,tmp :LongInt;
    ch :Char;
  begin
    ReadLn(S); n:=Length(S); QSort(1,n);
    FillChar(D,SizeOf(D),0);
    FillChar(Free,SizeOf(Free),true);
    for i:=1 to n do Inc(D[S[i]]);
    X:='';
    for i:=1 to n do X:=X+' ';
    tmp:=1;
    for ch:='A' to 'Z' do tmp:=tmp*Factorial(D[ch]);
    WriteLn(Factorial(n) div tmp);
    A[0]:='';
    m:=0;
  end;
 
  procedure Back(i :LongInt);
  var
    j :LongInt;
  begin
    for j:=1 to n do
      if (Free[j]) then
        begin
          X[i]:=S[j];
          Free[j]:=false;
          if (i=n) and (X>A[m]) then
            begin
              WriteLn(X); Inc(m); A[m]:=X;
            end
          else Back(i+1);
          Free[j]:=true;
        end;
  end;
 
Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  Enter;
  Back(1);
  Close(Input); Close(Output);
End.
Chủ đề: SPOJ

PNUMBER- spoj

18/06/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • bạn chỉ cần tạo hàm kiểm tra số nguyên tố thôi nhé.
  • hàm mình tạo ở dưới code này. Các bạn đọc để dễ hiểu hơn nhé.

Code:

#include<bits/stdc++.h>
using namespace std;
int a,b;
int kt(int n)
{
    if(n<2) return 0;
    for (int i=2;i<=sqrt(n);i++) 
      if (n%i==0) 
           return 0; 
return 1; 
}
 int main() 
{ cin>>a>>b;
    for (int j=a;j<=b;j++)
    {
        if(kt(j)) cout<<j<<endl;
    }
    return 0;
 
}
  • Phần int kt(int n) chính là hàm kiểm tra số nguyên tố mà mình đã nói ở trên nhé ^_^
    • Chủ đề: SPOJ

    COUNTCBG – spoj

    18/06/2017 by Leave a Comment

    Đề bài:

    Thuật toán:

    • Ta xét tổng các số từ l -> r thì ta cần tìm l , r sao cho :l + (l+1) + … + (r-1) + r = n

      ⇒ (r+l)(r-l+1)/2 = n

      ⇒ (l+r)(r-l+1) = 2n

      Giải phương trình nghiệm nguyên đơn giản này

      Ta xét phần (l+r). Đương nhiên l + r >= 2 vì l >= 1, r >= l;

      Do l <= r nên ta chỉ cần xét (l + r) từ 2 -> sqrt(2n) thôi vì phần còn lại sẽ tạo ra bộ nghiệm tương tự phần ta xét

      Cho i = 2 -> sqrt(2n) :

      Nếu (2n) chia hết cho i thì ta bắt đầu :

      l + r = i và r – l + 1 = 2n/i hay r – l = 2n/i -1

      ⇒ 2r = i + 2n/i -1 mà r nguyên

      ⇒ (i + 2n/i – 1) chẵn

      ⇒ l cũng nguyên do r nguyên

      Vậy điều kiện để có một nghiệm cho bài toán là

      (2n) chia hết cho i và (i + 2n / i – 1) chẵn

      Nhận xét thời gian thực thi thuật toán là :

      O(100*sqrt(2*10^9))

    Code:

    Program COUNTCBG;
Var
  n,res :LongInt;
 
  procedure Solve;
  var
    i :LongInt;  
  begin
    res:=0;
    for i:=2 to Trunc(Sqrt(2*n)) do
      if (2*n mod i=0) then
        if ((i+2*n div i-1) mod 2=0) then Inc(res);
  end;
 
Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  while not EoF do
    begin
      ReadLn(n);
      Solve;
      WriteLn(res);
    end;
  Close(Input); Close(Output);
End.
    Chủ đề: SPOJ

    BASEH – spoj

    18/06/2017 by Leave a Comment

    Đề bài:

    Thuật toán:

    • Chuyển n về hệ nhị phân
    • Các bạn có thể tham khảo code sau

    Code:

    #include<bits/stdc++.h>
using namespace std;
int main()
{
    long long  a[10000005], n,dem=0,k;
    cin>>n>>k;
    while(n>0)
    {
               a[dem] = n%2;
               n = n/2;
               dem++;
    }
    for(long long  i=dem-1; i>=0;i--)
    cout<<a[i];
    return 0;
}
    Chủ đề: SPOJ