poj1611 并查集基础题

poj1067

WARush posted @ 2010年6月28日 01:14 in poj的挣扎 with tags 博弈 Beatty定理 库佐夫博弈 , 1384 阅读

Description

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一 是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到 你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。

Input

输 入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数 目,a和b都不大于1,000,000,000。

Output

输 出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0




在数论中,贝亚蒂定理(英文:Beatty sequence)指:若 p,q \in \mathbb{R^+} ,p,q \not\in
\mathbb{Q} 使 得\frac{1}{p} + \frac{1}{q} = 1。 定义集(贝亚蒂列P = \{\lfloor np \rfloor : n \in
Z^+ \}, Q=\{\lfloor nq \rfloor : n \in Z^+\}, 则P 和 Q 构成正整数集的一个分划: P \cap Q = \emptysetP \cup Q = Z^+

即是说:若两个正无理数的倒数之和是1,则任何正整数都可 刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

 

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    double alpha=(1.0+sqrt(5.0))/2.0;
    double beta=(3.0+sqrt(5.0))/2.0;
    int num1,num2;
    int temp1,temp2;
    while(scanf("%d%d",&num1,&num2))
    {
        if(num1<num2)swap(num1,num2);
        n=(int)(ceil(num1/beta));
        temp1=(int)(beta*n);
        temp2=(int)(alpha*n);
        if((num1==temp1)&&(num2==temp2))
         printf("0\n");
         else printf("1\n");
    }
    return 0;
}
  • 无匹配
Junior Dakil Result 说:
2022年8月31日 13:52

Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. Junior Dakil Result Dinajpur Board The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.

boardmodelpaper.com 说:
2024年1月06日 17:08

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter