VOGAME – spoj

November 30, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Mình tham khảo từ solution của anh Lê Anh Đức
    Thuật toán:
    -Nhận xét là tính chẵn lẻ của số bi đỏ ko đổi, vậy nên kết quả sẽ là số bi đỏ modulo 2.
    -Hãy thử tạo 1 test và sinh ra dãy A, các bạn sẽ nhận thấy dãy A tuần hoàn theo chu kì D+1, từ đó có thể giải quyết bài toán này. Sau đây là code của mình:

Code:

#include<bits/stdc++.h>
#define N 100001
using namespace std;
int t,n,d;
long long a[N], s[3];
int main()
{
	cin>>t;
	for (int z=1; z <= t; z++)
		{
			s[0]=s[1]=0;
			cin>>n>>d;
			for (int i=1; i <= d; i++)
				{
					cin>>a[i];
					s[a[i]]=s[a[i]]+1;
				}
			if (n == d)
				{
					cout<<s[1]%2<<endl;
					continue;
				}
			d=d+1;
			a[d]=s[1]%2;
			s[a[d]]=s[a[d]]+1;
			int ck=n/d;
			int du=n-ck*d;
			long long kq=s[1]*ck;
			for (int i=1; i <= du; i++)
				kq=kq + a[i]%2;
			cout<<kq%2<<endl;
		}
}
Chủ đề: SPOJ, Toán học Mức độ:

PVOI14_4 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

Uses    math;
const   fi      ='';
        fo      ='';
        maxN    =5*trunc(1e4)+1;
 
type    arr1    =array[0..maxN] of longint;
        arr2    =array[0..maxN,1..4] of longint;
 
var     n       :longint;
        a       :arr1;
        T       :arr2;
        cs      :arr1;
        f       :arr2;
procedure QS(var a,cs:arr1;l,r:longint);
var     i,j,x,tg        :longint;
begin
        i:=l;j:=r;
        x:=a[l+random(r-l+1)];
        repeat
                while a[i]<x do inc(i);
                while a[j]>x do dec(j);
                if i<=j then
                begin
                        tg:=a[i];a[i]:=a[j];a[j]:=tg;
                        tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if l<j then QS(a,cs,l,j);
        if i<r then QS(a,cs,i,r);
end;
 
Procedure Update(x,k,v:longint);
begin
        while x<=maxN do
        begin
                T[x,k]:=max(T[x,k],v);
                x:=x+x and (-x);
        end;
end;
 
function Get(x,k:longint):longint;
begin
        Get:=0;
        while x>0 do
        begin
                Get:=Max(Get,t[x,k]);
                x:=x-x and (-x);
        end;
end;
 
procedure xuly;
var     i, j    :longint;
        a2 :arr1;
        dem     :longint;
        max_h   :longint;
        tmp     :longint;
        ans     :longint;
begin
        for i:=1 to n do a2[i]:=a[i];
        fillchar(t,sizeof(t),0);
        QS(a2,cs,1,n);
        dem:=1;
        a[cs[1]]:=dem;
        for i:=2 to n do
                begin
                        if a2[i]>a2[i-1] then inc(dem);
                        a[cs[i]]:=dem;
                end;
        //for i:=1 to n do write(a2[i],' ');writeln;
        max_h:=dem;
        ///// 1
        for i:=1 to n do
                begin
                        f[i,1]:=Get(a[i]-1,1)+1;
                        Update(a[i],1,f[i,1]);
                end;
        ///2
        for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],2)+1;
                        if tmp<=2 then tmp:=0;
                        begin
                                f[i,2]:=tmp;
                                Update(max_h-a[i]+1,2,max(f[i,1],f[i,2]));
                        end;
                end;
       // writeln(f[5,2]);
        ///3
         for i:=1 to n do
                begin
                        tmp:=Get(a[i]-1,3)+1;
                        if tmp<=3 then tmp:=0;
 
                        begin
                                f[i,3]:=tmp;
                                Update(a[i],3,max(f[i,2],f[i,3]));
                        end;
                end;
         //writeln(f[11,3]);
         //4
          for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],4)+1;
                        if tmp<=4 then tmp:=0;
 
                        begin
                                f[i,4]:=tmp;
                                Update(max_h-a[i]+1,4,max(f[i,3],f[i,4]));
                        end;
                end;
         // writeln(f[14,4]);
          ans:=0;
          for i:=1 to n do ans:=max(ans,f[i,4]);
          writeln(ans);
