144 - Student Grants

[monika]

I keep getting WA for 144....

It would be very helpful, if somebody could provide me a sample set of input/output.

or if somebody could give me his ACCEPTED program for 144, so that I can compare my outputs.

Thanks.

[Joe Smith]

I keep getting WA for 144....

It would be very helpful, if somebody could provide me a sample set of input/output.

or if somebody could give me his ACCEPTED program for 144, so that I can compare my outputs.

Thanks.

I didn't test my solution much, so I'll just post the code. Enjoy...

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <deque>

using namespace std;

deque<int> q;
int N, k, gotten[30];

int main()
{
while (scanf("%d %d", &N, &k)==2) {
if (0==N+k) break;
for (int i=1; i<=N; i++) q.push_back(i);
memset(gotten,0,sizeof(gotten));
int at=1, store=0;
while (!q.empty()) {
if (store==0) {
store=at;
if (++at > k) at=1;
}
int z = q.front();
q.pop_front();
int amt = min(store, 40-gotten[z]);
store -= amt;
gotten[z] += amt;
if (gotten[z] < 40) q.push_back(z);
else printf("%3d", z);
}
printf("\n");
}
}
[/cpp]

[monika]

Thanks a Lot!!!

I got Accepted now

[ec3_limz]

Are there hidden traps in this problem? Please help.

[cpp]#include <stdio.h>

int nguy, cap, idx[25], grant[25];

void init() {
int i;

for (i = 0; i < nguy; i++) {
idx = i + 1;
grant = 40;
}
}

void movetoback() {
int tmp1, tmp2, i;

tmp1 = idx[0], tmp2 = grant[0];
for (i = 0; i < nguy - 1; i++)
idx = idx[i + 1], grant = grant[i + 1];
idx[nguy - 1] = tmp1, grant[nguy - 1] = tmp2;
}

