MULONE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';//MULONE.INP';
  fo = '';//MULONE.OUT';
  maxn = 10000000;
var
  n,test,t : longint;
  kq : array[1..maxn] of longint;
 
procedure sol;
var
  i,nho,tong : longint;
  count : longint;
begin
  tong:=0; nho:=0; count:=0;
  for i:=1 to n do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=n-1 downto 1 do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=count downto 1 do write(kq[i]);
  writeln;
end;
 
BEGIN
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
  readln(T);
  for test:=1 to T do
    begin
      readln(N);
      sol;
    end;
  close(input);
  close(output);
END.

C11PNUM – spoj

Đề bài:

Thuật toán:

  • Sàng nguyên tố
  • Tính các tích k số nguyên tố liên tiếp để cập nhập cho kết quả

Code:

const   fi='';
        fo='';
        oo=3000000;
var     k,t,i,j,tt:longint;
        tam,n,res:qword;
        f:text;
        tmp:array[2..oo] of boolean;
        ngto:array[1..oo] of longint;
        d	:longint;
function max(a,b:qword):qword;
begin
        if a>b then exit(a) else exit(b);
end;
procedure xl;
var     i,j :longint;
begin
	for i:=1 to d-k+1 do
		begin
			tam :=1;
			for j:=i to i+k-1 do
			begin
				tam := tam*ngto[j];
			end;
                        if tam>n then break else res := max(res,tam);
		end;
end;
procedure init;
begin
        for i:=2 to trunc(sqrt(oo)) do
                if tmp[i]=false then
                        begin
                            j:=i*i;
                            while j<=oo do
                                begin
                                    tmp[j]:=true;
                                    j:=j+i;
                                end;
                        end;
        d:=0;
        for i:=2 to oo do
                if tmp[i]=false then begin inc(d); ngto[d]:=i; end;
        j:=d;
end;
procedure nhap;
begin
    assign(f,fi);reset(f);
    assign(output,fo);rewrite(output);
    read(f,t);
    for tt:=1 to t do
        begin
            read(f,n,k);
            res := 0;
            xl;
            if res=0 then writeln(-1) else writeln(res);
        end;
    close(f);close(output);
end;
begin
    init;
    nhap;
end.

DEGREE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int dp[35][35],base[35],bin[35];
void init()
{
    dp[0][0]=base[0]=1;
    for(int i=1;i<=32;i++)
    {
        dp[i][0]=1;
        base[i]=base[i-1]<<1;
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
    }
}
int calc(int x,int k)
{
    int i,one=0,ans=0;
    for(i=31;i>=0;i--)
    {
        if(x&base[i])
        {
            if(one>k)
                break;
            ans+=dp[i][k-one];
            one++;
            x-=base[i];
        }
    }
    if(one==k)
        ans++;
    return ans;
}
int getbin(int x,int b)
{
    int ct=0,i,ret=0;
    if(!x)
        return x;
    while(x)
    {
        bin[ct++]=x%b;
        x/=b;
    }
    for(i=ct-1;i>=0;i--)
    {
        if(bin[i]>1)
            break;
        if(bin[i])
            ret=ret<<1|1;
        else
            ret<<=1;
    }
    while(i>=0)
    {
        ret=ret<<1|1;
        i--;
    }
    return ret;
}
int main()
{
    int x,y,k,b;
 
    init();
    while(~scanf("%d%d%d%d",&x,&y,&k,&b))
    {
        y=getbin(y,b);
        x=getbin(x-1,b);
        printf("%d\n",calc(y,k)-calc(x,k));
    }
    return 0;
}

listgame – kattis

Đề bài
Thuật toán
Code

SHHV – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 13;
const int oo = 1e9+3;
string s;
 
ll gt[MAXN+1];
int n, x, a[MAXN+1], b[MAXN+1], i, j;
bool chon[MAXN+1];
ll t;
 
void init() {
    gt[0] = 1;
    gt[1] = 1;
    for (int i=2; i<=MAXN; i++) gt[i] = gt[i-1]*i;
}
 
void query1() {
    ll ans = 0;
    memset(chon,0,sizeof(chon));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]-1; j++)
        if (!chon[j]) {
            ans += gt[n-i];
        }
        chon[a[i]] = 1;
    }
    cout << ans+1 << endl;
}
 
void query2() {
    memset(chon,0,sizeof(chon));
    t--;
    for (i=1; i<=n; i++) {
        int tmp = 0;
        for (j=1; j<=n; j++) {
            if (!chon[j]) tmp++;
            if (gt[n-i]*tmp>t) break;
        }
        t -= gt[n-i]*(tmp-1);
        b[i] = j;
        chon[j]=1;
    }
    for (int i=1; i<=n; i++) cout << b[i] << " ";
}
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    while (cin>>a[++n]);
    t=a[--n]; n--;
    init();
    query1();
    query2();
    return 0;
}

FIBVAL – spoj

Đề bài

Thuật toán

Để giải được bài này, ta cần áp dụng 1 tính chất đặc biệt của dãy Fibonacci, đó là chu kỳ Pisano

Dãy Fibonacci có dạng:

  • f(0) = 0
  • f(1)=1
  • f(i)=f(i-1)+f(i-2)

Đối với 1 số nguyên n bất kì thì dãy g(i)=f(i) mod n có tính chu kì.

Ví dụ: Với n=3 ta có:

f 0 1 1 2 3 5 8 13 15 28 43
g 0 1 1 2 0 2 2 1 0 1 1

Ở bài này, ta có chu kì gồm 7 nốt nhạc vì vậy ta xét tính chu kì trên dãy g(i)=f(i) mod 7.

Chu kì Peisano của 7 trong bài này gồm 16 số:

 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1

Như vậy, độ dài đoạn nhạc dài nhất có tính chu kì chỉ có thể là 2 hoặc có dạng 16*k.

Code

CONST
    tfi = '';
    tfo = '';
VAR
    fi,fo           : text;
 
Function pro(l,r: longint): longint;
    Var
        len,res: longint;
    Begin
        len:=r-l+1;
        l:=l mod 16;
        r:=r mod 16;
        If l=0 then l:=16;
        If r=0 then r:=16;
        res:=len div 16;
        If len>=32 then exit(res*16)
        else
            If len>=9 then exit(2)
            else
                If ((l=9)) or ((l>9) and (r0 do
            begin
                read(fi,l,r);
                writeln(fo,pro(l,r));
                dec(test);
            end;
    End;
 
BEGIN
    assign(fi,tfi); reset(fi);
    assign(fo,tfo); rewrite(fo);
        process;
    close(fi); close(fo);
END.

Nguồn: không rõ

C11SUM – spoj

Đề bài:

Thuật toán:

  • Các bạn đọc code xem thuật toán dễ thế nào nhé 🙂

Code:

{$H+}
Uses math;
Const
	inp = '';
	out = '';
	maxn = 1000001;
	oo = 1000000007;
 
Var
	a,b : array [0..maxn] of int64;	
	s : string;
	n,i,x : longint;
	res,hold : int64;
 
begin
	assign(input,inp); reset(input);
	assign(output,out); rewrite(output);
	readln(s);
	n := length(s);
	hold := 0;
	for i := 1 to n do
	  begin
	  	x := ord(s[i])-ord('0');
	  	hold := (hold*10+i*x) mod oo;
	  	res := (res +hold) mod oo;
	  end;
	writeln(res);
end.