Gym 100917L Liesbeth and the String 规律&&胡搞
2024-08-24 07:28:13
题目:
Description
standard input/output
Statements
Statements
Little Liesbeth likes to play with strings. Initially she got a string of length n, consisting of letters 'a' only.
Then Liesbeth performs next operations with the string:
- If the first letter of the string is 'a', then she adds to the end of the string "bc", and after that removes first two letters of the string.
- If the first letter of the string is 'b', then she adds to the end of the string 'a', and after that removes first two letters of the string.
- If the first letter of the string is 'c', then she adds to the end of the string 'aaa" and after that removes first two letters of the string.
Liesbeth stops when she has the string of length 1. For example, if n = 4, she needs 6 operations :
Liesbeth found that for some n number of operations is too big, and its hard to understand if the process is finite. So she asked You to write the program to help her.
Input
First line of the input contains one integer n (2 ≤ n ≤ 106) — length of the initial string.
Output
Print one integer — number of operations needed to obtain string of length 1. If process is infinite, print - 1 insteaSample Input
Input
4
Output
6
Input
3
Output
24 题目大意:给出一个字符串(只含a)的初始长度,做一下变换,求得到字符串长度为1时的步骤数,变换如下:
1.字符串首字母为a时 字符串末尾加bc 并删除前2个字符
2.字符串首字母为b时 字符串末尾加a 并删除前2个字符
3.字符串首字母为c时 字符串末尾加aaa 并删除前2个字符 题目思路:找规律,
当字符串长度为偶数时:经过n/2步变为只含bc长度为n的形式,再经过n/2步变成只含a长度为n/2的形式
当字符串长度为奇数时:经过(n+1)/2 步变为含c+k(bc)形式长度为n的串,在经过(n+1)/2步变成只含a长度为n/2*3+2的串
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#define INF 0x3f3f3f3f
#define MAX 10000005
#define Temp 1000000000 using namespace std; int main()
{
long long n,sum;
while(scanf("%lld",&n)!=EOF)
{
sum=;
while(n>)
{
if(n%==)
{
while(n> && n%==)
{
sum+=n;
n/=;
}
} else
{
while(n% && n>)
{
sum+=(n/+);
sum+=(n/+);
n=n/*+;
}
}
}
printf("%lld\n",sum);
}
return ;
}
最新文章
- git conifg
- What is the most common software of data mining? (整理中)
- Asp.Net Web API 2第十六课——Parameter Binding in ASP.NET Web API(参数绑定)
- WPF总结
- EasyUI——弹窗展示数据代码
- C++运行字符编码于MSVC和GCC之间的区别
- ELK学习记录一 :初识ELK
- 好用的有多种样式的搜索界面创建UISearchBar
- mysql按条件 导出sql
- call、apply、bind
- python中关于turtle库的学习笔记
- Golang入门教程(十一)beego 框架之RESTful Controller 路由
- Android 百度sdk5.0定位
- Python3基础 response.read 输出网页的源代码
- 每天CSS学习之text-overflow
- java之常量折叠
- Memcached下载安装、NET对Memcached进行CRUD操作(2)
- redis进程守护脚本
- Centos上把新安装的程序添加到系统环境变量的两种方法
- Windows下如何正确下载并安装可视化的Redis数据库管理工具(redis-desktop-manager)(图文详解)