input
standard input
output
standard output
A continued fraction is an expression of the form:
a0+1a1+1a2+1⋱+1ana0+1a1+1a2+1⋱+1an
where a0,a1,…,ana0,a1,…,an are nonnegative integers.
Given a fraction xyxy(x,yx,y are positive integers), please expand it into a continued fraction.
Input
The first line contains an integer TT (1≤T≤1031≤T≤103), denoting the number of test cases.
The only line of each test case contains two integers x,yx,y (1≤x,y≤1091≤x,y≤109), denoting a fraction xyxy. It's guaranteed that gcd(x,y)=1gcd(x,y)=1.
Output
For each test case, output one line: first an integer nn denoting the height of the continued fraction, then n+1n+1 integers denoting a0,…,ana0,…,an. Your solution should gurarantee that 0≤n≤1000≤n≤100, 0≤ai≤1090≤ai≤109.
If there are multiple valid solutions, you only need to output one of them.
Example
input
Copy
2 105 38 1 114
output
Copy
4 2 1 3 4 2 1 0 114
Note
For the convenience of you, we give explanation of sample:
10538=2+11+13+14+1210538=2+11+13+14+12
1114=0+11141114=0+1114
代码实现：文章来源地址https://www.toymoban.com/news/detail-660605.html
int x,y;
int main()
{
int t;
cin>>t;
while(t--)
{
int a[N];
cin>>x>>y;
int cnt=0;
if(x==1||y==1)
{
if(x==1)
{
cout<<"1 0 "<<y<<"\n";
}
if(y==1)
cout<<"1 0 "<<x<<"\n";
continue;
}
while(x>1&&y>1)
{
a[cnt++]=x/y;
x=x%y;
swap(x,y);
}
if(x==1)
a[cnt]=y;
if(y==1)
a[cnt]=x;
cout<<cnt<<" ";
for(int i=0;i<=cnt;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
}L. It Rains Again
Suppose that in a Cartesian coordinate system on an infinite plane, the x-axis represents the ground and there are n rainscreens (We don't consider their thickness.) in the sky.
Every rainscreen can be described as a segment which starts from the (x1,y1)(x1,y1) and ends at (x2,y2)(x2,y2). Now if it starts to rain from the infinite high sky, I want you to tell me how many units of the x-axis will not get rained on.
To simplify the problem,the rain can only move vertically whenever it falls.
Note that two rainscreens can overlap and intersect with each other, and there is no rainscreen which is placed vertically.
Input
The first line contains one positive integer n(1≤n≤100000)n(1≤n≤100000).
Each of the next n lines contains four positive integers x1,y1,x2,y2(1≤x1<x2≤100000,1≤y1,y2≤100000)x1,y1,x2,y2(1≤x1<x2≤100000,1≤y1,y2≤100000), representing a rainscreen which starts from the (x1,y1)(x1,y1) and ends at (x2,y2)(x2,y2).
Output
The only one integer - the number of units of the x-axis which will not get rained on.
Example
input
Copy
5 1 2 2 1 1 1 2 2 3 3 4 3 5 1 6 3 6 3 7 2
output
Copy
4
算法思想：
使用区间和算法的模板求出相对应的被覆盖的区间吗，然后通过总的区间数减去所覆盖的
的区间数即可，然后注意最后需要加上原来的剩余哪一个区间加一即可
代码实现；
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10;
int n;
vector<PII> segs;
void merge(vector<PII>&segs)
{
vector<PII>res;
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;
for(auto seg:segs)
if(ed<seg.first)
{
if(st!=-2e9)
res.push_back({st,ed});
st=seg.first,ed=seg.second;
}
else
ed=max(ed,seg.second);
if(st!=-2e9)
res.push_back({st,ed});
segs=res;
}
int main()
{
cin>>n;
int minx=0;
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
segs.push_back({x1,x2});
minx=max(minx,x2);
}
//cout<<minx<<"\n";
merge(segs);
cout<<(minx-segs.size())<<endl;
return 0;
}K
Gather sand to form a tower is a Chinese idiom, whose Pinyin is ju` sha¯ che´ng taˇju` sha¯ che´ng taˇ. It means to pile sand into a pagoda, referring that a little makes a lot. From the fahua Sutra - convenience products.
Suppose the tower has NN floors. There are i×ii×i rooms on the ithith floor. Each room can accommodate MM people. How many people can the NN floor tower accommodate?
Input
The first line is a positive integer T (1≤T≤100)T (1≤T≤100), indicating that there are TT test data.
Next, there are TT lines. Each line has two positive integers NN and M (1≤N,M≤100)M (1≤N,M≤100), indicating the number of floors of the tower and the number of people that can be accommodated in each room in a test data.
Output
Each test data outputs a line containing one positive integer, that is, the total number of people that can be accommodated in the NN floor tower.
Example
input
Copy
2 2 2 3 3
output
Copy
10 42
算法思想：只需要数组的基本知识即可进行相对应得代码 叠加求和 即可
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int t;
int sum;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
sum=0;
for(int i=1;i<=n;i++)
{
sum+=i*i*m;
}
cout<<sum<<"\n";
}
}H. Hearthstone So Easy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Hearthstone is a turn-based card game. The game flow of each round is: Player 1 draws card ⇒⇒player 1 plays cards ⇒⇒player 2 draws card ⇒⇒player 2 plays cards.
We simplify the game logic as follows:
- During each player's draw stage, the player attempts to draw a card from his or her deck.
- During each player's playing stage, the player can choose:
- to increase his/her health by kk points. Note that there is no upper limit on health.
- to reduce the opponent's health by kk points.
When there are no cards in the player's card deck, the player will enter a state of fatigue. At this time, the player will increase his/her fatigue value by one every times he/she tries to draw a card, and then deduct the amount of health by the fatigue value. The fatigue value of each player is initially 00 points.
pllj and freesin like playing hearthstone very much. In a certain game, both players have no cards in their decks, and both the fatigue points are 00 points, and the health points are both nn points. When a player's health is less than or equal to 00, the player immediately loses the game.
At this time, it's pllj's turn to draw card. Both players are very smart, so they play the game optimally. Who will be the winner? Please output his name.
Input
The first line contains a single integer tt (1≤t≤1051≤t≤105), which represents the number of data cases.
Each group of data is a row of two positive integers n,kn,k separated by spaces (1≤n,k≤1091≤n,k≤109), of which meaning is described before.
Output
For each case of data, output a line of string pllj or freesin to indicate the winner.
Example
input
Copy
2 10 9 5 3
output
Copy
pllj freesin
Note
For the first data case:
- pllj's draw stage: pllj tries to draw cards from a empty deck. His fatigue value increases by 11 to become 11, and then pllj's health deducts by one point, leaving 99 health points.
- pllj's playing stage: pllj causes 99 points of damage to freesin. After this time, freesin has 11 point of life left.
- freesin's draw stage: freesin tries to draw cards from a empty deck. His fatigue value increases by 11 to become 11, and then freesin's health deducts by one point, leaving 00 points. At this time, freesin loses the game.
算法实现：
简单的博弈题，只需要考虑最后一个之前即可文章来源：https://www.toymoban.com/news/detail-660605.html
代码实现：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,k;
cin>>n>>k;
if(n==1)
cout<<"freesin"<<"\n";
else if(n<=k+1)
cout<<"pllj"<<"\n";
else
cout<<"freesin"<<"\n";
}
}到了这里，关于ACM训练的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
