---
# System prepended metadata

title: Uva solved problem records
tags: [C++, Uva]

---

# Uva solved problem records
###### tags: `C++` `Uva` 

&nbsp;

## 481 - What Goes Up

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=422)   
>[LIS,高等演算法整理](https://alan23273850.github.io/Online-Judge-Problems/algorithms/%E5%BA%8F%E5%88%97/2.-%E6%9C%80%E9%95%B7%E9%81%9E%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/)   
>[Binary Search (1)](https://medium.com/@lindingchi/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1)   
>[Binary Search (2)](https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%BA%8C-%E6%89%BE%E4%B8%8D%E5%88%B0%E6%80%8E%E9%BA%BC%E8%BE%A6-a308f5b9ce12)     
>[find()函式](https://www.geeksforgeeks.org/how-to-find-index-of-a-given-element-in-a-vector-in-cpp/)

### Code

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, i, j, l, r,n;
    vector<pair<int, int>> b; 
    vector<int> c;            
    stack<int>d;             
    while (cin >> a)          
    {
        b.push_back(make_pair(a, 1));
    }
    for (i = 0; i < b.size(); i++)
    {
        if (c.empty() or c.back() < b[i].first)
        {
            c.push_back(b[i].first);
            b[i].second = c.size();
        }
        else    
        {
            *lower_bound(c.begin(), c.end(), b[i].first) = b[i].first; 
            auto m = find(c.begin(), c.end(), b[i].first); 
            b[i].second = int(m - c.begin()) + 1; 
        }
    }
    n=c.size();
    for (i = b.size() - 1; i >= 0; i--)
    {
        if(b[i].second==n)
        {
            d.push(b[i].first);
            n--;
        }
    }
    cout << c.size() << "\n"
         << "-"
         << "\n";
    while(!d.empty())
    {
        cout<<d.top()<<"\n";
        d.pop();
    }
}
```

&nbsp;

## 11286 - Conformity

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2261)

### Steps

1. stringstream 分割字串 轉數字
2. algorithm 排序數字
3. ostringstream 合併數字成一個文字
4. map 以文字為索引 儲存數量
5. 儲存的同時尋找最大值
6. 遍歷 加總擁有最大值組合的人數
(可能課程組合不同 但同時都是最大的人數 要加一起)

### Code

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    stringstream s;
    ostringstream o;
    vector<int> b;
    map<string, int> q;
    int i, j, a, e, p, m, r;
    string c;
    while (cin >> i)
    {
        q.clear();
        r = 0;
        m = 1;
        p = i;
        getchar();
        if (i == 0)
            break;
        for (i; i > 0; i--)
        {
            getline(cin, c);
            b.clear();
            s.str("");
            s.clear();
            o.clear();
            o.str("");
            s << c;
            while (s >> a)
            {
                b.push_back(a);
            }
            sort(b.begin(), b.end());
            for (j = 0; j < b.size(); j++)
            {
                o << b[j];
            }
            q[o.str()]++;
            if (q[o.str()] > m)
            {
                m = q[o.str()];
            }
        }
        for (const auto &n : q)
        {
            if (n.second == m)
            {
                r += m;
            }
        }
        cout << r << "\n";
    }
}
```

&nbsp;

## 10035 - Primary Arithmetic

>2022/5/6

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=976)

### Code - 1

```cpp
//判斷式多 不簡潔
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    int i,j,k,l=0;
    while(cin>>a>>b)
    {
        l=0;
        k=0;
        if(a=="0" and b=="0")break;
        i=a.length()-1;
        j=b.length()-1;
        while(1)
        {
            if(j<0 and i<0 )break;
            if(min(i,j)<0 and max(i,j)>=0 and l==1)
            {
                if(i>j)
                {
                    if(int(a[i]-'0')+1>=10)k++;
                    else l=0;
                }
                else
                {
                    if(int(b[j]-'0')+1>=10)k++;
                    else l=0;
                }
            }
            else if(i>=0 and j>=0)
            {
                if(int(a[i]-'0')+int(b[j]-'0')+l>=10)
                {
                    k++;
                    l=1;
                }
                else
                {
                    l=0;
                }
            }else 
                break;
            j--;
            i--;
        }
        if(k==0)cout<<"No carry operation."<<"\n";
        else if (k==1)cout<<"1 carry operation."<<"\n";
        else cout<<k<<" carry operations."<<"\n";
    }
}
```

&nbsp;

### Code - 2

```cpp
//Better solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,i,j;
    while(cin>>a>>b)
    {
        i=0;
        j=0;
        while(a>=0 or b>=0)
        {
            if(a==0 and b==0)break;
            else if(a %10+b%10+i>=10)
            {
                i=1;
                j++;
            }
            else
            {
                i=0;
            }
            a=a/10;
            b=b/10;
        }
        if(j==0)cout<<"No carry operation."<<"\n";
        else if (j==1)cout<<"1 carry operation."<<"\n";
        else cout<<j<<" carry operations."<<"\n";
    }
}
```

&nbsp;

## 10252 - Common Permutation

>2022/5/6

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1193)

### Steps

