2016年11月10日 星期四

TIOJ 1297 - 第三題　發人的經驗獎勵

http://tioj.infor.org/problems/1297

 其實直接除基本上就好了(?
但是因為是浮點數 怕會有誤差啥的
所以求出原本的值之後怕爛掉所以在那附近掃一下就好了

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main(){
    int d;
    while(cin>>d){
        if(d<0){cout<<"stupid\n";continue;}
        if(d==0){cout<<"0\n";continue;}
        int res = (int)(((long double)d)*100/101)-2;
        for(;res<1026;res++){
            if((int)(((long double)res)*101/100)==d) break;
        }
        if(res<0 || res>1024)cout<<"stupid\n";
        else cout<<res<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1126 - 尋找對稱字串

http://tioj.infor.org/problems/1126

 長度短短的 $n^2$ 硬幹就好了

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int mx=0;
        for(int i=0;i<(int)s.length();i++){
            for(int j=0;i-j>=0 && i+j<(int)s.length();j++){
                if(s[i-j]==s[i+j]){
                    mx=max(mx,2*j+1);
                    continue;
                }
                else{
                    mx=max(mx,2*j-1);
                    break;
                }
            }
        }
        for(int i=0;i<(int)s.length();i++){
            for(int j=0;i-j>=0 && i+1+j<(int)s.length();j++){
                if(s[i-j]==s[i+1+j]){
                    mx=max(mx,2*j+2);
                    continue;
                }
                else{
                    mx=max(mx,2*j);
                    break;
                }
            }
        }
        cout<<mx<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1110 - [入門] Bat-Bogey

http://tioj.infor.org/problems/1110

統計統計就好



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;

int alp[30];

int main(){
    int n;
    cin>>n;
    while(n--){
        memset(alp,0,sizeof(alp));
        int k;
        cin>>k;
        string s;
        cin>>s;
        int mx=0;
        for(int i=0;i<k;i++){
            alp[s[i]-'a']++;
            mx=max(mx,alp[s[i]-'a']);
        }
        for(int i=0;i<26;i++){
            if(alp[i]==mx){
                cout<<(char)(i+'a');
            }
        }
        cout<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1047 - C.邏輯計算機

http://tioj.infor.org/problems/1047

 照著優先順序做事就好 做完的就把運算元清掉
然後把運算子的地方換成答案

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin>>s && s[0]!='E'){
        bool nt=0;
        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='!'){
                nt=!nt;
                s[i]=' ';
            }
            if(s[i]=='0' && nt){
                s[i]='1';
                nt=0;
            }
            if(s[i]=='1' && nt){
                s[i]='0';
                nt=0;
            }
        }

        // cout<<"not processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='*'){
                int j,k;
                for(j=i;j>=0 && s[j]!='1' && s[j]!='0';j--){}
                for(k=i;k<(int)s.length() && s[k]!='1' && s[k]!='0';k++){}
                int jj=s[j]-'0';
                int kk=s[k]-'0';
                int res=jj&kk;
                // cout<<"process and with jj="<<jj<<" and kk="<<kk<<". res="<<res<<endl;
                s[i]=res+'0';
                s[j]=' ';
                s[k]=' ';
            }
        }

        // cout<<"and processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='+'){
                int j,k;
                for(j=i;j>=0 && s[j]!='1' && s[j]!='0';j--){}
                for(k=i;k<(int)s.length() && s[k]!='1' && s[k]!='0';k++){}
                int jj=s[j]-'0';
                int kk=s[k]-'0';
                int res=jj|kk;
                s[i]=res+'0';
                s[j]=' ';
                s[k]=' ';
            }
        }

        // cout<<"all processed:"<<s<<"--\n";

        for(int i=0;i<(int)s.length();i++){
            if(s[i]=='1' || s[i]=='0'){
                cout<<s[i]<<'\n';
            }
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1030 - Floor Machine

http://tioj.infor.org/problems/1030

 greedy做事就好
為了節省樓層 所以每個樓層如果能讓兩個胖虎的歌聲都存在就好(當然那層不能有人)
所以讓大的排在一起 空隙就會比較小

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int r[100005];

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    while(cin>>n && n){
        for(int i=0;i<n;i++){
            cin>>r[i];
        }
        sort(r,r+n);
        ll ans=1;
        for(int i=0;i<n;i++){
            ans+=r[i];
        }
        ans+=r[n-1];
        cout<<ans<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1833 - Problem B 陽炎眩亂

http://tioj.infor.org/problems/1833

 還是很普通的disjoint-set

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int n,m;
int djs[100005];

int F(int a){
    if(djs[a]==a)return a;
    else return djs[a] = F(djs[a]);
}
void U(int a,int b){
    a=F(a);
    b=F(b);
    djs[b]=a;
}
void P(){
    cout<<"djs:";for(int i=1;i<=n;i++)cout<<djs[i]<<" ";cout<<endl;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)djs[i]=i;
    while(m--){
        string s;
        cin>>s;
        if(s[0]=='M'){
            int a,b;
            cin>>a>>b;
            U(a,b);
            // P();
        }
        else{
            int k;
            cin>>k;
            cout<<F(k)<<'\n';
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1312 - 家族

http://tioj.infor.org/problems/1312

 很普通的disjoint-set

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
int n,m;
int djs[10005];

int F(int a){
    if(djs[a]==a)return a;
    else return djs[a] = F(djs[a]);
}
void U(int a,int b){
    a=F(a);
    b=F(b);
    if(b>a)swap(a,b);
    djs[a]=b;
}
void P(){
    cout<<"djs:";for(int i=1;i<=n;i++)cout<<djs[i]<<" ";cout<<endl;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>n>>m){
        memset(djs,0,sizeof(djs));
        for(int i=1;i<=n;i++)djs[i]=i;
        while(m--){
            int a,b;
            cin>>a>>b;
            U(a,b);
            // P();
        }
        int k;
        cin>>k;
        cout<<F(k)<<'\n';
    }
}
張貼者： 於 沒有留言:

TIOJ 1013 - Fire in the forest

http://tioj.infor.org/problems/1013

 就火跟人一起BFS就好了
然後人不能走的地方火也不能走
我當初卡這個卡好久 不知道在幹嘛((

 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

struct pnt{
    int x,y,len;
    pnt():x(0),y(0),len(0){};
    pnt(int xx,int yy,int lll):x(xx),y(yy),len(lll){};
};

string mp[10]={
    "*****************",
    "*...*.......**..*",
    "**..*....*.*.*..*",
    "*......*.**.**.**",
    "*..**...**..**.**",
    "**.....**..*.*..*",
    "*....*..........*",
    "*.....****.*...**",
    "****.*.*........*",
    "*****************"
};
int n,m,t;
int fx,fy,sx,sy,ex,ey;
bool gone[20][20],fgone[20][20];

queue<pnt> fq,mq;

void fWalk(){
    if(fq.empty())return;
    int time = fq.front().len;
    while(fq.size() && fq.front().len==time){
        pnt tmp = fq.front();fq.pop();
        int x = tmp.x,y = tmp.y,len = tmp.len;
        if(!fgone[x+1][y] && (mp[x+1][y]=='.' || mp[x+1][y]=='w') && x+1 <n){fgone[x+1][y]=1;mp[x+1][y]='*';fq.push({x+1,y,len+1});};
        if(!fgone[x-1][y] && (mp[x-1][y]=='.' || mp[x-1][y]=='w') && x-1>=0){fgone[x-1][y]=1;mp[x-1][y]='*';fq.push({x-1,y,len+1});};
        if(!fgone[x][y+1] && (mp[x][y+1]=='.' || mp[x][y+1]=='w') && y+1 <m){fgone[x][y+1]=1;mp[x][y+1]='*';fq.push({x,y+1,len+1});};
        if(!fgone[x][y-1] && (mp[x][y-1]=='.' || mp[x][y-1]=='w') && y-1>=0){fgone[x][y-1]=1;mp[x][y-1]='*';fq.push({x,y-1,len+1});};
    }
}

int meGo(){
    if(mq.empty())return -1;
    int time = mq.front().len;
    while(mq.size() && mq.front().len==time){
        pnt tmp = mq.front();mq.pop();
        int x=tmp.x, y=tmp.y, len=tmp.len; if(mp[x][y]=='*') continue;
        if(mp[x][y]=='!' || (x==ex && y==ey))return len;
        if(!gone[x+1][y] && mp[x+1][y]!='*'){if(mp[x+1][y]!='!'){mp[x+1][y]='w';}if(mp[x+1][y]=='!'){return len+1;}gone[x+1][y]=1;mq.push({x+1,y,len+1});};
        if(!gone[x-1][y] && mp[x-1][y]!='*'){if(mp[x-1][y]!='!'){mp[x-1][y]='w';}if(mp[x-1][y]=='!'){return len+1;}gone[x-1][y]=1;mq.push({x-1,y,len+1});};
        if(!gone[x][y+1] && mp[x][y+1]!='*'){if(mp[x][y+1]!='!'){mp[x][y+1]='w';}if(mp[x][y+1]=='!'){return len+1;}gone[x][y+1]=1;mq.push({x,y+1,len+1});};
        if(!gone[x][y-1] && mp[x][y-1]!='*'){if(mp[x][y-1]!='!'){mp[x][y-1]='w';}if(mp[x][y-1]=='!'){return len+1;}gone[x][y-1]=1;mq.push({x,y-1,len+1});};
    }
    return -1;
}

void P(){
    cout<<"now map:\n";
    for(int i=0;i<n;i++){
        cout<<mp[i]<<endl;
    }
    cout<<endl;
}

void S(){
    fq.push({fx,fy,0});
    mp[fx][fy]='*';
    fgone[fx][fy]=1;
    // cout<<"Init map: ";
    // P();
    for(int time=1;time<t;time++){
        fWalk();
        // P();
    }
    // P();
    // cout<<"pre gone.\n\n";

    mq.push({sx,sy,0});
    gone[sx][sy]=1;
    int cnt=1200;
    while(mq.size()){
        int res = meGo();
        if(res!=-1){
            cout<<res<<endl;
            return;
        }
        fWalk();
        // P();
    }
    cout<<"Help!\n";
}

int main(){
    n=10,m=17;
    fx=rit(),fy=rit(),t=rit(),sx=rit(),sy=rit(),ex=rit(),ey=rit();

    mp[ex][ey]='!';

    S();
}
張貼者： 於 沒有留言:

TIOJ 1355 - 河內之塔-蘿莉塔

http://tioj.infor.org/problems/1355

 普通到不能再普通的河內塔(?

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
}

int n;
int cnt;

void o(int a,int b){
    printf("#%d : move the dish from #%d to #%d\n",cnt++,a,b);
}

void Hn(int from,int dist,int step,int tmp){
    if(step==1){
        o(from,dist);
        return;
    }
    Hn(from,tmp,step-1,dist);
    o(from,dist);
    Hn(tmp,dist,step-1,from);
    return;
}

int main(){
    cin>>n;
    cnt=1;
    Hn(1,3,n,2);
}
張貼者： 於 沒有留言:

TIOJ 1026 - 惡猿果實

http://tioj.infor.org/problems/1026

 反過來想 一開始先從最大步的開始走 然後每次/2
就發現 如果現在的數是正的 代表這一步一定是向右走的
(因為就算全部都往左最後往右還是正的) 反之
所以就扣掉(或加回來) 然後繼續走 直到回原點
然後記得反過來輸出就好

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define ll long long

string ans;
ll d,mxi;

void walk(){
    if(d>0){
        ans='+'+ans;
        d-=mxi;
    }
    else{
        ans='-'+ans;
        d+=mxi;
    }
    mxi>>=1;
}

int main(){
    cin>>d;
    {
        mxi=1;
        for(;mxi<=d;mxi<<=1){}
        mxi>>=1;
    }
    while(d){
        walk();
    }
    cout<<ans.length()<<'\n'<<ans<<'\n';
}
張貼者： 於 沒有留言:

TIOJ 1185 - 三角蕃的煩惱

http://tioj.infor.org/problems/1185

 三角形基本性質
用int小心會噴掉

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
unsigned int a[3];
int main(){
    while(cin>>a[0]>>a[1]>>a[2]){
        sort(a,a+3);
        if(a[0]+a[1]>a[2]){
            cout<<"SAFE\n";
        }
        else{
            cout<<"BYE\n";
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1031 - Collecting Beans

http://tioj.infor.org/problems/1031

 分堆的時候如果出現奇數就會被丟掉(?
所以能夠進桶的豆子就是比那個數字小的最大的2的冪次

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
    ios_base::sync_with_stdio(0);
    while(getline(cin,s)){
        if(s[0]=='0')break;
        stringstream ss;ss<<s;
        int ans=0,n;
        while(ss>>n && n){
            int i;
            for(i=1;i<=n;i<<=1){}
            ans+=(i>>1);
        }
        cout<<ans<<'\n';
    }
}
張貼者： 於 沒有留言:
訂閱： 文章 (Atom)