Harmonic Value Description

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 786    Accepted Submission(s): 456
Special Judge

Problem Description

The harmonic value of the permutation p1,p2,?pn is

∑i=1n−1gcd(pi.pi+1)

Mr. Frog is wondering about the permutation whose harmonic value is the strictly k-th smallest among all the permutations of [n].

Input

The first line contains only one integer T (1≤T≤100), which indicates the number of test cases.

For each test case, there is only one line describing the given integers n and k (1≤2k≤n≤10000).

Output

For each test case, output one line “Case #x: p1 p2 ? pn”, where x is the case number (starting from 1) and p1 p2 ? pn is the answer.

Sample Input

2

4 1

4 2

Sample Output

Case #1: 4 1 3 2

Case #2: 2 4 1 3

//题目看上去比较复杂,其实就需要一点点思维,问 1-n n个数,第 k 小的harmonic value的排列是怎样的

题解: 要第 k 大就把前 k 个偶数丢前面去,剩下的不变就好了

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5
 6 int main()
 7 {
 8     int T;
 9     cin>>T;
10     for (int cnt=1;cnt<=T;cnt++)
11     {
12         int n ,k;
13         scanf("%d%d",&n,&k);
14         printf("Case #%d:",cnt);
15         for (int i=1;i<=k;i++)
16             printf(" %d",i*2);
17         for (int i=1;i<=n;i++)
18         {
19             if (i%2==0&&i<=2*k) continue;
20             printf(" %d",i);
21         }
22         printf("\n");
23     }
24     return 0;
25 }

时间: 05-09

Harmonic Value Description的相关文章

HDU 5916 Harmonic Value Description 【构造】(2016中国大学生程序设计竞赛(长春))

Harmonic Value Description Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0    Accepted Submission(s): 0Special Judge Problem Description The harmonic value of the permutation p1,p2,?pn is ∑i=1

CCPC2016长春F (hdu 5916 Harmonic Value Description)

构造一个n个数字的排列,使其作为 sigma( gcd( a[i] , a[i+1] ) ) 中第k小的排列. 因为题目给的 k*2 <= n ,所以可以知道只会询问最小到第 n/2 小,易得最多移动一个数字即可得到答案. 假设原始排列为1 2 3 ... n,如果询问最小直接输出排列,否则询问x且x是偶数就把x移动到2*n与2*n-1之间. 如果x是奇数就将x与 2*n-1或者2*n+1交换.因为有可能2*n-1和2*n+1与x-1或者x+1不互质. //#define test #inclu

HDU5916

Harmonic Value Description Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 287    Accepted Submission(s): 184Special Judge Problem Description The harmonic value of the permutation p1,p2,?pn is

LightOJ 1234 Harmonic Number (打表)

Harmonic Number Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu Submit Status Practice LightOJ 1234 Description In mathematics, the nth harmonic number is the sum of the reciprocals of the first n natural numbers: In this p

LightOJ 1234 Harmonic Number(打表 + 技巧)

http://lightoj.com/volume_showproblem.php?problem=1234 Harmonic Number Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu Submit Status Practice LightOJ 1234 Description In mathematics, the nth harmonic number is the sum of th

Description Resource Path Location Type The superclass &quot;javax.servlet.http.HttpServlet&quot; was not foun

一段时间没亲自建新项目玩乐,今天建立了一Maven project的时候发现了以下异常,Description Resource Path Location Type The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path index.jsp /easyBuy/src/main/webapp line 1 JSP Problem 经过查找原因,原来是因为忘记设置server

获取枚举类型Description特性的描述信息

C#中可以对枚举类型用Description特性描述. 如果需要对Description信息获取,那么可以定义一个扩展方法来实现.代码如下: public static class EnumExtensions { public static string GetDescription(this object value) { if (value==null) return string.Empty; Type type = value.GetType(); var fieldInfo = ty

1245 - Harmonic Number (II)(规律题)

1245 - Harmonic Number (II)   PDF (English) Statistics Forum Time Limit: 3 second(s) Memory Limit: 32 MB I was trying to solve problem '1234 - Harmonic Number', I wrote the following code long long H( int n ) {     long long res = 0;     for( int i =

Description方法&amp;&amp;SEL类型

description方法和sel数据类型 一.description方法 Description方法包括类方法和对象方法.(NSObject类所包含) (一)基本知识 -description(对象方法) 使用NSLog和@%输出某个对象时,会调用对象的description方法,并拿到返回值进行输出. +description(类方法) 使用NSLog和@%输出某个对象时,会调用类对象的description方法,并拿到返回值进行输出,把整个对象一次性打印出来,打印对象使用%@. 使用@%打