首页 > 试题广场 >

旋转数字

[编程题]旋转数字
  • 热度指数:467 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小图(Tu)和小森(Simple)最近发现了一个有趣的游戏。

在游戏的一开始,小图和小森会分别获得一个初始数字t和s,10 < t, s < 109。之后,他们会从初始数字开始,不停地将自己数字的第一位移动到最后一位。

例如,初始数字是123的时候,数字的变化是:

123 -> 231 -> 312 -> 123 -> ...

在这之后,他们需要把每一个数字依次接到前一个数字最高位的前面,构成一列无限长的数字。例如,对于上面的例子,构成的数字是:

... 231123312231123312231123

假设小森拿到的数字是31321,那么他构成的数字是:

... 1313221313321311321331321

接下来,他们会选择一个k值,并比较他们自己数字的后k位,较大的人会赢得最终的胜利。

小图和小森有他们进行的若干局游戏的记录,每局游戏都记录了t、s和k的值。他们希望知道,在这些游戏中,分别是谁获得了胜利?

输入描述:
输入的第一行是一个n(1 <= n <= 104),表示游戏进行的局数。
接下来的n行中每行有三个数,依次为题目中的t、s和k(10 < t, s < 109, 1 <= k <= 109)。
为了方便计算,小图和小森的初始数字(t、s)的所有数位都不是0。


输出描述:
输出包含n行,每一行是"Tu"、"Simple"和"Draw"中的一个字符串(不含引号),表示胜利者是谁,或者是平局。
示例1

输入

3
123 31321 1
123 31321 3
123 31321 9

输出

Tu
Simple
Simple

说明

两个人的初始数字和题目描述中一致。以第三组为例,k=9,那么两个人数字的后9位分别是:
312231123

321331321
所以获胜者是小森(Simple)。
#include <bits/stdc++.h>

using namespace std;

void get_re(string& temp,string tmp, int k)
{
    temp = tmp;
    while (temp.size() < k)
    {
        tmp.push_back(tmp[0]);
        tmp.erase(tmp.begin());
        // const string tmp2 = tmp.substr(1, tmp.size() - 1);
        temp = tmp + temp;
    }
    temp=temp.substr(temp.size() - k, temp.size());
}

