状态 耗时 内存占用

#1 Accepted 0ms 65.957MiB
#2 Accepted 0ms 65.949MiB
#3 Accepted 0ms 65.957MiB
#4 Accepted 0ms 65.953MiB
#5 Accepted 0ms 65.957MiB
#6 Accepted 0ms 65.957MiB
#7 Accepted 15ms 65.949MiB
#8 Accepted 15ms 65.961MiB
#9 Accepted 15ms 65.957MiB
#10 Accepted 0ms 65.961MiB
```c++
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <ciso646>
#include <stack>
using namespace std;

int dp[17000000];

int ans;
int n, i;

int main()
{
scanf("%d", &n);

dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for (i = 4;i <= n;i++)
{
if (i%3!=0)
dp[i] = dp[i / 3+1] + 1;
else dp[i] = dp[i / 3] + 1;

}
dp[1] = 0;
printf("%d", dp[n]);

system("pause");

return 0;
}

这道题无疑是数据太弱了，我手算了整整一页纸，题解这一页的代码基本都有大大小小的漏洞
首先连续除以三那个肯定是错的，然后有人提出来说n=n/3+n%3的递推式，但是这个递推式本身是错误的，因为在n=3k+2的情况下，最优解应该是k，k+1，k+1，在那个递推式情况下就会变成k，k，k+2，这样最优解就变成了a[k+2]+1而不是a[k+1]+1.所以那个递推式写的程序连样例都过不去的。然后唯一一个用dp的pascal代码的问题在于a[1]初始化成了1，就是说整个递推式是好运过去的。

下面说说我的想法
对于3k的情况毫无疑问答案是a[k]+1,因为分成3个k称一次之后就跟k的情况相同
对于3k+1和3k+2，分别分成k，k，k+1和k，k+1，k+1，运气最差的情况就是那个重的在k+1的堆里，那么答案就是a[k+1]+1.

这道题的数据是越小越容易检测出程序的bug，当数变大的时候所有错误的解法都能得到正确的结论，因为a[k],a[k+1],a[k+2]只有在k很小的时候才会不同



如果还有什么bug欢迎探讨。。。。我是菜鸟，大牛勿喷

每次分3堆，如果天平一样重，就说明在天平外的堆中，否则在天平重的那堆上。
本质上求log3(n)的向上取整。精度问题请用long double。

#include <iostream>
#include <cmath>

using namespace std;

long double n;

int main()
{
    cin>>n;
    int ans=0;
    ans=ceil(log(n)/log(3));
    cout<<ans<<endl;
    return 0;
}

数学题，很简单。（大佬们可以200秒切掉的）

其实就是求log3(n);

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int n;
int main() {
    scanf("%d",&n);
    int cnt=0;
    while (n) {
        n/=3;
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

#include <stdio.h>

int calc(int x) {
    if (x < 4)
        return 1;
    return calc(x / 3 + (x % 3 != 0)) + 1;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", calc(n));
}

#include <iostream>
using namespace std;
int main()
{
int n,m,i,j;
cin>>n;
j=1;
for(i=1;i<n-1;i++) {j=j*3;if(n>j&&n<=j*3) {m=i+1;break;}}
if(n<=3) m=1;
cout<<m;
return 0;
}

其实这道题可以是分治
不考虑整数的划分
二分搜索的思想：每次把n个球分成两份，然后取重的一份，再分，再取...最后得到的就是重球，而称了大约log2(n)次
然而答案大约是log3(n)次，这就考虑n=3的情况
。而n=3时，若称出平衡则第三个是重球，若称出不平衡显然重的就是要找的球，所以只用称一次
所以推广到多个时，每次分成三份就知道重球一定在其中的某一份，就是三分

#include<cstdio>
int qpow(int x,int n)
{
    int ret=1;
    while(n)
    {
        if (n&1) ret*=x;
        x*=x,n>>=1;
    }
    return ret;
}
int main()
{
    int n,ans;
    scanf("%d",&n);
    for (ans=0;qpow(3,ans)<n;ans++);
    printf("%d",ans);
}

小哥，其实不需要用dp啊。

#include<iostream>
using namespace std;

int n;

int Calc (int num) {
    
    if (num==1) return 0;
    else if (num==2||num==3) return 1;
    else
      if (num%3==0) return Calc(num/3)+1;   
        else return Calc(num/3+1)+1;
    
} 

int main () {
    
    cin>>n;
    cout<<Calc(n)<<endl;
    
  return 0; 
    
} 

小学数学书原题！
规律：3^x<n<=3^(x+1)时
ans=x+1

#include <stdio.h>

int main()
{
int n,m=0;
scanf("%d",&n);
while(n>3)
{
n=n/3+n%3;
m++;
}if(n!=1)m++;
printf("%d",m);
return 0;
}

var
  n,t:longint;
begin
  readln(n);dec(n);
  while n<>0 do
  begin
    n:=n div 3;
    inc(t);
  end;
  writeln(t);
end.  

''' pascal
var
n,t:longint;
begin
readln(n);dec(n);
while n<>0 do
begin
n:=n div 3;
inc(t);
end;
writeln(t);
end.

'''

###**water**
c++
#include <cstdio>
int main() {
int n,ans = 0;
scanf("%d",&n);
while (n) n /= 3,ans++;
printf("%d",ans);
return 0;
}


楼下的真长！厉害！！！
#include<iostream>
using namespace std;
int main()
{
int n,s;
cin>>n;
s=0;
do{
n=n/3;
s++;
}while(n!=0);
cout<<s;
return 0;
}
真是水！！！

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
typedef long long lg;
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)

lg n;

lg f(lg n)
{
    //cout<<n<<endl;
    if(n==2||n==1||n==3) return 1;
    if(n&1) n--;
    int t=double(n)/3.0+0.5;
    return f(max(t,n-t-t))+1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    cout<<f(n);
    return 0;
}

var
n:longint;
s1,s2,t:longint;
begin
read(n);
if n<=3 then begin writeln(1); halt; end;
s1:=3; s2:=9;
t:=2;
while true do
begin
if (n>s1)and(n<=s2) then begin writeln(t); halt; end;
s1:=s1*3; s2:=s2*3; t:=t+1;
end;
end.

1.这道题只能说数据非常弱。很多错误的代码都能通过。下面这个就是其中之一：
#include<iostream>
using namespace std;
int main()
{
long n, total = 0;
cin >> n;
while(n > 0)
{
n /= 3;
total ++;
}
cout << total << endl;
return 0;
}
2.这道题描述非常不好：最少称几次，当然是一次了。
应该说成：让绝顶聪明之人去称量，最多称几次；
或者说：绝顶聪明之人在点特别背的情况下称几次才能找到那个球。
3.正确答案如下：
int f(int n){
if (n == 1)return 0;
if(n==2)return 1;
return f(n / 3+n%3) + 1;
}
把球分成3堆才可以，毕竟三分要比二分快很多。
其次，怎样分成三堆：当然是尽量的平均了。也就是说：天平上两边各有n/3个球，天平下边还剩下（n/3+n%3）个球。
最后，因为要考虑最坏的情况：当然是破球在最大的那一堆里了。也就是（n/3+n%3）.
这显然与很多除3到0的答案不一样。

30题~~~

记录信息
评测状态 Accepted
题目 P1361 天平称量
递交时间 2014-08-03 14:59:44
代码语言 C++
评测机 VijosEx
消耗时间 30 ms
消耗内存 272 KiB
评测时间 2014-08-03 14:59:50
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 272 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 272 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 272 KiB, score = 10
Accepted, time = 30 ms, mem = 272 KiB, score = 100

测试数据 #0: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 732 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 732 KiB, score = 10
Accepted, time = 15 ms, mem = 732 KiB, score = 100

var n,k:longint;
begin
readln(n);k:=0;
while n<>0 do begin n:=n div 3;inc(k);end;
writeln(k);
end.
6行秒杀 仅供参考

var n,m:qword;
ans:longint;
begin
read(n);
m:=1;
for ans:=1 to 30000 do
begin
m:=m*3;
if m>=n then
begin
write(ans);
halt;
end;
end;
end.

其实用log3的解是错的，但却AC了.................
wrong：input 3
output 2
right： input 3
output 1
好像没有设计这种数据...