[USACO 2017 Jan S]Secret Cow Code

NC24056. [USACO 2017 Jan S]Secret Cow Code

描述

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string s, let F(s) be s followed by s "rotated" one character to the right (in a right rotation, the last character of s rotates around and becomes the new first character). Given an initial string s, the cows build their infinite-length code string by repeatedly applying F; each step therefore doubles the length of the current string.

Given the initial string and an index N, please help the cows compute the character at the Nth position within the infinite code string.

输入描述

The input consists of a single line containing a string followed by N. The string consists of at most 30 uppercase characters, and $N \leq 10^{18}$ .

Note that N may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

输出描述

Please output the Nth character of the infinite code built from the initial string. The first character is N=1.

示例1

输入:

COW 8

输出:

说明:

In this example, the initial string COW expands as follows:
COW -> COWWCO ->
COWWCOOCOWWC
12345678

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 408K, 提交时间: 2022-02-28 14:53:03

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	string s;
    ll n;
	cin>>s>>n;
	ll len=s.size();
	while(len<n){
		ll i=len;
		while(n>i*2){
			i*=2;
		}
		n-=i;
		n--;
		if(n==0){
			n=i;
		}
	}
	cout<<s[n-1]<<endl;
	return 0;
}

Python3(3.9) 解法, 执行用时: 22ms, 内存消耗: 2812K, 提交时间: 2020-12-12 15:31:18

S,n = input().split()
n = int(n)
t = len(S)
while t<n:
    k=t
    while k<n:
        k<<=1
    k>>=1
    n-=(k+1)
    if n==0:
        n=k
print(S[n-1])

上一题

下一题

详情