Suspects

题面翻译

一共有N个人，其中有一人为罪犯。
现在每个人说了N句话，内容是说谁是罪犯或
谁不是罪犯(也可以说自己)。其中有M句真话。

给定N和M以及N个数，设为a[1]~a[N]
如果a[i]>0,代表第i个人说第a[i]个人是罪犯，反之代表第i个人说第-a[i]个人不是罪犯。
输出有N行，如果第i个人说的一定是真话，输出"Truth"；
如果第i个人说的一定是假话，输出"Lie";
如果第i个人说的可能是真话也可能是假话则输出"Not defined"。

题目描述

As Sherlock Holmes was investigating a crime, he identified $n$ suspects.

He knows for sure that exactly one of them committed the crime.

To find out which one did it, the detective lines up the suspects and numbered them from $1$ to $n$ .

After that, he asked each one: “Which one committed the crime?”.

Suspect number $i$ answered either "The crime was committed by suspect number $ai$ ", or “Suspect number $a_i$ didn’t commit the crime”.

Also, the suspect could say so about himself ( $a_i=i$ ).

Sherlock Holmes understood for sure that exactly $m$ answers were the truth and all other answers were a lie.

Now help him understand this: which suspect lied and which one told the truth?

输入格式

The first line contains two integers $n$ and $m$ ( $1<=n<=10^5,0<=m<=n$ ) — the total number of suspects and the number of suspects who told the truth.

Next $n$ lines contain the suspects’ answers.

The $i$ -th line contains either "+ $a_i$ " (without the quotes), if the suspect number $i$ says that the crime was committed by suspect number $a_i$ , or "- $a_i$ " (without the quotes), if the suspect number $i$ says that the suspect number $a_i$ didn’t commit the crime ( $a_i$ is an integer, $1<=a_i<=n$ ).

It is guaranteed that at least one suspect exists, such that if he committed the crime, then exactly $m$ people told the truth.

输出格式

Print $n$ lines.

Line number $i$ should contain “Truth” if suspect number $i$ has told the truth for sure.

Print “Lie” if the suspect number $i$ lied for sure and print “Not defined” if he could lie and could tell the truth, too, depending on who committed the crime.

样例 #1

样例输入 #1

1 1
+1
1
2

样例输出 #1

Truth
1

样例 #2

样例输入 #2

3 2
-1
-2
-3
1
2
3
4

样例输出 #2

Not defined
Not defined
Not defined
1
2
3

样例 #3

样例输入 #3

4 1
+2
-3
+4
-1
1
2
3
4
5

样例输出 #3

Lie
Not defined
Lie
Not defined
1
2
3
4

提示

The first sample has the single person and he confesses to the crime, and Sherlock Holmes knows that one person is telling the truth.

That means that this person is telling the truth.

In the second sample there are three suspects and each one denies his guilt.

Sherlock Holmes knows that only two of them are telling the truth.

Any one of them can be the criminal, so we don’t know for any of them, whether this person is telling the truth or not.

In the third sample the second and the fourth suspect defend the first and the third one.

But only one is telling the truth, thus, the first or the third one is the criminal.

Both of them can be criminals, so the second and the fourth one can either be lying or telling the truth.

The first and the third one are lying for sure as they are blaming the second and the fourth one.

#include
using namespace std;
const int N=2e6+10;
typedef long long ll;
int n,m;
int p[N],yes[N],no[N],noman=0,sign[N],maybe=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		if(p[i]>0) yes[p[i]]++;
		else{
			no[-p[i]]++;
			noman++;
		}
	}
	for(int i=1;i<=n;i++){
		if(yes[i]+noman-no[i]==m){
			sign[i]=1;
			maybe++;
		}
	}
	for(int i=1;i<=n;i++){
		if(p[i]>0){
			if(maybe==1&&sign[p[i]]==1) puts("Truth");
			else if(sign[p[i]]==0) puts("Lie");
			else puts("Not defined");
		}
		else{
			if(sign[-p[i]]==0) puts("Truth");
			else if(maybe==1) puts("Lie");
			else puts("Not defined");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Movie Critics

题面翻译

给出一个长度为 $n$ 的序列，序列仅包含 $1$ 到 $k$ 的数字，且对于每个数字，在序列中的出现次数至少为一次。

现在请你选出一个数字，使删去数列中所有的这个数字后，相邻位置的数字是不同的个数最小。

如果答案有多个，请输出最小的一个。

题目描述

A film festival is coming up in the city N.

The festival will last for exactly $n$ days and each day will have a premiere of exactly one film.

Each film has a genre — an integer from 1 to $k$ .

On the $i$ -th day the festival will show a movie of genre $a_i$ .

We know that a movie of each of $k$ genres occurs in the festival programme at least once. In other words, each integer from 1 to $k$ occurs in the sequence $a_1,a_2,...,a_n$ at least once.

Valentine is a movie critic.

He wants to watch some movies of the festival and then describe his impressions on his site.

As any creative person, Valentine is very susceptive.

After he watched the movie of a certain genre, Valentine forms the mood he preserves until he watches the next movie.

If the genre of the next movie is the same, it does not change Valentine’s mood.

If the genres are different, Valentine’s mood changes according to the new genre and Valentine has a stress.

Valentine can’t watch all $n$ movies, so he decided to exclude from his to-watch list movies of one of the genres.

In other words, Valentine is going to choose exactly one of the $k$ genres and will skip all the movies of this genre.

He is sure to visit other movies.

Valentine wants to choose such genre $x$ ( $1<=x<=k$ ), that the total number of after-movie stresses (after all movies of genre $x$ are excluded) were minimum.

输入格式

The first line of the input contains two integers $n$ and $k$ ( $2<=k<=n<=10^5$ ), where $n$ is the number of movies and $k$ is the number of genres.

The second line of the input contains a sequence of $n$ positive integers $a_1$ , $a_2$ , …, $a_n$ ( $1<=a_i<=k$ ), where $a_i$ is the genre of the $i$ -th movie. It is guaranteed that each number from 1 to $k$ occurs at least once in this sequence.

输出格式

Print a single number — the number of the genre (from 1 to $k$ ) of the excluded films.

If there are multiple answers, print the genre with the minimum number.

样例 #1

样例输入 #1

10 3
1 1 2 3 2 3 3 1 1 3
1
2

样例输出 #1

3
1

样例 #2

样例输入 #2

7 3
3 1 3 2 3 1 2
1
2

样例输出 #2

1
1

提示

In the first sample if we exclude the movies of the 1st genre, the genres $2,3,2,3,3,3$ remain, that is 3 stresses;

if we exclude the movies of the 2nd genre, the genres $1,1,3,3,3,1,1,3$ remain, that is 3 stresses;

if we exclude the movies of the 3rd genre the genres $1,1,2,2,1,1$ remain, that is 2 stresses.

In the second sample whatever genre Valentine excludes, he will have exactly 3 stresses.

#include
using namespace std;
const int N=2e6+10;
typedef long long ll;
int n,k,a[N],b[N],sign[N],kmax=0,kk=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=a[i-1]){
			b[++kk]=a[i];
			sign[a[i]]++;
			kmax=max(kmax,sign[a[i]]);
		}
	}
	for(int i=1;i<=kk;i++){
		if(b[i-1]==b[i+1]){
			sign[b[i]]++;
			kmax=max(kmax,sign[b[i]]);
		}
	}
	for(int i=1;i<=k;i++){
		if(sign[i]==kmax){
			printf("%d\n",i);
			return 0;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Fish Weight

题面翻译

已知极地海洋中有k种鱼类，编号从1到k。它们按权重的非递减顺序排序，且是一个正数

北极熊爱丽丝和鲍勃各自抓了一些鱼，当给定这些数据和题设条件后要判断Alice的鱼的总重量是否能够比Bob的大。

说明：在这个例子中，令w1=1,w2=2,w3=2.5，即可使得w_Alice=6，w_Bob=4.5，所以此情况输出“YES”，否则输出“NO”.

题目描述

It is known that there are $k$ fish species in the polar ocean, numbered from $1$ to $k$ .

They are sorted by non-decreasing order of their weight, which is a positive number.

Let the weight of the $i$ -th type of fish be $w_i$ , then KaTeX parse error: Expected 'EOF', got '&' at position 2: 0&̲lt;w_{1}<=w_{2}… holds.

Polar bears Alice and Bob each have caught some fish, and they are guessing who has the larger sum of weight of the fish he/she’s caught.

Given the type of the fish they’ve caught, determine whether it is possible that the fish caught by Alice has a strictly larger total weight than Bob’s.

In other words, does there exist a sequence of weights $w_i$ (not necessary integers), such that the fish caught by Alice has a strictly larger total weight?

输入格式

The first line contains three integers $n,m,k$ $(1<=n,m<=10^5,1<=k<=10^9)$ — the number of fish caught by Alice and Bob respectively, and the number of fish species.

The second line contains $n$ integers each from 1 to $k$ , the list of fish type caught by Alice.

The third line contains $m$ integers each from 1 to $k$ , the list of fish type caught by Bob.

Note that one may have caught more than one fish for a same species.

输出格式

Output “YES” (without quotes) if it is possible, and “NO” (without quotes) otherwise.

样例 #1

样例输入 #1

3 3 3
2 2 2
1 1 3
1
2
3

样例输出 #1

YES
1

样例 #2

样例输入 #2

4 7 9
5 2 7 3
3 5 2 7 3 8 7
1
2
3

样例输出 #2

NO
1

提示

In the first sample, if $w_1=1,w_2=2,w_3=2.5$ , then Alice has a total of $2+2+2=6$ weight units, while Bob only has $1+1+2.5=4.5$ .

In the second sample, the fish that Alice caught is a subset of Bob’s. Therefore, the total weight of Bob’s fish is always not less than the total weight of Alice’s fish.

#include
using namespace std;
const int N=2e6+10;
typedef long long ll;
int n,m,k,a[N],b[N];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	int i=1,j=1;
	while(i<=n&&j<=m){
		if(a[i]<=b[j]) i++,j++;
		else j++;
	}
	if(i<=n) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Plate Game

题面翻译

你有一个长方形的桌子，长度 a ,宽度 b ,以及无限多的半径 r的圆盘。

两位玩家玩以下游戏：他们轮流把圆盘放在桌子上，使得盘子之间不能互相重叠(但他们的边缘可以互相接触)，任何盘子上的任何点都位于桌子的边界内（也就是盘子的任意一部分不能悬空）。在比赛中，人们不能移动已经摆在桌子上的盘子。不能再往桌子上合法的摆圆盘的玩家输。

你的任务是确定哪个玩家赢了，先放圆盘的玩家称为“First”，后放圆盘的玩家称为“Second”，当然两个球员都发挥得最好。

题目描述

You’ve got a rectangular table with length $a$ and width $b$ and the infinite number of plates of radius $r$ .

Two players play the following game: they take turns to put the plates on the table so that the plates don’t lie on each other (but they can touch each other), and so that any point on any plate is located within the table’s border.

During the game one cannot move the plates that already lie on the table.

The player who cannot make another move loses.

Determine which player wins, the one who moves first or the one who moves second, provided that both players play optimally well.

输入格式

A single line contains three space-separated integers $a$ , $b$ , $r$ $(1<=a,b,r<=100)$ — the table sides and the plates’ radius, correspondingly.

输出格式

If wins the player who moves first, print “First” (without the quotes). Otherwise print “Second” (without the quotes).

样例 #1

样例输入 #1

5 5 2
1

样例输出 #1

First
1

样例 #2

样例输入 #2

6 7 4
1

样例输出 #2

Second
1

提示

In the first sample the table has place for only one plate. The first player puts a plate on the table, the second player can’t do that and loses.

In the second sample the table is so small that it doesn’t have enough place even for one plate. So the first player loses without making a single move.

#include
using namespace std;
const int N=2e6+10;
typedef long long ll;
int a,b,r;
int main(){
	cin>>a>>b>>r;
	if(a<r*2||b<r*2)printf("Second");
	else printf("First");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

Hometask

题面翻译

题意：给你一串字符串，再给你k<=13个只有两个字符得串，且这些字符不重复，问你需要在原串中删除多少个字符才能保证原串中不含这k个串及其反向串。

题目描述

Sergey attends lessons of the $N$ -ish language.

Each lesson he receives a hometask.

This time the task is to translate some sentence to the $N$ -ish language.

Sentences of the $N$ -ish language can be represented as strings consisting of lowercase Latin letters without spaces or punctuation marks.

Sergey totally forgot about the task until half an hour before the next lesson and hastily scribbled something down.

But then he recollected that in the last lesson he learned the grammar of $N$ -ish.

The spelling rules state that $N$ -ish contains some “forbidden” pairs of letters: such letters can never occur in a sentence next to each other.

Also, the order of the letters doesn’t matter (for example, if the pair of letters “ab” is forbidden, then any occurrences of substrings “ab” and “ba” are also forbidden).

Also, each pair has different letters and each letter occurs in no more than one forbidden pair.

Now Sergey wants to correct his sentence so that it doesn’t contain any “forbidden” pairs of letters that stand next to each other.

However, he is running out of time, so he decided to simply cross out some letters from the sentence.

What smallest number of letters will he have to cross out?

When a letter is crossed out, it is “removed” so that the letters to its left and right (if they existed), become neighboring.

For example, if we cross out the first letter from the string “aba”, we get the string “ba”, and if we cross out the second letter, we get “aa”.

输入格式

The first line contains a non-empty string $s$ , consisting of lowercase Latin letters — that’s the initial sentence in $N$ -ish, written by Sergey.

The length of string $s$ doesn’t exceed $10^5$ .

The next line contains integer $k$ ( $0<=k<=13$ ) — the number of forbidden pairs of letters.

Next $k$ lines contain descriptions of forbidden pairs of letters.

Each line contains exactly two different lowercase Latin letters without separators that represent the forbidden pairs.

It is guaranteed that each letter is included in no more than one pair.

输出格式

Print the single number — the smallest number of letters that need to be removed to get a string without any forbidden pairs of neighboring letters.

Please note that the answer always exists as it is always possible to remove all letters.

样例 #1

样例输入 #1

ababa
1
ab
1
2
3

样例输出 #1

2
1

样例 #2

样例输入 #2

codeforces
2
do
cs
1
2
3
4

样例输出 #2

1
1

提示

In the first sample you should remove two letters b.

In the second sample you should remove the second or the third letter. The second restriction doesn’t influence the solution.

#include
using namespace std;
const int N=2e6+10;
typedef long long ll;
int n,l,k,ans=0;
char p[N],p2[N];
int main(){
	scanf("%s",p);
	l=strlen(p);
	cin>>k;
	while(k--){
		scanf("%s",p2);
		int k1=0,k2=0;
		for(int i=0;i<l;i++){
			if(p[i]==p2[0]) k1++;
			else if(p[i]==p2[1]) k2++;
			else{
				ans+=min(k1,k2);
				k1=k2=0;
			}
		}
		ans+=min(k1,k2);
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26