CodeForces 173A Rock-Paper-Scissors 数学

时间:2022-09-17 23:13:47

Rock-Paper-Scissors

题目连接:

http://codeforces.com/problemset/problem/173/A

Description

Nikephoros and Polycarpus play rock-paper-scissors. The loser gets pinched (not too severely!).

Let us remind you the rules of this game. Rock-paper-scissors is played by two players. In each round the players choose one of three items independently from each other. They show the items with their hands: a rock, scissors or paper. The winner is determined by the following rules: the rock beats the scissors, the scissors beat the paper and the paper beats the rock. If the players choose the same item, the round finishes with a draw.

Nikephoros and Polycarpus have played n rounds. In each round the winner gave the loser a friendly pinch and the loser ended up with a fresh and new red spot on his body. If the round finished in a draw, the players did nothing and just played on.

Nikephoros turned out to have worked out the following strategy: before the game began, he chose some sequence of items A = (a1, a2, ..., am), and then he cyclically showed the items from this sequence, starting from the first one. Cyclically means that Nikephoros shows signs in the following order: a1, a2, ..., am, a1, a2, ..., am, a1, ... and so on. Polycarpus had a similar strategy, only he had his own sequence of items B = (b1, b2, ..., bk).

Determine the number of red spots on both players after they've played n rounds of the game. You can consider that when the game began, the boys had no red spots on them.

Input

The first line contains integer n (1 ≤ n ≤ 2·109) — the number of the game's rounds.

The second line contains sequence A as a string of m characters and the third line contains sequence B as a string of k characters (1 ≤ m, k ≤ 1000). The given lines only contain characters "R", "S" and "P". Character "R" stands for the rock, character "S" represents the scissors and "P" represents the paper.

Output

Print two space-separated integers: the numbers of red spots Nikephoros and Polycarpus have.

Sample Input

7

RPS

RSPP

Sample Output

3 2

Hint

题意

两个人在玩石头剪刀布

给你一个字符串表示第一个人的顺序

给你第二个字符串表示第二个人石头剪刀布的顺序

然后玩n局之后,问你两个人各输多少局

题解:

就求一个lcm之后,然后我们暴力这个lcm里面各输多少局,然后再暴力算余数里面各数多少局。

就好了

这样复杂度可以降为O(lcm)的

代码

#include<bits/stdc++.h>
using namespace std; string s1;
string s2;
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
int solve(char a,char b)
{
if(a=='R'&&b=='P')
return 1;
if(a=='P'&&b=='S')
return 1;
if(a=='S'&&b=='R')
return 1;
return 0;
}
int main()
{
int n;
scanf("%d",&n);
cin>>s1>>s2;
int c = lcm(s1.size(),s2.size());
int ans1=0,ans2=0;
int len1 = s1.size(),len2 = s2.size();
for(int i=0;i<c;i++)
{
ans1+=solve(s1[i%len1],s2[i%len2]);
ans2+=solve(s2[i%len2],s1[i%len1]);
}
ans1*=n/c;
ans2*=n/c;
int p = n-n/c*c;
for(int i=0;i<p;i++)
{
ans1+=solve(s1[i%len1],s2[i%len2]);
ans2+=solve(s2[i%len2],s1[i%len1]);
}
cout<<ans1<<" "<<ans2<<endl;
}

