Hello,
The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a >= b);
}
#include <bits/stdc++.h>
using namespace std;
bool isp(int x){
if (x < 2)return false;
for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;
return true;
}
int main(){
int x;
scanf("%d", &x);
if (isp(x - 2))printf("%d %d\n", 2, x - 2);
else printf("-1\n");
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int s , x ;
scanf("%d %d" , &s , &x) ;
int ans = 0 ;
while (s > 0){
s/=x ;
ans++;
}
if (ans != 0)
printf("%d\n" , ans) ;
else
printf("%d\n" , 1) ;
}
#include <bits/stdc++.h>
using namespace std;
void solve(){
string an;
for (int i = 0; i < 24; ++i)an += "DL";
an += "RRUU";
printf("%d\n%s\n", (int)an.size(), an.c_str());
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
void solve(){
string an;
f(it, 0, 24)an += "DL";
f(it, 0, 4){
f(it, 0, 5)an += 'U';
f(it, 0, 2)an += 'L';
f(it, 0, 5)an += 'D';
an += 'L';
f(it, 0, 5)an += 'D';
}
an += "RRRRRRRRDDUUURDDDDUUUUULLDDDDRRUUUU";
printf("%d\n%s\n", (int)an.size(), an.c_str());
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000;
#define pb push_back
int n,x[N],y[N],l[N],r[N],indeg[N];
bool g[N][N];
void get(int &n, int l, int r){
assert(scanf("%d",&n)+1);
assert(n>=l && n<=r);
}
set<pair<int, int>> st;
int main(){
get(n,1,3000);
for(int a,rn,i=0; i<n; ++i){
get(x[i], -oo, oo);
get(y[i], -oo, oo);
get(a, 0, 359);
get(rn, 0, 89);
l[i]=(a-rn+360)%360;
r[i]=(a+rn)%360;
assert(st.insert({x[i],y[i]}).second);
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(i==j)continue;
int dx=x[j]-x[i], dy=y[j]-y[i];
double ang=atan2(dy,dx);
if(ang<0)
ang+=2*PI;
ang*=180/PI;
bool in=0;
if(l[i]>r[i]){
if(ang+eps>=l[i] || ang-eps<=r[i])
in=1;
}else if(ang+eps>=l[i] && ang-eps<=r[i])
in=1;
g[i][j]=in;
indeg[j]+=in;
}
}
queue<int> q;
for(int i=0; i<n; ++i)
if(!indeg[i])
q.push(i);
vector<int> ans;
while(!q.empty()){
int u=q.front();
q.pop();
ans.push_back(u+1);
for(int i=0; i<n; ++i)
if(g[u][i] && !--indeg[i])
q.push(i);
}
if(ans.size()<n)
return cout<<-1<<endl,0;
for(int i=0; i<n; ++i)
printf("%d%c", ans[i], i<n-1?' ':'\n');
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 100000;
ll const inf = 2e18;
int n;
struct S{
int fr;
ll a, b, mn;
S(){}
S(int _a, ll _b):fr(1), a(_a), b(_b), mn(_a + _b) {}
S operator +(S const &o){
S an;
an.fr = fr + o.fr;
an.a = a + o.a;
an.mn = min(mn, o.mn + a);
return an;
}
}s[N << 2];
void st(int i, int a1, ll b1, int l = 1, int r = n, int id = 1){
if (l == r)return void(s[id] = S(a1, b1));
int m = l + r >> 1, a = id << 1, b = a | 1;
if (i <= m)st(i, a1, b1, l, m, a);
else st(i, a1, b1, m + 1, r, b);
s[id] = s[a] + s[b];
}
void kl(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){
if (l == r){
if(sm + s[id].mn >= x)return;
s[id].fr = 0;
s[id].a = 0;
s[id].b = inf;
s[id].mn = inf;
return;
}
int m = l + r >> 1, a = id << 1, b = a | 1;
if (s[b].mn + sm + s[a].a < x)kl(x, sm + s[a].a, m + 1, r, b);
if (s[a].mn + sm < x)kl(x, sm, l, m, a);
s[id] = s[a] + s[b];
}
int bs(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){
if (l == r)return x >= sm + s[id].a ? s[id].fr : 0;
int m = l + r >> 1, a = id << 1, b = a | 1;
if (s[a].a + sm > x)return bs(x, sm, l, m, a);
else return s[a].fr + bs(x, sm + s[a].a, m + 1, r, b);
}
int dead(ll x){
int fr = s[1].fr;
kl(x);
return fr - s[1].fr;
}
int hungry(ll x) { return s[1].fr - bs(x); }
int main(){
scanf("%d", &n);
f(i, 1, n + 1){
int a;
ll b;
scanf("%d%lld", &a, &b);
st(i, a, b);
}
int q;
scanf("%d", &q);
while (q--){
int o;
scanf("%d", &o);
if (o == 1){
ll x;
scanf("%lld", &x);
int b = hungry(x), a = dead(x);
printf("%d %d\n", a, b);
}else {
int a, c;
ll b;
scanf("%d%lld%d", &a, &b, &c);
st(c, a, b);
}
}
}
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1) ;
int main() {
double v , s ;
scanf("%lf %lf" ,&v , &s) ;
double ans ;
ans = s/(2.0 * sin(pi/v)) ;
printf("%.9lf" , ans * ans * pi) ;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000;
char s[N + 1];
int an[N], n;
inline bool isNumberDigit(char c) { return c >= '0' && c <= '9'; }
int I;
inline int readInteger(){
int an = 0;
while (isNumberDigit(s[I])){
an = an * 10 + s[I] - '0';
++I;
}
return an;
}
void readSoldier(int supervisor){
int id = readInteger();
while (s[I] == '('){
++I;
readSoldier(id);
++I;
}
an[id] = supervisor;
}
int main(){
scanf("%d%s", &n, s);
readSoldier(0);
printf("%d", an[1]);
f(i, 2, n + 1)printf(" %d", an[i]);
printf("\n");
}
#include <bits/stdc++.h>
using namespace std;
const int N = 2001,M = 1e9 + 7;
int n,m,k,dp[N][N],ans;
void add(int &a,int b){
a+=b;
if(a >= M)a-=M;
}
int main(){
scanf("%d%d%d",&n,&k,&m);
k = min(m,k);
dp[0][0] = 1;
for(int i = 0;i < m;i++)
for(int j = 0;j <= k;j++){
if(j + 1 <= k)add(dp[i + 1][j + 1],dp[i][j]);
if(j - 1 >= 0)add(dp[i + 1][j - 1],dp[i][j]);
}
for(int i = 2;i <= m;i+=2)add(ans,dp[i][0]);
printf("%d\n",2LL*n*ans%M);
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
int n , a[25];
vector<int>v ;
ll ans = 0 ;
void calc(int idx) {
if (idx == n)
{
int x = 0 ;
for(int i =0 ; i<v.size() ; ++i) {
x |=v[i] ;
}
ans+= 1ll *x ;
return ;
}
v.push_back(a[idx]) ;
calc(idx+1) ;
v.pop_back() ;
calc(idx+1) ;
}
int main() {
scanf("%d" , &n) ;
for (int i =0 ; i<n ; ++i) {
scanf("%d" , &a[i]) ;
}
calc(0) ;
printf("%lld\n" , ans) ;
return 0;
}
Instead of going through all the subsets, we will try to find a simpler way by going through the bits of the given numbers. we know that the number of subsets is $$$2^n - 1$$$, for the $$$i^{th}$$$ bit of each number we know it's either $$$1$$$ or $$$0$$$, you can notice that for a resulting subset of ORing some numbers, its $$$i^{th}$$$ bit is $$$0$$$ $$$iff$$$ all the $$$i^{th}$$$ bit of elements in the subset is $$$0$$$. With this observation we can eliminate all the $$$i^{th}$$$ bits of $$$0's$$$ in all subsets and add keep the $$$1's$$$ and then add the summation of the $$$1's$$$ of $$$i^{th}$$$ bit to the final answer. In short, what you have to do is to find the summation for each $$$i^{th}$$$ bit in all subsets, but don't forget to multiply by its digit place, and you get the resulting formula for the $$$i^{th}$$$ bit (assuming $$$x = 0's$$$ $$$count$$$ $$$for$$$ $$$i^{th}$$$ $$$bit$$$) the answer is : $$$((2^n -1) - (2^x-1)) * 2^i.$$$
Complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e5+5 ;
int n , a[N] , zero[31];
int main() {
scanf("%d" , &n) ;
for (int i =0 ; i<n; ++i) {
scanf("%d" , &a[i]) ;
}
for (int i = 0; i <31 ; i++){
for (int j = 0; j < n; j++) {
if (!(a[j] & 1 << i)) {
zero[i]++;
}
}
}
ll ans = 0;
for (int i = 0; i < 31 ; i++)
{
ans += (1ll * ( (1<<n) - 1) - (1ll*(1<<zero[i]) - 1)) * 1ll*(1<<i);
}
printf("%lld\n" , ans) ;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000;
char s[N + 1];
vector<pair<int, int> > an;
void no() { printf("-1\n"); exit(0); }
inline void ad(int tp, int i) { an.push_back(make_pair(tp, i)); }
int main(){
scanf("%s", s);
int n = strlen(s);
string v;
f(i, 0, n)if (s[i] == 'c'){ // first remove all 'c' characters
if (v.empty())no(); // 'c' is first character in string
if (v.back() == 'a'){ // "ac"
ad(3, v.size() + 1);
v += 'b';
v += 'a';
}else {
if (v.size() == 1)no(); // "bc"
if (v[v.size() - 2] == 'a'){ // "abc"
ad(4, v.size() - 1);
v.pop_back();
v.pop_back();
}else { // "bbc"
ad(2, v.size() - 1);
ad(3, v.size());
ad(4, v.size() + 1);
}
}
}else v += s[i];
string g;
f(i, 0, v.size())if (v[i] == 'b'){ // string contains only 'a' and 'b'
if (g.empty())no();
ad(2, g.size() + 1);
ad(4, g.size());
g.pop_back();
}else g += v[i];
f(i, 0, g.size()){ // remove any left 'a' characters
ad(1, 1);
ad(2, 2);
ad(4, 1);
}
printf("%d\n", (int)an.size());
f(i, 0, an.size())printf("%d %d\n", an[i].first, an[i].second);
}