codeforces 216C-Hiring Staff

时间：2014-03-14 05:23:40 阅读：474 评论：0 收藏：0 [点我收藏+]

Description

A new Berland businessman Vitaly is going to open a household appliances‘ store. All he‘s got to do now is to hire the staff.

The store will work seven days a week, but not around the clock. Every day at least k people must work in the store.

Berland has a law that determines the order of working days and non-working days. Namely, each employee must work for exactly nconsecutive days, then rest for exactly m days, then work for n more days and rest for m more, and so on. Vitaly doesn‘t want to break the law. Fortunately, there is a loophole: the law comes into force on the day when the employee is hired. For example, if an employee is hired on day x, then he should work on days [x,?x?+?1,?...,?x?+?n?-?1], [x?+?m?+?n,?x?+?m?+?n?+?1,?...,?x?+?m?+?2n?-?1], and so on. Dayx can be chosen arbitrarily by Vitaly.

There is one more thing: the key to the store. Berland law prohibits making copies of keys, so there is only one key. Vitaly is planning to entrust the key to the store employees. At the same time on each day the key must be with an employee who works that day — otherwise on this day no one can get inside the store. During the day the key holder can give the key to another employee, if he also works that day. The key will handed to the first hired employee at his first working day.

Each employee has to be paid salary. Therefore, Vitaly wants to hire as few employees as possible provided that the store can operate normally on each day from 1 to infinity. In other words, on each day with index from 1 to infinity, the store must have at least k working employees, and one of the working employees should have the key to the store.

Help Vitaly and determine the minimum required number of employees, as well as days on which they should be hired.

Input

The first line contains three integers n, m and k (1?≤?m?≤?n?≤?1000, n?≠?1, 1?≤?k?≤?1000).

Output

In the first line print a single integer z — the minimum required number of employees.

In the second line print z positive integers, separated by spaces: the i-th integer a_i (1?≤?a_i?≤?10⁴) should represent the number of the day, on which Vitaly should hire the i-th employee.

If there are multiple answers, print any of them.

Sample Input

Input

4 3 2

Output

4
1 1 4 5

Input

3 3 1

Output

3
1 3 5

思路：题目的意思大概是一个老板要雇佣工人，每个工人要工作n天后休息m天，而且每天必须保证工作的人数大于k，附加条件就是这个商店只有一把钥匙，工作的工人可以在工作时间把要是给另外一个人，以保证每天都有需要工作的人拿着钥匙开门。

把题目理解完了之后，就明白这是一道模拟题目，首先要保证每天工作人数达到k，从第一天开始模拟，那么第一天直达第n天都是要求k个人来工作，人后看n+1天，这天工作人数为0，所以没人有要是来开门，即使你在这天雇佣工人也不行，所以要返回到第n天，这天来雇佣一人拿钥匙，然后再模拟第n+1天，要求其人数达到k，依次类推，知道模拟到n+m+1天，那么就会形成一个循环，后面的情况就不用再考虑了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int s[4000],t[4000];

int main()
{
    int m,n,K;
    while(scanf("%d%d%d",&m,&n,&K)!=-1)
    {
        memset(t,0,sizeof(t));
        memset(s,0,sizeof(s));
        int mn=m+n;
        int p=mn;
        int i,j,k=0;
        while(t[1]<K)
        {
            s[k++]=1,t[1]++;
        }
        for(j=2; j<=p+1; j++)
            if((j-1)%mn<m) t[j]=t[1];
        for(i=2; i<=p; i++)
        {
            int flag=0;
            if(t[i]==0)
            {
                i--;
                flag++;
                t[i]++;
                s[k++]=i;
            }
            while(t[i]<K)
            {
                s[k++]=i,t[i]++;
                flag++;
            }
            if(flag)
                for(j=i+1; j<=p+1; j++)
                    if((j-i)%mn<m) t[j]+=flag;
        }
        if(t[p+1]==t[1]) s[k++]=p;
        printf("%d\n%d",k,s[0]);

        for(i=1; i<k; i++)
            printf(" %d",s[i]);
        printf("\n");
    }
    return 0;
}

codeforces 216C-Hiring Staff,布布扣,bubuko.com

codeforces 216C-Hiring Staff

原文：http://blog.csdn.net/knight_kaka/article/details/21182587

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)