列表

详情

NC16426. [NOIP2016]玩具谜题

描述

小南有一套可爱的玩具小人，它们各有不同的职业。
有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外，如下图：

这时 `singer` 告诉小南一个谜题：「眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个玩具小人那里。」

小南发现，这个谜题中玩具小人的朝向非常关键， 因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。
小南一边艰难地辨认着玩具小人，一边数着：
`singer` 朝内，左数第 3 个是 `archer`。
`archer` 朝外，右数第 1 个是 `thinker`。
`thinker` 朝外，左数第 2 个是 `writer`。
所以眼镜藏在 `writer` 这里！
虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：
有 n 个玩具小人围成一圈，已知它们的职业和朝向。现在第 1 个玩具小人告诉小南一个包含 m 条指令的谜题。其中第 i 条指令形如「左数/右数第 si 个玩具小人」。你需要输出依次数完这些指令后，到达的玩具小人的职业。

输入描述

输入的第一行包含两个正整数 n, m，表示玩具小人的个数和指令的条数。
接下来 n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 0 表示朝向圈内，1 表示朝向圈外。保证不会出现其他的数。字符串长度不超过 10 且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之问用一个空格隔开。
接下来 m 行，其中第 i 行包含两个整数 ai, si，表示第 i 条指令。若 ai = 0，表示向左数 si 个人；若 ai = 1，表示向右数 si 个人。保证 ai 不会出现其他的数。1 ≤  si < n。

输出描述

输出一个字符串，表示从第一个读入的小人开始，依次数完 m 条指令后到达的小人的职业。

示例1

输入: 

7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

输出: 

writer

说明:

这组数据就是「题目描述」中提到的例子。

示例2

输入: 

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

输出: 

y

原站题解

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

C++(g++ 7.5.0) 解法, 执行用时: 104ms, 内存消耗: 6100K, 提交时间: 2022-09-24 19:37:13 

#include <bits/stdc++.h>
using namespace std;
struct a {
	string name;
	int io;
};
int main () {
	struct a a[100000];
	int i, j, k, l, n, m, p=0;	
	cin>>n>>m;
	for (i=0; i<n; i++) {
		cin>>a[i].io>>a[i].name;
	} 
	for (i=0; i<m; i++) {
		cin>>k>>l;
		p=int(p+pow(-1,k+a[p].io+1)*l+n)%n;
	}
	cout<<a[p].name;
	return 0;
}

pypy3 解法, 执行用时: 524ms, 内存消耗: 31452K, 提交时间: 2023-07-25 15:16:27 

n,m=map(int,input().split())
d=[];p=[]
for i in range(n):
    a,b=input().split();a=int(a)
    d.append(a);p.append(b)
pos=0
for i in range(m):
    a,b=map(int,input().split())
    if d[pos]!=a:
        pos=(pos+b)%n
    else:
        pos=(pos-b)%n
print(p[pos])

C++11(clang++ 3.9) 解法, 执行用时: 111ms, 内存消耗: 7148K, 提交时间: 2020-03-07 11:52:29 

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[123456];
string s[202020];
int main()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;++i)
	cin>>a[i]>>s[i];
	for(;m--;)
	{
		int b,y;
		scanf("%d%d",&b,&y);
		k=(k+y*(b^a[k]?1:-1)+n)%n;
	}
	cout<<s[k];
}

Python3 解法, 执行用时: 569ms, 内存消耗: 14236K, 提交时间: 2022-01-07 19:23:26 

n,m=map(int,input().split())
peo=['']*(n)
ori=[0]*(n)
for i in range(n):
    x,y=input().split()
    peo[i]=y
    ori[i]=int(x)
st=0
for i in range(m):
    lr,dis=map(int,input().split())
    st=(st+(2*(lr^ori[st])-1)*dis+n)%n
print(peo[st])

上一题

© 2024 nowcoder.com