CodeupCoder's Blog

내가 한 엣코더 라운드 중에 가장 잘한 라운드다!

3솔했고, B에서 많이 뇌절했다.

B는 문제가 좀 별로인것 같다.

그리고 C번은 왤논이었는데 내가 그걸 모르고(...) 엄청 어렵게 풀었다.

풀이로 들어가자!

A. Slot

Problem Statement

You are playing the slots.

The result of a spin is represented by three uppercase English letters C1, C2, and C3. It is considered a win when all of them are the same letter.

Determine whether it is a win.

Constraints

Ci is an uppercase English letter.

Input

Input is given from Standard Input in the following format:

C1C2C3

Output

If the result is a win, print Won; otherwise, print Lost.

풀이

주어진 세개의 문자가 같은지를 판별하자.

#include<bits/stdc++.h>
int main(){
	char a,b,c;
	scanf("%c %c %c",&a,&b,&c);
	if(a==b&&a==c&&b==c) puts("Won");
	else puts("Lost");
	return 0;
}

[01:21 Accepted]

B. Alchoholic

Problem Statement

Takahashi had N glasses of liquor.

The amount and alcohol percentage of the i-th liquor were Vi milliliters and Pi percent by volume, respectively.

Takahashi gets drunk when his alcohol intake exceeds X milliliters.

Which of the N liquors was he drinking when he gets drunk? If he was not drunk even after drinking all the liquors, print -1 instead.

Constraints

• All values in input are integers.
• 1≤N≤10^3
• 0≤X≤10^6
• 1≤Vi≤10^3
• 0≤Pi≤100

Input

Input is given from Standard Input in the following format:

N X

V1 P1

⋮

VN PN

Output

If Takahashi got drunk when drinking the i-th liquor, print i. If he was not drunk even after drinking all the liquors, print -1 instead.

풀이

각 주어지는 음료별로 알코올의 양을 구해서 더하면 된다.

그대로 코드를 짜고 제출하면 틀린다.

왜그럴까? 바로 실수 오차 때문이다.

실수 오차를 없엘려면 실수를 없에 버리면 된다.

따라서 알코올의 양을 100으로 나누지 않고, 즉 알코올의 양*100을 구하고 그 값을 마실수 있는 최대 알코올의 양*100과 비교해주면 된다.

실수오차 참 짜증난다:(

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x;cin >> n >> x;
    int v[1000], p[1000];
    for (int i = 0; i < n; ++i) cin >> v[i] >> p[i];
    long long t[1000];
    for (int i = 0; i < n; ++i) t[i] = v[i] * p[i];
    long long ans = 0;
    for (int i = 0; i < n; ++i){
        ans += t[i];
        if (ans > x * 100){
            cout << i+1 << endl;
            break;
        }
    }
    if (ans <= x * 100) cout << -1;
}

[13:00 Wrong answer]

[15:07 Wrong answer]

[18:23 Wrong answer]

[25:29 Wrong answer]

[27:52 Wrong answer]

[30:25 Accepted]

C. Mandarine Orange

Problem Statement

There are N dishes arranged in a row in front of Takahashi. The i-th dish from the left has Ai oranges on it.

Takahashi will choose a triple of integers (l,r,x) satisfying all of the following conditions:

• 1≤l≤r≤N
• 1≤x
• for every integer I between l and r (inclusive), x≤Ai.

He will then pick up and eat x oranges from each of the l-th through r-th dishes from the left.

At most how many oranges can he eat by choosing the triple (l,r,x) to maximize this number?

Constraints

• All values in input are integers.
• 1≤N≤10^4
• 1≤Ai≤10^5

Input

Input is given from Standard Input in the following format:

N

A1 … AN

Output

Print the maximum number of oranges Takahashi can eat.

풀이

이 문제는 왜인지 모르겠지만 왤논이라고 한다,,

나는 대회 중에 진짜 이상한 방법으로 풀어서 11분만에 템플릿 미포함 1442B를 짜는 미친짓을 했다.

여러분은 이런 풀이를 하지 않았으면 한다.. ㅠㅠㅠ

내 풀이를 설명하면 머리만 아프니까 에디토리얼에 있는 간단한 풀이를 설명하도록 하겠다.

One can first fix l, then update x while increasing r one by one to find them in a total of O(N^2) time.

아 너무 쉽다

<에디토리얼 코드>

#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	int ans=0;
	for(int l=0;l<n;l++){
		int x=a[l];
		for(int r=l;r<n;r++){
			x=min(x,a[r]);
			ans=max(ans,x*(r-l+1));
		}
	}
	cout << ans;
}

<내 코드>

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> f(vector<ll> &v){
	ll i,j,k,l,n=v.size();
	vector<ll> res(n);stack<ll> st;
	for(i=0;i<n;i++){
		while(!st.empty()&v[i]<=v[st.top()]) st.pop();
		if(st.empty()) res[i]=-1;
		else res[i] = st.top();
		st.push(i);
	}
	return res;
}
vector<ll> g(vector<ll> &v){
	ll i,j,k,l,n=v.size();vector<ll> res(n);stack<ll> st;
	for(i=n-1;i>=0;i--){
		while(!st.empty()&v[i]<=v[st.top()]) st.pop();
		if(st.empty()) res[i]=n;
		else res[i] = st.top();
		st.push(i);
	}
	return res;
}
void solve(){
	ll i,j,k,n,m,a,b,u;cin>>n;vector<ll> v(n);
	for(i=0;i<n;i++) cin>>v[i];
    vector<ll> l = f(v);vector<ll> r = g(v); ll ans=0;
    for(i=0;i<n;i++) ans = max(ans, v[i]*(r[i]-l[i]-1));
    cout<<ans;
}
int main(){
    ll t;t=1;
    while(t--) solve();
}

제 코드가 얼마나 더러운지 알겠나요

[41:55 Accepted]

D 굉장히 어려워 보여서 안풀었다 ㅋㅋㅋㅋ

업솔빙도 안할예정

A랑 B 빨리 풀었다고 신났다가 망함..;;

바로 풀이로 들어가자.

A. Brick

Problem Statement

We have a truck, which can carry at most N kilograms.

We will load bricks onto this truck, each of which weighs W kilograms. At most how many bricks can be loaded?

Constraints

• 1≤N,W≤1000
• N and W are integers.

Input

Input is given from Standard Input in the following format:

N W

Output

Print an integer representing the maximum number of bricks that can be loaded onto the truck.

풀이

n 킬로그램까지 실을 수 있는 트럭에 w킬로그램 나가는 물건을 얼마나 실을 수 있는지 물어보는 문제이다.

C, C++에서는 그냥 나누면 되고, 파이썬은 정수 나눗셈을 이용한 풀이를 할 수 있다.

정말 쉬운 문제이고, 27초 만에 풀어서 그때 스코어보드 97등이었다. XD

#include<stdio.h>
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d",a/b);
    return 0;
}

[00:27 Accepted]

B. Blocks on Grid

Problem Statement

We have a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has Ai,j blocks stacked on it.

At least how many blocks must be removed to make all squares have the same number of blocks?

Constraints

• 1≤H,W≤100
• 0≤Ai,j≤100

Input

Input is given from Standard Input in the following format:

H W

A1,1 A1,2 …… A1,W

⋮

AH,1 AH,2 …… AH,W

Output

Print the minimum number of blocks that must be removed.

풀이

모든 블럭의 개수를 체크해서 가장 작은 값으로 만들어야 한다. 따라서 모든 블럭의 개수만큼 반복문을 돌리고, 해당 칸의 블록의 개수에서 가장 적은 블록의 개수를 뺀 것들의 합이 정답이 된다.

#include<stdio.h>
int main()
{
    int a,b,min = 99999999,i,j;
    int sum=0;
    int arr[1001][1001];
    scanf("%d%d",&a,&b);
    for(i=0;i<a;i++)
    {
        for(j=0;j<b;j++)
        {
            scanf("%d",&arr[i][j]);
            if(arr[i][j]<min)
            {
                min = arr[i][j];
            }
        }
    }
    for(i=0;i<a;i++)
    {
        for(j=0;j<b;j++)
        {
            sum = sum + (arr[i][j]-min);
        }
    }
    printf("%lld",sum);
    return 0;
}

[04:12 Accepted]

여기까지는 나의 ABC 최고기록이었다.

그리고 C, D, E에서 동시에 뇌절하는 바람에 더 못풀었다... ㅠㅠㅠ

C, D업솔빙 예정

UPD : C업솔빙 완료

일요일 9시에 열리는 대회는 내가 일정이 있어서 풀 시간이 얼마 없다..ㅠ

그래도 괜찮은(?) 결과가 나와서 기분은 좋았지만 rating은...다.

