`
jishublog
  • 浏览: 861820 次
文章分类
社区版块
存档分类
最新评论

UVa 133 - The Dole Queue

 
阅读更多

UVa 133 - The Dole Queue

Table of Contents

1题目

===================

The Dole Queue

In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered counter-clockwise up to N (who will be standing on 1's left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise, counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.

Input

Write a program that will successively read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 20) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).

Output

For each triplet, output a single line of numbers specifying the order in which people are chosen. Each number should be in a field of 3 characters. For pairs of numbers list the person chosen by the counter-clockwise official first. Separate successive pairs (or singletons) by commas (but there should not be a trailing comma).

Sample input

10 4 3
0 0 0

Sample output

tex2html_wrap_inline344tex2html_wrap_inline348,tex2html_wrap_inline349tex2html_wrap_inline345,tex2html_wrap_inline343tex2html_wrap_inline341,tex2html_wrap_inline342tex2html_wrap_inline346,tex2html_wrap_inline5010,tex2html_wrap_inline347

wheretex2html_wrap_inline50represents a space.


===================

2思路

这是一个双向约瑟夫环问题,使用循环双向链表实现。题目本身不难,关键在于 理解题目的意思,并考虑到一些特殊状态的处理。注意是两个officer先都确定下 人,然后这两个人再出去,不是先出去一个,再出去一个。另外,需要考虑两人 选择相同人时的情况;还要考虑被选的两人位置相邻时的情况,这和一般情况下对 链表的操作是不一样的。

3代码

/*
 * Problem: UVa 133 The Dole Queue
 * Lang: ANSI C
 * Time: 0.009s
 * Author: minix
 */
#include <stdio.h>

#define N 20

typedef struct _node {
  struct _node *pre;
  struct _node *next; 
  int seq;
}Node;

Node g_node[N];

int main() {
  int n, k, m, i;
  Node *pa = NULL;
  Node *pb = NULL;
  while (scanf ("%d%d%d", &n,&k,&m) != EOF) {
    if (n==0 && k==0 && m==0) break;
    /* init double & circle queue */
    for (i=1; i<=n; i++) {
      g_node[i].seq = i;
      g_node[i].pre = &g_node[i-1];
      g_node[i].next = &g_node[i+1];
    }
    g_node[1].pre = &g_node[n];
    g_node[n].next = &g_node[1];

    /* kill */
    pa = &g_node[1];
    pb = &g_node[n];

    while (n != 0) {
      for (i=1; i<=(k-1); i++)
        pa = pa->next;
      for (i=1; i<=(m-1); i++)
        pb = pb->pre;

      if (pa == pb) {
        printf ("%3d", pa->seq);
        pa->pre->next = pa->next;
        pa->next->pre = pa->pre;
        pa = pa->next;
        pb = pb->pre;
        n -= 1;
      } else {
        printf ("%3d%3d", pa->seq, pb->seq);
        n -= 2;
        if (pa->next == pb) {
          pa->pre->next = pb->next;
          pb->next->pre = pa->pre;
          pa = pb->next;
          pb = pa->pre;
        } else {
          pa->pre->next = pa->next;
          pa->next->pre = pa->pre;
          pb->pre->next = pb->next;
          pb->next->pre = pb->pre;
          pa = pa->next;
          pb = pb->pre;
        }
      }

      if (n != 0) printf (",");
    }
    printf ("\n");
  }
  return 0;
}


分享到:
评论

相关推荐

    大学知识产权所有权归属模式演进及其对技术转移的影响

    自20世纪80年代美国颁布影响大学技术转移的“Bayh-Dole”法案以来,调整大学科研成果的知识产权所有权归属,成为世界各国科技政策制定者关心的焦点。我国长期受计划经济体制的影响,使制定的大学科研成果知识产权归属...

    专利激励如何影响大学研究人员?-研究论文

    鼓励大学和其他科学研究公共资金的受益者根据 Bayh-Dole 法案为由此产生的发明申请专利。 这个有争议的框架要求大学与发明人分享由此产生的专利使用费,从而使学术资助接受者在其发明的成功中获得直接的经济利益。 ...

    大学专利和许可活动:文献回顾-研究论文

    这篇关于大学专利和许可活动的文献综述基于 1980 年至 2004 年间发表的 125 篇论文,这些论文是通过查询 ABI/INFORM 和 EconLit 获得的,使用关键词“大学”、“专利”、“许可”、“ Bayh-Dole”、“triple helix...

    与大学专利相关的实证分析-研究论文

    在过去的二十年中,... 然后讨论了 Bayh-Dole 法案,该法案促进了联邦资助的大学发明的专利和许可。 本章最后描述了过去 20 年中大学专利申请的实证研究,强调了该文献中的一些未解决的问题,并提出了新的研究途径。

    accrete-rb:星型发电机

    请参阅以获取Stephen H.Dole的原始论文 本地开发设置 先决条件 Ruby 通过\curl -L https://get.rvm.io | bash安装rvm \curl -L https://get.rvm.io | bash \curl -L https://get.rvm.io | bash 通过rvm install _...

    leetcode伪代码-Aps:应用程序

    dole na tastaturata) -&gt; sluzi za generate code, konstruktor, getters setters... 查找班级 – Ctrl + N -&gt; 要查找您要查找的班级,只需按 Ctrl + N 并输入名称即可。 智能代码完成 –&gt; Ctrl + Shift + Space - ...

    IP需要IP吗? 适应知识产权范式之外的知识生产-研究论文

    学术研究长期以来一直在共享制度下进行,即使在 Bayh-Dole 法案允许大学对教师发明申请专利权之后,默顿主义的共产主义规范继续对学术实践产生强大的影响。 正如埃里克·冯·希Perl (Eric von Hippel) 充分证明的...

    accretejs:tmandersonAccrete.js 的分叉和扩展

    差不多十年后,卡尔·萨根和理查德·艾萨克森改进了 Dole 的模型——此后不久,该模型也在 FORTRAN 中实现,并再次由 Martin Fogg 精心和学术性地出版。 到了 80 年代后期,Matt Burdick 将这个无价的程序带给了...

    影响公立学校学生教育决策的因素

    DOLE 宾夕法尼亚大学 众所周知,教育决策,如职业决策,通常与家庭愿望、社会经济地位、职业目标、教育成就有关、能力、价值观、兴趣和其他变量。 (尤其参见 Beezer &amp; Hjelm,1961;Cass &amp; Tiedeman,1960...

    Factors in educational decisions among public school pupils

    DOLE University of Pennsylvania It is well established that educational decisions, like vocational decisions, generally are associated with family aspirations, socioeconomic status, occupational...

    学术界的创业转型——多角度详解:规则、实践、结构、专利活动和教师意见-研究论文

    学术界在促进技术转让和经济增长方面的作用现在被认为是国家科技政策的一个关键要素。 从博士论文开始,我的研究旨在了解学术界在这种新的环境压力面前的行为,并揭示了意大利大学专利活动的详细说明、国家立法、...

    2ASK实验.docx

    熟悉2ASK和2FSK调制原理 (2)学会运用Matlab编写2ASK和2FSK调制程序。 (3)会画出原信号和调制信号的波形图。 (4)掌握数字通信的2ASK和2FSK的调制方式

Global site tag (gtag.js) - Google Analytics