end;
procedure run;
var     i :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        cs[i]:=i;
                end;
        xuly;
        close(input);close(output);
end;
 
begin
        run;
end.
Chủ đề: BIT Mức độ:

PVOI14_6 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
int factorial(int n, long long MOD) {
    int ret = 1;
    for(int i = 1; i <= n; i++) ret = ((long long)(ret) * i) % MOD;
    return ret;
}
 
int power(int x, int k, long long MOD) {
    if (k == 0) return 1;
    long long t = power(x, k / 2, MOD);
    t = (t * t) % MOD;
    if (k % 2 == 1) t = (t * x) % MOD;
    return t;
}
 
int count_in_grid(int m, int n, int s) {
    return max(0, min(max(0, s - 1), m) - max(max(0, s - n), 1) + 1);
}
 
int calc(int m, int n, long long MOD) {
    int x = 1;
    for(int i = 1; i < m + m; i++) {
        int j = m + m + 1 - i;
        int k = count_in_grid(m - n, m - n, j) + 2 * count_in_grid(n, m - n, j - m);
        x = ((long long)(x) * power(i, k, MOD)) % MOD;
    }
    int ret = ((long long)(factorial((long long)(m) * m - (long long)(n) * n, MOD)) * power(x, MOD - 2, MOD)) % MOD;
    return ret;
}
 
int main()
{
    //freopen("L.inp","r",stdin);
    //freopen("L.out","w",stdout);
	int m, n ;
	long long MOD;
    cin >> m >> n >> MOD;
    cout << calc(m, n, MOD);
}
Chủ đề: Toán học Mức độ: ,

PVOI14_3 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Ta có 1 công thức sau:

Gọi k là chi phí nhỏ nhất cần tìm.

Nếu tồn tại một chuyến đi để mất chi phí là k thì

(S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp) = k

⇔ S1 + S2 + … + Sp – k * (T1 + T2 + … + Tp) = 0

⇔ (S1 – k * T1) + (S2 – k * T2) + … + (Sp – k * Tp) = 0.

 

Giả sử tồn tại 1 chuyến đi có chi phí km < k khi đó ta có:

kmin < k = (S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp)

⇔ (S1 – kmin * T1) + (S2 – kmin * T2) + … + (Sp – kmin * Tp) > 0

 

Từ đây ta có nghĩ ra 1 thuật toán như sau.

  • Chặt nhị phân chi phí nhỏ nhất(x), với mỗi chi phí Mình tạo trọng số mỗi cho mỗi cạnh (s ,t) -> (s – x * t)
  • Nếu tồn tại 1 chu trình âm với trọng số mới -> không thể tạo ra chi phí là x.
  • Ngược lại nếu không tồn tại 1 chu trình âm nào thì kết quả cần tìm sẽ <=x
    => Chúng ta có thể sử dụng thuật toán FordBellman để tìm chu trình âm

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
#define N 1010
#define M 10010
const double esp = 1e-5;
 
int n, m,  trace[N], u[M], v[M], c[M];
double d[N];
 
bool Ok(int x, int y) {
    while (x != 1){
        x = trace[x];
        if (x == 0) return false;
        if (x == y) return true;
    }
    return false;
}
bool FordBellman(double mid) {
    for (int i = 1; i<=n; i++) d[i] = 1e18;
    d[1] = 0;
    memset(trace, 0, sizeof trace);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            int x = u[j]; int y = v[j];
            if (d[y] > d[x] + c[j] - mid) {
                d[y] = d[x] + c[j] - mid;
                if (Ok(x, y)) {
                    return true;
                }
                trace[y] = x;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i<m; i++) {
        cin>>u[i]>>v[i]>>c[i];
    }
    double l = 0;
    double r = 1e10;
    double cur = 0;
    while (r - l >= esp) {
        double mid = (l + r) / 2;
        if (!FordBellman(mid)) {
            cur = mid;
            l = mid;
        }else r = mid;
    }
    if (abs (cur - 1e10) <=esp) {
        cout<<"NO TOUR";
    }else
    cout<<fixed<<setprecision(2)<<cur;
}
{$MODE OBJFPC}
program SmartDogContest;
const
  InputFile  = '';
  OutputFile = '';
  maxN = 1000;
  maxM = 10000;
  maxW = 1000000000;
  maxD = (maxN + 1) * maxW;
type
  TEdge = record
    u, v, c: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[1..maxM] of TEdge;
  d: array[1..maxN + 1, 1..maxN] of Int64;
  n, m: Integer;
  BestMiu: Extended;
 