void sim() {
int store, refill, payout;

store = 0, refill = 1;
while (nguy > 0) {
if (store == 0) {
store = refill;
refill = refill % cap + 1;
}
if (grant[0] < store)
payout = grant[0];
else
payout = store;
store -= payout;
grant[0] -= payout;

movetoback();
if (grant[nguy - 1] <= 0) {
printf("%3d", idx[nguy - 1]);
nguy--;
}
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("otuput.dat", "w", stdout);
#endif

while (true) {
scanf("%d%d", &nguy, &cap);
if (nguy + cap == 0)
break;

init();
sim();
}

return 0;
}[/cpp]

[globi]

Hello. My program seems to work good, but the judge gives WA.

Could you look at that and tell me, what wrong?!

[cpp]
#include <stdio.h>

int lenghtof(int);

int main()
{
int count, // ilosc studentow
max, // maksymalna kwota w automacie
amount, // aktualna kwota w automacie
amount2, // tymczasowa kwota
pos, // aktualny student
pos2, // aktualny student wyjsciowy
count2, // ilu studentow zostalo na liscie
tmp; // rozne inne

while(1)
{
scanf("%d %d", &count, &max);
if(count == 0 && max == 0) return 0;

int *std, *out;
std = new int[count+1]; out = new int[count+1];
for(tmp = 1; tmp <= count; tmp++) { std[tmp] = 0; out[tmp] = 0; }
amount = 1; amount2 = 0; pos = 0; count2 = count; pos2 = 0; tmp = 0;

while(1)
{
if(count2 == 0) break;

if(pos == count) pos = 1;
else pos++;

if(amount2 == 0)
{
if(std[pos] == 40);
else
{
if(std[pos] + amount <= 40)
{
std[pos] += amount;
if(amount == max) amount = 1;
else amount++;
}
else
{
amount2 = amount - (40-std[pos]);
if(amount == max) amount = 1;
else amount++;
std[pos] = 40;
}
if(std[pos] == 40) { out[pos2] = pos; pos2++; count2--; }
}
}
else
{
if(std[pos] == 40);
else
{
if(std[pos] + amount2 <= 40)
{
std[pos] += amount2;
amount2 = 0;
}
else
{
amount2 = amount2-(40-std[pos]);
std[pos] = 40;
}
if(std[pos] == 40) { out[pos2] = pos; pos2++; count2--; }
}
}
}

for(tmp = 0; tmp <= count; tmp++)
{
for(int a = 0; a < 3-lenghtof(out[tmp]); a++) printf(" ");
printf("%d", out[tmp]);
}
delete std; delete out;
}
return 0;
}

int lenghtof(int what)
{ int sum = 1; while(what >= 10) { sum++; what /= 10; } return sum; }
[/cpp]

Thx.

[turuthok]

I probably missed it, but I didn't see new line printed out in your code.

And BTW, ... you can use printf("%3d", n) instead of computing the padding yourself.

-turuthok-

[globi]

Ok

I repaired that and I accepted.

Thx.

[bignad98]

When filling a student's grant completely, doesn't empty the output store, how many coins will the reserve spit out when the store does empty? For example:

Student 1 has $39. The machine store has $2. Filling student 1's grant leaves $1 in the output store. Student 2 gets the $1 from the store. Now, does the machine increment the $1 that was in it last time to $2 (case A), or does it increment the last amount it filled the store with (to $3, case B)? The code samples I've seen all seem to just increment whatever was left in the output store, or case A. Just wanted to check.

[dawynn]

Ok, this worked on my Debian Linux box, using the 3.3 GNU compilers, but Judge is giving me a runtime error:

Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.000 seconds.

[cpp]
// Problem solved. Code removed from board.
[/cpp]

Anyone see any issues that would cause a floating point error?

[Krzysztof Duleba]

In the last case in the input, when N=k=0, you try to do iNextCoins%k - a division by 0.

[dawynn]

Yup! That was my problem. Hmm. That should have happened in Unit Test too. Oh, well. I'm accepted now. Thanks!

[danielrocha]

Just in case someone has this same doubts: the correct option is case B! For example: if a student has $39 and has to receive $4, he gets $1, the next one gets $3 (the change, or $39+$4-$40) and the next one gets $5! The machine continues its work normally.

I'll try to make myself more clear : let's suppose N=5 and K=10. At some point, we'll have the following situation:

money = { 21, 27, 35, 39, 35 }

The machine has $10 and it's the last guy's turn to get the money. He gets $5 (completes his $35) and goes home. The next guy (the first guy) gets the $5 he left. The next guy (the second one) goes to the machine (which was empty) and the machine gives him $1. The final configuration would be something like this:

money = { 26, 28, 35, 39 }

The simulation then continues as normally..

I hope I could help someone!

[zaj_tam]

Code: Select all

#include <iostream>
#include <stdlib.h>

using namespace std;

int n;
int k;
int student [25];
int resitev [25];
int stanje_l = 100;
int res = 0;
int prazno = 0;
int aha = 0;

int main(int argc, char *argv[])
{

cin >> n >> k;
if ( n != 0 && k != 0 ) {
 for ( int a = n; a > 0; )
 {
 
  for ( int b = 1; b <= n; b++ )
  {
   if ( stanje_l >= k ) 
      { stanje_l = 1; } 
   else if ( stanje_l < k )
      { stanje_l++; } 
   else
      { }

   if ( student[b-1] < 40 ) {
   if ( aha > 0 ) {
    student[b-1] = aha;
    stanje_l--;
    } else {
    student[b-1] += stanje_l;
    }
    if ( student[b-1] >= 40 ) { 
    resitev[res] = b; 
    res++; 
    a--;
    stanje_l = student[b-1] - 40;
    }
   }
  }

 }
 for ( int g = 0; g <= (n -1); g++ ) { 
cout << resitev[g];
 }
} 
return 0;
}

This works well on my computer, it also outputs the right numbers for given input 5 3. Thats the only one i can be shure of because it written here->http://acm.uva.es/p/v1/144.html

What is wrong?

[Almost Human]

are you sure that your program handle all the input ?

you should get input and output the answer until the input is 0 for both n and k ...

your program just get input 1 time ...

hope it helps

[Guest]

Hi,
I'm getting WA for this problem . Can anyone give me the outputs of their accepted solutions for the following inputs?
I would really appreciate any i/o set other than this one.

5 10
25 40
25 1
1 1
1 40
10 30
10 10
3 39
22 2
13 13
0 0

Thank you.