---
title : 題解：第一次讀書會
tags : solution
---

# UVa 100 - The 3n+1 problem
- [UVa100 - The 3n+1 problem](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=36)

這題的數字範圍很小，所以還不用太在意會出現超時(TLE)的情形，
用最簡單的邏輯解吧(我個人習慣會把這個東西寫成function)：

# include <iostream>
# include <cmath>
using namespace std;

int cycle_len(int n){
    int l = 1;
    
    while( n!=1 )
        n = (n&1 ? 3*n+1 : n/2), l++;
        
    return l;
}

int main(){
    int a,b,max_len;
    
    while(cin>>a>>b){
        max_len = 0;
        if(a>b) //XOR-swap
            a^=b, b^=a, a^=b;
        cout<<a<<' '<<b<<' ';
        
        while(a<=b)
            max_len = max(cycle_len(a++),max_len);
            
        cout<<max_len<<"\n";
    }
}

嗯...執行時間有點久呢(310ms)，
如果數字範圍很大的話，這個寫法就會炸掉了OAO

**<font color= red>( !!! 以下做法超出目前範圍，看不懂的話沒事的 !!! )</font>**

其實從數字的規律來看，是可以找出一種加速解的。
假設一個n的值是13，將其拿去跑3n+1的迴圈，會得出：
[ 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 ]
套用函式可以得出：

cycle_length(13) = 10、
cycle_length(40) = 9、
cycle_length(20) = 8、...

其實很多時候，這種3n+1數列是會出現重複元素的，比如說n=22時：
[22, 11, 34, 17, 52, 26, <font color=red>13, 40, 20, 10, 5, 16, 8, 4, 2, 1</font> ]
或是n=32時：[32, <font color=red>16, 8, 4, 2, 1</font>]
如果有方法能夠紀錄已經算過的cycle_length值，
理所當然就可以省去很多步循環操作的步驟。

有一個簡單的作法，用陣列來存！！！！！！

cycle_length[13] = 10、
cycle_length[40] = 9、
cycle_length[20] = 8、...

(陣列範圍得開得盡量大，好讓循環過程中所產生的n都能被存入陣列)

這種紀錄前面已經計算過的數值的方式，稱之為「<font color=blue>動態規劃(Dynamic Programming)</font>」，
是一種利用記憶體空間換取時間的加速方式
(未來學習演算法與一些難題，都會很常用到這種方式)

以下為本題利用動態規劃加速後的Solution Code：

# include <iostream>
# include <cmath>
using namespace std;

int dp[1000000];

int cycle_len(const int &n) {

    if(n<1000000) {
        if(dp[n])
            return dp[n];
        return dp[n] = 1 + cycle_len(n&1 ? 3*n+1 : n/2);
    }

    return 1 + cycle_len(n&1 ? 3*n+1 : n/2);
}

int main() {
    int a,b,max_len;

    while(cin>>a>>b) {
        cout<<a<<' '<<b<<' ';
        max_len = 0;
        dp[1] = 1;
        if(a>b) //XOR-swap
            a^=b, b^=a, a^=b;

        while(a<=b)
            max_len = max(cycle_len(a++),max_len);

        cout<<max_len<<"\n";
    }
}

(時間複雜度為O(n)，I/O加速後，其程式碼耗時為0ms)

---

# ZJ e800 - 影片推薦

- [e800 - 影片推薦](https://zerojudge.tw/ShowProblem?problemid=e800)

用struct下去寫，可以在讀取的時候就用float讀取，
(注意：小於2的24次方純整數在存到float的時候並不會出現精準度的問題)
記得存優先度的時候要用float，
比較麻煩的部分是在sort，可以選擇用泡沫排序法來排序
(推薦可以嘗試把sort寫成一個函式)

我想你們應該都已經聽說了(?)，在algorithm裡面有個sort的函式可以用，
但是sort只能排單一變數......嗎?
以下定義一個cmp函式，可以自訂比較數據方式的寫法：

# include <iostream>
# include <string>
# include <algorithm>
using namespace std;

struct Film {
    string name;
    float prior;
};

bool cmp(Film a, Film b) {
    return a.prior > b.prior;
}

int main() {
    int N,n;
    float p,l,w,r;
    Film f[50];

    cin>>N;
    for(n = 0 ; n<N ; n++) {
        cin>>f[n].name>>p>>l>>w>>r;
        f[n].prior = p*w/l*r;
    }
    sort(f,f+N,cmp);
    
    for(n = 0 ; n<N ; n++)
        cout<<f[n].name<<"\n";
}

---

# ZJ e799 - 資工系的浪漫

- [e799 - 資工系的浪漫](https://zerojudge.tw/ShowProblem?problemid=e799)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    while (cin >> n >> m){
        char c; cin >> c;
        while (n--){
            long long int num; cin >> num;
            string s="";
            for (int i=0;i<m;i++){
                if (num%2)s+='1';
                else s+='0';
                num/=2;
            }
            //cout << s << endl;
            for(int i=m-1;i>=0;i--){
                if (s[i] == '1') cout << c << " ";
                else cout << ". ";
            }
            cout << "\n";
        }
    }
}

#include<iostream>
using namespace std;

int main(){
    int N,M;
    long long int i,a;

    char c;
    cin>>N>>M>>c;
    while(N--){
        cin>>i;
        a = (long long int)1<<(M-1);

        if(i>=a)
            cout<<c, i-=a;
        else
            cout<<".";

        while(a>>=1){
            if(i>=a)
                cout<<" "<<c, i-=a;
            else
                cout<<" .";
        }
        cout<<"\n";
    }
}

Python version：

import sys

for l in [input()]:
    n,m=list(map(int, l.replace('\n','').split(' ')))
    c=str(input())
    for j in range(n):
        num=int(input().replace('\n',''))
        s=''
        for i in range(m):
            if num%2: s+='1'
            else: s+='0'
            num//=2
        #print(s)
        
        for i in range(m-1,-1,-1):
            if s[i]=='1': print(c,end=' ')
            else: print('.',end=' ')
        print()

---

# UVa 272 - TEX Quotes
- [UVa 272 - TEX Quotes](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=208)

這一題其實並不需要過多的花招，
用純C的語法下去寫是最好寫的，
在抓入一個字元，判斷是不是雙引號，
再判斷現在的狀態是第一個雙引號還是第二個雙引號就好
(切換狀態的方式可以用XOR就好，就不需要用條件判斷之類的了)

# include <stdio.h>

int main(){
    char c;
    bool first = true;

    while( ( c = getchar() ) != EOF ){
        if(c == '\"') {
            putchar(first ? '`' : '\'');
            putchar(first ? '`' : '\'');  // do twice
            first ^= true; // switch mode
        }
        else
            putchar(c);
    }
}

###### posted date: