#include <stdio.h>

#define MaxN        30
#define MaxK        10e8



unsigned long _2N(unsigned int N){
        unsigned int i;
        unsigned long result=1;
        i=N;
        while(i--)result*=2;
        return(result);
}


unsigned int lighting(unsigned int N,unsigned long K){
        unsigned int result;
        unsigned int N1;
        unsigned long K1;
        N1=_2N(N);
        K1=K+1;
        result=!(unsigned int)(K1%N1);
        return(result);
}


void main(){
        unsigned int T;
        unsigned int N[255];
        unsigned long K[255];
        unsigned int i;

        scanf("%d\n",&T);
        for (i=0;i<=T-1;++i)
                scanf("%d %d\n",&N[i],&K[i]);
        for (i=0;i<=T-1;++i){
                printf("Case #%d:",i+1);
                if (N[i]==0 || N[i]>MaxN || K[i]>MaxK)
                        printf("ERROR\n");
                else if(lighting(N[i],K[i]))
                        printf("ON\n");
                else printf("OFF\n");
        }
        printf("Press any key to exit...\n");
        getchar();

}

原帖由 周瑜 于 2010-5-25 04:43 发表
01 链式开关

原帖由 周瑜 于 2010-5-25 04:45 发表
主题公园

#include <fstream>
#include <sstream>
#include <string>
#include <vector>

typedef std::vector<int> TIntVector;

__int64 Calc(TIntVector const& Group, int R, int k)
{
        __int64 Total = 0;
        TIntVector Step;
        TIntVector Count;
        int const GroupSize = Group.size();

        Step.resize(GroupSize);
        Count.resize(GroupSize);

        for (int i = 0; i < GroupSize; ++i)
        {
                int ItStep = 0;
                int ItCount = 0;

                for (int j = 0; j < GroupSize; ++j)
                {
                        int Sub = i + j;

                        if (Sub >= GroupSize)
                        {
                                Sub -= GroupSize;
                        }

                        if (ItCount + Group[Sub] <= k)
                        {
                                ++ItStep;
                                ItCount += Group[Sub];
                        }
                        else
                        {
                                break;
                        }
                }

                Step[i] = ItStep;
                Count[i] = ItCount;      
        }

        if (GroupSize == Step[0])
        {
                Total = Count[0] * static_cast<__int64>(R);
        }
        else
        {
                int Next = 0;

                for (int i = 0; i < R; ++i)
                {
                        Total += Count[Next];
                        Next += Step[Next];

                        if (Next >= GroupSize)
                        {
                                Next -= GroupSize;
                        }
                }
        }

        return Total;
}

int main()
{
        std::ifstream In("in.txt");
        std::ofstream Out("testout.txt");
        std::string Line;
        int T = 0;

        In >> T;

        for (int i = 0; i < T; ++i)
        {
                int R = 0;
                int k = 0;
                int N = 0;

                In >> R;
                In >> k;
                In >> N;

                int Value;
                TIntVector Group;

                for (int j = 0; j < N; ++j)
                {
                        In >> Value;
                        Group.push_back(Value);
                }

                __int64 Result = Calc(Group, R, k);

                Out << "Case #" << i + 1 << ": " << Result << std::endl;
        }

        return 0;
}

原帖由 周瑜 于 2010-5-29 10:56 发表
第1题并不是输出第k位，而是要求最低k位全是1。

第3题程序有点小错误，最后的
if (k == Step)
应改为
if (GroupSize == Step)

11秒已经是比较好的成绩了，但是算法上还有可以改进的地方，比换好机器管 ...

原帖由 周瑜 于 2010-5-25 04:45 发表
主题公园

__int64 Calc2(TIntVector const& Group, int R, int k)
{
        __int64 Total = 0;
        TIntVector Step;
        TIntVector Count;
        int const GroupSize = Group.size();

        Step.resize(GroupSize);
        Count.resize(GroupSize);

        for (int i = 0; i < GroupSize; ++i)
        {
                int ItStep = 0;
                int ItCount = 0;

                for (int j = 0; j < GroupSize; ++j)
                {
                        int Sub = i + j;

                        if (Sub >= GroupSize)
                        {
                                Sub -= GroupSize;
                        }

                        if (ItCount + Group[Sub] <= k)
                        {
                                ++ItStep;
                                ItCount += Group[Sub];
                        }
                        else
                        {
                                break;
                        }
                }

                Step[i] = ItStep;
                Count[i] = ItCount;
        }

        if (GroupSize == Step[0])
        {
                Total = Count[0] * static_cast<__int64>(R);
        }
        else
        {
                std::vector<__int64> PreCount;
                TIntVector PreR;
                TIntVector FlagN;
                int Next = 0;
                __int64 ItPreCount = 0;
                int ItPreR = 0;
                __int64 CycleCount = 0;
                int CycleR = 0;
                int TailNext = 0;
                bool Finish = true;

                PreCount.resize(GroupSize);
                PreR.resize(GroupSize);
                FlagN.resize(GroupSize);

                for (int i = 0; i < R; ++i)
                {
                        if (0 == FlagN[Next])
                        {
                                PreCount[Next] = Total;
                                PreR[Next] = i;
                                FlagN[Next] = 1;

                                Total += Count[Next];
                                Next += Step[Next];

                                if (Next >= GroupSize)
                                {
                                        Next -= GroupSize;
                                }
                        }
                        else
                        {
                                ItPreCount = PreCount[Next];
                                ItPreR = PreR[Next];
                                CycleCount = Total - ItPreCount;
                                CycleR = i - ItPreR;
                                TailNext = Next;
                                Finish = false;

                                break;
                        }
                }

                if (!Finish)
                {
                        __int64 Tail = 0;

                        for (int i = 0; i < ((R - ItPreR) % CycleR); ++i)
                        {
                                Tail += Count[TailNext];
                                TailNext += Step[TailNext];

                                if (TailNext >= GroupSize)
                                {
                                        TailNext -= GroupSize;
                                }
                        }

                        Total = ItPreCount + (R - ItPreR) / CycleR * static_cast<__int64>(CycleCount) + Tail;
                }
        }

        return Total;
}

原帖由 周瑜 于 2010-5-25 04:44 发表
02 太空观测

原帖由 周瑜 于 2010-5-31 03:13 发表
可能是我描述的不够清楚，已把题目改为“整数ti，表示过去的某次事件到现在的时间。”ti未必有序，也未必互不相等，但不会全相等。

原帖由 Maxwell 于 2010-5-31 00:12 发表


后来想了一下，是否排序无所谓。不过两个相等的数值代表什么含义呢，是两次同时发生的事件还是重复数据？

原帖由 周瑜 于 2010-6-1 03:19 发表


是重复数据。其实这完全是干扰条件，只是手头拿到的数据就有重复的。

原帖由 周瑜 于 2010-5-25 04:44 发表
02 太空观测

#include <fstream>
#include <string>
#include <vector>
#include <gmp.h>
#include <gmpxx.h>


typedef std::vector<mpz_class> TMpzVector;

mpz_class Calc1(TMpzVector const& Data)
{
        mpz_class MinTime = Data[0];
        mpz_class MinGcd = 0;
        size_t const DataLen = Data.size();

        for (size_t i = 1; i < DataLen; ++i)
        {
                mpz_class Diff = abs(Data[0] - Data[i]);

                if (Diff > 0)
                {
                        if (0 == MinGcd)
                        {
                                MinGcd = Diff;
                        }
                        else
                        {
                                mpz_class Gcd;

                                mpz_gcd(Gcd.get_mpz_t(), Diff.get_mpz_t(), MinGcd.get_mpz_t());
                               
                                if (Gcd < MinGcd)
                                {
                                        MinGcd = Gcd;
                                }
                        }
                }

                if (Data[i] < MinTime)
                {
                        MinTime = Data[i];
                }
        }

        mpz_class R = MinTime % MinGcd;
        mpz_class Ret;
       
        if (0 == R)
        {
                Ret = 0;
        }
        else
        {
                Ret = MinGcd - R;
        }

        return Ret;
}


int main()
{
        std::ifstream In("in.txt");
        std::string Line;
        int T = 0;
        FILE* Out = fopen("testout.txt", "w");

        In >> T;

        for (int i = 0; i < T; ++i)
        {
                int N = 0;
                std::string Num;
                TMpzVector Data;

                In >> N;

                for (int j = 0; j < N; ++j)
                {
                        In >> Num;
                        Data.push_back(mpz_class(Num));
                }

                mpz_class Result = Calc1(Data);

                gmp_fprintf(Out, "Case #%d: %Zd\n", i + 1, Result.get_mpz_t());
        }

        return 0;
}

原帖由 周瑜 于 2010-5-25 04:46 发表
甲乙面前有两堆豆子，每人轮流取，每次只能从多的那堆取少的那堆豆子数量的整数倍，把其中一堆取完的输掉游戏。

例如两堆豆子分别为 12 和 51，
甲先取，从 51 中拿掉 12 的 3 倍 36 个，剩余数量为 12 和  ...

原帖由 周瑜 于 2010-5-25 04:46 发表
输入格式：
第一行为测试样本数量 T ，以下 T 行每行为一个样本，包含以空格分隔的四个整数 A1，B1，A2，B2。

输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 为先手必胜 (A,B) 对的个数。

限制条件：
1 ≤ T ≤ 100
1 ≤ A1 ≤ A2 ≤ 1,000,000
1 ≤ B1 ≤ B2 ≤ 1,000,000

示例输入：
3
5 5 8 8
11 11 2 2
1 6 1 6

示例输出：
Case #1: 0
Case #2: 1
Case #3: 20

原帖由 阿尔法孝直 于 2010-6-3 14:10 发表


样本2：A1=11，B1=11，A2=2，B2=2……好奇怪，A1>A2，B1>B2
样本3：A1=1，B1=6，A2=1，B2=6……这样看来只有1组，怎么结果会是20组呢？

原帖由 阿尔法孝直 于 2010-5-29 00:51 发表
从右往左数，最右边是第一个开关。

一开始是：

灯—00000000……00000000—电源，第一个断开的开关是通电的，那么按一下按钮之后，最后一个开关状态翻转：
灯—00000000……00000001—电源，此时电流通过 ...

原帖由 zhaohaidao 于 2010-10-23 18:12 发表

000000000000000000100 的情况下，此时电流到了第四个开关，题目说按一下按钮可以让所有通电开关翻转一次，电流到了第四个开关，那第三个跟第四个开关变不变呢？

function GCD(a, b)
    if b = 0
       return a
    else
       return GCD(b, a mod b)

function GCD(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a