当前位置: 首页 > 工具软件 > shashlik > 使用案例 >

B - Shashlik Cooking

林英朗
2023-12-01

Long story short, shashlik is Miroslav’s favorite food. Shashlik is prepared on several skewers simultaneously. There are two states for each skewer: initial and turned over.

This time Miroslav laid out n skewers parallel to each other, and enumerated them with consecutive integers from 1 to n in order from left to right. For better cooking, he puts them quite close to each other, so when he turns skewer number i, it leads to turning k closest skewers from each side of the skewer i, that is, skewers number i−k, i−k+1, …, i−1, i+1, …, i+k−1, i+k (if they exist).

For example, let n=6 and k=1. When Miroslav turns skewer number 3, then skewers with numbers 2, 3, and 4 will come up turned over. If after that he turns skewer number 1, then skewers number 1, 3, and 4 will be turned over, while skewer number 2 will be in the initial position (because it is turned again).

As we said before, the art of cooking requires perfect timing, so Miroslav wants to turn over all n skewers with the minimal possible number of actions. For example, for the above example n=6 and k=1, two turnings are sufficient: he can turn over skewers number 2 and 5.

Help Miroslav turn over all n skewers.

Input
The first line contains two integers n and k (1≤n≤1000, 0≤k≤1000) — the number of skewers and the number of skewers from each side that are turned in one step.

Output
The first line should contain integer l — the minimum number of actions needed by Miroslav to turn over all n skewers. After than print l integers from 1 to n denoting the number of the skewer that is to be turned over at the corresponding step.

Examples

Input
7 2

Output
2
1 6

Input

5 1
Output

2
1 4

Note
In the first example the first operation turns over skewers 1, 2 and 3, the second operation turns over skewers 4, 5, 6 and 7.

In the second example it is also correct to turn over skewers 2 and 5, but turning skewers 2 and 4, or 1 and 5 are incorrect solutions because the skewer 3 is in the initial state after these operations.

题目大意:给定x枚硬币(功能相同),每次翻指定位置左右y个硬币(总计翻2*y+1枚,左右硬币数量不够除外),问:从哪个位置开始可以把所有硬币全部翻一遍且翻的次数最少。并给出每次翻的中心位置。(同一枚硬币不能被多次翻转)

	首先判断输入的y是否为0,若是0的话一定是从1开始一直翻到x;
	
	另外,判断x%(2*y+1)?=0 ||x%(2*y+)?y。若是等于零或者大于y就不能从位置1开始翻,因为这样会导致最后翻的硬币有部分重复翻。(可以通过对样例进行测试或者对样例进行改变去验证)
	
	其他的情况即可从位置1开始翻转最后不会出现同一枚硬币重复翻转问题。
	
AC代码:
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int x,y;
    cin>>x>>y;
    if(y==0)
    {
        cout<<x<<endl;
        for(int i=1;i<=x;i++)
            cout<<i<<" ";
    }
    else if(x<=(2*y+1))
    {
        cout<<"1"<<endl;
        cout<<x/2+1;
    }
    else if(x%(2*y+1)==0||x%(2*y+1)>y)
    {
        int times=0;							//times的作用是判断一共需要翻转多少次
        for(int i=y+1;i<=x;i+=2*y+1)
        {
            times++;
        }
        cout<<times<<endl;
        for(int i=y+1;i<=x;i+=2*y+1)
        {
            cout<<i<<" ";
        }
    }
    else
    {
        int times=0;
        for(int i=1;i<=x;i+=2*y+1)
            times++;
        cout<<times<<endl;
        for(int i=1;i<=x;i+=2*y+1)
            cout<<i<<" ";
    }
    return 0;
}

 类似资料: