CIELRCPT - Editorial

can any one please check my code .I don’t know what is wrong it passed all sample tests.
https://www.codechef.com/viewsolution/17515413

Hello, guys, I have a website for downloading music from SoundCloud.
http://soundcloudmp3downloader.com/

And I hope u could help me… how can I get the information about bitrate of SC tracks?
is it possible? any idea?

My solution is a bit different and is very short if you are using C++ and stl as your tool to solve the problem
It uses a greedy approach to find the nearest value just smaller than or equal to n from the menu list.

    while (n > 0) {
        long nearest = upper_bound(menuList.begin(), menuList.end(), n) - menuList.begin();
        n -= menuList[nearest - 1];
        ++count;
    }

Here menuList is an array of the powers of 2 up to the required item - [1,2,4,8…]

int price[12] = {1, 2, 4, 8, 16, 32,
64, 128, 256, 512, 1024, 2048};

int t, p, c;
cin >> t;

for (int k = 0; k < t; k++)
{
    c = 0;
    cin >> p;
    while(p != 0) 
    {
        for (int i = 11; i >= 0; i--)
        {
            if (p >= price[i])
            {
                p -= price[i];
                c++;
                break;
            }
        }
    }
    cout << c << endl;
}
1 Like

if someone interested in dynamic programming solution

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>



using namespace std;
  #define MAX 1000007
   vector<int>v(12);
   vector<int>dp(100002,-1);


 int recu(int p)
    {
      if(p==0)
       return 0;
       if(p<0)
       return MAX;
    
      if(dp[p]!=-1)
       return dp[p];
       int q=MAX;
       for(int i=0;i<12;i++)
       {
        q=min(q,recu(p-v[i])+1);
       }
      return dp[p]=q;
    }


  int main()
        {
        int t,p;
        cin>>t;
        
        dp[0]=0;
        dp[1]=1;
        for(int i=0;i<12;i++)
        {
          v[i]=(1<<i);
        }
        
        while(t--)
        { 
            int ans=0;
           cin>>p;
     
           ans=recu(p);
          cout<<ans<<"\n";
    
       }
    return 0;
    }

link text

I am not familiar with Python but it seems that you are using file for input. You should read from the standard input and output to the standard output.

1 Like

I actually am using standard input. It reads from an input file on my computer (for testing), but if that file doesn’t exist (when I submit) it uses raw_input() instead. I’ve tested this method on the codechef judge and it works for other problems, so I don’t understand why it gets runtime error now.

1 Like

The reason is:
Traceback (most recent call last):
File “prog.py”, line 17, in
NameError: name ‘bin’ is not defined

2 Likes

That doesn’t make sense… bin is a built-in function, how could it not be defined? I thought it must be something with the input because this solution CodeChef: Practical coding for everyone got accepted.

1 Like

You will be angry, but your code works - CodeChef: Practical coding for everyone , is there problem with whitespace, PY is “whitespace sensitive”, isn’t it?

2 Likes

That link doesn’t work, but I see that you got my solution accepted. So I tried it myself and got runtime error CodeChef: Practical coding for everyone. (this is the exact same code that you got accepted, right?) And yeah, python is whitespace-sensitive, but I don’t see how that could be the problem because the solution I posted above got accepted. Something really weird is going on…

1 Like

problem was with comma in link, try again, is your editor replacing multiple spaces with one tab (but it is just a tip)?

1 Like

@anton_lunyov, can you make diff of these two solutions on filesystem?

1 Like

wow this is total B.S. How does the exact same code get accepted for betlista but runtime error for me???

1 Like

No. Your solution will not work for, suppose, 4096. You have to first divide p with 2048 and then count number of one in the remainder.

2 Likes
for _ in range(int(input())):
p = int(input())
c = 0
if p<=2048:
    print(bin(p).replace("0b","").count('1'))
    continue
else:
    c = p//2048
    p = p - 2048*(c)
    print(c + bin(p).replace("0b","").count('1'))

Check out this

1 Like

When I run my code sometimes its showing correct results, sometimes wrong results.
#include
#include<bits/stdc++.h>
using namespace std;

long long d;
long long n;

int findOpt(int d,int size,int a[])
{
int count=0;
for(int j=size;j>=1;j–)
{
while(a[j]<=d){
d=d-a[j];
count++;
}
}
return count;
}

int main() {
cin>>n;
int a[12];
for(int i=1;i<=12;i++){
double result = pow(2, i-1);
a[i] = (int)round(result);
}
int size=sizeof(a)/sizeof(a[1]);
sort(a, a+size+1);
while(n–)
{
d=0;
cin>>d;
int c=findOpt(d,size,a);
cout<<c;
cout<<’\n’;
}
}

1 Like
#include <iostream>

using namespace std;

int main(){
int t;
cin >> t;
while(t–){
long long n,flag = 0;
cin >> n;

    long long cnt = 0;
    while(n > 2048){
        n = n - 2048;
        cnt++;
    }

    while(n != 0){       
        if(n & 1){
            flag++;
        }
        n >>= 1;
        // cout << n << " ";
    }
    flag = flag + cnt;
    cout << flag << endl;
}

}

1 Like

we can solve this using recursion