procedure Enter;
var
  i: Integer;
begin
  ReadLn(fi, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, c);
end;
 
procedure Init;
var
  i: Integer;
begin
  FillQWord(d, SizeOf(d) div 8, maxD);
  for i := 1 to n do
    d[1, i] := 0;
end;
 
procedure Minimize(var target: Int64; value: Int64); inline;
begin
  if target > value then target := value;
end;
 
procedure Optimize;
var
  k, i: Integer;
begin
  for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
    for i := 1 to m do
      with e[i] do
        Minimize(d[k, v], d[k - 1, u] + c);
end;
 
procedure GetBest;
var
  v, k: Integer;
  min, max, trial: Extended;
begin
  min := maxD;
  for v := 1 to n do
    if d[n + 1, v] < maxD then
      begin
        max := -maxD;
        for k := 1 to n do
          if d[k, v] < maxD then
            begin
              trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
              if max < trial then max := trial;
            end;
        if max < min then
          min := max;
      end;
  BestMiu := min;
end;
 
begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    Init;
    Optimize;
    GetBest;
    if BestMiu = maxD then
      Write(fo, 'NO TOUR')
    else
      Write(fo, BestMiu:0:2);
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.
Chủ đề: Đồ thị, Floyd, SPOJ Mức độ: ,

PVOI14_2 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e6;
const int INF = 1e9 + 7;
typedef pair<int, int> ii;
 
int p[MAXN], a[1001][1001];
vector < ii > adj[MAXN];
int n, maxa;
 
int get(int i, int j)
{
    return (i - 1) * n + j;
}
 
int pa(int x)
{
    while (p[x] > 0) x = p[x];
    return x;
}
 
int Union(int r1, int r2)
{
    int tmp = p[r1] + p[r2];
    if (p[r1] < p[r2]){
        p[r2] = r1;
        p[r1] = tmp;
    } else{
        p[r1] = r2;
        p[r2] = tmp;
    }
    return -tmp;
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
//	freopen("RSELECT.inp", "r", stdin);
  //  freopen("RSELECT.out", "w", stdout);
    cin >> n;
    FORE(i, 1, n) FORE(j, 1, n) {
        cin >> a[i][j];
        maxa = max(maxa, a[i][j]);
    }
    FORE(i, 1, n) FORE(j, 1, n){
        int u = get(i, j);
        if (i < n) adj[abs(a[i][j] - a[i + 1][j])].push_back(ii(u, get(i + 1, j)));
        if (j < n) adj[abs(a[i][j] - a[i][j + 1])].push_back(ii(u, get(i, j + 1)));
    }
    memset(p, -1, sizeof(p));
    int ans = 0;
    FORE(ll, 0, maxa){
        FOR(i, 0, adj[ll].size()) {
            p[adj[ll][i].first] = -1;
            p[adj[ll][i].second] = -1;
           // cout<<ll<<" "<<adj[ll][i].first<<" "<<adj[ll][i].second<<endl;
        }
        FOR(i, 0, adj[ll].size()){
            int u = adj[ll][i].first, v = adj[ll][i].second;
            int r1 = pa(u), r2 = pa(v);
            if (r1 != r2) ans = max(ans, Union(r1, r2));
        }
    }
    cout<<ans<<endl;
	return 0;
}
Chủ đề: Đồ thị, Kruskal Mức độ: ,

PVOI14_5 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code: (ideone)

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
 
const int MAXN = 1000000 + 10;
const int MAXV = 10000 + 10;
 
int freq[MAXV];
int a[MAXN];
int c[MAXN];
vector<pair<int, int> > b[MAXV];
int n;
 
void init() {
    vector<bool> p(MAXV, true);
    p[0] = p[1] = false;
    for(int i = 2; i * i <= 10000; i++) {
        if (p[i]) {
            int j = i + i;
            while (j <= 10000) {
                p[j] = false;
                j += i;
            }
        }
    }
    vector<int> prime;
    for(int i = 1; i <= 10000; i++) {
        if (p[i]) prime.push_back(i);
    }
    for(int i = 1; i <= 10000; i++) {
        if (freq[i] == 0) continue;
        for(int j = 0; j < prime.size(); j++) {
            int cnt = 0;
            int v = i;
            while (v % prime[j] == 0) {
                cnt++; v /= prime[j];
            }
            b[prime[j]].push_back(make_pair(cnt, freq[i]));
        }
    }
}
 
