Rei's blog

By Rei, 10 years ago, translation, In English
Problem B.
One just needs to calculate all possible answers and find the minimum. For example one may run on a set of numbers, for all pairs of numbers apply next operation to that pair and recursively run on a new set of numbers. When only one number remains, compare it to the already obtained minimum, and change that minimum if  it's needed.
 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you describe how the answer to 1st test is 3?
1 1 1 1
+ + *

i proceed this way
+
2 2 1 1

+
2 3 3 1

*
2 3 3 3

???
  • 10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Read the problem statement carefully. The operations are:

    1 1 1 1

    +
    2 1 1

    +
    3 1

    *
    3
  • 10 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it
    I think you didn't understand the statement correctly. "... replaced them with their sum or their product." means that he erases two numbers and writes only one (sum or product). I see ambiguity in mentioned phrase, but you can derive right interpretation from the next sentence: "In the end he got one number". So after 3 minutes there should be only one number at the blackboard.
    In 1st test we have:
    1 1 1 1
    +
    2 1 1
    +
    3 1
    *
    3
    We apologize for that ambiguity, but believe that it is not very hard to resolve it by reading statement carefully one more time.

    Meh, I am too slow.
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks!
i thought "them" in the problem statement refered both of the numbers.
»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Time: 30 ms, memory: 3636 KB Verdict: WRONG_ANSWER Input 323 771 559 347 + * * Participant's output 443006 Jury's answer 149067730 Checker comment wrong answer 1st numbers differ — expected: '149067730', found: '443006'

This was one of the testcases my program failed but clearly my program finds the smaller output and the jury's output is the larger one. I multiplied the first two numbers and added it with the multiplication of the last two numbers.

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

my solution..

include<bits/stdc++.h>

using namespace std;

define pii pair<int,int>

define uii unordered_map<int,int>

define usi unordered_map<string,int>

define ui unordered_set

define umi unordered_multiset

define fon(i,n,j) for(int i=j;i<n;i++)

define mid(x,y) (x+y)/2

define vi vector

define pb push_back

typedef unsigned long long int ll;

ll help(vector v,char* arr){

if(v.size()==2){ if(arr[0]=='+'){ return v[0]+v[1]; } else{ return v[0]*v[1]; } }

ll ans=10000000000000;

for(int i=0;i<v.size()-1;i++){ for(int j=i+1;j<v.size();j++){ std::vector temp; for(int k=0;k<v.size();k++){ if(k!=i&&k!=j) temp.pb(v[k]); } ll x; if(arr[0]=='+') x=v[i]+v[j]; else x=v[i]*v[j]; temp.pb(x); ll y=help(temp,arr+1); ans=min(ans,y); } }

return ans; }

void solve(){

vector v(4); for(int i=0;i<4;i++) cin>>v[i]; char arr[3]; fon(i,3,0) cin>>arr[i];

cout<<help(v,arr);

return ; }

int main(){

#ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif

int t=1; //cin>>t; while(t--){ solve(); }

return 0; }