【codeforces 527A】Playing with Paper
with Codeforces Paper
2023-09-14 09:03:47 时间
【题目链接】:http://codeforces.com/contest/527/problem/A
【题意】
让你每次从一个长方形里面截出一个边长为长方形的较短边的正方形;
然后留下的部分重复上述步骤;
直到剩下的部分为正方形为止;
问你一共截出了多少个正方形
【题解】
写个递归求解就好;
每次短边的边长不变;
然后答案递增长边长度/短边长度
长边的边长变为长边%短边->为0的话就改为短边长度,下一次递归结束就好;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 110;
LL a, b,ans = 0;
void dfs(LL a, LL b)
{
//a>b
if (a == b)
{
ans++;
return;
}
LL t = a / b;
a = a%b;
if (a == 0)
{
a = b;
t--;
}
ans += t;
dfs(b, a);
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
rel(a), rel(b);
dfs(max(a,b),min(a, b));
printf("%lld\n", ans);
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
相关文章
- Robust Online Visual Tracking with a Single Convolutional Neural Network
- [Node.js] Migration with Umzug
- [Javascript] Remove an Event Listener with removeEventListener
- [React] Use react styled system with styled components
- [Compose] 19. Leapfrogging types with Traversable
- [Python] Problem with Default Arguments
- [React] Create component variations in React with styled-components and "extend"
- [Most.js] Create Streams From Single Values With Most.js
- [Redux] Colocating Selectors with Reducers
- [RxJS] Reactive Programming - Using cached network data with RxJS -- withLatestFrom()
- EasyPlayer RTSP Windows(with ActiveX/OCX插件)播放器支持H.265播放与抓图功能
- [Cloud DA] Serverless Framework with AWS
- [Mise] Update a count state value with the x-on event listener directive in Alpine JS
- [Javascirpt] Developer-friendly Flow Charts with flowchart.js
- [Javascript] Iterate Over Items with JavaScript's for-of Loop
- [Webpack 2] Optimize React size and performance with Webpack production plugins
- [Grunt] Cleaning your build folder with grunt-contrib-clean
- 【codeforces 128C】Games with Rectangle
- 【codeforces 757E】Bash Plays with Functions