Codeforces #1493B Planet Lapituletti

문제

https://codeforces.com/problemset/problem/1493/B

걸린 시간

01 : 29 : 26

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

string twoDigit(int input){
    if(input < 10) return "0" + to_string(input);
    else return to_string(input);
}

vector<string> split(string input, char delimiter){
    vector<string> ret;
    istringstream iss(input);
    string token;
    while(getline(iss, token, delimiter))
        ret.push_back(token);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int h, m;
        cin >> h >> m;
        string s;
        cin >> s;
        int valid = 0;
        valid |= 1<<0;
        valid |= 1<<1;
        valid |= 1<<2;
        valid |= 1<<5;
        valid |= 1<<8;
        // init
        vector<string> hm = split(s, ':'); 
        int time = atoi(hm[0].c_str())*m+atoi(hm[1].c_str());
        map<char, char> dict;
        dict['0'] = '0';
        dict['1'] = '1';
        dict['2'] = '5';
        dict['5'] = '2';
        dict['8'] = '8';
        while(true){
            int ch = (time/m)%h;
            int cm = time%m;
            string sh = twoDigit(ch);
            string sm = twoDigit(cm);
            int alphabet = 0; 
            for(int c : sh) alphabet |= 1<<(int)c-0x30;
            for(int c : sm) alphabet |= 1<<(int)c-0x30;
            if(valid == (alphabet |= valid)){
                string rh = sh;
                string rm = sm;
                reverse(all(rh));
                rh[0] = dict[rh[0]];
                rh[1] = dict[rh[1]];
                reverse(all(rm));
                rm[0] = dict[rm[0]];
                rm[1] = dict[rm[1]];
                if(atoi(rh.c_str()) < m && atoi(rm.c_str()) < h){
                    cout << sh << ":" << sm << "\n";
                    break;
                }
            }
            time += 1;
        }
    }
    return 0;
}

Round 705 의 A 번 문제 이해에 시간을 다 사용하는 바람에 풀어보지 못한 문제이다. 설명이 매우 길어 어려워보이지만 읽어보면 반 이상은 풀이에 도움이 되지 않는 스토리이다.

Lapituletti 행성의 시간은 지구와 같이 흘러가지만 하루의 시간이 h 시간 m 분 까지 있다. h, m 과 현재 시간을 나타내는 문자열 s 가 주어질 때, 거울에 반사된 디지털 시계의 올바르게 읽히는 시간 중 시작 시간에 제일 근접한 시간을 구하는 것이 목표이다.

구현에 필요한 개념에는 문자열, 문자열 파싱, 비트마스킹 등 이 있다.