VMRR–spoj

Đề bài:

Thuật toán:

  • (Đang cập nhật)

Code:

 

#include <bits/stdc++.h>
using namespace std;
 
main(){
    string s,a;
    getline(cin,s);
    cin>>a;
    int dem=0; int z; long long res; char x,y;
    x=a[0];y=a[1]; res=0;z=0;
    for(int i=s.size()-2;i>=0;--i){
        if(s[i+1]==y) z++;
        if(s[i]==x) res+=z;
    }
    cout<<res;
}

C11SEQ3 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
        tfi='';//c11seq3.inp';
        tfo='';//c11seq3.out';
 
var
        fi,fo:text;
        n:longint;
        f:array[0..24]of qword;
        t:array[0..5] of qword=(244445,48889, 77789, 155578, 111356, 122227);
 
procedure dao(i:longint);
        var s:string;
                tg:char;
                i1,j,code:longint;
        begin
                str(f[i],s);
                for i1:=1 to length(s)-1 do
                        for j:=i1+1 to length(s) do
                                if s[i1]>s[j] then
                                        begin
                                                tg:=s[i1];
                                                s[i1]:=s[j];
                                                s[j]:=tg;
                                        end;
                val(s,f[i],code);
        end;
 
procedure xuli;
        var i:longint;
        begin
                read(fi,n);
                f[1]:=1;
                for i:=2 to 24 do
                        begin
                                f[i]:=f[i-1]*2;
                                dao(i);
                        end;
                if n<=24 then write(f[n])
                else writeln(fo,t[n mod 6]);
        end;
 
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(Fi);
        rewrite(fo);
        xuli;
        close(fo);
end.

CBUYING – spoj

Đề bài:

Thuật toán:

  • Chọn số những sô cô la có giá rẻ nhất

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<ll,ll> 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 = 1E6+3;
const int oo = 1e9+3;
 
int n;
ll ans, b;
PII a[MAXN];
 
bool cmp(PII a, PII b) {
    return (a.fi < b.fi);
}
 
int main() {
    cin >> n >> b;
    FOR(i,1,n) cin >> a[i].fi >> a[i].se;
    sort(a+1,a+n+1,cmp);
    FOR(i,1,n) {
        if (b < a[i].fi) break;
        ll tmp = b / a[i].fi;
        b -= min(tmp,a[i].se) * a[i].fi;
        ans += min(tmp,a[i].se);
    }
    cout << ans;
	return 0;
}

KPLANK – spoj

Đề bài:

Thuật toán:

  • Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e6)+3;
var
  st : array[1..maxn] of longint;
  a,l,r : array[1..maxn] of longint;
  i,j,n : longint;
  res : int64;
  top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(a[i]);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
function get: longint;
  begin
    get := st[top];
  end;
procedure process;
  begin
    top :=0 ;
    for i:=1 to n do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then l[i] := 0 else l[i] := get;
        push(i);
      end;
    top := 0;
    for i:=n downto 1 do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then r[i]:=n+1 else r[i] := get;
        push(i);
      end;
    for i:=1 to n do
      if r[i]-l[i]-1>=a[i] then
        res := max(res, a[i]);
end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
  end;
begin
  enter;
  process;
  print;
end.

NKTICK – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động

Code:


const   fi='';
        fo='';
        max=30000;
var n,i:longint;
t:array[1..60000] of integer;
f:array[-1..60000] of longint;
r:array[0..59999] of integer;
w:text;
function min(x,y:longint):longint;
begin
    if x>y then min:=y else min:=x;
end;
procedure nhap;
begin
    assign(w,fi);
    reset(w);
    readln(w,n);
    for i:=1 to n do read(w,t[i]);
    for i:=1 to n-1 do read(w,r[i]);
    close(w);
end;
procedure xuly;
begin
        f[0]:=0; f[-1]:=0; r[0]:=max;
        for i:=1 to n do
        f[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);
end;
procedure inkq;
begin
        assign(w,fo);
        rewrite(w);
        writeln(w,f[n]);
        close(w);
end;
begin
    nhap;
    xuly;
    inkq;
end.

listgame – kattis

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

NKNUMFRE – spoj

Đề bài:

Thuật toán:

  • Vét cạn.

Code:

const
  fi='';
  fo='';
var
  a,b,i,j,dem,num : longint;
procedure swap(var x,y : char);
  var tg :char;
  begin
    tg:=x;x:=y;y:=tg;
  end;
function gcd(a,b : longint) : longint;
  var r : longint;
  begin
    while b>0 do
      begin
        r := a mod b;
        a:=b;
        b:=r;
      end;
    exit(a);
  end;
function dao(x : longint) : longint;
  var s : string;
      y : longint;
  begin
    str(x,s);
    i:=1;j:=length(s);
    while i<j do
      begin
        swap(s[i],s[j]);
        inc(i);dec(j);
      end;
    val(s,y);
    exit(y);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(a,b);
  for num := a to b do
    if gcd(dao(num),num)=1 then inc(dem);
  writeln(dem);
  close(input);close(output);
end.