개인적으로 B번을 시간 안에 못 풀기도 했고, C번은 내가 좋아하는 조합이론 문제가 나와서 대회가 마음에 들었다.

(참고로 내가 가장 좋아하는 문제의 종류는 조합/기하 관련 문제들이다)(물론 쉬운거)

바로 풀이로 들어가자.

A. ABC Preparation

Problem statement

Takahashi has decided to hold some number of programming contests.
Holding one contest requires one 100100-point problem, one 200200-point problem, one 300300-point problem, and one 400400-point problem.
When he has A1, A2, A3, and A4 drafts of 100-, 200-, 300-, and 400-point problems, respectively, at most how many contests can he hold?
The same draft can be used only once.

Input

Input is given from Standard Input in the following format:

A1 A2 A3 A4

Output

Print an integer representing the maximum number of contests that can be held.

풀이

어짜피 모든 배점의 문제를 다 똑같은 개수만큼 출제하는 것이기 때문에 가장 적은 개수가 있는 문제의 개수만큼만 대회를 만들 수 있다. 따라서 입력되는 값 중에서 가장 작은 값을 출력하면 된다.

#include<stdio.h>
int min(int a, int b){if(a>=b){return b;}else{return a;}}
int main()
{
    int a,b,c,d,;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    printf("%d",min(a,min(b,min(c,d))));
    return 0;
}

[02:29 Accepted]

C. Duodecim Ferra

Problem statement

There is an iron bar of length L lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length.
Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways.
Under the constraints of this problem, it can be proved that the answer is less than 2^63.

Input

Input is given from Standard Input in the following format:

L

Output

Print the number of ways to do the division.

풀이

길이가 L인 bar에는 자를 수 있는 곳이 L-1개 있다. 그 L-1개 중에서 11개를 선택하는 방법의 수가 정답이므로 L-1C11을 출력하면 된다.

import math
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)
a = int(input())
print(nCr(a-1,11))

다름이 아니라 C로 짜니까 nCr함수에서 오류가 나는지 자꾸 WA 떠서 파이썬으로 풀었다

[67:12 Wrong Answer]

[67:26 Wrong Answer]

[73:55 Runtime Error]

[76:21 Accepted]

B는 업솔빙 예정

대회 후기를 써볼려고 한다..

사실 이 대회는 끝나기 약 15분 전에 들어와서 2문제 밖에 풀지 못했는데, 지금껏 내가 한 대회 중(몇개 안되지만) 가장 빨리 2개를 푼 셋이라 한번 올려본다.

앞으로는 모든 대회에 대한 후기를 올리도록 하겠다.

A. Determinant(100)

Problem Statement

Given is a 2×2 matrix A=[a b

                                                            c d].
The determinant of A can be found as ad−bc.
Find it.

Constraints

• All values in input are integers.
• −100≤a,b,c,d≤100

말 그대로 a*d - b*c를 출력하면 된다.

[89:39 AC]

#include<stdio.h>
int main()
{
    int a,b,c,d;
    scanf("%d %d\n%d %d",&a,&b,&c,&d);
    printf("%d",a*d-b*c);
}

B. Quizzes(200)

Problem Statement

Takahashi will answer N quiz questions.
Initially, he has X points. Each time he answers a question, he gains 1 point if his answer is correct and loses 1 point if it is incorrect.
However, there is an exception: when he has 0 points, he loses nothing for answering a question incorrectly.

You will be given a string S representing whether Takahashi's answers are correct.
If the i-th character of S from the left is o, it means his answer for the i-th question is correct; if that character is x, it means his answer for the i-th question is incorrect.
How many points will he have in the end?

Constraints

• 1≤N≤2×1051≤N≤2×105
• 0≤X≤2×1050≤X≤2×105
• S is a string of length N consisting of o and x.

역시 간단한 구현 문제이다.

[88:09 AC]

#include <stdio.h>
int main()
{
    int i,a,b;
    char n;
    scanf("%d %d\n",&a,&b);
    for(i=0;i<a;i++)
    {
        char n;
        scanf("%c",&n);
        if(n=='o')
        {
            b++;
        }
        if(n=='x')
        {
            if(b==0)
            {
                b=0;
            }
            else
            {
                b--;
            }
        }
    }
    printf("%d",b);
    return 0;
}

대회 중에는 여기까지 풀었다.

늦게 들어와서 등수가 많이 떨어졌다.

C번은 업솔빙 예정이다.