Codeforces Round #573 (Div. 2)

果然太久不打CF手感全无,又是fst的一场,所幸没掉太多分


A. Tokitsukaze and Enhancement

time limit per test1 second memory limit per test256 megabytes

Tokitsukaze is one of the characters in the game “Kantai Collection”. In this game, every character has a common attribute — health points, shortened to HP.

In general, different values of HP are grouped into 44 categories:

  • Category AA if HP is in the form of (4n+1)(4n+1), that is, when divided by 44, the remainder is 11;
  • Category BB if HP is in the form of (4n+3)(4n+3), that is, when divided by 44, the remainder is 33;
  • Category CC if HP is in the form of (4n+2)(4n+2), that is, when divided by 44, the remainder is 22;
  • Category DD if HP is in the form of 4n4n, that is, when divided by 44, the remainder is 00.

The above-mentioned nn can be any integer.

These 44 categories ordered from highest to lowest as A>B>C>DA>B>C>D, which means category AA is the highest and category DD is the lowest.

While playing the game, players can increase the HP of the character. Now, Tokitsukaze wants you to increase her HP by at most 22 (that is, either by 00, 11 or 22). How much should she increase her HP so that it has the highest possible category?Input

The only line contains a single integer xx (30≤x≤10030≤x≤100) — the value Tokitsukaze’s HP currently.Output

Print an integer aa (0≤a≤20≤a≤2) and an uppercase letter bb (b∈{A,B,C,D}b∈{A,B,C,D}), representing that the best way is to increase her HP by aa, and then the category becomes bb.

Note that the output characters are case-sensitive.
Examplesinput

33

output

0 A

input

98

output

1 B

Note

For the first example, the category of Tokitsukaze’s HP is already AA, so you don’t need to enhance her ability.

For the second example:

  • If you don’t increase her HP, its value is still 9898, which equals to (4×24+2)(4×24+2), and its category is CC.
  • If you increase her HP by 11, its value becomes 9999, which equals to (4×24+3)(4×24+3), and its category becomes BB.
  • If you increase her HP by 22, its value becomes 100100, which equals to (4×25)(4×25), and its category becomes DD.

Therefore, the best way is to increase her HP by 11 so that the category of her HP becomes BB.

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
void solve(){
	scanf("%d",&n);
	int re=n%4;
	if(re==1) printf("0 A\n");
	else if(re==2) printf("1 B\n");
	else if(re==3) printf("2 A\n");
	else printf("1 A\n");
}
int main(){
	solve();
}

 


B. Tokitsukaze and Mahjong

time limit per test1 second memory limit per test256 megabytes

Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzupinzu or souzu) and a number (a digit ranged from 11 to 99). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, ……, 9m, 1p, 2p, ……, 9p, 1s, 2s, ……, 9s.

In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.

Do you know the minimum number of extra suited tiles she needs to draw so that she can win?

Here are some useful definitions in this game:

  • mentsu, also known as meld, is formed by a koutsu or a shuntsu;
  • koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;
  • shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu.

