11847 - Cut the Silver Bar

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

11847 - Cut the Silver Bar

Post by apurba » Tue Sep 21, 2010 2:02 pm

Code: Select all

happy coding
Last edited by apurba on Wed Sep 22, 2010 4:33 pm, edited 1 time in total.

Code: Select all

keep dreaming...

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11847 Cut the Silver Bar

Post by Nursoltan_h » Tue Sep 21, 2010 3:47 pm

I think it's wrong. I'm getting WA too. :-?

When Input is 10 answer is 4. Is it true???

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11847 Cut the Silver Bar

Post by patsp » Tue Sep 21, 2010 9:09 pm

I thought the solution should be 2 if n > 3, 0 if n == 1, 1 if n == 2 or n == 3

2 if n > 3: Cut one piece of size 1, another piece of size 2, then we have 3 pieces of size 1,2, n-3
On the first day the miner can give the n-3 size piece, then the 1 size piece and the next n-2 days he can give 2 and take back 1, give 1 and take back 2, and so on (so the creditor has always more silver than needed except the last 3 days)

This also gives WA. Can anyone tell me whether I misunderstood the problem statement and explain a solution?

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11847 Cut the Silver Bar

Post by Nursoltan_h » Wed Sep 22, 2010 4:41 am

I got the answer.
Optimal solution is divide 1,2,4,8,... and so on.
When input is 10 answer becomes 3.
It means answer is log2(n).

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 11847 Cut the Silver Bar

Post by sitz » Thu Sep 23, 2010 1:25 pm

Is the solution really log2(n) as I keep on getting WA applying the same algorithm :o
Or please provide some critical test cases

Thanx :)

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11847 Cut the Silver Bar

Post by Khongor_SMCS » Thu Sep 23, 2010 2:31 pm

Answer is floor(log2(n))

Dav_Avi
New poster
Posts: 2
Joined: Sat Sep 25, 2010 12:37 am

Re: 11847 Cut the Silver Bar

Post by Dav_Avi » Sat Sep 25, 2010 12:47 am

Good day to all

I need help, I found a different solution to the logarithm
Divicion using the 1-2-4-8 pattern ........ but to send receipt
WA, I am a rookie I think the error is the reading of data that compare
mine responses to the cast to use log2 (n) and my answer is correct
I tried it with 1 2 3 4 5 7 10 15 100 1000 8000 9000 15000 17000 18000 19000 19999 and get the same
answers to my program as the logarithm,

IS MY FIRST ERJECICIO

my way of reading data is as follows

(InSilverFile ifstream ("silver.in", ios:: in );)// to open
(InSilverFile>> n;) / / to store each number after Declarationof n integer.

SOMEONE HELP A ROOKIE?

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11847 Cut the Silver Bar

Post by Khongor_SMCS » Sat Sep 25, 2010 4:20 am

You have to read from standard input.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11847 Cut the Silver Bar

Post by arifcsecu » Tue Sep 28, 2010 5:06 pm

say n is input. So

m=__builtin_clz(n)
a=31-m

Answer is a.

Here n is unsigned long
Try to catch fish rather than asking for some fishes.

Dav_Avi
New poster
Posts: 2
Joined: Sat Sep 25, 2010 12:37 am

Re: 11847 Cut the Silver Bar

Post by Dav_Avi » Wed Sep 29, 2010 2:47 am

Khongor_SMCS wrote:You have to read from standard input.

I use standart input even though the problem says that the entry should be read silver.in file,
then it should always be done online for judges??

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 11847 Cut the Silver Bar

Post by @ce » Sat Jan 12, 2013 9:35 am

I am getting AC for submisssion in C++.

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>

#define L long long int
#define U unsigned long long int
using namespace std;

main()
{
      while(1)
      {
            int n;
            scanf("%d", &n);
            if(!n)
                  break;
            printf("%d\n",(int)(log2(n)));
      }
}
But I am getting WA for submission of almost same code in C.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
int main()
{
      while(1)
      {
            int n;
            scanf("%d", &n);
            if(!n)
                  break;
            printf("%d\n", (int)(log2(n)));
      }
      return 0;
}
Someone, please tell me why is this happening?
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11847 Cut the Silver Bar

Post by brianfry713 » Mon Jan 14, 2013 9:31 pm

If you submit your C code as using the C++ compiler it will get AC. It's probably a precision error in log2. Whenever possible avoid floating point.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 118 (11800-11899)”