178 - Shuffling Patience

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

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Sat Feb 16, 2002 3:59 am

Sorry I post so much on here, but really I'm stuck on this one... see, I don't get the thing about assessed after each card, when a pair play is supposed to be indivisible: I did make a program where a pair was played such that it was reassessed for each time, but that came out wrong. Anyone help? Besides, this produces the right answer for the test case.

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 178 C++ */

// Send to judge@uva.es

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

int totals[16], nfilled;
int tops[16];
int cards[52];

int findcard(int n);

int main() {
char c, d;
int i, j;
int num = 0;

while(ins >> c) {
if(c == '#') break;
ins.putback(c);

for(i = 0; i < 52; i++) {
ins >> c >> d;

if(c == 'T')
cards = 10;
else if(c == 'J')
cards = 11;
else if(c == 'Q')
cards = 12;
else if(c == 'K')
cards = 13;
else if(c == 'A')
cards = 1;
else cards = c - '0';
}

nfilled = 0;

for(i = 0; i < 52; i++) {
for(j = 0; j < nfilled; j++) {
if(tops[j] < 11) {
int f = findcard(11 - tops[j]);

if(f >= 0) {
totals[j]++;
tops[j] = cards[i++];
if(i >= 52) break;
totals[f]++;
tops[f] = cards;
break;
}
} else {
int g, h;

if(tops[j] == 11)
g = findcard(12), h = findcard(13);
if(tops[j] == 12)
g = findcard(11), h = findcard(13);
if(tops[j] == 13)
g = findcard(11), h = findcard(12);

if(g >= 0 && h >= 0) {
totals[j]++;
tops[j] = cards[i++];
if(g < h) {
if(i >= 52) break;
totals[g]++;
tops[g] = cards[i++];

if(i >= 52) break;
totals[h]++;
tops[h] = cards;
} else {
if(i >= 52) break;
totals[h]++;
tops[h] = cards[i++];

if(i >= 52) break;
totals[g]++;
tops[g] = cards;
}

break;
}
}
}

if(i >= 52) break;

if(j >= nfilled) {
if(nfilled >= 16) break;
totals[nfilled] = 1;
tops[nfilled++] = cards;
}
}

outs << ++num << ":";

if(i >= 52) {
for(i = 0; i < nfilled; i++)
outs << setw(3) << totals[i];

outs << endl;
} else {
outs << " Overflowed on card no " << i++ << endl;
}
}

return 0;
}

int findcard(int n) {
int j;

for(j = 0; j < nfilled; j++)
if(tops[j] == n) return j;

return -1;
}

// @END_OF_SOURCE_CODE

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

178 error in description

Post by Caesum » Thu May 16, 2002 8:26 pm

it quite clearly says:
All numbers are to be right justified in a field 3 characters wide
and 'All' has been placed in bold for emphasis and yet when you do this you get PE. To get accepted without PE you need to not right justify the number that is printed in the line 'Overflowed on card no %d'

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » Wed Jun 12, 2002 8:51 pm

there is no space after the "no", so the description is correct
(format is "... card no%3d")

(that's not to say there wasn't a space there last month, but it's correct now at least...)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark

178 - Shuffling Patience

Post by olestorm » Thu Aug 01, 2002 8:55 pm

Hi all,

I have been trying to solve problem 178, but with no success. My program fails to give the right solution to the sample input given.

For the input:

TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

my program produces:

1: 8 10 5 1 6 4 6 2 2 4 4

instead of the required sample output:

1: 8 6 7 4 3 5 4 4 2 5 4

I have even tried to solve the problem by hand without reaching the result of the sample output.

It seems that I have misunderstood the rules of the game. The following phrase is central to solving the problem: "Cards are always covered in the same order they were dealt, that is left to right, top to bottom. The first card covered shall be the eligible card nearest the start of play. The second card covered (and also the third for a triple) is its partner nearest the start of play."
I interpret this sentence such that the pair or triplet to be covered is the pair/triplet occupying the 2 or 3 lowest indexed piles. I enumerate the piles of the game like this:

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Consequently I interpret "the start of the play" to be the pile with index 0.

If, with my understanding fo the problem, two pairs exists at positions (2,5) and (3,6) and a triplet at (0,10,11), I choose to cover the piles 0, 10 and 11 in this order. I do NOT consider covering triplets or pairs until the triplet has been covered.

Any idea as to where I am going wrong on this problem???

Kind regards,

Ole Storm.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Mar 24, 2003 9:05 am

I'm do it in the same way and I got WA too ....
Maybe someone tell us tricky inputs ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark

Post by olestorm » Thu Apr 03, 2003 11:03 pm

Hi Dominik.

Recently I managed to solve P178 :D

If you still get WA I may be able to give you a hint of some kind.


Ole.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Apr 04, 2003 8:04 am

Yes, I'm still faced with WA on this problem :(
Could you tell me something special about it ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

olestorm
New poster
Posts: 3
Joined: Thu Aug 01, 2002 8:31 pm
Location: Denmark

Post by olestorm » Wed Apr 09, 2003 12:12 am

Hi Dominik,

I finally solved the problem when I relaized that my initial program (which solved the single test-problem OK) would fail on a deck of cards where the final card (card no 52) would be dealt as the first card on pile no. 16. My program would suggest an overflow on card no. 53, which obviously was not the case. When I corected this flaw I got accepted.

Below are some test-problems with answers, which might help you.

Regards,

Ole.


TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D

9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C

AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C

6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D

TS JS JS JS JS QS QS QS QS KS KS KS KS
AS AS AS AS 2S 2S 2S 2S 3S 3S 3S 3S 4S
4S 4S 4S 5S 5S 5S 5S 6S 6S 6S 6S 7S 7S
7S 7S 8S 8S 8S 8S 9S 9S 9S 9S TS TS TS

4S 4S 4S 5S 5S 5S 5S 6S 6S 6S 6S 7S 7S
TS JS JS JS JS QS QS QS QS KS KS KS KS
AS AS AS AS 2S 2S 2S 2S 3S 3S 3S 3S 4S
7S 7S 8S 8S 8S 8S 9S 9S 9S 9S TS TS TS

QH 2D 3H KH 9H TS QC 8S 8D 2H TH KS KC
2S QS TD 2C 4H 9D JH 7H JD 5H AD 4D 5D
7S JS 8H 3D 8C 6D 4S 9S 5S 3S 4C 6S 9C
KD JC 7D AC 5C AS 7C AH 6H TC QD 6C 3C

3C AS 7C AH 6H 5C TC QD 6C KD JC 7D AC
KC TS QC 8S 8D 9H 2H TH KS QH 2D 3H KH
5D 9D JH 7H JD 4H 5H AD 4D 2S QS TD 2C
9C 6D 4S 9S 5S 8C 3S 4C 6S 7S JS 8H 3D

9C 6D 4S 9S 5S 8C 3S 4C 6S 7S JS 8H 3D
KC TS QC 8S 8D 9H 2H TH KS QH 2D 3H KH
3C AS 7C AH 6H 5C TC QD 6C KD JC 7D AC
5D 9D JH 7H JD 4H 5H AD 4D 2S QS TD 2C
#

1: 8 6 7 4 3 5 4 4 2 5 4
2: 10 6 10 4 1 1 2 5 5 5 3
3: 13 5 7 2 3 1 5 2 3 3 1 2 1 4
4: 13 7 5 6 4 2 2 6 1 2 4
5: 10 4 7 7 5 2 5 4 6 2
6: 8 14 4 5 1 3 2 3 3 1 2 6
7: Overflowed on card no 31
8: 7 3 6 7 4 4 4 4 2 3 3 1 2 2
9: 12 4 5 2 3 5 2 3 2 3 3 2 2 1 3
10: 9 9 2 5 6 4 4 6 2 5
11: 9 9 6 6 3 5 5 2 3 2 2

DataCompBoy
New poster
Posts: 1
Joined: Sat Aug 02, 2003 4:31 pm
Location: Novosibirsk, Russia
Contact:

Re: Problem 178 - Shuffling Patience

Post by DataCompBoy » Sat Aug 02, 2003 4:37 pm

olestorm wrote: my program produces:
1: 8 10 5 1 6 4 6 2 2 4 4
ummm... Yep, my program produces this output too :(
Can you say, what move incorrect?

(card "1" is ace, ":" is ten)

Code: Select all

      0 0 0 0
      0 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: :S
:     1 0 0 0
      0 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: QC
:Q    1 1 0 0
      0 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 8S
:Q8   1 1 1 0
      0 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 8D
:Q88  1 1 1 1
      0 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: QH
:Q88  1 1 1 1
Q     1 0 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 2D
:Q88  1 1 1 1
Q2    1 1 0 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 3H
:Q88  1 1 1 1
Q23   1 1 1 0
      0 0 0 0
      0 0 0 0
Cards to: 2 6 -1
Card: KH
:QK8  1 1 2 1
Q23   1 1 1 0
      0 0 0 0
      0 0 0 0
Cards to: 6 -1 -1
Card: 9H
:QK8  1 1 2 1
Q29   1 1 2 0
      0 0 0 0
      0 0 0 0
Cards to: 1 2 4
Card: 2H
:2K8  1 2 2 1
Q29   1 1 2 0
      0 0 0 0
      0 0 0 0
Cards to: 2 4 -1
Card: :H
:2:8  1 2 3 1
Q29   1 1 2 0
      0 0 0 0
      0 0 0 0
Cards to: 4 -1 -1
Card: KS
:2:8  1 2 3 1
K29   2 1 2 0
      0 0 0 0
      0 0 0 0
Cards to: 1 6 -1
Card: KC
:K:8  1 3 3 1
K29   2 1 2 0
      0 0 0 0
      0 0 0 0
Cards to: 6 -1 -1
Card: 9D
:K:8  1 3 3 1
K29   2 1 3 0
      0 0 0 0
      0 0 0 0
Cards to: 5 6 -1
Card: JH
:K:8  1 3 3 1
KJ9   2 2 3 0
      0 0 0 0
      0 0 0 0
Cards to: 6 -1 -1
Card: 7H
:K:8  1 3 3 1
KJ7   2 2 4 0
      0 0 0 0
      0 0 0 0
Cards to: 1 4 5
Card: JD
:J:8  1 4 3 1
KJ7   2 2 4 0
      0 0 0 0
      0 0 0 0
Cards to: 4 5 -1
Card: 2S
:J:8  1 4 3 1
2J7   3 2 4 0
      0 0 0 0
      0 0 0 0
Cards to: 5 -1 -1
Card: QS
:J:8  1 4 3 1
2Q7   3 3 4 0
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: :D
:J:8  1 4 3 1
2Q7:  3 3 4 1
      0 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 2C
:J:8  1 4 3 1
2Q7:  3 3 4 1
2     1 0 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 4H
:J:8  1 4 3 1
2Q7:  3 3 4 1
24    1 1 0 0
      0 0 0 0
Cards to: 6 9 -1
Card: 5H
:J:8  1 4 3 1
2Q5:  3 3 5 1
24    1 1 0 0
      0 0 0 0
Cards to: 9 -1 -1
Card: 1D
:J:8  1 4 3 1
2Q5:  3 3 5 1
21    1 2 0 0
      0 0 0 0
Cards to: 0 9 -1
Card: 4D
4J:8  2 4 3 1
2Q5:  3 3 5 1
21    1 2 0 0
      0 0 0 0
Cards to: 9 -1 -1
Card: 5D
4J:8  2 4 3 1
2Q5:  3 3 5 1
25    1 3 0 0
      0 0 0 0
Cards to: -1 -1 -1
Card: 6D
4J:8  2 4 3 1
2Q5:  3 3 5 1
256   1 3 1 0
      0 0 0 0
Cards to: 6 10 -1
Card: 4S
4J:8  2 4 3 1
2Q4:  3 3 6 1
256   1 3 1 0
      0 0 0 0
Cards to: 10 -1 -1
Card: 9S
4J:8  2 4 3 1
2Q4:  3 3 6 1
259   1 3 2 0
      0 0 0 0
Cards to: 4 10 -1
Card: 5S
4J:8  2 4 3 1
5Q4:  4 3 6 1
259   1 3 2 0
      0 0 0 0
Cards to: 10 -1 -1
Card: 7S
4J:8  2 4 3 1
5Q4:  4 3 6 1
257   1 3 3 0
      0 0 0 0
Cards to: 0 10 -1
Card: JS
JJ:8  3 4 3 1
5Q4:  4 3 6 1
257   1 3 3 0
      0 0 0 0
Cards to: 10 -1 -1
Card: 8H
JJ:8  3 4 3 1
5Q4:  4 3 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 0 1 5
Card: 3D
3J:8  4 4 3 1
5Q4:  4 3 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 1 5 -1
Card: 8C
38:8  4 5 3 1
5Q4:  4 3 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 5 -1 -1
Card: 3S
38:8  4 5 3 1
534:  4 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 0 1 -1
Card: 4C
48:8  5 5 3 1
534:  4 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 1 -1 -1
Card: 6S
46:8  5 6 3 1
534:  4 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 1 4 -1
Card: 9C
49:8  5 7 3 1
534:  4 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 4 -1 -1
Card: 1S
49:8  5 7 3 1
134:  5 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 1 8 -1
Card: 7C
47:8  5 8 3 1
134:  5 4 6 1
258   1 3 4 0
      0 0 0 0
Cards to: 8 -1 -1
Card: 1H
47:8  5 8 3 1
134:  5 4 6 1
158   2 3 4 0
      0 0 0 0
Cards to: 0 1 -1
Card: 6H
67:8  6 8 3 1
134:  5 4 6 1
158   2 3 4 0
      0 0 0 0
Cards to: 1 -1 -1
Card: KD
6K:8  6 9 3 1
134:  5 4 6 1
158   2 3 4 0
      0 0 0 0
Cards to: 0 9 -1
Card: JC
JK:8  7 9 3 1
134:  5 4 6 1
158   2 3 4 0
      0 0 0 0
Cards to: 9 -1 -1
Card: 7D
JK:8  7 9 3 1
134:  5 4 6 1
178   2 4 4 0
      0 0 0 0
Cards to: 2 4 -1
Card: 1C
JK18  7 9 4 1
134:  5 4 6 1
178   2 4 4 0
      0 0 0 0
Cards to: 4 -1 -1
Card: 5C
JK18  7 9 4 1
534:  6 4 6 1
178   2 4 4 0
      0 0 0 0
Cards to: 2 7 -1
Card: :C
JK:8  7 9 5 1
534:  6 4 6 1
178   2 4 4 0
      0 0 0 0
Cards to: 7 -1 -1
Card: QD
JK:8  7 9 5 1
534Q  6 4 6 2
178   2 4 4 0
      0 0 0 0
Cards to: 0 1 7
Card: 6C
6K:8  8 9 5 1
534Q  6 4 6 2
178   2 4 4 0
      0 0 0 0
Cards to: 1 7 -1
Card: 3C
  1:  8 10  5  1  6  4  6  2  2  4  4
suicide proc near\n call death\n suicide endp

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Aug 12, 2003 1:08 am

First of all, it would probably be easier to debug if you printed the number of the top card, instead of size of the pile. But I think I found a problem:

Code: Select all

Card: 9H
:QK8  1 1 2 1
Q29   1 1 2 0
      0 0 0 0
      0 0 0 0 
Cards to: 1 2 4
Now, after the previous move, the cards should be like so:

Code: Select all

T Q K 8
Q 2 9
Why does your code think the next sequence should be pile 1, pile 2, and pile 4? (which are currently, Q, K, 9 respectively -- the triple must have a jack, a queen, and a king, and since there are no jacks on the board, there can be no triple) ... The next cards should go onto pile 5 and 6 (the 2 and 9 which add up to 11) ... Hope this helps!

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed Aug 13, 2003 1:42 am

[didn't mean to reply here.. woops]

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 06, 2006 12:25 pm

my program produces:
1: 8 10 5 1 6 4 6 2 2 4 4
If you get this as the output of the sample input, you probably misunderstood the condition for covering a triple. A triple of cards can be covered if they form the set {jack, queen, king}, in other words, all 3 face cards must be present.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

sorry i don't know your program..

Post by sds1100 » Fri Mar 03, 2006 8:43 am

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

178 Shuffling Patience need further explanation

Post by mars kaseijin » Fri Apr 27, 2007 11:27 am

I am confused by the problem description of 7 cards dealt,
should not the 7th card cover the 4th card 8D <- 3H ?
before 3H gets played on a different pile all by itself?
8S + 3H is 11, so a covering should take place right above 8D. NO? :-?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Apr 28, 2007 10:17 pm

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 1 (100-199)”