Some examples:

  • [2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;
  • [4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;
  • [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu.

Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.Input

The only line contains three strings — the tiles in Tokitsukaze’s hand. For each string, the first character is a digit ranged from 11 to 99 and the second character is m, p or s.Output

Print a single integer — the minimum number of extra suited tiles she needs to draw.
Examplesinput

1s 2s 3s

output

0

input

9m 9m 9m

output

0

input

3p 9m 2p

output

1

Note

In the first example, Tokitsukaze already has a shuntsu.

In the second example, Tokitsukaze already has a koutsu.

In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
string s[4];
int cmp(string a,string b){return a[0]<b[0];}
int a[4];
void solve(){
	cin>>s[1]>>s[2]>>s[3];
	sort(s+1,s+4,cmp);
	rep(i,1,3) a[i]=s[i][0]-'0'; 
	if(s[1]==s[2]&&s[2]==s[3]) {puts("0");return;}
	if(s[1][1]==s[2][1]&&s[2][1]==s[3][1]&&(a[3]==a[2]+1)&&(a[2]==a[1]+1)) {puts("0");return;}
	if(s[1]==s[2]||s[2]==s[3]||s[1]==s[3]) {puts("1");return;}
	if(a[2]==a[1]+1&&s[1][1]==s[2][1]) {puts("1");return;}
	if(a[3]==a[2]+1&&s[2][1]==s[3][1]) {puts("1");return;}
	if(a[3]==a[1]+1&&s[3][1]==s[1][1]) {puts("1");return;}
	if(s[1][1]==s[2][1]&&s[2][0]-s[1][0]<=2){puts("1");return;}
	if(s[3][1]==s[2][1]&&s[3][0]-s[2][0]<=2){puts("1");return;}
	if(s[1][1]==s[3][1]&&s[3][0]-s[1][0]<=2){puts("1");return;}
	puts("2");return;
}
int main(){
	solve();
}

 


C. Tokitsukaze and Discard Items

time limit per test1 second memory limit per test256 megabytes

Recently, Tokitsukaze found an interesting game. Tokitsukaze had nn items at the beginning of this game. However, she thought there were too many items, so now she wants to discard mm (1≤m≤n1≤m≤n) special items of them.

These nn items are marked with indices from 11 to nn. In the beginning, the item with index ii is placed on the ii-th position. Items are divided into several pages orderly, such that each page contains exactly kk positions and the last positions on the last page may be left empty.

Tokitsukaze would do the following operation: focus on the first special page that contains at least one special item, and at one time, Tokitsukaze would discard all special items on this page. After an item is discarded or moved, its old position would be empty, and then the item below it, if exists, would move up to this empty position. The movement may bring many items forward and even into previous pages, so Tokitsukaze would keep waiting until all the items stop moving, and then do the operation (i.e. check the special page and discard the special items) repeatedly until there is no item need to be discarded.

Consider the first example from the statement: n=10n=10, m=4m=4, k=5k=5, p=[3,5,7,10]p=[3,5,7,10]. The are two pages. Initially, the first page is special (since it is the first page containing a special item). So Tokitsukaze discards the special items with indices 33 and 55. After, the first page remains to be special. It contains [1,2,4,6,7][1,2,4,6,7], Tokitsukaze discards the special item with index 77. After, the second page is special (since it is the first page containing a special item). It contains [9,10][9,10], Tokitsukaze discards the special item with index 1010.

Tokitsukaze wants to know the number of operations she would do in total.Input

The first line contains three integers nn, mm and kk (1≤n≤10181≤n≤1018, 1≤m≤1051≤m≤105, 1≤m,k≤n1≤m,k≤n) — the number of items, the number of special items to be discarded and the number of positions in each page.

The second line contains mm distinct integers p1,p2,…,pmp1,p2,…,pm (1≤p1<p2<…<pm≤n1≤p1<p2<…<pm≤n) — the indices of special items which should be discarded.Output

Print a single integer — the number of operations that Tokitsukaze would do in total.
Examplesinput

10 4 5
3 5 7 10

output

3

input

13 4 5
7 8 9 10

output

1

Note

For the first example:

  • In the first operation, Tokitsukaze would focus on the first page [1,2,3,4,5][1,2,3,4,5] and discard items with indices 33 and 55;
  • In the second operation, Tokitsukaze would focus on the first page [1,2,4,6,7][1,2,4,6,7] and discard item with index 77;
  • In the third operation, Tokitsukaze would focus on the second page [9,10][9,10] and discard item with index 1010.

For the second example, Tokitsukaze would focus on the second page [6,7,8,9,10][6,7,8,9,10] and discard all special items at once.

暴力乱搞就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
ll n,k,a[maxn];
int m;
void solve(){
	scanf("%lld%d%lld",&n,&m,&k);
	rep(i,1,m) scanf("%lld",&a[i]);
	ll tot=0,ans=0;
	while(tot<m){
		ll st=tot%k+1;
		ll r=st+(a[tot+1]-st)/k*k+k;
		rep(i,tot+1,m){
			if(a[i]<r) tot++;
			if(a[i]>=r) break;
		}
		ans++;
	}
	printf("%lld\n",ans);
}
int main(){
	solve();
}

 


D. Tokitsukaze, CSL and Stone Game

time limit per test1 second memory limit per test256 megabytes

Tokitsukaze and CSL are playing a little game of stones.

In the beginning, there are nn piles of stones, the ii-th pile of which has aiai stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?

Consider an example: n=3n=3 and sizes of piles are a1=2a1=2, a2=3a2=3, a3=0a3=0. It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be [1,3,0][1,3,0] and it is a good move. But if she chooses the second pile then the state will be [2,2,0][2,2,0] and she immediately loses. So the only good move for her is to choose the first pile.

Supposing that both players always take their best moves and never make mistakes, who will win the game?

Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.Input

The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of piles.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤a1,a2,…,an≤1090≤a1,a2,…,an≤109), which mean the ii-th pile has aiai stones.Output

Print “sjfnb” (without quotes) if Tokitsukaze will win, or “cslnb” (without quotes) if CSL will win. Note the output characters are case-sensitive.
Examplesinput

1
0

output

cslnb

input

2
1 0

output

cslnb

input

2
2 2

output

sjfnb

input

3
2 3 1

output

sjfnb

Note

In the first example, Tokitsukaze cannot take any stone, so CSL will win.

In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.

In the third example, Tokitsukaze will win. Here is one of the optimal ways:

  • Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.
  • Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.
  • Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose.

In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.

首先判掉n=1和sum=0,1的情况,接下来有几种情况是先手输的:

1. 出现a,a+1,a+1这样的三元组
2. 出现a,a,b,b这样的四元组

取完所有石子后应该是0,1,2…n-1这样的排列,那么我们再看看能取走的石子的奇偶性就可以了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[maxn];
ll sum=0;
void solve(){
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]),sum+=a[i]; 
	sort(a+1,a+1+n);
	if(n==1){printf(sum%2==0?"cslnb\n":"sjfnb\n");return;}
	if(sum==0||sum==1){printf("cslnb\n");return;}
	sum=a[1];
	int flag=2;
	rep(i,2,n){
		if(a[i]==a[i-1]){
			if(a[i]==0||(a[i-1]==a[i-2]+1&&i-2)){flag=0;break;}
			if(flag==1){flag=0;break;}
			--flag;
		}
		sum+=a[i]+1-i;
	}
	if(!flag){printf("cslnb\n");return;}
	else printf(sum%2==0?"cslnb\n":"sjfnb\n");
}
int main(){
	solve();
}

 

发表评论,支持MarkDown语法