어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.
입력
첫째 줄에 두 정수 N과 L이 들어온다.
둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.
출력
첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.
예제 입력
3 3
1 6
13 17
8 12
예제 출력
5
접근방식
1. 널빤지를 어떻게 채울 것인가? 2. 겹치는 부분은 하나로 처리
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, l, idx, plank, result;
int a, b;
vector<pair<int, int>> v;
int main()
{
cin >> n >> l;
for (int i = 0; i < n; i++)
{
cin >> a >> b;
v.push_back({ a,b });
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++)
{
if (v[i].second <= idx) continue; // 널빤지 끝 부분 index
if (idx < v[i].first)
{
plank = (v[i].second - v[i].first) / l + ((v[i].second - v[i].first) % l ? 1 : 0);
idx = v[i].first + plank * l;
}
else // 웅덩이의 크기가 더 큰 경우
{
plank = (v[i].second - idx) / l + ((v[i].second - idx) % l ? 1 : 0);
idx = idx + plank * l;
}
result += plank;
}
cout << result;
return 0;
}
총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다.
이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.
톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.
두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.
위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.
톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다.
둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다음 줄에는 회전 횟수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
돌릴 때는 rotate함수를 사용하고 rbegin을 사용하면 된다. (12345678 > 23456781) 돌릴 때 꼭지점을 정해주고 돌리면 더 쉬울것 같아서 꼭지점을 정해 주었다. > 꼭지점에 도달하면 돌려서 배열 정보 저장 순열을 사용해서 돌려가면서 행의 가장 적은 값을 찾으면 된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <tuple>
#include <string.h>
using namespace std;
const int dy[] = { 0,1,0,-1 };
const int dx[] = { 1,0,-1,0 };
int n, m, k, a[104][104], temp[104][104], visited[104][104], sy, sx, ey, ex, r, c, s, direction, result = 99999999;
vector<pair<int, int>> v;
vector<int> v_idx;
vector<tuple<int, int, int>> rotateV;
void directionChange(int y, int x, int first)
{
if (!first && y == sy && x == sx) direction++;
if (!first && y == sy && x == ex) direction++;
if (!first && y == ey && x == ex) direction++;
if (!first && y == ey && x == sx) direction++;
int ny = y + dy[direction];
int nx = x + dx[direction];
if (visited[ny][nx]) return;
visited[ny][nx] = 1;
v.push_back({ ny,nx });
directionChange(ny, nx, 0);
}
void rotateAll(int y, int x, int cnt)
{
for (int i = 1; i <= cnt; i++)
{
sy = y - 1 * i;
sx = x - 1 * i;
ey = y + 1 * i;
ex = x + 1 * i;
v.clear();
direction = 0;
memset(visited, 0, sizeof(visited));
visited[sy][sx] = 1;
v.push_back({ sy,sx }); // 돌려야 할 것 뽑아내기
directionChange(sy, sx, 1);
vector<int> v2;
for (pair<int, int> c : v)
{
v2.push_back(temp[c.first][c.second]);
}
rotate(v2.rbegin(), v2.rbegin() + 1, v2.rend());
for (int i = 0; i < v.size(); i++)
{
temp[v[i].first][v[i].second] = v2[i];
}
}
}
int min_rowSum()
{
for (int i : v_idx)
{
rotateAll(get<0>(rotateV[i]), get<1>(rotateV[i]), get<2>(rotateV[i]));
}
int tempResult = 99999999;
for (int i = 0; i < n; i++)
{
int cnt = 0;
for (int j = 0; j < m; j++)
{
cnt += temp[i][j];
}
tempResult = min(tempResult, cnt);
}
return tempResult;
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
for (int i = 0; i < k; i++)
{
cin >> r >> c >> s;
r--; // 0부터 시작하려고 뺌
c--;
rotateV.push_back({ r,c,s });
v_idx.push_back(i);
}
do
{
memcpy(temp, a, sizeof(temp));
result = min(result, min_rowSum());
} while (next_permutation(v_idx.begin(), v_idx.end()));
cout << result;
return 0;
}
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
예제 입력
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L
예제 출력
9
21
13
접근방식
1. 뱀이 사과를 먹으면 앞부분 추가, 사과를 안먹고 움직이면 끝 부분을 삭제하고 앞부분을 추가하는 식으로 이동 > deque사용 2. 벽 또는 자기 몸에 충돌하면 끝 > 방문처리 visited가 필요 3. 방향 전환 dy, dx를 사용, 모듈러 연산을 통해 방향 전환 가능 (4방향)
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <tuple>
using namespace std;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0 ,-1 };
int n, k, l, x, y_, x_, idx, direction = 1, _map[104][104], visited[104][104], result;
char c;
vector<pair<int, int>> time_vector;
deque<pair<int, int>> dq;
int main()
{
cin >> n >> k;
for (int i = 0; i < k; i++)
{
cin >> y_ >> x_;
_map[--y_][--x_] = 1;
}
cin >> l;
for (int i = 0; i < l; i++)
{
cin >> x >> c;
if (c == 'D')
{
time_vector.push_back({ x,1 }); // 시간 정보와 방향 정보 저장 (D == 1, C == 3)
}
else
{
time_vector.push_back({ x,3 });
}
}
dq.push_back({ 0,0 });
while (dq.size())
{
result++;
tie(y_, x_) = dq.front();
int ny = y_ + dy[direction];
int nx = x_ + dx[direction];
if (ny >= n || ny < 0 || nx >= n || nx < 0 || visited[ny][nx]) break; // 사망처리
if (!_map[ny][nx]) // 사과가 없으면
{
visited[dq.back().first][dq.back().second] = 0; // 꼬리 부분 지우고
dq.pop_back();
}
else
{
_map[ny][nx] = 0; // 사과 먹은 처리
}
visited[ny][nx] = 1;
dq.push_front({ ny,nx }); // 머리 부분 채워주기
if (result == time_vector[idx].first)
{
direction = (direction + time_vector[idx].second) % 4; // 방향 전환
idx++;
}
}
cout << result;
return 0;
}
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
예제 입력
3
2 2 2
4 4 4
8 8 8
예제 출력
16
접근방식
이동해서 합치는 함수를 만들고 그것을 90도로 돌리는 함수를 만들면 계속 사용할 수 있다. 슬라이드 하고 90도로 돌리는걸 4번 반복하면 4방향을 모두 슬라이드 하는 것이니 이 중 가장 큰 값을 구하면 된다. 중간에 돌리거나 이동하거나 할 때 temp를 사용해서 보드 갱신
코드
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, result;
struct Board
{
int board[24][24];
void rotate90()
{
int temp[24][24];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
temp[i][j] = board[n - j - 1][i];
}
}
memcpy(board, temp, sizeof(board));
}
void move()
{
int temp[24][24];
for (int i = 0; i < n; i++)
{
int c = -1, d = 0;
for (int j = 0; j < n; j++)
{
if (board[i][j] == 0) continue;
if (d && board[i][j] == temp[i][c])
{
temp[i][c] *= 2;
d = 0;
}
else
{
temp[i][++c] = board[i][j];
d = 1;
}
}
for (c++; c < n; c++)
{
temp[i][c] = 0;
}
}
memcpy(board, temp, sizeof(board));
}
void get_max()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
result = max(result, board[i][j]);
}
}
}
};
void solution(Board c, int here)
{
if (here == 5)
{
c.get_max();
return;
}
for (int i = 0; i < 4; i++) // 4방향 모두 슬라이드
{
Board d = c;
d.move();
solution(d, here + 1);
c.rotate90();
}
return;
}
int main()
{
cin >> n;
Board c;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> c.board[i][j];
}
}
solution(c, 0);
cout << result;
return 0;
}
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
(r, c)에 남은 미세먼지의 양은 Ar,c- ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.
예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,
키보드
헤어드라이기
핸드폰 충전기
디지털 카메라 충전기
키보드
헤어드라이기
키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.
입력
첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.
출력
하나씩 플러그를 빼는 최소의 횟수를 출력하시오.
예제 입력
2 7
2 3 2 3 1 2 7
예제 출력
2
접근방식
일단 미래의 나타날 숫자를 미리 알고 있으므로 가장 먼 미래(뒤에 있는 인덱스)에 나타나는 수를 찾아서 바꾸고 경우의 수를 1 추가하면 된다. 방문 처리할 visited가 필요하고 전기 용품이 꽂혀있는 벡터가 필요하다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, k, result, a[104], visited[104];
vector<int> v;
int main()
{
cin >> n >> k;
for (int i = 0; i < k; i++)
{
cin >> a[i];
}
for (int i = 0; i < k; i++)
{
if (!visited[a[i]])
{
if (v.size() == n)
{
int last_idx = 0, pos;
for (int element : v)
{
int here_pick = 99999999;
for (int j = i + 1; j < k; j++) // 가장 먼 미래에 참조 되는 것을 찾음
{
if (element == a[j])
{
here_pick = j;
break;
}
}
if (last_idx < here_pick)
{
last_idx = here_pick;
pos = element;
}
}
visited[pos] = 0;
result++;
v.erase(find(v.begin(), v.end(), pos));
}
v.push_back(a[i]);
visited[a[i]] = 1;
}
}
cout << result;
return 0;
}
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai+ aj= x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
예제 입력
9
5 12 7 10 9 1 2 3 11
13
예제 출력
3
접근방식
두 수를 가지고 무엇을 한다고 했을 때 투 포인터로 생각을 했고 정렬을 하고 left와 right를 정해주고 right의 값이 left보다 크면 탐색을 종료하는 반복문을 만들어 두 수의 합이 x와 같으면 경우의 수가 증가하고 right를 감소시키고 두 수의 합이 x보다 크면 right만 감소하여 다시 탐색, 두 수의 합이 x보다 작으면 left만 증가시켜 다시 탐색한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, x, result;
vector<int> v;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> m;
v.push_back(m);
}
sort(v.begin(), v.end());
int left_p = 0, right_p = n - 1;
while (left_p < right_p)
{
if (v[left_p] + v[right_p] == x)
{
right_p--;
result++;
}
else if (v[left_p] + v[right_p] > x)
{
right_p--;
}
else if (v[left_p] + v[right_p] < x)
{
left_p++;
}
}
cout << result;
return 0;
}
