Grace

배열이나 set을 이용하여 문제를 해결할 수 있다.

주의해야할 사항은 시간초과와 메모리초과이다.

1. 시간초과

밑의 두가지 코드를 통해 해결한다.

ios_base::sync_with_stdio(false); // c의 stdio와 cpp의 iostream의 동기화를 해제해준다.

cin.tie(NULL); // 버퍼를 비워줌 cin와 cout을 독립적으로 만들어준다.

2. 메모리초과

결과값을 담아 마지막에 한번에 출력해주는 vector를 사용하면 메모리 초과가 난다. input stream / output stream은 별개이니 굳이 마지막에 모아서 결과를 출력하지 않아도 된다.

배열을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

vector<int> v(21); // index값 1-존재, 0-없음.

void init(){ // 1~20 초기화.
    for (int i = 1; i <= 20; i++){
        v[i] = 1;
    }
}

void arrEmpty(){
    for (int i = 1; i <= 20; i++){
        v[i] = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,x;
    string type;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0) init();
        else if (type.compare("empty") == 0) arrEmpty();
        else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                v[x] = 1;
            }
            if (type.compare("remove") == 0)
            {
                v[x] = 0;
            }
            if (type.compare("check") == 0)
            {
                v[x] == 1 ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                v[x] == 1 ? v[x] = 0 : v[x] = 1;
            }
        }
    }
}

set을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

set<int> s;
set<int> init;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i <= 20; i++)
        init.insert(i);

    int n; cin >> n;
    string type;
    int x;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0)
        {
            s = init;
        }else if (type.compare("empty") == 0)
        {
            s = {};
        }else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                s.insert(x);
            }
            if (type.compare("remove") == 0)
            {
                s.erase(x);
            }
            if (type.compare("check") == 0)
            {
                s.find(x)!=s.end() ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                if(s.find(x)!=s.end()){ // 있는 경우 삭제
                    s.erase(s.find(x));
                }
                else
                { // 없는 경우 추가
                    s.insert(x);
                }
            }
        }
    }
}

liked layer에서 유선통신을 할 때는 csma / cd 프로토콜을 사용한다.

❗ wireless

유선 csma / cd를 그대로 사용할 경우 몇가지 문제점이 발생한다.

문제점 1.

유선통신에서는 csma / cd 사용하면 되지만 무선의 경우 거리에 따라서 주파수에 따라 전파가 도달가능한 범위가 다르기 때문에 노드들이 서로의 신호를 인지하지 못할 수 있다.

문제점 2.

collision detection이 불가능하다. 노드는 자신이 통신 중일때 전파 특성상 다른 노드의 신호를 인지할 수 없다.

이를 해결하기 위해 wifi는 CSMA / CA 라는 mac 프로토콜을 사용한다.

❗ wifi

• 기술적 명칭은 IEEE 802.11이다.
• wireless fidelity의 약자이다.
• ap가 초당 10~100회 정도로 주기적으로 boradcast를 하여 자신을 알린다.
• 유선 csma / cd에서는 노드들이 스스로 충돌감지를 할 수 있기 때문에 ack가 필요없지만 wifi에서는 충동감지가 불가능 하기때문에 ap의 ack가 따로 필요하다.
• csma / ca를 사용한다. (collision avoidance의 약자)

❗ CSMA/ CA 동작원리

csma / cd에서는 충돌 감지 후 곧 바로 통신을 중지하지만 와이파이는 충돌감지 자체가 불가능하기 때문에 충돌발생시 발생하는 손해가 유선에 비해 더욱 크다. 와이파이는 충돌감지를 위해 RTS(ready to send)와 CTS(clear to send)라는 control frame을 추가시켜서 통신을 진행하게 된다.

노드는 cast를 sence하고 있다가 일정시간 동안 조용할 경우 RTS라는 작은 크기의 프레임을 보낸다. RTS를 보내는 이유는 충돌 시 발생하는 손해가 크기 때문에 그 손해를 최소화하기 위함이다.

1. a와 b가 RTS경쟁을 하다가 RTS가 충돌날 경우 AP는 아무것도 듣지못하지만 피해는 크지않다.
2. a와 b는 exponential backoff을 가진 후 다시 rts를 보내게 된다.
3. RTS를 충돌 없이 정상적으로 받은 경우 ap는 a의 통신에 대한 cts를 뿌린다.
4. 그 후 A는 ap와 자유롭게 데이터 통신이 가능하게 된다.

rts와 cts에는 누가 얼마 동안에 어떤 채널을 사용한다는 정보가 담겨 있고 이를 받은 모든 반경의 노드들은 그 정보를 통해 특정 시간만큼 기다린다.

❗ CSMA/ CA 한계

하지만 CSMA/ CA 에도 결점이 존재한다.

다음과 같은 시나리오를 생각해보자.

1. ap가 A의 rts를 정상적으로 받은 후 cts를 보냈다.
2. cts를 보내는 중에 B가 ap에게 rts를 보내는 경우 B는 CTS를 정상적으로 받은 A가 통신중이라는 것을 알지 못한다.
3. 이때 a, ap는 정상통신이 가능하다고 예측을 하고 통신을 진행하지만 B는 그 사실을 알지 못한상태가 되어 a가 채널을 사용중에 있을 때 RTS를 보내 충돌이 발생되어 전송이 와해되게 된다.
4. ap에게 데이터에 대한 ack를 받지못한 a는 재전송을 위해 다시 Rts경쟁을 하게 된다.

서로 통신 반경이 다른 노드들간의 관계에 의해서, rts 혹은 cts가 미세한 시간차이로 인해 노이즈가 되어버리는 경우가 불가피 하다. 따라서 사람이 많을수록 충돌-지연-충돌-지연이 다수 발생하게 된다.

csma / ca는 재전송을 7번까지만 허용한다. 7번 이후에는 다음 프레임으로 넘어간다. 그렇다면 보내지 못한 데이터는 어떻게 되는가? tcp의 timer가 터지면 재전송을 위해 다시 내려오게 된다.

mac 프로토콜은 liked layer에서의 충돌 방지를 위한 프로토콜을 말한다.

❗ csma(carrier sence multiple access)

csma는 random access 방식을 사용한다. 다시말해 호스트는 자신이 원할때 마다 통신을 할 수 있다는 것을 의미한다.

기본적인 컨셉은 listen before send으로 carrier(데이터를 보낼 host)가 보내지 전에 우선석으로 sence(듣고)한 후 데이터를 보내는 방식이다.

하지만 propagation delay(빛의 속도, c)가 0이 아니기 때문에 boradcast 매체인 liked layer에서는 충돌이 발생할 수 밖에 없다. 즉 충돌은 나기마련이라는 것이 결론이다. 따라서 충돌을 방지할 수 있는 mac 프로토콜이 필요하다.

❗ csma / cd(carrier sence multiple access / collision detection)

그래서 등장한 것이 csma의 보완버전으로 충돌을 관리하는 mac 프로토콜이다.

작동원리

NIC가 충돌을 감지하면 그 순간 통신을 멈춘다. 그 후 일정시간을 기다린다. 이 과정을 binary exponential backoff이라고 한다. 0,1,2,…,2^m-1(m is count of collision) 중 랜덤으로 값을 선택하여 그 만큼의 딜레이를 갖는다. exponential한 값중에 랜덤하게 선택하기 때문에 충돌횟수가 늘어나면 더 오래기다릴 확률이 높아진다.

tcp의 congest control과 비슷한 원리인듯 하다. cast의 상황을 독립적으로 판단하고 적절히 양보하게 된다.

❗ 네트워크가 너무 느린데?!

가끔 많은 사람들이 같이 와이파이를 사용하는 경우에 우리가 체감적으로 네트워크가 느리다고 느끼는 것이 실제 네트워크가 느린것이 아니라 사람이 몰려서 backoff 시간이 늘어난다는 요인이 작용하기 때문이다.

❗ethernet minimum frame size

propagation delay가 빛의 속도이지만, csma / cd 만으로는 충돌이 발생했음에도 불구하고 충돌을 인식하지 못하는 아주 최악의 상황이 발생할 수 있다.

충동이 일어났음에도 인지하지 못하는 경우는 어떤 상황일까?

A와 B가 boradcast 매체의 host라고 가정하자.

1. A가 B에게 데이터를 보냈다.

2. A가 B에게 보낸 데이터가 B에게 도달하기 전에 B 또한 A에게 데이터를 보낸다.

3. 이때 B->A로 오는 와중에 A입장에서, A->B 데이터 전송이 끝난다면,

4. B->A데이터는 이미 노이즈 섞인 불완전한 데이터이지만

5. A는 자신이 통신을 모두 마친 후 아주 평안한 상태에서 받은 데이터이기 때문에 충돌이라는 것을 인지하지 못한다.

이처럼 충돌이 발생했음에도 불구해고 탐지하지 못하는 상황이 발생하는 것을 막기위해 최소전송단위시간이 존재한다. 찰나의 순간에 데이터를 같이 보내는 경우 그것을 인지하기 위해 일정크기 이상으로 데이터를 보내자는 약속이 있는 것이다. 이것이 바로 ethernet minimum frame size (64byte)이다. 만약 보내는 데이터가 64byte보다 작다면 padding 집어넣어서 64byte를 맞추어 보낸다.

multiset을 이용했다.

iterator를 통해 begin(최소값) end(최대값)에 접근하였다.

#include <iostream>
#include <set>

using namespace std;

int main(){
    int T = 0;
    cin >> T;
    for (int t = 0; t < T; t++){
        int n;
        cin >> n;
        multiset<int> ms;
        for (int i = 0; i < n; i++){
            char type;
            int input;
            cin >> type >> input;
            if(type == 'I'){ // 삽입
                ms.insert(input);
            }
            else{ // 샥제
                if(input == 1 && !ms.empty()){ // 최대값 삭제
                    ms.erase(ms.find(*(ms.rbegin())));
                }
                if(input == -1 && !ms.empty()){ // 최소값 삭제
                    ms.erase(ms.find(*(ms.begin())));
                }
            }
        }
        if(ms.empty())
            cout << "EMPTY\n";
        else
            cout << *ms.rbegin() << " " << *ms.begin() << "\n";
     }
}

배운 점

1. find를 이용한 중복된값 단일제거
erase은 인자값으로 iter와 value 모두 받는다.
인자로 value를 넣게되면 해당 value과 같은 값을 가지는 요소들을 모두 삭제하기 때문에 itr로 접근해야 한다.
따라서 find를 통해 특정값의 itr를 구하고 이것을 erase에 인자로 전달하여 하나의 요소만 삭제하도록 한다.

2. rbegin end 차이
end는 past-the-end의 iterator 즉, 마지막 원소의 다음 주소를 가리킨다.
past-the-end를 사용함으로써 컨테이너의 탐색을 용이하게 하고 (itr가 end()를 가리킬때까지 반복)
컨테이너 내부가 비었을때 begin과 end가 같은 값을 가리키도록 하기 때문이다.
따라서 마지막 원소를 삭제할때는 end()보다 한칸 앞에 있는 값을 지정해야하므로 --end()로 접근하거나 rbegin()을 사용해야 한다.

재귀로 접근한다.

basic step

1. n==1 인 경우, 즉 한칸까지 탐색범위가 좁아졌을 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

2. 모든 색종이가 같은 색일 경우에 -> 색종이 색에 따른 카운팅을 시행한다.

Recursive step

basic step에 해당하지 않아서 탐색범위를 좁어야 하는 경우,

해당 시점을 기준으로 4등분한 solve()를 각각 콜한다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int a[128][128]={0,};
int white = 0;
int blue = 0;

void solve(int x, int y, int n){

    if (n == 1){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }

    bool res = true;
    for (int i = x; i < x+n; i++)
    {
        for (int j = y; j < y+n;  j++){
            if(a[i][j] != a[x][y]){
                res = false;
            }
        }
    }

    if(res){
        if(a[x][y] == 1) blue++;
        if(a[x][y] == 0) white++;
        return ;
    }else{
        solve(x, y, n / 2);
        solve(x, y + n / 2, n / 2);
        solve(x + n / 2, y, n / 2);
        solve(x + n / 2, y + n / 2, n / 2);
        return;
    }
    return;
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    solve(0, 0, n);

    cout << white << endl;
    cout << blue << endl;
}

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

풀이

unordered_map을 이용한다. unordered_map은 hash_map c++ lib이다. 내부적으로 hash로 구현되어 있어 탐색하는데 O(1)의 복잡도를 가진다. 데이터가 최대 10만개를 가지고 최대 10만개의 문제가 주어지기 때문에 unordered_map을 사용해야 한다.

key를 통해 value로 접근하기 때문에

name으로 number를 접근하기 위한 unordered_map과

number으로 name를 접근하기 위한 unordered_map을 각각 만들어 접근한다.

주어진 문제에 대해서 isdigit을 통해 숫자인지 이름인지를 판단하고

숫자인 경우 stoi를 통해 숫자변환 후 find를 진행한다.

이름인 경우에는 key를 이름으로 하는 unordered_map에 바로 접근할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cctype>

using namespace std;

unordered_map<string, int> list_name;
unordered_map<int, string> list_number;
vector<string> quiz;
int n, m;

int main(){
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    string str;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> str;
        list_name.insert({str, i});
        list_number.insert({i, str});
    }

    for (int i = 1; i <= m; i++){
        cin >> str;
        quiz.push_back(str);
    }

    for (int i = 0; i < m; i++){
        if(isdigit(quiz[i][0]) != 0){
            int num = stoi(quiz[i]);
            cout << list_number[num] << "\n";
        }else{
            cout << list_name[quiz[i]] << "\n";
        }
    }
}

배운 점

unordered_map : hash 기반의 map. crud O(1)를 가짐. 많은 데이터를 저장할때 사용.
stoi(string to integer) : string에 문자가 있으면 오류 발생. 문자열로된 순수 숫자로 이루어져있어야함.
atio() : c에서의 stoi. string타입을 지원하지 않기 때문에 str.c_str()로 변환하여 사용할 수 있음.
isdigit : string 전체가 아니라 인덱스 하나만 받아서 판별해준다.

<요약>

자본주의 정신에 있어서 가장 큰 영향을 미친 것은 청도교 정신이다. 자본주의 정신은 자본주의를 발달시켰다. 자본주의가 발달한 곳에 자본주의 정신이 있었다. 자본주의 정신은 금욕주의적이고 삶을 체계적으로 조직하여 살아가는 그들의 삶의 방식이다. 존재론적인 불안감을 떨처내고 싶어했던 당시의 개신교들은 구원의 확실성에 대한 많은 고민이 있었다. 청교도들은 금욕주의적 삶을 살아가는 것 많은 절제와 인내가 요구되기 때문에 구원받은 이가 아니라면 할 수 없다는 논리로서 금욕주의적 삶을 살아가는 것을 삶의 목표로 하였다. 그것이 그들에게 구원의 확실성을 증명하고 불안에서 자유하게 만들어 주었기 때문이다.

❗ 루터의 직업정신

루터의 직업 개념

세속적인 노동을 중요시해야 한다는 생각은 오래전부터 꾸준히 있어왔다. 하지만 종교개혁을 통해 새로운 의미의 직업 개념이 등장했다. 루터는 세속적인 노동을 종교적인 가치와 연관시켰다. 노동이 그 자체로 도덕적인 의무라고 생각했다. 루터에게 도덕적 의무를 다한다는 것은 직업 자체가 하나님께서 인간에게 주신 특별한 사명이기 때문이라기 보다는 자신이 처한 상황에서의 직업의 의무와 사명에 최선을 다하는 운명, 섭리론적인 의미를 갖는 전통주의적 개념이다.

→ 근대 자본주의적 직업 개념의 기원으로 보기 어렵다.

칼빈주의와 개신교 분파의 영향

자본주의 발달사에서 칼빈주의와 개신교 분파가 주목할만한 영향을 끼쳤다. 하지만 종교개혁이 직접적으로 근대 자본주의 정신이나 자본주의 체계를 탄생시켰다는 것은 아니다. 다수의 종교개혁자들은 그 누구도 윤리개혁을 목표로 삼지 않았다. 종교개혁자들의 관심자는 오로지 영혼의 구원이었다. 하지만 그들이 원했든 원하지 않았든 종교개혁의 종교적 동기가 근대 문화에 영향을 끼치게 되었다. 즉, 종교개혁이 근대 자본주의 문화에 직접적으로 영향을 미친것이 아니라 부수적인 영향을 끼쳤다는 것이다. 따라서 저자가 밝히고자 하는 것은 종교개혁의 종교적인 동기가 근대 자본주의 문화의 어떠한 요소들을 역사적으로 발전시켜왔는지에 대한 것이다.

 ❗ 금욕주의적 개신교의 직업윤리

저자가 관심갖는 것은 윤리적 지침이 아니라 금욕주의적인 생활양식을 이끌었던 심리학적 동력이다. 종교적 신앙과 삶의 양식 그리고 그러한 삶을 유지하게 하는 심리학적 동력에 주목한다.

칼빈주의

칼빈주의의 핵심교리는 예정론이다. 예정론은 문화사에 대단히 큰 영향을 미쳤다. 이 예정론이 어떠한 역사적인 인과적 중요성을 갖는지를 알아본다. 먼저 예정론 교리에 대해 간략히 설명한다.

- 예정론 교리

인간은 전적으로 타락하여 스스로 구원할 수 없는 무능력한 존재이다. 하나님은 영원전부터 모든 계획을 하시고 주관하신다. 또한 이 세상에 대한 절대주권을 갖는다. 본질적으로 소망없는 인간에게 하나님은 영원전부터 예정하신 개개인에 대한 예정에 따라 전적인 은혜를 통해 구원의 길로 부르신다. 구원은 전적으로 하나님의 주권과 예정에 있다. 예정된 인간을 그것을 거부할 수 없으며 은혜를 주지 않기로 작정된 인간은 절대로 구원받을 수 없다.. 루터교는 인간의 신앙심에 따라 구원을 여부가 결정된다는 입장이지만 칼빈주의는 영원전부터 모든것을 계획하신 하나님의 절대주권에 인간이 영향을 끼칠 수 없다고 본다.

- 세상, 타인 혐오와 불안

예정론은 극단적인 신앙의 형태이다. 칼빈주의자들로 하여금 세상을 거대한 시간의 흐름속에 잠깐 존재하는 무가치한 것으로 인식하도록 하였다. 문화에 대한 혐오를 낳았고 세상이 악하기 때문에 타인에 대한 신뢰를 약화하는 경향을 낳았다. 칼빈주의는 영혼을 구원하는 것은 하나님의 사역이라고 보았기 때문에 주어진 상황을 묵묵히 살아내는 것이 하나님의 영광을 드높이는 것이라 생각하였고 이는 인간성의 상실로 이어졌다.

- 구원의 확실성과 금욕주의

영혼 구원 에 대한 본질적인 불안은 하나님과의 직접적인 교통을 추구하게 만들었다. 그렇다면 어떻게 구원을 확신할 수 있는가? 첫째로 구원 받았음을 믿는 것이다. 구원에 대한 의심은 마귀의 역사이며 견고한 믿음은 은혜로부터 오는 것이다. 둘째로 성실하고 부지런한 직업적 노동이다. 이를 곧 택함의 증거로 보았다. 내적 체험을 강조하고 신비주의적인 태도를 갖는 루터교와는 달리, 칼빈주의는 믿음의 작용에 의한 행위적인 특질을 구원의 증거로 보았다. 하나님의 영광을 위한 생활양식을 성실히 영위하는 것이다. 따라서 조직적인 자기통제가 구원이 확실성을 만들어 낸다고 본다.

칼빈주의의 관심은 오로지 구원에 있었고 자신이 구원받았음을 확증하기 위한 동기로 하나님의 영광을 위한 세속에서의 자기통제, 자기주도적 삶이 중시되었다. 따라서 일시적인 감정을 따르는 것이 아닌 이성에 의한 규범을 추구하는 삶을 사는 금욕주의적 생활양식을 띄게 되었다. 악한 감정 뿐 아니라 무의미하고 무절제한 감정도 악으로 치부하였는데, 이는 이성을 냉철을 약화시키기 때문이었다. 또한 발전과정에서 세속적 직업활동을 통해 구원의 유무를 증명해야한다는 요소가 더해지면서 금욕주의적이지만 다른 한편으로 적극적이고 세속적인 삶의 기반을 마련했다. 그리고 체계적인 노동을 통해 세상을 윤택하게 하는 것이 타인에게 유익을 끼치는 행위 즉 이웃사랑을 실천하는 것이라고 보았다.

경건주의

경건주의는 개혁교회의 금욕주의적인 전통이 강화된 형태이다. 이들은 교리나 신학적인 지식보다 경건한 행위와 삶에 대해 관심을 가졌다. 신학적 학식이 뛰어나다고 해서 분명한 열매를 맺는 것은 아니며, 지식이 없다고 해서 열매를 맺지 못하는 것이 아니기 때문이다. 경건한 행위 추구라는 가치에 공감하는 이들이 모여 작은 집단을 이루는 것이 특징이다.

구원의 확신을 위해서 실천적 성화를 강조했던 칼빈주의와는 달리 경건주의는 죄사함을 중시하여 세속에서의 하나님과 함께함을 느끼는 내적 체험과 감성을 강조한다. 은혜의 상태에 있음을 삶 속에서 확증해야 한다는 칼빈주의 사상이 경건주의에서는 감성적이고 정서적인 방향으로 전환된다. 이로 인해 칼빈주의에 비해 세속적인 삶의 조직화 정도가 약화되었지만 루터교에 비해서는 종교적 삶의 체계적인 조직화는 강화된 모습을 띈다.

감리교

존 웨슬리로 유명한 감리교의 핵심은 회심과 성화이다. 감성적인 회심은 성화로 들어가게 한다. 감성적인 회심을 강조하지만 삶을 체계적이고 조직적으로 살아가는 합리주의 기반의 금욕주의를 말한다.

웨슬리는 행위구원을 비판한다. 주객이 전도되어있기 때문에다. 행위가 구원의 조건이 아니라 구원의 확실성을 확인하는 근거이다. 그리고 그 행위로 하나님의 영광을 위한 마음의 동기를 가질 때 참되다.

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

높이를 구하는 문제이기에 처음에는 이분탐색으로 풀수 있을거라고 생각했다.

하지만 여러케이스를 상성하고 고려해 보았을때 특정 높이로 땅을 고를수 있다고 했을때 어떠한 기준으로 범위를 좁혀나갈지를 정하는 것이 불가능했다.

지금까지 나온 시간중 최소시간이라고 하더라도 더 높은 곳에 최소시간을 갖는 높이가 존재할 수도 있고 더 낮은 곳에 최소시간을 갖는 높이가 존재할 수 있기 때문이다.

고민끝에 brute force방식으로 구현하였다.

0~256의 모든 높이에 대해 땅 고르는 시간을 구하고 그 중에서 최소값과 그 높이를 찾아 출력한다.

고려해야할 점이 한가지 있는데, 이는 해당높으로 땅을 고를 수 있느냐 하는 것이다. 인벤토리안에 주어진 B와 땅을 고르기 위해 파낸 땅의 개수가 target 높이를 맞추기 위해 놓은 땅의 개수보다 작으면 안된다.

#include <iostream>

using namespace std;

int main(){
    int n, m, b;
    int input[500][500]={0,};
    int sum = 0, min=987654321, h_index=0;
    int in_ground = 0, out_ground = 0;

    //input
    scanf("%d %d %d", &n, &m, &b);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            scanf("%d", &input[i][j]);
        }
    }

    //solved
    for (int h = 0; h <= 256; h++){
        sum = 0, in_ground = 0, out_ground = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(h - input[i][j] > 0){
                    sum += (h - input[i][j]); // 땅을 심어야하는 경우
                    in_ground += h - input[i][j];
                }
                if (h - input[i][j] < 0)
                {
                    sum += (input[i][j] - h)*2; // 땅을 파야하는 경우
                    out_ground += input[i][j] - h;
                }
            }
        }
        if(in_ground<=out_ground+b && min >= sum){
            min = sum;
            h_index = h;
        }
    }
    printf("%d %d", min, h_index);
    return 0;
}