20/04/06 유사코

• USACO 2020 January Contest

USACO 2020 January Contest

브론즈 문제들 (solved브론즈 아님... 브론즈도 맞긴한데)

코포 div 2,3 의 B정도 난이도 

 

Word Processor, 18322번

https://www.acmicpc.net/problem/18322

18322번: Word Processor

N개의 단어를 입력받아 임시저장한다. 임시정한 단어의 길이 합이 K이상이 되면 출력해준다.

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a, b;
    string s;
    string tem;
    int siz = 0;
    cin >> a >> b ;
    for (int i =1; i <= a; i++) {
        string tem2;
        cin >> tem2;
        if (siz + tem2.size() > b) {
            cout << tem << '\n';
            tem = tem2;
            siz = tem2.size();
        }
        else {
            siz += tem2.size();
            if (tem.size() != 0)
                tem += " ";
            tem += tem2;
        }
    }
    cout << tem;
}

 

Photoshoot, 18323번

https://www.acmicpc.net/problem/18323

18323번: Photoshoot

N-1개의 수를 입력받아($b_1, b_2, ...b_{n-1}$)

$b_i = a_i + a_{i+!}$을 만족하는 $a_1, a_2, ...a_{n-1}$들을 찾아 출력하면된다. 

단  여러개의 ai중 사전순으로 가장 작은 순으로 출력하여야 한다. $a_1$이 결정되면 나머지$a_1, a_2, ...a_{n-1}$들은 자동으로 고정 되므로 $a_1$ 를 1부터 n-1까지 증가시키면서 탐색하다 모든값이 정해지면 탈출한다.

onst int MAXN =1004;
 
int arr[MAXN];
bool che[MAXN];
vector<int> v;
int a;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> a;
    for (int i = 1; i < a; i++) {//a-1개 입력받기
        int tem;
        cin >> tem;
        v.push_back(tem);
    }
    for (int i = 1; i <= v[0]-1; i++) {
        for (int j = 0; j <= a; j++)
            che[j] = 0;
        che[i] = 1;
        arr[0] = i;
        int che1 = 0;
        for (int j = 1; j < a; j++) {
            int next = v[j-1] - arr[j-1];
            if (che[next]||next<=0) {
                che1 = 1;
                break;
            }
            che[next] = 1;
            arr[j] = next;
        }
        if (che1 == 0) {//사전순으로 젤작은것을 찾아으니 탈출!
            for (int j = 0; j < a; j++)
                cout << arr[j]<<' ';
            break;
        }
    }
}

Race , 18324번

https://www.acmicpc.net/problem/18324

18324번: Race

위의 2브론즈 문제와 달리 같은 브론즈인데 난이도가 급상승한 느낌이었따. 

달리기의 속력은 0에서 부터 올라가고 최고점을 r이라고 생각하고 이분탐색을 짠다.

모든 경우는 1-> r -> n (r>n) or 1->r(r<=n)으로 표현할수 있고 그중에 각숫자 1~r까지의 이동은 원하는대로 할 수 있다. 가장 빨리 도달 하여야 하기에 최고 속도로 이동하는 것을 목표로 한다. (38줄)

ll K, N;
 
int n;
int day = 0;
bool fun(ll a) {//a의 속도를 최고 속도로 하였을때 가능한지 여부를 확인한다.
    ll sum;
    if (a >= n)//1-> a 까지 간 후 a-1 -> n까지 
        sum = a * (a + 1) / 2 + (a - 1) * a / 2 - n * (n - 1) / 2;
    else//최고속도가 n보다 낮을경우 최고속도 까지만 올려주기 확인
        sum = a * (a + 1) / 2 ;
    if(a * (a + 1) / 2 + (a - 1) * a / 2)
    return sum <= K;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> K >> N;
    for (int i = 1; i <= N; i++) {    
        cin >> n;
        ll l = 0;
        ll r = 1000000;
        while (l <= r) {//r에 if문을 만족하지 않는 값들중 가장 오른쪽 값이 들어가 있게된다.
            ll mid = (l + r) / 2;
            if (!fun(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
    
        int t = r;//일단 속도를 r까지 올리는데 걸리는 시간
        ll len = K - r * (1 + r) / 2;//속도를 r까지 올릴때 이동한 거리
        if (r > n) {//최고 속도가 n보다 높다면 r-n칸을 한칸씩 내려가야함
            t += r - n;//추가 
            len -= r * (r - 1) / 2 - n * (n - 1) / 2;//남은 거리
        }
        int ans = t + len/r;//최고속도로 이동할수 있을만큼 이동
        if (len % r)//나머지가 있으면 한번더 이동해야함
            ans++;
        cout << ans << "\n";
    }
}