long long power(int x, int k) {
    long long ret = 1;
    for(int i = 1; i <= k; i++) ret *= x;
    return ret;
}
 
int main()
{
    //freopen("P.inp", "r", stdin);
    //freopen("P.out", "w", stdout);
 
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) freq[a[i]]++;
    init();
    long long ans1 = 0; long long ans2 = 1;
    for(int i = 1; i <= 10000; i++) {
        if (b[i].size() > 0) {
            for(int j = 0; j <= 50; j++) c[j] = 0;
            for(int j = 0; j < b[i].size(); j++) c[b[i][j].first] += b[i][j].second;
            long long tot = 0;
            for(int j = 0; j <= 50; j++) tot += (long long)(j) * c[j];
            int p = (n + 1) / 2, l = 0;
            long long s = 0;
            for(int j = 0; j <= 50; j++) {
                s += (long long)(j) * c[j]; l += c[j];
                if (l >= p) {
                    int kk = (long long)(l) * j - s + (tot - s) - (long long)(n - l) * j;
                    ans1 += (long long)(l) * j - s + (tot - s) - (long long)(n - l) * j;
                    ans2 *= power(i, j);
                    break;
                }
            }
        }
    }
    cout << ans1 << " " << ans2 << endl;
}
Chủ đề: Toán học

LEM3 – spoj

November 17, 2016 by 2 Comments

Đề bài:

Thuật toán:

  • Đây là bài cơ bản của thuật toán quy hoạch động trạng thái.
  • Nếu giải bài này bằng duyệt sẽ không ăn được hết test.
  • Gọi F[i,state] là độ dài hành trình ngắn nhất khi đến được i và trạng thái thăm/chưa thăm các thành phố là state
    • state có dạng dãy bit 0,1. 1 là đã thăm, 0 là chưa thăm

Code:

Pascal (ideone)

uses    math;
const   fi='';
        fo='';
        maxn = 16;
        oo = 1 shl 16 -1;
var     f       :array[0..oo,1..maxn] of longint;
        i,j,n   :longint;
        c       :array[1..maxn,1..maxn] of longint;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(c[i,j]);
        close(input);
end;
function getbit( i,x :longint):byte;
begin
        getbit := (x shr (i-1)) and 1;
end;
function turnoff( i,x   :longint):longint;
begin
        turnoff := x and not (1 shl (i-1));
end;
procedure process;
var     i,j,k,t,state   :longint;
begin
        t := 1 shl n -1;
        for i:= 0 to t do
                for j:=1 to n do
                        f[i,j] := trunc(1e9);
        for i := 0 to t do
                for j := 1 to n do
                        if getbit(j,i)=1 then
                        begin
                                state := turnoff(j,i);
                                if state = 0 then begin f[i,j] := 0; break; end;
                                for k:=1 to n do
                                        if getbit(k,i)=1 then
                                                f[i,j] := min(f[i,j], f[state,k] + c[k,j]);
                        end;
        res := trunc(1e9);
        for i:=1 to n do
                res := min(res, f[t,i]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++ (ideone)

#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 1e5 ;
const int base = 1e9 + 7;
const int maxa = 1e6 * 5 + 1;
const int N = 50;
using namespace std;
int n,a[N][N],f[maxn][N],t[N],ans;
 
int get(int x,int i)
{
    return (x>>(i-1))&1;
}
 
int off(int x,int i)
{
    return x ^ (1<<(i-1));
}
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("trip.INP","r",stdin);
    //freopen("trip.OUT","w",stdout);
    cin>>n;
    fore(i,1,n)
    fore(j,1,n) cin>>a[i][j];
    int xx = (1<<n)-1;
    fore(x,1,xx)
    {
        int l = 0;
        fore(i,1,n)
        if (get(x,i)) t[++l] = i;
        if (l == 1) continue;
        fore(i,1,l)
        {
            int x1 = off(x,t[i]);
            f[x][t[i]] = base;
            fore(j,1,l)
            if (i != j && f[x][t[i]] > f[x1][t[j]] + a[t[j]][t[i]])
                f[x][t[i]] = f[x1][t[j]] + a[t[j]][t[i]];
            //if (x == 36)
                //cout<<t[i]<<' '<<f[x][t[i]]<<endl;
        }
    }
    ans = base;
    //cout<<get(36,1)<<endl;
    fore(i,1,n)
    ans = min(ans , f[xx][i]);
    cout<<ans;
    return 0;
}
Chủ đề: Quy hoạch động trạng thái Mức độ: