티스토리 뷰
카테고리 없음
Technocup 2022 — Elimination Round 1 and Codeforces Round #749 (Div. 1+Div. 2)
jjang36524 2021. 10. 18. 20:16망했다 ㅠㅠ
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();
}