Hi,

1. If any product is mentioned in the list then the minimum weight of that product should be at least 1. So, if you have input like this

3
a 1 1000
b 0
c 0

Then the minimum total weight of this scenario is 1002 because b and c got to have at least 1. The maximum is 3000. The final answer is NO.

2. Multiple products can have same weights so for the above case the max total weight is 3000 with a = b = c = 1000.

The problem can be solved by finding the minimum possible weight and maximum possible weight and checking if 10000 is in between them. For example:

3
a 0
b 0
c 1 5

The minimum possible weight is 15 (a = b = c = 5) and the maximum possible weight is 20005 (a = b = 10000 and c = 5). And so 15 <= 10000 <= 20005 and hence the answer is true. Well the real answer is a = 4998, b = 4997 and c = 5. You just need to run two loops, one for finding minimum weight and the another one for finding maximum weight.

And here some test cases from other places on this forum:

Test Case 1

4
Water 0
Cocoa-butter 0
Cocoa-powder 1 4000
Lecithin 0

Minimum Sum is 12001 and maximum sum is 28000 so the answer is NO.

Test Case 2

5
a1 1 2001
a2 0
a3 0
a4 0
a5 1 1999

Minimum sum is 9997 and the maximum sum is 10003 and so the answer is YES.

Test Case 3

4
w 1 10
a 0
b 1 1
c 0

Minimum sum is 13 and the maximum sum is 22 so the answer is NO.

Test Case 4

3
a 1 3
b 0
c 0

Minimum sum is 5 and the maximum sum is 9 so the answer is NO.

Test Case 5

3
a 1 10000
b 0
c 0

Minimum sum is 10002 and the maximum sum is 30000 so the answer is NO.

Test Case 6

3
a 0
b 0
c 0

Minimum sum is 3 and the maximum sum is 30000 so the answer is YES

Test Case 7

5
a1 1 9997
a2 0
a3 0
a4 0
a5 0

Minimum sum is 10001 and the maximum sum is 49985 so the answer is NO.

Varun

Edited by author 24.12.2010 08:51

Why I have worng anserw in test #2??

My code:

#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    string nazwa[5000];
    int wartosc[1000], wartosc2[1000], x, koniec = n-1, pocz = 0, min = 1, max = 10000, summin = 0, summax = 0;
    for (int i=0; i<n; i++)
    {
            cin >> nazwa[i];
            cin >> x;
            if (x == 1)
               cin >> wartosc[i];
            if (x == 0)
                wartosc[i] = 0;
            wartosc2[i] = wartosc[i];
    }

    for (int i = koniec; i>=0; i--)
    {
        if (wartosc[i] == 0)
                       wartosc[i] = min;
        else
            min = wartosc[i];
        summin += wartosc[i];
    }

    for (int i = pocz; i < n; i++)
    {
        if (wartosc2[i] == 0)
                       wartosc2[i] = max;
        else
            max = wartosc2[i];
        summax += wartosc2[i];
    }

if ( summin < 10000 && 10000 < summax)
   cout << "YES";
else
    cout << "NO";
    getchar();
    getchar();
    return 0;
    system("PAUSE");
}


Edited by author 24.01.2011 01:13

Hi,

I keep getting wrong answer for test 7. Any hint as to what is test 7 ?

Thanks

3
q 0
r 0
e 1 5

right ans:Yes

Could anybody give me some tests?? i can't find mistake in my solution.. :-(

If you failed on test 12,try this test.
3
a 10000
b 0
c 0

You should output NO because the amount of "b" and "c" can't be less than 1.

program Ural1190;

var
  h:array[1..5000]of longint;
  a,can,n,l,m:longint;
  w:char;

begin
  readln(n);
  fillchar(h,sizeof(h),0);
  l:=maxlongint;
  for a:=1 to n do
    begin
      w:='a';
      while w<>' ' do
        read(w);
      read(m);
      if m=1 then
      readln(h[a])
      else h[a]:=-1;
    end;
  l:=1;
  can:=0;
  for a:=1 to n do
    begin
      if h[a]=-1 then inc(l);
      if h[a]<>-1 then
      begin
        can:=can+h[a]*l;
        l:=1;
      end;
    end;
  if can>10000 then
  begin
    writeln('NO');
    halt;
  end;
  can:=0;
  l:=1;
  for a:=n downto 1 do
    begin
      if h[a]=-1 then inc(l);
      if h[a]<>-1 then
      begin
        can:=can+h[a]*l;
        l:=1;
      end;
    end;
    if l>1 then can:=can+10000;
    if can<10000 then
    begin
      writeln('NO');
      halt;
    end;
  writeln('YES');
end.

Edited by author 07.02.2009 08:15

Edited by author 07.02.2009 08:15

I know AC solution that answers YES for test

2
Cocoa-butter 1 10000
Cocoa-powder 0

I think that answer for this test should be NO because if it is true, then fraction of Cocoa-powder is 0, and it should not be mentioned in the list at all.

One more problematic test is

3
Cocoa-butter 1 9999
Cocoa-powder 0
Lecithin 0

It is not clear whether fraction may be less than one handredth of percent. If it may then the answer is YES, if it cannot then the answer is NO. I suggest to clarify this in statement.

Edited by author 04.02.2009 23:25

Test 3 contains duplicate names of components.

If one component may be mentioned several times, then for the following test

2
Water 1 6000
Water 0

answer should be 'NO' because according to component list bar consists entirely of water, and percent of water should be 100 (10000 in input).

All known to me AC solutions ignore names of components so I suggest to rename duplicate names in test 3 and add into statement notice that all names in the list are different.

WA Test 9.
Can anyone test my program?
Anyone know what is the test #9?

I thing, that my program solve this task!
But wrong Test#4.
What I hadn't read?
Sum of all thing must be 100 00?
I don't know...
[или я просто не фтыкаю информатику  ;)]
==== SOURSE ====

Var
 cur,last:longint;
 i,n:longint;
 s:string;
 f:boolean;
Begin
 readln(n);
 readln(s);
 last:=GetProc(s);
 sum:=0;
 f:=false;
 for i:=2 to n do
    Begin
     readln(s);
     cur:=GetProc(s);
     if (last>=cur) then cur:=last
                    else
                      Begin
                         f:=true;
                         cur:=last;
                      End;
    End;
 if f then writeln('NO')
      else writeln('YES');
End.

*** GetProc - returne procent of thing.

The following situation doesn't checked in tests or the problem statement is incorrect.
---------------
2
Cocoa-butter 1 1000
Cocoa-powder 1 9000
---------------
Here we have weights written in increasing order (problem says: they should be in non-increasing order!).

My solution checks this and gets WA. But the solution from forum says YES and gets AC. ;)

I have Crash#1. And I know, that first string in input is not number, because I catch exception, than I convert this String to Integer.

Problem statement: 0 < N < 5000.
Test 3: N = 5000.