HPU算法协会一二年级联合训练赛
今天跟大二一起打了一场训练赛，说来话长。。。
13道题，全是英文题，懒得没拿词典，后来才知道可以用电子词典(当然正经比赛里面是不可以的。先写一下我做出来的题解在总结吧。
MaratonIME helps Pablito
Description:
♬ Caloventor tiene miedo... ♬
Benedetto, Nathan
As is well known by any cultured person, rats are the smartest beings on earth. Followed directly by dolphins.
MaratonIME knows about the species hierarchy and uses this knowledge in it's regard. Usually, when they need some resource, they know it's always useful to have a smart rat available. Unfortunately, rats are not very fond of us, primates, and will only help us if they owe us some favour.
With that in mind, MaratonIME decided to help a little rat called Pablito. Pablito is studying rat's genealogy, to help with cloning and genetic mapping. luckily, the way rats identify themselves make the job much easier.
The rat society is, historically, matriarchal. At first, there were little families, each of which had it's own leading matriarch. At that time, it was decided that rats would organize themselves according to the following rules:
Each martiarch had an id number greater than one.
Each of these ids were chosen in a way such that they would have the least amount of divisors possible.
Each family member had the same id as the matriarch.
The id of any newborn rat would be the product of its parents id's.
For instance, the offspring of a rat with id 6 and another with id 7 is 42.
Pablito needs to know if two given rats have a common ancestor, but his only tool is the id number of each of the two rats, which is always a positive integer greater than 1 with no more than 16 digits. Can you help him?
Create a program that decides if a pair of rats have some common ancestor.
Input
The input begins with a positive integer t ≤ 105, the number of test cases.
After that, follows t lines, each with two integers ai e bi identifying two rats.
Every rat's id is a positive integer greater than 1 and with no more than 16 digits.
Output
For each test case, print "Sim" if the rats ai and bi share a common ancestor and "Nao" otherwise.
Example
Input
2
2 4
3 5
Output
Sim
Nao
Problem solving:
这道题我没看太懂意思。
题意好像就是如果两个数gcd不为1的话就说明有相同的祖先。
看着样例感觉像是简单题，看了一下一血时间，准备试一下gcd，然后，就过了。
Code:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long n,a,b;
cin>>n;
while(n--)
{
cin>>a>>b;
if(__gcd(a,b)==1) puts("Nao");
else puts("Sim");
}
}MaratonIME plays Cîrokime
Description:
Have you ever seen flavored vodka?
Everaldo, Glauber
The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named "Cîrokime". The game works as follows:
First, n cups with Cîroc1 are lined up. In front of the i-th cup a number ai is written. It is guaranteed that ai < ai + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.
The player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup's number ai is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.
"Cîrokime" is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home3
However, the DESMAME4 is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.
Input
The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.
1 ≤ n ≤ 1e5
For all i, 1 ≤ ai ≤ 1e9
For i < n, ai < ai + 1
Output
The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.
Examples
Input
3
2 5 7
Output
2
Input
8
1 2 3 4 5 6 7 8
Output
4
Note
1: Cîroc is a vodka brand made in France, known by its high sales price in market2
2: Balalaika also works
3: Based on real facts
4: Pre-BIFE5 party
5: University games that IME6 attends
6: Institute of Mathematics and Statistics
Problem solving:
这道题其实就是个猜数问题。问你在最差的情况下需要猜几次。
题意知道了，就很简单了，答案只跟n有关，中间的数都没用。看n可以除以2几次，就是答案。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,a;
scanf("%lld",&n);
for(int i=0;i<n;i++) scanf("%lld",&a);
ll ans=0;
while(n)
{
n/=2;
ans++;
}
printf("%lld\n",ans);
}MaratonIME plays Nim
Description:
Ai Fox!
UnionFind, Germano
You open your eyes, but everything remains dark. The world is dark, and everything shakes. You realize you are locked in, but before desperation takes hold, you hear the door opening and the light invades your sight and blinds you for a few moments.
They help you out, you had been locked inside a trunk. You don't know the masked faces before you, but remember that in the last competitive programming practice they told you that "the beginning is yet to come". "So this is the fabled MaratonIME's initiation challenge", you had heard rumors of this event, and you feel honored to be chosen.
After walking into and abandoned building, they sit you on an old chair. The first test is to watch a soccer game without any show of excitement. Easy. The second is to install Linux on a notebook in less than 5 minutes. You were prepared, carrying the Arch Linux pendrive as usual, just in case. You face more tests, and manage to pass all of them despite a few difficulties.
Hours go by, the members remove their masks, and each take a coin out of their pocket. "I won! And I even got rich" you think, but realize they place the coins in a table in front of you, divided in two piles. Renzo, MaratonIME's great boss, takes a chair and sits in front of you. You will play a match of Nim, and if you win you will become an honorary member of MaratonIME, that is, you win a balloon.
Nim is a game of two players, alternating their turns. Two piles of coins are placed on a table and in each turn you can remove any non zero quantity of coins from one of the piles. The last player to take their turn (leaving both piles empty) wins.
You start the game. So it would not be unfair, it is guaranteed that it is possible for you to win. Write a program than beats Renzo 100% of the time.
Input
In the first line, two integers, x and y, the size of the piles, such that 0 ≤ x, y ≤ 1e4. It is guaranteed that you can win the game.
Interaction
In your turn, print two integers, i and x, where i is the number of the pile from which you will remove the coins (), and x is the number of coins you will remove (x ≥ 1, such that i has at least x coins).
In Renzo's turn, read two integers, in the same format as in your turn.
Example
Input
2 1
1 1
Output
1 1
2 1
Note
Of course we do not do an initiation challenge like this :P
In the example, we have a pile with 2 coins and another with 1. You remove 1 coin from the first pile, and now no matter what coin Renzo removes, you can remove the other and win.
Remember, after printing your play, flush the output, like: fflush(stdout); in C, cout.flush(); in C++, or sys.stdout.flush() in Python.
Problem solving:
据说是nim博弈，毫无思路。
以后再补吧。。。
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
MaratonIME plays Chess
Description:
This problem is boring as duck.
Kawakami, Marcos
Our dear Nathan, when a little child, used to like chess a lot, but this was a long time ago. One of these days he was challenged by @luisgust to a chess match and, as he is a guy that likes hard challenges, he accepted it. The problem is that Nathan keeps forgetting the rules of the game, so he asked you to help him determine if a given opponent's piece can be captured in one move.
Chess, in MaratonIME, is represented as a matrix of characters. Instead of playing with black and white pieces, they play with uppercase and lowercase letters. Nathan has chosen to play with the lowercase letters.
Besides that, as usual, the positions on the matrix are given in the following coordinates system: Each position is a pair with a character between a and h (inclusive), representing the column, and an integer between 1 and 8 (inclusive), representing the row. For exemple, the position d2 refers to the fourth column (from left to right) and second row (from bottom to top), and the position f6 refers to the sixth column and sixth row. Lowercase letters start on the bottom of the grid, on lines 1 and 2.
Here position A is adjacent position B if A shares a vertex with B, that is, if the distance between their rows is at most one and the distance between their columns is at most one. For example, the position c4 is adjacent to 8 positions: b3, b4, b5, c3, c5, d3, d4 and d5.
They decided to play a simplified version of chess. To help you, they gave you the following manual on how to play it:
The pawn, represented by p or P, can capture pieces that share a diagonal and is in front of it, that is, the lowercase pawn on c4 can capture pieces at b5 or d5.
The knight, represented by c or C, makes L-shaped moves in any of the 8 possible directions, that is, it moves two positions in any direction and after that one position in a direction that is perpenticular to the first one. A knight on c4 can capture, in one move, pieces on positions a3, a5, b2, b6, d2, d6, e3 and e5.
The rook, represented by t or T, can capture pieces that are on the same row or the same column as it, as long as no other piece lies between them. For example, a rook on c4 can capture any piece on column c or row 4, as long as there is no other piece in between. If the rook is on c4 and there is another piece on c6, the rook can't capture pieces on c7 and c8.
The bishop, represented by b or B, can capture any piece on one of its diagonals as long as there are no piece between them (diagonaly). For example, the bishop on c4 can capture a piece on f7 as long as there are no piece on d5 and e6.
The queen, represented by r or R, can capture any piece that lies on the same row, column or diagonal, given there are no pieces in between, as if it were a bishop and a rook at the same time.
The king, represented by k or K, can capture any piece that is adjacent to it.
The character . represents an empty position.
Given a matrix representing a chess board and an opponent's piece, your program needs to determine whether you can capture it with one of your pieces. It is guaranteed that each player has at most two bishops, two rooks, two knights, eight pawns, one king and one queen.
Input
The input begins with 8 lines with 8 characters each, representing the chess board. The first line contains the characters on the positions a8, b8, ... , h8. The second line contains the characters on positions a7, b7, ... , h7, and so on. After that follows a line containing the position of the opponent's piece you wish to capture.
Output
Print a single line containing the word Sim if it is possible to capture the piece or Nao otherwise.
Examples
Input
TCBRKBCT
PPPPPPPP
........
........
........
........
pppppppp
tcbrkbct
d8
Output
Nao
Input
........
........
........
..R.....
...p....
........
........
........
c5
Output
Sim
Problem solving:
毫无思路题。
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
MaratonIME rides the university bus
Description:
If we organize it correctly, ...
Unknown
To make the trip to the subway less boring and tiring, the SPSU, Sao Paulo State University, tried one of its most famous inventions: buses with Infinite Inner Length! In such a modern engineering wonder, there's always a couple of empty seats for the students to sit and chat during the trip.
MaratonIME crew is very popular, so popular that they have friends at every SPSU institute. Like everyone else from this university, they need to take the bus after a long day learning how to fix the Wi-Fi network. Because they don't practice sports like rowing, every SPSU student sits right after entering the bus, making pairs whenever possible. Thinking about that, Gi, an ICPC expert, comes with a problem to think on the way to the subway: given a number n which indicates the number of institutes at SPSU and n integers ai representing the amount of people waiting for the bus at the institute i, Gi wants to know for m pairs lj, rj (lj ≤ rj) if all the people waiting for the bus at any point between lj e rj (inclusive) took an empty bus, they could sit together in pairs (nobody would sit alone).
Input
The input consist in one line with two integers n and m, the number of institutes and the number of Gi's questions. In the second line there are n integers ai, the number of people waiting for the bus at the ith institute. Then follows m lines with two integers each, li and ri, the first and last institute of Gi's question.
1 ≤ n, m ≤ 1e5
0 ≤ ai ≤ 1e5
1 ≤ li ≤ ri ≤ n
Output
Output "Sim" if it is possible to organize all the pairs in a way nobody sits alone or "Nao" otherwise.
Example
Input
5 2
1 4 10 3 2
3 5
2 3
Output
Nao
Sim
Note
In the first sample we have 5 institutes with 1, 4, 10, 3 and 2 students. Gi asks if it is possible to form only couples if the ones between the 3rd and the 5th institutes takes an empty bus and the ones between the 2nd and the 3rd. For the first we have 15 so we can't and for the second we have 14 so we can.
Problem solving:
这道题的意思就是给你一组数，问你第i个数到第j个数的和的奇偶。
不知道直接查询会不会超时，但是我用了前缀和数组。也算是个简单题吧。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[213344],b[213344];
int main()
{
ll n,m,x,y;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
b[0]=a[0];
for(int i=1;i<n;i++) b[i]=b[i-1]+a[i];
while(m--)
{
cin>>x>>y;
x--,y--;
if((b[y]-b[x-1])%2!=0) puts("Nao");
else puts("Sim");
}
}MaratonIME attends the lecture (or not)
Description:
Has the prof taken attendance yet?
Student, IME's
In MaratonIME, as many other groups, some students want to attend lectures just enough to not be flunked by frequency (as we know, in USP, University of Sao Paulo, it is necessary to have 70 percent frequency), however some others are dedicated and try to accomplish the most frequency percent possible, going to school even when they are ill or tired. Curiously, there is not any other kind of students in MaratonIME.
Wood, an old MaratonIME's member, needs help. He is taking the course MAC4815162342, and attended k of m lectures that were given. Consider that MAC4815162342 has n lectures in total per semester. He ask you to help finding the best way to accomplish his objectives, but, as you are new in MaratonIME, you don't know the kind of student that he is. Embarassed to ask more, you decide to solve two problems, so there is not way to go wrong.
Input
The input consists of a just one line. In this line, you are given three integers n, m and k, with 1 ≤ n ≤ 1e7 and 0 ≤ k ≤ m ≤ n.
n is the number of lectures of MAC4815162342 per semester, m is the quantity of lectures that were given and k is the number of lectures attended by Wood.
Output
In the first line, print the minimum number of lectures that Wood needs to attend to accomplish at least 70% frequency, or - 1 if it is impossible to accomplish 70% frequency.
In the second line, print the maximum frequency percent that Wood can accomplish, if he goes to all of the lectures from the next lecture. This value has to be rounded down to the closest integer. Don't print '%'.
Examples
Input
10 5 2
Output
5
70
Input
11 2 1
Output
7
90
Note
On the second example, the maximum percentage that Wood can get is 90.9090.
Problem solving:
这道题意思就是有一门课本学期只上n节，现在已经上了m节，这个同学m节里面只去了k节，问你他还能不能达到70%的出勤率，如果不能输出-1，如果可以输出他最少再去上几次课就可以达到70%，然后输出他能达到的最大的出勤率。
题挺简单的，最大出勤率也好算，就是(n-m+k)/n
还有个坑点就是你需要先判断一下他现在的出勤率是不是已经够了。这个也可以不处理，就像我用的那个max一样也行。
但是这道题我WA了n发，因为这个题它对精度要求比(ka)较(jing)高(du)。
这里涉及到高精度，我就想到用python写了，其实c++一样的
Code:
a,b,c=input().split()
a=eval(a)
b=eval(b)
c=eval(c)
x=a-b
y=int((a*70+99)/100) #精度问题
z=y-c
if x<z:
print("-1")
else:
print(max(0,int(y)-c)) #处理如果当前出勤率已经到了%70的情况
ans=int((x+c)*100/a)
print(ans) MaratonIME goes rowing
Description:
Speed down, Colombooo!!!
rowing coach, Gabi
As common sense tells us, competitive programmers excel at rowing. The olympic lane is a wonderful place to row, run and work out. What few take their time to appreciate are the capybaras that inhabit the region. Capybaras are fascinating animals! Aside from their beauty, they possess many interesting behaviours. Did you know that capybaras can live in packs as big as 100 individuals?
In a pleasant sunny morning, Yan was running, as usual. Watching the capybaras, he noticed that they would line up to sunbath. Each capybara was paired with another one, and only another one. Two capybaras can be paired if and only if both see each other. A capybara sees everything in the direction it is looking.
Curious, Yan decided to represent the capybaras by the letters A and B, where A indicates that the capybara is looking right, and B indicates that the capybara is looking left.
For example, the sequence AABABB accurately represents capybaras sunbathing, because it is possible to pair every capybara according to the rules above. Yan was so fascinate by this that he slipped and felt into the water, messing his representations. He was able to recover some, but now they are all messed up with each other. Can you help him and find out if a given sequence represent capybaras sunbathing?
Input
Every instance contains a sequence S of characters, composed only of 'A' and 'B' – Yan's representation. You may assume that 1 ≤ |S| ≤ 105.
Output
The output should contain a single line. Print "Sim" if the sequence represents capybaras sunbathing, or "Nao" otherwise.
Example
Input
AABABB
Output
Sim
Problem solving:
这道题的意思就是一个a能和一个b能配对。但必须是a在左面b在右面，给你一串字符串问你可不可以全部配对。
这道题跟括号匹配很像，用一个栈实现就行了。
然后，，我比赛时候没想到，也不知道咋想到一个很zz的贪心算法，现在仔细一想才发现是错的，关键是。。还过了。。。数据水了吧。(我打败了它，滑稽
Code:
这是我的水过的代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int x=0,y=0;
cin>>s;
if(s[0]=='B'||s[s.size()-1]=='A')
puts("Nao");
else
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='A')x++;
else y++;
}
if(x!=y) puts("Nao");
else puts("Sim");
}
return 0;
}这是一血大佬cloudy_happy的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
int main()
{
ios::sync_with_stdio(false);
string s;
cin>>s;
stack<int> st;
for (int i = 0;i < s.size();i ++)
{
if (s[i] == 'A')
st.push(1);
else
{
if (!st.empty()) st.pop();
else
{
cout<<"Nao"<<'\n';
return 0;
}
}
}
if (st.empty()) cout<<"Sim"<<'\n';
else cout<<"Nao"<<'\n';
return 0;
}MaratonIME goes to the movies
Description:
Better than "Fifth Wave"
in the World, Everyone
Believe it if you can, studies show that we in MaratonIME live not only out of competitive programming.
In a saturday, after taking part in a virtual contest, our heroes decide to enjoy the afternoon watching a movie session. But they didn't choose any movie, but an n-D movie, that is, a movie with n dimensions.
During a chase scene, the main character jumps over a chain in the parking lot. Of course this was done in a very athletic way, and for some reason that drove Yan, one of the competitive programmers, mad.
"Hollywood makes everything seem easy, but jumping over a chain is really hard!"
The rest of the crowd, after the movie, argued with Yan that the actor surely jumped over the chain, but Yan disagreed, saying that it was done by some camera trick or by special effects.
To prove his point, he bought another ticket for the movie and this time he took highly precise measuring instruments to the session. Yan's plan was to show that the distance from the actor's foot to the floor was smaller than the distance from the chain to the floor, and that would prove that the actor didn't actually jump over the chain.
But math in n dimensions is hard. Everyone knows that distance in the 2D plane between two points (x0, y0) and (x1, y1) is given by the formula
Most people also know that distance between two points (x0, y0, z0) e (x1, y1, z1) in 3D space is given by the formula
Both formulas describe the euclidean distance, in the 2 and 3 dimensional case. Your task is, given three points in an n dimensional space, tell if the the closest ones are the foot and the floor or the chain and the flooor, according to euclidean distance.
Input
The input begins with an integer n, followed by three lines, each with the representation of a point in an n-dimensional space.
Dimensions confuse us, humans, so you can assume that 1 ≤ n ≤ 1e5.
The second line represents the coordinates of the floor, and contains n integers a1, ..., an.
The third line represents the coordinates of the foot of the main character, and contains n integers b1, ..., bn.
The fourth line represents the coordinates of the chain, and contains n integers c1, ..., cn.
The movie theather is not arbitrarily large, so you can assume that the absolute value of these coordinates are not greater than 1e4.
Output
Print who wins the argument, that is, print "Yan" if the distance between the floor and the foot is not greater than the distance between the floor and the chain, or "MaratonIME" otherwise.
Examples
Input
2
0 0
1 1
2 2
Output
Yan
Input
4
0 0 0 0
2 2 2 2
1 1 1 1
Output
MaratonIME
Problem solving:
这道题如果看懂了也不难。就是问你两个点的距离的大小，然后再比较一下，只不过是n维的，跟二维三维的公式一样，往里面套就行了。一个for循环，然后最后在开根号。
输入三行对应着三个点，比较的是第二个和第三个点相对于第一个点的距离的大小。
Code:
#include<bits/stdc++.h>
using namespace std;
const int sijia = 211314;
typedef long long ll;
ll f[sijia],m[sijia],gj[sijia];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>f[i];
for(int i=0;i<n;i++) cin>>m[i];
for(int i=0;i<n;i++) cin>>gj[i];
double x,y;
x=y=0;
for(int i=0;i<n;i++)
{
x+=(m[i]-f[i])*(m[i]-f[i]);
y+=(gj[i]-f[i])*(gj[i]-f[i]);
}
if(x<=y)
puts("Yan");
else puts("MaratonIME");
}MaratonIME goes to a japanese restaurant
Description:
Matsu?
Member, MaratonIME's
Nathan and Yan are very dedicated programmers. They apply their knowledge in algorithms in problems beyond the programming competitions themselves, optimizing even the most trivial every day things.
Some question if they aren't just crazy, and if it wouldn't be better to just do what has to be done.
Anyhow, eventually some conflicts happen when their approaches differ about what has to be done. That always happens when they decide to go to japanese restaurants.
Everybody knows that the objective in an all-you-can eat it to try to eat many distinct kinds of food. Nathan and Yan differ in opinions on how to achieve that. Both competitors, when sitting to eat an asian delicacy, eat until nothing is left on their plates.
The difference is that Yan, respecting the wisdom of the nipponic masters, eats in the order the food arrives, whereas Nathan claims that the food is better the latter it arrives, to spare the most expensive ingredients, and so asks that his plates come in inverted order.
Given the default order the dishes will arrive and the time Nathan and Yan will stay at the restaurant, determine who is going to eat the most different kinds of food, or if both ate the same number of different kinds of food, given that Yan eats the food in order and Nathan in inverted order.
Input
The first line of input has two integers: 0 < n ≤ 1e5, how many plates will be served and 0 < T ≤ 1e6, how long (in minutes) Yan and Nathan will stay at the restaurant.
In the following line, n integers 0 < ti ≤ 1e3, ti is how long it takes to eat the i-th dish (in minutes).
The restaurants are very well administrated, so you can assume that when one of the competitors finishes his dish, the following dish is already on the table.
Output
If Yan is going to taste more dishes than Nathan, print "Yan". If Nathan is going to taste more dishes than Yan, print "Nathan". Otherwise, if we have a tie, print "Empate".
Examples
Input
10 45
1 2 3 4 5 6 7 8 9 10
Output
Yan
Input
10 45
10 2 3 4 5 6 7 8 9 1
Output
Nathan
Problem solving:
这道题的意思就是给你一个序列代表每个菜吃完需要用的时间，然后给你一个整数，代表你总共可以用的时间。现在有两个顺序，一个是正序一个是倒序，问你在那种情况下，可以吃到菜的种类比较多。并且每个菜都必须吃完。
所以用两次for循环遍历直到给的整数不大于当前菜所需要的时间退出循环。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[211314];
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=0;i<n;i++)
cin>>a[i];
ll x,y,s1=0,s2=0;
x=m,y=m;
for(ll i=0;i<n;i++)
{
if(x>=a[i])
{
x-=a[i];
s1++;
}
else break;
}
for(ll i=n-1;i>=0;i--)
{
if(y>=a[i])
{
y-=a[i];
s2++;
}
else break;
}
if(s1>s2) puts("Yan");
else if(s1<s2) puts("Nathan");
else puts("Empate");
}MaratonIME goes to the japanese restaurant (again)
Description:
Nakato?
from MaratonIME, Members
After a long day of hard training, MaratonIME (マラトニメ) members decided to go to a Japanese restaurant. Yeah, we love Japanese food.
After a lot of sushi boats, when everyone was more than satisfied, they asked the sushi-man Sussushi (ススシ) for the last boat. Sussushi felt challenged and answered:
– You want one more boat? You shall have one more boat...
The sushi boat that he brought was the biggest that any contestant had ever seen. Some contestants even dare saying that was the biggest sushi boat that ever existed, exceeding the previous limit of 105 sushis made by the suhiwoman Gioza (ジョザ) in 742, in a festival for the king that year, Carlos-sama (カーロス様).
Besides that the contestants accepted the challenge, and together they managed to eat all the sushis. After that, the contestants we're so full that they couldn't touch each other. They couldn't even think about programming problems. Help them find what pair of friends are touching themselves, so they can move away from each other.
The contestant are represented as circles in plane, and two contestants touch each other if the circles touch each other. It's guaranteed that the intersection area of any two circles is null.
Input
In the first line there is a single integer, n indicating the number of contestants (2 ≤ n ≤ 1000).
Each one of the next n lines has 3 integers xi, yi e ri, the (i + 1)-th line describes the ith contestant. (xi, yi) are the coordinates of the center of the circle, and ri is the radius. ( - 1e4 ≤ xi, yi ≤ 1e4, 1 ≤ ri ≤ 2·1e4)
It is guaranteed that the intersection area of any two circles is null.
Output
For each pair of circles that touch each other, print in one line the indexes of these circles. The collisions can be printed in any order, the indexes of both circles can also be printed in any order.
Don't print the collisions more than once, that means, if i intersects with j, print i j or j i, but not both.
Example
Input
3
0 0 2
5 0 3
10 10 1
Output
1 2
Problem solving:
这道题的意思就是给你几个圆的圆心以及半径，问你哪几个圆是相交的，有的话输出。
输入的时候我用了结构体直接存的，然后两个for进行查找，因为n最大时1000，所以不会超时。
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,r;
}a[1314];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].r;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(sqrt((a[j].y-a[i].y)*(a[j].y-a[i].y)+(a[j].x-a[i].x)*(a[j].x-a[i].x))<=(a[i].r+a[j].r))
cout<<i <<" "<<j<<endl;
}
}
return 0;
}MaratonIME goes to the karaoke
Description:
♬ Hit me, lock me up, do anything with me, ... ♬
and Marrone, Bruno
After thousands of years repeating the title of this problem statement, always with an excited and inviting tone, Nathan finally persuaded his colleagues to go to the karaoke. He is feeling radiant with this achievement.
But there is a problem. After so much time trying to make his friends go to the karaoke, Nathan is afraid of embarrassing himself when he goes to sing the following classics of Brazilian music:
Waitress – Reginaldo Rossi
Blue Nightclub – Joaquim and Manuel
Paper Heart – Sérgio Kings
Love Bubble – Fagner
You did not teach me to forget – Fernando Mendes
To avoid the humiliation, and to not discourage his fellows in future hang outs at the karaoke, Nathan decided to print all the song’s ciphers that are available in the karaoke, to check while he sings. However, this resulted in a colossal amount of paper, that he is not able to carry.
But the perseverance and ingenuity of an envious programmer is not something you should underestimate.
Nathan realized that, after all, there were only 7 musical notes. The specialists in this matter used to represent this notes with the letters A, B, C, D, E, F and G. Even more, it’s common that the same note appears several times in sequence. He decided then, to compress the songs, changing every occurrence of repeated notes with the note followed by how many times it occurs.
For instance, given the sequence
[(A,A,A,B,B,B,C,G,G,G,G,G,G,G,G,G,G,G)] the compressed version is [A3B3C1G11]
Unfortunately, Nathan also needs to pack his floral suit and to comb his beard – two homeric jobs – and he is out of time to compress the notes. Help him to not embarrass himself by writing a program that can solve this task.
Input
Each input consist of a single line, a sequence of caracteres S such as |S| ≤ 105, formed only by the letters A, B, C, D, E, F and G.
Output
For each input, print in a single line, such as each sequence of similar notes are replaced by the note that occurs and how many times it occurs, as showed in the example.
Examples
Input
ABBGA
Output
A1B2G1A1
Input
AAABBBCGGGGGGGGGGG
Output
A3B3C1G11
Problem solving:
这道题我没看题，直接看的样例哈哈。
这道题是给你一个字符串问你这个字符串中连续出现的字符以及个数。我用结构体存了一下，然后输出。
注意：同一个字母如果没有连着出现是不能算在一起的，这个看样例应该就可以看出来。
Code:
#include<cstdio>
#include<string>
#include<iostream>
const int xiaozhu=1e5+10;
struct node{
char s;
int ti;
}sijia[xiaozhu];
using namespace std;
int main()
{
string s;
cin>>s;
sijia[0].s=s[0];sijia[0].ti=1;
int pos=0;
for(int i=1;i<s.size();i++)
{
if(s[i]==sijia[pos].s)
{
sijia[pos].ti++;
}
else
{
pos++;
sijia[pos].s=s[i];
sijia[pos].ti=1;
}
}
for(int i=0;i<=pos;i++)
{
cout<<sijia[i].s<<sijia[i].ti;
}
return 0;
}MaratonIME goes karting
Description:
Yan, it's red!!!
desperate, Passengers
Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME's coach, suggested they should do something fun to relax. After a big discussion, they decided to go karting. Looking for a place that was viable to all students, they found Kartforces, a kart track near Cidade Universitária. However, the track was too small and only fitted two racers by race. As passionate competitive programmers, they organised a fair tournament where everyone raced against everyone, two by two, only once. In each race, the winner got one point on the scoreboard. Draws were allowed and no one scored in this case. The winner was the biggest scorer. There were N competitive programmers present and:
Each competitive programmer had a skill hi.
If hi > hj where 1 ≤ i, j ≤ N and i ≠ j, then the competitive programmer i won the race against j.
You had access to the skills of all competitive programmers and now asks who was the champion.
Input
The first line consists on a single integer N, the number of competitive programmers. The second line contains N integers hi, the skill of the i - th competitive programmer.
1 ≤ N ≤ 1e5
0 ≤ hi ≤ 1e9
Output
The output consists in a single integer i, the champion competitive programmer. If it's not possible to determine the champion, print - 1.
Example
Input
3
2 4 6
Output
3
Problem solving:
这道题的题意我没看很懂，但是就是给你一组数据问是否能确定一个冠军出来。
什么情况下才不会产生冠军呢？就是如果有两个人得分相等的时候就不会产生冠军。而且题目说的是相邻两个人的比赛，所以只需要一个for循环比较一下看相邻的有没有相等的，如果有直接输出-1，没有的话直接输出最大值即可。
Code:
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{
ll x,id;
}a[100005];
bool cmp(node a,node b)
{
return a.x>b.x;
}
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].x);
a[i].id=i;
}
for(int i=1;i<n;i++)
{
if(a[i].x==a[i+1].x)
{
puts("-1");
return 0;
}
}
sort(a+1,a+n+1,cmp);
printf("%lld\n",a[1].id);
}MaratonIME returns home
Description:
♬ Renzo, they're calling. Renzo, pick up the phone ♬
Ringtones, Top
Popular among the most traditional coders, the Summer Camp is famous for its fancy parties. After each party all attendees must return to their homes, but the way back home is not always easy: mildly drunk coders walk weird and often find or lose money along the way. However, MaratonIME always has a sober member in the group, who assures no one will lose money, except when they are robbed.
On its way back MaratonIME knows that they can call their coach, Renzo, who will pick them up immediately. Instead of doing that right after the party, they want to know what is the maximum amount of money they can carry back to their homes.
Your task is to write a program that solves this problem. Consider the following facts:
The city map can be seen as an N by M grid;
Members of MaratonIME are initially at the top left corner, and start walking right, carrying no money;
Whenever they reach the end of a row, they walk to the row below and start walking in the opposite direction (if they were walking right, they walk left the next row, and vice-versa);
They cannot go past the last row;
Whenever they meet a burglar, they lose all their money;
They can call Renzo at anytime, and he will pick them up instantly.
Input
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 103), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either:
,_meaning there is nothing at this cell of the grid;
, '.' meaning there is a coin worth 1 unit of money at this cell;
, 'L' meaning there is a burglar at that cell.
Output
The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.
Example
Input
3 3 __. _._ L._
Output
2
Note
In the example above, MaratonIME follows the following path: (1, 1) (1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.
Problem solving:
这道题就是给你一个图，问你在走的过程中能够拿到的最多的金币数。但是图里会有强盗，用L表示，如果你经过强盗，那么金币清零。但是因为方向是固定的，所以可以直接特殊的遍历一下图就行，或者可以像我一样构建一个新的字符串。
然后遍历整个字符串取每个状态下金币数的最大值就是答案。
Code:
#include<bits/stdc++.h>
using namespace std;
const int xiao =1314;
const int zhu =1314;
char sijia[xiao][zhu];
int n,m,ans,flag;
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",sijia[i]);
string s;
for(int i=0;i<n;i++)
{
if(i%2==0)
{
for(int j=0;j<m;j++)
s+=sijia[i][j];
}
else
{
for(int j=m-1;j>=0;j--)
s+=sijia[i][j];
}
}
int now=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='.') now++;
if(s[i]=='L') now=0;
ans=max(ans,now);
}
cout<<ans<<endl;
}