CodeForces 173A Rock-Paper-Scissors 数学的更多相关文章

  1. 2018 ACM-ICPC 中国大学生程序设计竞赛线上赛 H题 Rock Paper Scissors Lizard Spock&period;&lpar;FFT字符串匹配&rpar;

    2018 ACM-ICPC 中国大学生程序设计竞赛线上赛:https://www.jisuanke.com/contest/1227 题目链接:https://nanti.jisuanke.com/t ...

  2. SDUT 3568 Rock Paper Scissors 状压统计

    就是改成把一个字符串改成三进制状压,然后分成前5位,后5位统计, 然后直接统计 f[i][j][k]代表,后5局状压为k的,前5局比和j状态比输了5局的有多少个人 复杂度是O(T*30000*25*m ...

  3. FFT(Rock Paper Scissors Gym - 101667H)

    题目链接:https://vjudge.net/problem/Gym-101667H 题目大意:首先给你两个字符串,R代表石头,P代表布,S代表剪刀,第一个字符串代表第一个人每一次出的类型,第二个字 ...

  4. Gym - 101667H - Rock Paper Scissors FFT 求区间相同个数

    Gym - 101667H:https://vjudge.net/problem/Gym-101667H 参考:https://blog.csdn.net/weixin_37517391/articl ...

  5. Gym101667 H&period; Rock Paper Scissors

    将第二个字符串改成能赢对方时对方的字符并倒序后,字符串匹配就是卷积的过程. 那么就枚举字符做三次卷积即可. #include <bits/stdc++.h> struct Complex ...

  6. 【题解】CF1426E Rock&comma; Paper&comma; Scissors

    题目戳我 \(\text{Solution:}\) 考虑第二问,赢的局数最小,即输和平的局数最多. 考虑网络流,\(1,2,3\)表示\(Alice\)选择的三种可能性,\(4,5,6\)同理. 它们 ...

  7. 题解 CF1426E - Rock&comma; Paper&comma; Scissors

    一眼题. 第一问很简单吧,就是每个 \(\tt Alice\) 能赢的都尽量让他赢. 第二问很简单吧,就是让 \(\tt Alice\) 输的或平局的尽量多,于是跑个网络最大流.\(1 - 3\) 的 ...

  8. HDOJ&lpar;HDU&rpar; 2164 Rock&comma; Paper&comma; or Scissors&quest;

    Problem Description Rock, Paper, Scissors is a two player game, where each player simultaneously cho ...

  9. HDU 2164 Rock&comma; Paper&comma; or Scissors&quest;

    http://acm.hdu.edu.cn/showproblem.php?pid=2164 Problem Description Rock, Paper, Scissors is a two pl ...

  10. 1090-Rock&comma; Paper&comma; Scissors

    描述 Rock, Paper, Scissors is a classic hand game for two people. Each participant holds out either a ...

随机推荐

  1. 在UIView上添加tableView设置代理属性

  2. VS2010 win7 QT4&period;8&period;0,实现VS2010编译调试Qt程序,QtCreator静态发布程序

    下载源代码,注意一定是源码压缩包如qt-everywhere-opensource-src-4.8.0.zip, 不是Qt发布的已编译的不同版本的标准库如qt-win-opensource-4.8.0 ...

  3. mysql awr v1&period;0&period;2发布

    改进说明: 1.新增监控Mysql实例通过web控制台http://ip:port/hosts.html进行,无需更改mysql-jdbc.properties配置文件和spring-servlet. ...

  4. Android之解析GML并显示

    本例主要实现在APP中解析GML数据并显示 GML,地理标记语言(外语全称:Geography MarkupLanguage.外语缩写:GML),它由开放式地理信息系统协会(外语缩写:OGC)于199 ...

  5. 【Xamarin笔记】Events&comma; Protocols and Delegates

    Events, Protocols and Delegates   事件.协议和委托 This article presents the key iOS technologies used to re ...

  6. Redis与Java - 数据结构

    Redis与Java 标签 : Java与NoSQL Redis(REmote DIctionary Server) is an open source (BSD licensed), in-memo ...

  7. hbuilder的aptana php插件无法提示命名空间之外函数和对象的解决办法

  8. java 反编译插件 JD-Eclipse 和 JD-IntelliJ

    去官网 : http://jd.benow.ca/ 找到 JD-Eclipse 和  JD-IntelliJ,下载,前者安在eclipse上,后者安在as上.

  9. swfupload操作手册

    SWFUpload SWFUpload 最初是Vinterwebb.se 开发的客户端文件上传工具.它联合javascript和flash,在浏览器中提供一个优于传统上传标签 <input ty ...

  10. object-fit&colon; 炒鸡方便的图片居中方法

    今天在项目中遇到图片居中的问题,嗯,之前也有写过解决这个问题的文章,有n种方法.不过今天要说一个新的方案:object-fit ,嗯,这个才是真的方便的方案啊. 先看预览: object-fit 只能 ...