int main()
{
    int n;

    cin >> n;
    string t[n], s[n], k[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> t[i] >> s[i] >> k[i];

        int ki = stoi(k[i]);
        string t_tmp;
        get_re(t_tmp,t[i], ki);
        string s_tmp;
        get_re(s_tmp,s[i], ki);
        if (t_tmp > s_tmp)
        {
            cout << "Tu" << endl;
        }
        else if (t_tmp < s_tmp)
        {
            cout << "Simple" << endl;
        }
        else
        {
            cout << "Draw" << endl;
        }
    }
    return 0;
}
代码应该是对的,运行超时。如上边截图,测试数据集很大
编辑于 2020-05-15 11:54:43 回复(0)
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int getIndex(string &s, int k){
    int n = s.size();
    return ((((k - 1) / n) % n) + (n - k % n)) % n;
}
int gcd(int a, int b){
    while(b){
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int lcm(int a, int b){
    return a / gcd(a, b) * b;
}
int main(){
    int n;
    cin >> n;
    while (n--){
        string t, s; 
        int k;
        cin >> t >> s >> k;
        if (t == s){
            cout << "Draw" << endl;
            continue;
        }
        int flag = 0;
        int a = t.size();
        int b = s.size();
        int cnt = lcm(max(a,b) * max(a, b), min(a,b) * min(a,b));
        while (k && cnt--){
            int i = getIndex(t, k);
            int j = getIndex(s, k);
            if (t[i] > s[j]){
                flag = 1;
                break;
            }else if (t[i] < s[j]){
                flag = 2;
                break;  
            }else{
                --k;
            }
        }
        if (flag == 0){
            cout << "Draw" << endl;
        }else if (flag == 1){
            cout << "Tu" << endl;
        }else{
            cout << "Simple" << endl;
        }
    }
    return 0;
}
发表于 2021-10-17 12:15:04 回复(1)
分为以下几种情况:
1.判断是否为AAA,BBB类
2.判断是否为ABC,ABC两个输入相等
3.一般情况

class Solution:
    def sol(self, sample):
        t,s,k = list(sample[0]), list(sample[1]), int(sample[2])


        t_same = all(w == t[0] for w in t)
        s_same = all(w == s[0] for w in s)

        if t_same and s_same:
            t = int(t[0])
            s = int(s[0])
            if t == s:
                return 'Draw'
            if t > s:
                return 'Tu'
            if t < s:
                return 'Simple'

        elif sample[0]==sample[1]:
            return 'Draw'

        else:
            t = self.snack(t)
            s = self.snack(s)
            long_t_v = self.str_to_num(t)
            long_s_v = self.str_to_num(s)
            num_t = int(k/len(str(long_t_v)))
            num_s = int(k/len(str(long_s_v)))

            for j in range(num_t):
                t += t
            for j in range(num_s):
                s += s

            t = self.str_to_num(t,k)
            s = self.str_to_num(s,k)
            if t == s:
                return 'Draw'
            if t > s:
                return 'Tu'
            if t < s:
                return 'Simple'

    def str_to_num(self,s,num=None):
        list = []
        if num == None:
            num = len(s)
        list += s[-num:]
        restlt = 0
        for i in range(num):
            w = int(list.pop(0))
            restlt = restlt*10+w
        return restlt

    def snack(self,string):
        longstr = []
        longstr = longstr+string
        for i in range(len(string)-1):
            w = string.pop(0)
            string.append(w)
            longstr = string + longstr
        return longstr

        # write code here



S = Solution()
num = int(input())
_samples=[]

for i in range(num):
    string = input()
    _s,_t,_k = [str(n) for n in string.split()]
    _samples.append([_s,_t,_k])

del _s,_t,_k

for _sample in _samples:
    dance = (S.sol(_sample))
    print(dance)

发表于 2020-07-12 22:16:10 回复(0)
存在循环节
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        int k;
        string s1, s2;
        cin >> s1 >> s2 >> k;
        int size_1 = s1.size();
        int size_2 = s2.size();
        string str = s1 + s1;
        string vs1 = "", vs2 = "";
        for(int i = size_1 - 1; i >= 0; i --)
        {
            string s = str.substr(i, size_1);
            vs1 += s;
        }
        str = s2 + s2;
        for(int i = size_2 - 1; i >= 0; i --)
        {
            string s = str.substr(i, size_2);
            vs2 += s;
        }
        size_1 = vs1.size();
        size_2 = vs2.size();
        int lcm = size_1 * size_2 / __gcd(size_1, size_2);
        int kd1 = lcm / size_1;
        size_1 *= kd1;
        kd1 --;
        str = vs1;
        while(kd1 --)
            vs1 += str;
        int kd2 = lcm / size_2;
        size_2 *= kd2;
        kd2 --;
        str = vs2;
        while(kd2 --)
            vs2 += str;
        int mark = 0;
        if(k <= lcm)
        {
            for(int i = lcm - k; i < lcm; i ++)
            {
                if(vs1[i] > vs2[i])
                {
                    mark = 1;
                    break;
                }
                else if(vs1[i] < vs2[i])
                {
                    mark = -1;
                    break;
                }
            }
        }
        else
        {
            k = k % lcm;
            for(int i = lcm - k; i < lcm; i ++)
            {
                if(vs1[i] > vs2[i])
                {
                    mark = 1;
                    break;
                }
                else if(vs1[i] < vs2[i])
                {
                    mark = -1;
                    break;
                }
            }
            if(!mark)
                for(int i = 0; i < lcm - k; i ++)
                {
                    if(vs1[i] > vs2[i])
                    {
                        mark = 1;
                        break;
                    }
                    else if(vs1[i] < vs2[i])
                    {
                        mark = -1;
                        break;
                    }
                }
        }
        if(!mark)
            cout << "Draw" << endl;
        else if(mark == 1)
            cout << "Tu" << endl;
        else
            cout << "Simple" << endl;
    }
}


发表于 2020-06-03 16:01:51 回复(0)
importjava.math.BigInteger;
importjava.util.Scanner;
 
publicclassMain {
 publicstaticvoidmain(String[] args) {
     String str1;
     String str2;
     String str3;
     String str4;
    Scanner it=newScanner(System.in);
      intn=it.nextInt();
     for(inti=0;i<n;i++) {
         intt=it.nextInt();
         ints=it.nextInt();
         intk=it.nextInt();
       str3=  str1=String.valueOf(t);
      str4=   str2=String.valueOf(s);
         
     while(str3.length()<k) {
            str1=str1.charAt(0)+str1.substring(1, str1.length());
            str3=str1+str3;
     }
     while(str4.length()<k) {
            str2=str2.charAt(0)+str2.substring(1, str1.length());
            str4=str2+str4;
     }
     BigInteger a=newBigInteger(str3.substring(str3.length()-k, str3.length()));
     BigInteger b=newBigInteger(str4.substring(str4.length()-k, str4.length()));
    inttemp= a.compareTo(b);
 
     if(temp==0) {
      
     System.out.println("Draw");
     }
     elseif(temp>0) {
     System.out.println("Tu");}
     elseSystem.out.println("Simple");
      
      
      
      
     }
     
 }
     
     
     
}   为什么无法通过
发表于 2019-11-25 16:34:28 回复(0)

热门推荐

通过挑战的用户