1. 分別對兩個字串,以字母元素為索引,儲存數量
2. 比對兩個map,若有相同元素則匯入multiset
3. 同元素重複出現,則匯入多次
4. 遍歷multiset

### Code

```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<char,int>a,c;
    multiset<char>b;
    string i,j;
    int m;
    while(getline(cin,i),getline(cin,j))
    {
        m=0;
        a.clear();
        c.clear();
        b.clear();
        for(int l=0;l<i.length();l++)
        {
            a[i[l]]++;
        }
        for(int l=0;l<j.length();l++)
        {
            c[j[l]]++;
        }
        for(const auto &l:a)//l.first字母 l.second數量
        {
            if(c[l.first]>=1)
            {
                for(int i=1;i<=min(c[l.first],l.second);i++)
                {
                    b.insert(l.first);
                }
            }
        }
        for(const auto&l :b)
        {
            cout<<l;
        }
        cout<<"\n";
    }
}
```

&nbsp;

## 793 - Network Connections

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=734)

### Code

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    map<int, map<int, int>> e;
    vector<pair<int, int>> h;
    int a, b, g, d, m;
    char c;
    cin >> a;
    while (a--)
    {
        m = 0;
        h.clear();
        e.clear();
        cin >> b;
        getchar();
        while (cin.get(c))
        {
            if (c == '\n')
            {
                break;
            }
            else if (c == 'c')
            {
                cin >> g >> d;
                getchar();
                e[g][d] = 1;
                e[d][g] = 1;
            }
            else if (c == 'q')
            {
                cin >> g >> d;
                getchar();
                h.push_back(make_pair(g, d));
            }
        }
        for (const auto n : e)
        {
            e[n.first][n.first] = 1;
        }
        for (const auto t : h)
        {
            for (const auto n : e[t.first])
            {
                if (e[t.second][n.first] == 1)
                {
                    m++;
                    break;
                }
            }
        }
        cout << m << "," << h.size() - m << "\n\n";
    }
}
```

&nbsp;

## 245 - Uncompress

>2022/6/19

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=181)

### Code

```cpp
#include<bits/stdc++.h>
using namespace std;
vector<string> b;
string c,w;
int d=0;
int main()
{   
    while(getline(cin,c))
    {
        if(c =="0")break;
        c+='\n';
        for(int i=0;i<c.length();i++)
        {
            if(isalpha(c[i]))
            {
                w+=c[i];
            }
            else if(isdigit(c[i]))
            {
                d*=10; //進一位
                d+=int(c[i]-'0'); //新增一位
            }
            else //空格 標點符號
            {
                //判斷前一個是數字or單字
                if(d!=0)
                {
                    //是數字 讀取vector裡面的單字
                    cout<<b[d-1];
                    w=b[d-1];
                    b.erase(b.begin()+d-1);
                    b.insert(b.begin(),w);
                    w="";
                    d=0;
                }
                if(w!="")
                {
                    //是單字 新增到vector裡面
                    cout<<w; 
                    b.insert(b.begin(),w);
                    w="";
                }
                cout<<c[i];
            }
        }
    }
}
```

&nbsp;

## 10242 - Fourth Point

>2022/7/1

### Websites

>[online judge 題目連結](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1183)

### Steps

1. 輸入兩組點 , 共八個座標 , 兩組中各有一個相同的座標 (因為是兩條相鄰的邊)
2. 只有四種排列方式 用判斷式與```swap()``` 函式 , 將數據整理成同一種
3. 利用向量概念求出第個點
4. ```cout << fixed << setprecision(3)<<``` , 控制輸出三位小數

### Warning 

+ 要用```double``` , ```float``` 不夠精 , 會有四捨五入的問題

### Code

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<double> po; // points
string i;
double j;
double nex, ney;
stringstream ss;
int main()
{
    while (getline(cin, i))
    {
        ss.str("");
        ss.clear();
        ss << i;
        while (ss >> j)
        {
            po.push_back(j);
        }
        if (po[0] == po[4] and po[1] == po[5])
        {
            swap(po[0], po[2]);
            swap(po[1], po[3]);
        }
        else if (po[2] == po[6] and po[3] == po[7])
        {
            swap(po[4], po[6]);
            swap(po[5], po[7]);
        }
        else if (po[0] == po[6] and po[1] == po[7])
        {
            swap(po[0], po[2]);
            swap(po[1], po[3]);
            swap(po[4], po[6]);
            swap(po[5], po[7]);
        }
        nex = po[6] + po[0] - po[2];
        ney = po[7] + po[1] - po[3];
        cout << fixed << setprecision(3) << nex << " " << ney << "\n";
        po.clear();
    }
}

```

&nbsp;

## Problem

>Date

### Websites

>[online judge 題目連結]()

### Code

```cpp

```

&nbsp;

## Problem

>Date

### Websites

>[online judge 題目連結]()

### Code

```cpp

```

&nbsp;

## Problem

>Date

### Websites

>[online judge 題目連結]()

### Code

```cpp

```

&nbsp;

## Problem

>Date

### Websites

>[online judge 題目連結]()

### Code

```cpp

```

&nbsp;

## Problem

>Date

### Websites

>[online judge 題目連結]()

### Code

```cpp

```

&nbsp;
