Codejam Qualification Round 2019

basasuya 2019-04-07 14:00:00 阅读数:173 评论数:0 收藏数:0

A. Foregone Solution

``````#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
// #include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

char num[105];
char a[105];
char b[105];
int main() {
int _;
scanf("%d", &_);
for(int cas = 1; cas <= _; ++cas) {
scanf("%s", num);

bool flag = true;
for(int i = 0, len = strlen(num); i < len; ++i) {
if(num[i] == '4') {
a[i] = '2';
b[i] = '2';
flag = false;
} else {
a[i] = num[i];
b[i] = '0';
}
}

if(flag == true) {
int pos = -1;

for(int i = strlen(num) - 1; i >= 0; --i) {
if(num[i] != '0') {
pos = i;
// if(num[i] == '1') {
//     hasOne = true;
// }
break;
}
}
int hasOne = false;
for(int i = 0, len = strlen(num); i < len; ++i) {
if(i < pos) {
a[i] = num[i];
b[i] = '0';
} else if(i == pos) {
if(num[i] == '5') {
a[i] = '3';
b[i] = '2';
} else if(num[i] == '1' && i != strlen(num) - 1) {
a[i] = '0';
b[i] = '0';
hasOne = true;
} else {
a[i] = num[i] - 1;
b[i] = '1';
}
} else {
if(hasOne) {
a[i] = '9';
b[i] = (i == strlen(num) - 1) ? '1' :'0';
} else {
a[i] = num[i];
b[i] = '0';
}
}
}
}

printf("Case #%d: ", cas);
for(int i = 0, len = strlen(num), flag = true; i < len; ++i) {
if(a[i] == '0' && flag) {
} else {
flag = false;
printf("%c", a[i]);
}
}
printf(" ");
for(int i = 0, len = strlen(num), flag = true; i < len; ++i) {
if(b[i] == '0' && flag) {
} else {
flag = false;
printf("%c", b[i]);
}
}
printf("\n");

}
return 0;
}``````

B. You Can Go Your Own Way

``````#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
// #include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

char seq[100005];
char result[100005];
int main() {
int _;
scanf("%d", &_);
for(int cas = 1; cas <= _; ++cas) {
int n;
scanf("%d %s", &n, seq);
for(int i = 0, len = strlen(seq); i < len; ++i) {
if(seq[i] == 'S')
result[i] = 'E';
else
result[i] = 'S';
}

printf("Case #%d: ", cas);
for(int i = 0, len = strlen(seq); i < len; ++i) {
printf("%c", result[i]);
}
printf("\n");

}
return 0;
}``````

C. Cryptopangrams

