HackerEarth 女友的需求挑战

Question

问题描述可见Here。我的程序正在生成与示例测试用例相匹配的输出，但是当遇到大整数时，程序会崩溃，我无法找出原因。当用户提供的数据类似于 a:=252509054433933447 b:=760713016476190629 时，程序要么停止响应，要么出现 SIGABRT 错误，或者处理 1 个输入文件的时间超过了最大分配时间。我的代码有什么问题？有人可以建议一个更好的算法吗？请帮我找出错误。

#include<stdio.h>
#include<string.h>
int main()
{
      long long int a,b,input,len,len1,len2;
      char dem[1000];
      char temp[100000];
      scanf("%s",dem);
      scanf("%u",&input);

      len=strlen(dem);

      for(unsigned int i=0;i<input;i++)
      {
        scanf("\n%lld %lld",&a,&b);

        if(b>len)
        {
          len1=b/len;
          for(unsigned int j=1;j<=((len1+1));j++)
          {
          strcat(temp,dem);
          }
         }
         else
         {
            if(dem[a-1]==dem[b-1])
            {
             printf("\nYes");
            }
            else
            {
              printf("\nNo");
            } 
         }
        len2=strlen(temp);
        if(len2!=0)
        {
        if(temp[a-1]==temp[b-1])
        {
          printf("\nYes");
        }
        else
        {
          printf("\nNo");
        }
        }  

        }

}

Answer 1

哇，这是一个厌恶女性的问题描述。真可惜。

你的问题在这里：

for(unsigned int j=1;j<=((len1+1));j++)
{
   strcat(temp,dem);
}

您不应该将给定的字符串与其自身连接起来，因为对于给定的限制，这将不适合内存。相反，如果您确实进行了串联，请尝试使用模运算来查找某个位置的字符。

例如，如果你有字符串 abc 并且我问，通过无限次重复 abc 形成的字符串中位置 10 的字符是什么，你会做 (从零开始的索引):

char_at_position = str[10 % len(abc)] = str[10 mod 3] = str[1] = b

0123456789 10
abcabcabca b  c
           *

HackerEarth 女友的需求挑战

HackerEarth Girlfriend's Demand Challenge

c

algorithm

runtime-error

time-complexity