Technocup 2022 — Elimination Round 1 and Codeforces Round #749 (Div. 1+Div. 2)

망했다 ㅠㅠ

4문제밖에 못 풀었다.

A번 풀이: 1개, 2개, 3개를 지우는 모든 경우를 생각해주면 풀린다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int isp(int n)
{
	int i;
	for (i = 2; i < n; i++)
	{
		if (n % i == 0)
			return 1;
	}
	return 0;
}
int main()
{
	int T;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> T;
	while (T--)
	{
		int N;
		cin >> N;
		vector<int>x;
		int i;
		int su = 0;
		for (i = 0; i < N; i++)
		{
			int a;
			cin >> a;
			su+=a;
			x.push_back(a);
		}
		if (isp(su))
		{
			cout << N << '\n';
			for (i = 0; i < N; i++)
			{
				cout << i+1 << ' ';
			}
		}
		else
		{
			
			for (i = 0; i < N; i++)
			{
				if (isp(su - x[i]))
				{
					cout << N - 1 << '\n';
					int j;
					for (j = 0; j < N; j++)
					{
						if (j != i)
						{
							cout << j+1 << ' ';
						}
					}
					goto T;
				}
			}
			for (i = 0; i < N; i++)
			{
				int k;
				for (k = i + 1; k < N; k++)
				{
					if (isp(su - x[i]))
					{
						cout << N - 2 << '\n';
						int j;
						for (j = 0; j < N; j++)
						{
							if (j != i&&j!=k)
							{
								cout << j + 1 << ' ';
							}
						}
						goto T;
					}
					
				}
				
			}
			for (i = 0; i < N; i++)
			{
				int k;
				for (k = i + 1; k < N; k++)
				{
					int l;
					for (l = k + 1; l < N; l++)
					{
						if (isp(su - x[i]))
						{
							cout << N - 3 << '\n';
							int j;
							for (j = 0; j < N; j++)
							{
								if (j != i&&j!=k&&j!=l)
								{
									cout << j + 1 << ' ';
								}
							}
							goto T;
						}
						
					}
					
				}

			}
			
		}
		T:
		cout << '\n';
	}
}

B번: b에 들어가지 않는 원소를 최대한 중앙 쪽에 넣도록 해야 한다. b에 안 들어가는 원소를 중심에 놓고 나머지 모든 원소와 중심을 연결하면 문제의 조건을 만족할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int isp(int n)
{
	int i;
	for (i = 2; i < n; i++)
	{
		if (n % i == 0)
			return 1;
	}
	return 0;
}
int vis[100100];
int main()
{
	int T;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> T;
	while (T--)
	{
		int N, M;
		cin >> N >> M;
		int i;
		for (i = 0; i < M; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;
			vis[b] = 1;
		}
		for (i = 1; i <= N; i++)
		{
			if (!vis[i])
			{
				int j;
				for (j = 1; j <= N; j++)
				{
					if(i!=j)
						cout << i << ' ' << j << '\n';
				}
				break;
			}
		}
		memset(vis, 0, sizeof(T) * (N + 5));
	}
}

C번: 

?x

x?과 같은 모양을 생각하자. 이 모양에서는 ?를 결정할 수 있는 방법이 없다. 항상 끝에 도달하지 못하기 때문이다. 길이가 1이면 항상 YES이고, 아니면 위와 같은 모양이 있는지를 체크해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
vector<string>x;
int psum[1000100];
int main()
{
	int N,M;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	int i;
	for (i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		x.push_back(s);
	}
	for (i = 1; i < M; i++)
	{
		int bef = 0;
		int cu = 0;
		int j;
		for (j = 1; j < N; j++)
		{
			if (x[j-1][i] == 'X'&&x[j][i-1]=='X')
			{
				psum[i + 1] = 1;
			}
			
		}
		psum[i+1] += psum[i];
	}
	int Q;
	cin >> Q;
	while (Q--)
	{
		int a, b;
		cin >> a >> b;
		if (psum[b] == psum[a])
			cout << "YES";
		else
			cout << "NO";
		cout << '\n';
	}
}

D번: 한 원소가 2이고 나머지가 1인 쿼리와, 한 원소가 1이고 나머지가 2인 쿼리를 통해, 특정 원소와 1 차이 나면서 특정 원소 전에 있는 원소를 찾을 수 있다. 이를 이용해서 선형 그래프를 만들고, 시작점 하나가 1이고 나머지가 N인 쿼리를 통해 어느 쪽이 1이고 어느 쪽이 N인지 찾으면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
vector<string>x;
vector<int>link[101];
int ans[101];
int main()
{
	int N,M;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	int i;
	for (i = N-1; i >0; i--)
	{
		cout << "? ";
		int j;
		for (j = 0; j < N; j++)
		{
			cout << 1 + (i == j) << ' ';
		}
		cout << '\n';
		cout.flush();
		int a;
		cin >> a;
		if (a && a <= i)
		{
			link[a - 1].push_back(i);
			link[i].push_back(a - 1);
		}
		cout << "? ";
		for (j = 0; j < N; j++)
		{
			cout << 2 - (i == j) << ' ';
		}
		cout << '\n';
		cout.flush();
		cin >> a;
		if (a && a <= i)
		{
			link[a - 1].push_back(i);
			link[i].push_back(a - 1);
		}
	}
	int st = -1;
	int en = -1;
	for (i = 0; i < N; i++)
	{
		if (link[i].size() == 1)
		{
			if (st == -1)
			{
				st = i;
			}
			else
				en = i;
		}
	}
	cout << "? ";
	int j;
	for (j = 0; j < N; j++)
	{
		cout << N - (N-1)*(en == j) << ' ';
	}
	cout << '\n';
	cout.flush();
	int a;
	cin >> a;
	int cur = 0;
	if (a-1 == st)
	{
		cur = st;
	}
	else
		cur = en;
	for (i = 0; i < N; i++)
	{
		ans[cur] = i + 1;
		int j;
		for (j = 0; j < link[cur].size(); j++)
		{
			if (!ans[link[cur][j]])
			{
				cur = link[cur][j];
				break;
			}
		}
	}
	cout << "! ";
	for (i = 0; i < N; i++)
	{
		cout << ans[i] << ' ';
	}
	cout << '\n';
	cout.flush();
}