``````import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {
Scanner in = new Scanner(new BufferedInputStream(System.in));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
BigInteger seq[] = new BigInteger[105];
BigInteger prime[] = new BigInteger[105];
//    BigInteger num[] = new BigInteger[105];
int lower_bound(BigInteger[] nums, int begin, int end, BigInteger value) {
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (nums[mid].compareTo(value) == -1) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
void solve() {
int casNum;
casNum = in.nextInt();
for(int cas = 1; cas <= casNum; ++cas) {
BigInteger n;
int l;
n = in.nextBigInteger(); l = in.nextInt();
for(int i = 0; i < l; ++i) {
seq[i] = in.nextBigInteger();
}

int pos = -1;
for(int i = 1; i < l; ++i) {
if(seq[i].equals(seq[i-1]) == false) {
prime[i] = seq[i].gcd(seq[i-1]);
pos = i;
break;
}
}

for(int i = pos - 1; i >= 0; --i) {
prime[i] = seq[i].divide(prime[i + 1]);
}
for(int i = pos + 1; i <= l; ++i) {
prime[i] = seq[i-1].divide(prime[i-1]);
}

List<BigInteger> num=new ArrayList<>();
for(int i = 0; i <= l; ++i) {
num.add(prime[i]);
}
Set<BigInteger> uniqueGas = new HashSet<BigInteger>(num);
//            out.println(uniqueGas.size());
//            for(BigInteger i : uniqueGas) {
//                out.println(i);
//            }
BigInteger[] result = uniqueGas.toArray(new BigInteger[0]);
Arrays.sort(result, 0, uniqueGas.size());
assert(uniqueGas.size() == 26);
// printf("%d\n", (int)num.size());
// for(int i = 0, len = num.size(); i < len; ++i) printf("%lld ", num[i]); printf("\n");
out.printf("Case #%d: ", cas);

for(int i = 0; i <= l; ++i) {
int tt = lower_bound(result,0, uniqueGas.size(), prime[i]);
out.printf("%c", tt + 'A');
}
out.printf("\n");
}
out.flush();
}
public static void main(String args[]) {
new Solution ().solve();

}
}``````

D. Dat Bae

``````#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

vector<pair<int, int> > prepare;
vector<pair<int, int> > solve;
vector<int> preClip;
vector<int> solveClip;
int result[2005];
char answer[2005];
int main() {
int _;
scanf("%d", &_);
for(int cas = 1; cas <= _; ++cas) {
int n, b, f;
scanf("%d %d %d", &n, &b, &f);
prepare.clear();
preClip.clear();
prepare.push_back(make_pair(1, n));
preClip.push_back(n - b);

while(1) {
solveClip.clear();
solve.clear();
int flag = false;
int maxx = -1;
for(int i = 0, len = prepare.size(); i < len; ++i) {
int start = prepare[i].first; int end = prepare[i].second;
// if(end == start) {
//     solve.push_back(make_pair(start, end));
// } else {
int mid = (start + end) / 2;
solve.push_back(make_pair(start, mid));
solve.push_back(make_pair(mid + 1, end));
// }
maxx = max(maxx, end - start);
}
if(maxx == 1) flag = true;

for(int i = 0, len = solve.size(); i < len; ++i) {
int start = solve[i].first; int end = solve[i].second;
for(int j = start; j <= end; ++j) {
printf("%d", (i % 2 == 0) ? 0 : 1);
}
}
printf("\n");
fflush(stdout);
scanf("%s", answer);
for(int i = 0, len = preClip.size(), pre = 0; i < len; ++i) {
int pos = pre + preClip[i];
for(int j = pre, endJ = pre + preClip[i]; j < endJ; ++j) {
if(answer[j] == '1') {
pos = j;
break;
}
}
solveClip.push_back(pos - pre);
solveClip.push_back(preClip[i] - pos + pre);
pre += preClip[i];
}

if(flag == true) break;

// assert(solve.size() == solveClip.size());
// for(int i = 0, len = solve.size(); i < len; ++i) {
//     int start = solve[i].first; int end = solve[i].second; int val = solveClip[i];
//     printf("%d %d %d: ", start, end, val);
// } printf("\n");

prepare.swap(solve);
preClip.swap(solveClip);
}

assert(solve.size() == solveClip.size());

for(int i = 0, len = solve.size(); i < len; ++i) {
int start = solve[i].first; int end = solve[i].second; int val = solveClip[i];
if(start == end) {
if(val == 1) {
result[start] = 1;
} else {
result[start] = 0;
}
}
}
for(int i = 1, fir = true; i <= n; ++i) {
if(result[i] == 0) {
if(fir) fir = false;
else printf(" ");
printf("%d", i - 1);
}
}
printf("\n");
fflush(stdout);

int basa;
scanf("%d", &basa);
}
return 0;
}

/*
1000
5 2 10
answer(0 3)
2 1 10
answer(0)

*/``````

0101010101010101
0011001100110011
0000111100001111
0000000011111111

``````#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

void solve(){
int F = 4;
int n, b, fake_f;
cin >> n >> b >> fake_f;
// assert(fake_f >= F);
for(int f = 0; f < F; f++){
string g;
for(int i = 0; i < n; i++){
g += (char)('0' + ((i >> f) & 1));
}
cout << g << '\n' << flush;
}
vector<int> answers(n-b);
for(int f = 0; f < F; f++){
string res;
cin >> res;
for(int i = 0; i < n-b; i++){
answers[i] ^= (res[i] - '0') << f;
}
// for(int i = 0; i < n - b; ++i) {
//     printf("%d ", answers[i]);
// } printf("\n");
}
vector<int> broken;
int z = 0;
for(int i = 0; i < n-b; i++){
while((z & 15) != answers[i]){
cout << z << ' ';
z++;
}
z++;
}
while(z < n){
cout << z << ' ';
z++;
}
cout << '\n';
cout << flush;
int res;
cin >> res;
}

int main(){
int T;
cin >> T;
for(int t = 1; t <= T; t++){
solve();
}
}

/*
1000
5 2 10

01010
00110
00001
00000
00000
100
010
001
000
000
answer(0 3)
000
010
001
000
000
answer(0 3)

2 1 10
answer(0)

*/``````