首页 > 代码库 > SGU 137.Funny String

SGU 137.Funny String

题目描述

      一个序列S1 S2 S3... Sn 如果满足 新序列 S1-1 S2 S3 ...Sn+1能够通过旋转的操作(不是翻转)来得到旧的序列,那么这个序列就叫做Funny序列。例如 1 2 1 2 2就是Funny序列,1 2 1 2 就不是

输入

      给定一个数N,表示序列长度。一个数K,表示序列中所有数之和。 gcd(N,K)=1(这能保证本题一定有解)

输出

      一行,N个数,表示满足条件的序列。

样例输入

9 16

样例输出

1 2 2 2 1 2 2 2 2

 

 

 

 

 


 

Solution:

            假设原串S为,S0,S1....Sn-1.

            旋转t次后为,St,St+1....St-1

 

            根据对应的关系可知,

             S0==St,S1==St+1,

             即S== Sj ,当 i mod t==j nod t 时成立。

        

             读入n,和k之后,令S中所有元素都为 p=k/n

             那么还剩下k mod n,没有分配.

             由St=S0+1,知St=S2*t==Sm*t=p+1;  

             Sn-1=S0+1=p+1;

             令 d=k mod n,即要分配的1的个数为d,

             当 d*t%n==n-1;此时d个一全部分配完.

 

             由此,先枚举t,确定t的大小.

             再确定得到了1的那些元素,最后输出即可

 

参考代码:

 

#include <iostream>using namespace std;int n, k, t;int f[1000];int main() {	cin >> n >> k;	for (t = 1; t < n; t++) 		if ( (n - 1) == (k % n) *t % n) break;	for (int i = t; i != n - 1; i = (i + t) % n)		f[i] = 1;	f[n - 1] = 1;	for (int i = 0; i < n; i++) 		cout << k / n + f[i] << ‘ ‘;}