1301-D, *2000

Problem - D - Codeforces

문제

• 오일러 경로에 관련된 문제다

 

풀이

※ m = 1 인 경우 따로 처리해줘야한다

R ~ (m-1) 번
L ~ (m-1) 번
이후에는 다음 문자열이 (n-1) 번 반복된다
D/RUD/RUD/ ... /RUD ~ RUD 가 (m-1)개
LLL ... LLL ~ L 이 (m-1)개

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
int n, m, k;
string cycle = "";
string piece = "RUD";
 
void make_cycle()
{
    cycle += "D";
    loop(i, m-1) cycle += "RUD";
    loop(i, m-1) cycle += "L";
}
 
void sub_fill_in(vector<pair<int, string> >& res, int end) // end [1, cycle.size())
{
    res.emplace_back(1, "D");
    end -= 1;
    if(end == 0) return;
    if(end <= 3*(m-1)){
        int q = end/3;
        if(q == 0){
            res.emplace_back(1, piece.substr(0, end - 3*q));
            return;
        }
        res.emplace_back(q, piece);
        end -= 3*q;
        if(end == 0) return;
        res.emplace_back(1, piece.substr(0, end));
        return;
    }
    else{
        res.emplace_back(m-1, piece);
        end -= 3*(m-1);
        if(end == 0) return;
        res.emplace_back(end, "L");
        return;
    }
 
}
 
void fill_in(vector<pair<int, string> >& res)
{
    if(m == 1){
        if(k <= n-1){
            res.emplace_back(k, "D");
            return;
        }
        else{
            res.emplace_back(n-1, "D");
            k -= n-1;
        }
        res.emplace_back(k, "U");
        return;
    }
 
    if(k <= m-1){
        res.emplace_back(k, "R");
        return;
    }
    else{
        res.emplace_back(m-1, "R");
        k -= m-1;
    }
    if(k <= m-1){
        res.emplace_back(k, "L");
        return;
    }
    else{
        res.emplace_back(m-1, "L");
        k -= m-1;
    }
    int q = k/cycle.size();
    if(q == n-1){
        loop(i, n-1){
            res.emplace_back(1, "D");
            res.emplace_back(m-1, piece);
            res.emplace_back(m-1, "L");
        }
        k -= q*cycle.size();
        if(k == 0) return;
        else{
            res.emplace_back(k, "U");
            return;
        }
    }
    else{
        if(q == 0){
            sub_fill_in(res, k);
            return;
        }
        else{
            loop(i, q){
                res.emplace_back(1, "D");
                res.emplace_back(m-1, piece);
                res.emplace_back(m-1, "L");
            }
            k -= q*cycle.size();
            if(k != 0) sub_fill_in(res, k);
            return;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> k;
    int cri = 4*n*m-2*n-2*m;
    if(k <= cri){
        cout << "YES" << endl;
        vector<pair<int, string> > res;
        make_cycle();
        fill_in(res);
        cout << res.size() << endl;
        for(auto [f, s]: res) cout << f << ' ' << s << endl;
    }
    else cout << "NO" << endl;
 
    return 0;
}cs