Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

不能ac的O(1)代码。。。。

Posted by Qinz at 2008-10-19 22:29:45
In Reply To:这题重点是算法复杂度，应该没有什么特殊数据，建议您暴力生成数据来验证一下吧 Posted by:liangzhirong at 2008-10-19 20:18:49

#include<stdio.h>
int main()
{
	long long n,m,k;
	scanf("%d",&m);
	while(m)
	{
		scanf("%lld %lld",&n,&k);
		if (k<=n/2+1) printf("1/%d\n",n-k+1);
		else if (k<=5*n/6+1&&n%2==0)
		{
			if ((k-n/2)%2==0) printf("2/%d\n",n-(k-n/2-1));
			else printf("1/%d\n",n/2-(k-n/2-1)/2);
		}
		else if (k<=5*n/6+1&&n%2==1)
		{
			if ((k-n/2)%2==0) printf("2/%d\n",n-(k-n/2-2));
			else printf("1/%d\n",n/2-(k-n/2-2)/2);
		}
		else if (n%6==1)
		{
			if ((k-5*n/6)%4==2) printf("2/%d\n",2*n/3-(k-5*n/6-2)/4*2+1);
			else if ((k-5*n/6)%4==3) printf("3/%d\n",n-(k-5*n/6-3)/4*3);
			else if ((k-5*n/6)%4==0) printf("1/%d\n",n/3-(k-5*n/6)/4+1);
			else printf("3/%d\n",n-(k-5*n/6-1)/4*3+1);
		}
		else if (n%6==2)
		{
			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2);
			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+2);
			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4+1);
			else printf("3/%d\n",n-(k-5*n/6-2)/4*3);
		}
		else if (n%6==3)
		{
			if ((k-5*n/6)%4==0) printf("2/%d\n",2*n/3-(k-5*n/6)/4*2+1);
			else if ((k-5*n/6)%4==1) printf("3/%d\n",n-(k-5*n/6-1)/4*3+1);
			else if ((k-5*n/6)%4==2) printf("1/%d\n",n/3-(k-5*n/6-2)/4);
			else printf("3/%d\n",n-(k-5*n/6-3)/4*3-1);
		}
		else if (n%6==4)
		{
			if ((k-5*n/6)%4==1) printf("2/%d\n",2*n/3-(k-5*n/6-1)/4*2+1);
			else if ((k-5*n/6)%4==2) printf("3/%d\n",n-(k-5*n/6-2)/4*3);
			else if ((k-5*n/6)%4==3) printf("1/%d\n",n/3-(k-5*n/6-3)/4);
			else printf("3/%d\n",n-(k-5*n/6-4)/4*3-2);
		}
		else if (n%6==5)
		{
			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2);
			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+2);
			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4+1);
			else printf("3/%d\n",n-(k-5*n/6-2)/4*3);
		}
		else
		{
			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2-1);
			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+1);
			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4);
			else printf("3/%d\n",n-(k-5*n/6-2)/4*3-1);
		}
		m--;
	}
	return 0;
}
这是我的源码，测试很多数据都过了，就是不知道哪错了，哪位大牛帮我看下。。。

Followed by:

long long 的输入和输出不应该是%d吧 (13) liangzhirong 2008-10-19 22:54:25
- 我后来也发现这问题，改成%lld也过不了 (2) Qinz 2008-10-19 23:09:08
  - 参看FAQ，应该是 %I64d，可惜了 (6) liangzhirong 2008-10-19 23:16:22
    - 很复杂的构造，佩服。。。比赛时不敢这样想下去。。。。 (10) J_Factory 2008-10-20 08:01:20
里面有N个错误 (109) lyg 2008-10-20 11:25:15
这是我修改了一下的代码。 (3008) lyg 2008-10-20 11:38:47
- 成都网赛在这题耗了太多时间，以至最后看到1004有思路但没时间写。。。我感觉我还有很长的acm之路得走，感谢各位大牛的指导 (0) Qinz 2008-10-20 21:15:33

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<stdio.h>
> int main()
> {
> 	long long n,m,k;
> 	scanf("%d",&m);
> 	while(m)
> 	{
> 		scanf("%lld %lld",&n,&k);
> 		if (k<=n/2+1) printf("1/%d\n",n-k+1);
> 		else if (k<=5*n/6+1&&n%2==0)
> 		{
> 			if ((k-n/2)%2==0) printf("2/%d\n",n-(k-n/2-1));
> 			else printf("1/%d\n",n/2-(k-n/2-1)/2);
> 		}
> 		else if (k<=5*n/6+1&&n%2==1)
> 		{
> 			if ((k-n/2)%2==0) printf("2/%d\n",n-(k-n/2-2));
> 			else printf("1/%d\n",n/2-(k-n/2-2)/2);
> 		}
> 		else if (n%6==1)
> 		{
> 			if ((k-5*n/6)%4==2) printf("2/%d\n",2*n/3-(k-5*n/6-2)/4*2+1);
> 			else if ((k-5*n/6)%4==3) printf("3/%d\n",n-(k-5*n/6-3)/4*3);
> 			else if ((k-5*n/6)%4==0) printf("1/%d\n",n/3-(k-5*n/6)/4+1);
> 			else printf("3/%d\n",n-(k-5*n/6-1)/4*3+1);
> 		}
> 		else if (n%6==2)
> 		{
> 			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2);
> 			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+2);
> 			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4+1);
> 			else printf("3/%d\n",n-(k-5*n/6-2)/4*3);
> 		}
> 		else if (n%6==3)
> 		{
> 			if ((k-5*n/6)%4==0) printf("2/%d\n",2*n/3-(k-5*n/6)/4*2+1);
> 			else if ((k-5*n/6)%4==1) printf("3/%d\n",n-(k-5*n/6-1)/4*3+1);
> 			else if ((k-5*n/6)%4==2) printf("1/%d\n",n/3-(k-5*n/6-2)/4);
> 			else printf("3/%d\n",n-(k-5*n/6-3)/4*3-1);
> 		}
> 		else if (n%6==4)
> 		{
> 			if ((k-5*n/6)%4==1) printf("2/%d\n",2*n/3-(k-5*n/6-1)/4*2+1);
> 			else if ((k-5*n/6)%4==2) printf("3/%d\n",n-(k-5*n/6-2)/4*3);
> 			else if ((k-5*n/6)%4==3) printf("1/%d\n",n/3-(k-5*n/6-3)/4);
> 			else printf("3/%d\n",n-(k-5*n/6-4)/4*3-2);
> 		}
> 		else if (n%6==5)
> 		{
> 			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2);
> 			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+2);
> 			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4+1);
> 			else printf("3/%d\n",n-(k-5*n/6-2)/4*3);
> 		}
> 		else
> 		{
> 			if ((k-5*n/6)%4==3) printf("2/%d\n",2*n/3-(k-5*n/6-3)/4*2-1);
> 			else if ((k-5*n/6)%4==0) printf("3/%d\n",n-(k-5*n/6)/4*3+1);
> 			else if ((k-5*n/6)%4==1) printf("1/%d\n",n/3-(k-5*n/6-1)/4);
> 			else printf("3/%d\n",n-(k-5*n/6-2)/4*3-1);
> 		}
> 		m--;
> 	}
> 	return 0;
> }
> 这是我的源码，测试很多数据都过了，就是不知道哪错了，哪位大牛帮我看下。。。

Home Page Go Back To top